Optimization with convex constraints and convex objectives; notions related to convex optimization such as sub-gradients, normal cones, separating hyperplanes

learn more… | top users | synonyms

4
votes
1answer
109 views

Constrained optimization (QCLP) over $x$ with the constraint $x = Az$

I have a problem that looks very much like a (norm-constrained) linear program, but with an extra constraint that is unusual for me. The problem is, given a matrix $A$ and a vector $w$, $$ \min_{x ...
0
votes
1answer
90 views

Constrained optimal control problem

I am trying to solve an optimization problem which is probably reminiscent of optimal control theory but all of this is not exactly my field of expertize and I am a little bit lost in translation. If ...
0
votes
0answers
47 views

Finding a movement taking out of a convex set

There is a convex set $S$ as the hull of M points in an D-dimensional Euclidean space and a point $\vec P$ in the set. Then, there is a set of vectors $\vec W$ taking the form $\vec W=\sum_{i=1}^N ...
2
votes
1answer
75 views

Fixed point iteration on symmetric biconvex function

Suppose $X\subseteq\mathbb{R}^n$ is a convex set and that a function $g(x,y):X\times X\rightarrow\mathbb{R}_+$ is smooth, "strictly biconvex" (strictly convex in $x$ and $y$ independently but not ...
1
vote
2answers
171 views

Lower bound for $ \sum_{i=1}^n x_i f(x_i)$ when $\sum_{i=1}^{n}x_i = K$

Considering, the set of all n dim. vectors $\{x_i\}_{i=1,...,n} $ such that $x_i \geq 0 $ and $\sum_{i=1}^{n}x_i = K$ Any continuous and strictly increasing function $f^+(x)$ : $ \mathbb R^+ \to ...
5
votes
1answer
97 views

How to prove the existence of the polytope in $\mathbb{R}^d$ with a given number of faces, minimizing the isoperimetric ratio?

This is the isoperimetric type question. We know that in $\mathbb{R}^d$, balls are the sets that minimize the isoperimetric ratio $\frac{S^{d}}{V^{d-1}}$, where $S$ is the surface area and $V$ is the ...
4
votes
2answers
94 views

Convex optimization with full subdifferential information

Can anyone direct me to any algorithms or theorems that describe the difficulty of solving a non-smooth convex optimization problem for the special case where the full subdifferential is available? ...
1
vote
0answers
34 views

Condition for maximizer of convex combination to be expansion mapping

I have $\Pi_n:\mathbb R^{n+1}\rightarrow \mathbb R$ and $F_n:\mathbb R^2\rightarrow \mathbb R$ with $$F_n(x,a)=\Pi_n(x,...,x,a)$$ $$f_n(x)=\operatorname{ArgMax}_{a\in\mathbb R}\{F_n(x,a)\} $$ such ...
4
votes
1answer
133 views

Nonlinear least square with quadratic equality constraint

I am looking for an appropriate method or hint to solve the following constrained nonlinear least square problem: $\operatorname{argmin}_X \sum_{i\in I} \|\mathbf{X}_i - \mathbf{X}_{i+1}\|_2^2 + ...
2
votes
1answer
169 views

How can I find the maximum value of this function?

For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of: $$ \max_{x \in [0,1]^n} \|Ax+b \|_1 $$ Or is this problem NP-hard?
2
votes
1answer
234 views

Is there any way to compare between diagonals of a resolvent and a Cauchy transform?

Say $A$ is a symmetric matrix of $n$ dimensions. Then let the ``resolvent" of $A$ be the matrix valued function $R_A(z) = \frac{1}{z-A}$ and its Cauchy transform be the real valued function $C_A(z) = ...
0
votes
1answer
112 views

polynomial expression for counting number of integral points of a set

Let $v_i=a_ie_i\in\mathbb R^d$ and $w_i=b_ie_i\in\mathbb R^d$ for $i=1,\dots,d$ where $e_i$'s are unit vetcors and $a_i,b_i$ are positive integers. Let $$S=conv\{0,rv_i+sw_i:i=1,\dots,d\}.$$ Can we ...
2
votes
2answers
328 views

Can one estimate the distribution of eigenvalues of a matrix by its Cauchy/Stieltje transform?

Given a real symmetric $n$ dimensional matrix $A$, with eigenvalues $\lambda_i$ I am defining its Cauchy transform as the function, $f_A(z) = \sum_i \frac{1}{z-\lambda_i}\,$ Is there any information ...
2
votes
1answer
146 views

Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?

Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$. But do we have any quantitative ...
3
votes
1answer
148 views

Condition number after preconditioning

Suppose $A$ and $P$ are symmetric, positive definite matrices and that we factor $P^{-1}=EE^\top.$ Is it true that the condition number of $PA$ is upper-bounded by the condition number of ...
6
votes
2answers
213 views

What methods do we have to understand the spectrum of matrices with restricted entries?

Consider questions of the form (or the "most probable value of" version of these questions rather than the "largest possible"), What is the largest possible spectral radius of a $n \times n$ matrix ...
5
votes
2answers
312 views

Minimum of squared sum minus sum of squares

I know that $$ \min_{\|x\|_2=1=\|y\|_2} \left(\sum_{k=1}^nx_ky_k\right)^2-\sum_{k=1}^nx_k^2y_k^2 \geq -1/2 $$ with equality whenever $|x_k|=\frac{1}{\sqrt{2}}=|y_k|$ for two coordinates. I'm ...
2
votes
1answer
113 views

Rate of convergence for cyclic gradient descent

I'm trying to solve the optimization problem $\min_x \frac{1}{n} \sum_{i=1}^n f_i(x)$ where $f_i$ are (strongly) convex, smooth, lower semi-continuous, etc. However, I am not able to do conventional ...
2
votes
1answer
91 views

smooth minimization of piecewise linear convex function

Is it possible to apply Nesterov's smooth minimization of non smooth function on a problem of the form $$\mathop {\min }\limits_{\lambda \in {R^m}} \mathop {\max }\limits_{\sigma \in {{\left\{ ...
2
votes
1answer
57 views

When is a convex program continuous in its constraint vectors?

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$ I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...
2
votes
0answers
80 views

l1 Quadratic Programming [closed]

Within a SQP- algorithm it can happen that the constraints of the quadratic sub- problems are infeasible. In order to overcome this infeasibilities, a l1 penalty method can be used according to ...
2
votes
1answer
91 views

Functions that are easy to compare to a norm

Let $X$ be a subset of $\mathbb{R}^d$, let $\|\cdot \|_p$ be a norm with $1\leq p\leq\infty$, and let $f:\mathbb{R}^d\to\mathbb{R}$ be a function. I'm trying to find examples of $X$, $p$, and $f$ for ...
1
vote
0answers
58 views

Characterization of the maximizer of a function based on a parameter's value

Consider a smooth, continuously differentiable, and jointly concave function $f(x,y,z;a)$, where $x,y$ and $z$ are decision variables and $a$ is a problem parameter. I have two optimization problems. ...
3
votes
1answer
111 views

generalized mean inequality extension

from generalized inequality, we now that for $p>q$, we have $M_p(\mathbf{x})\ge M_q(\mathbf{x})$. now I am curious to know if we can find a constant $\alpha(p,q)$ which is only function of $p,q$ ...
3
votes
2answers
157 views

Constructing a quasiconvex function [closed]

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...
1
vote
1answer
58 views

monotonicity alike functions

assuming we have two smooth function ${f_1},{f_2}:{R^N} \to R$, under what condition, we have ${f_1}\left( {{{\bf{x}}_1}} \right) \ge {f_1}\left( {{{\bf{x}}_2}} \right) \leftrightarrow ...
0
votes
0answers
127 views

Hadamard / matrix product adjoint

First of all I would like to thank everyone over here at mathoverflow for their amazing generosity and help (for both pros and newbies like myself). I apologize if this question seems dumb; I'm a new ...
1
vote
0answers
76 views

On compactness in Sion's minimax theorem

Sions minimax theorem (wiki, paper) can be stated as follows: Let $X$ be a compact convex subset of a linear topological space and $Y$ a convex subset of a linear topological space. Let $f$ be a ...
1
vote
1answer
87 views

Nested convex optimization

Suppose I have a convex optimization problem of the form $$\min_x f(x) ~~s.t.\\x\in X$$. Say that $f(x)$ and its (sub)gradient are not given in a closed form, but are determined by solving a convex ...
1
vote
0answers
73 views

A version of isotone projection cones

We write $a \succeq b$, where both $a, b \in \mathbb{R}^n$, as a shorthand for $a_i \ge b_i$ for all $1 \le i \le n$. Let $C$ be a closed convex cone in the first orthant of $\mathbb{R}^n$ and denote ...
5
votes
0answers
66 views

Finding the optimal mixture of two convex functions

I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where ...
4
votes
1answer
94 views

Analysis of first-order methods for constrained convex optimization with approximate oracles

In many first-order optimization methods an oracle is needed whose action enforces the constraint/regularizations. For example, in projected gradient descent, conditional gradient method, and proximal ...
4
votes
1answer
152 views

Maximizing Frobenius Norm of Commutator (an opposite Procrustes problem)

I was wondering if anybody has any suggestions on the following problem: Let $S$ be an $n\times n$ positive definite symmetric matrix. I wish to find an $n\times n$ orthogonal matrix $R$ which ...
5
votes
0answers
178 views

Characterizing matrices with rank constraint

Given matrix $M\in\Bbb\{0,1\}^{n\times n}$, is there a nice method to characterize $$\mathscr{D}[M]=\{Q\in\Bbb\{0,1\}^{n\times n}:\mathsf{rank}(M-Q)= \mathsf{rank}(Q),\quad M-Q\in\Bbb\{0,1\}^{n\times ...
1
vote
0answers
85 views

Likelihood convexification

I am doing constrained vector optimization using a non-convex non-linear likelihood function. My problem is of the following form: $$\begin{align*}\hat Q &= \underset{\vec Q}{\arg\min} -\log ...
2
votes
0answers
84 views

How to solve the following generalized quadratic programming problem [closed]

I want to solve a generalized form of a quadratic programming problem $$\min_x \left(\sqrt{x^TPx}+\sqrt{x^TQx}\right)^2+c^Tx$$, $$\textrm{ s.t. } Ax\le b.$$ Here, $P$ and $Q$ are both positive ...
8
votes
3answers
312 views

Lower bound for spectral radius on $\operatorname{GL}(n,\mathbb{Z})$

Consider the group of matrices $G =\operatorname{GL}(n,\mathbb{Z})$ with integer entries and determinant $\pm 1$. For each matrix $D \in G$, the product of the eigenvalues of $D$ is equal to $\det D ...
6
votes
0answers
110 views

A specific case of the $p$-center problem

Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
1
vote
1answer
96 views

What's the most efficient way to solve this euclidean projection on non-negative affine space constraint?

I've come across this convex optimization problem in my research where I need to project a matrix $X_0$ onto a non-negative affine space constraint and box constraints. Concretely, $X \in ...
0
votes
1answer
76 views

accelerate convex optimization by proximal projection

I am using level method to solve non-smooth convex programming problem (where the objective function is given by an oracle from another program ): http://www2.isye.gatech.edu/~nemirovs/Lect_EMCO.pdf ...
1
vote
0answers
101 views

Proximal mapping of composition with linear operator

Let $A$ be an orthogonal matrix. Then the proximal mapping $prox_{f \circ A}(x)$ can be evaluated efficiently by $$ (I + \partial (f \circ A))^{-1}(x) = prox_{f \circ A}(x) = A^T prox_{f}(A x), $$ as ...
4
votes
0answers
130 views

Two quadratic programming problems always same answer? [closed]

Was exploring quadratic programming optimization and for two types of problems the answers seemed to always equal. Problem 1: Minimize $\tfrac{1}{2} \mathbf{x}^T Q\mathbf{x}$ Subject to $ A ...
0
votes
2answers
137 views

Does removing some constraints in convex program change the optimal solution? [closed]

Suppose I have a convex program which has only two variables, the objective function is strictly convex, and the constraints are linear functions. I think removing all non-tight constraints doesn't ...
1
vote
1answer
109 views

An optimization problem in complex space

Consider the following optimization problem $$ \min \| \textbf{Ax-B}\| $$ $$ s.t.|x_i|=1,i=1,...,n $$ where $\textbf{x}\in \mathbb{C}^{n}$ is the optimization varaible, $x_i$ is the $i$-th ...
5
votes
1answer
332 views

Algorithm to minimally connect line segments in Euclidean plane

Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?" More formally and generally, what I'm looking for ...
1
vote
0answers
118 views

Restricted strong convexity for biconvex functions

Recently, it has been shown (arxiv paper) that non-convex functions with the restricted strong convexity (RSC) property has the interesting property that their local minima lie within a small ball of ...
0
votes
1answer
67 views

Finding maximum of a function with unfixed number of variables

Can anybody solve this: For a constant positive integer $n\geq6$ find $k$ and positive integers $a_{1},a_{2},...,a_{k}$ that maximize the expression ...
17
votes
8answers
2k views

When do people actually use the maximum entropy distribution?

One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an ...
0
votes
1answer
179 views

Matrix equation

Let $A$ be $k\times n$ matrix i.e., $A=(a_{1},\ldots, a_{n})$ where $a_{j} \in \mathbb{R}^{k}$, $rank(A)=k$ and $1\leq k \leq n$. Let $q=(q_{1},\ldots, q_{n})\in\mathbb{R}^{n}$ be such that ...
2
votes
1answer
175 views

Necessary conditions for optimality in Banach spaces

Let $X$ denote the non-negative "orthant" of the Banach space $L^2$ (or whatever you call the set of functions in $L^2$ that are non-negative), and let $C$ be a closed, convex subset of $X$. Let $f$ ...