Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

learn more… | top users | synonyms

2
votes
0answers
23 views

Question on optimization problem computing its solution function

I was just presented with this in Optimization class involving an optimization problem, on which I have no clue, it reads: (P) minimize-> $ f(x_1,x_2) = (x_1^2 -2x_1 + x_2^2 + 1)^{1/2} $ subject ...
1
vote
2answers
13 views

If $q:R^n\to R$ is convex and $d^0,\ldots,d^k\in R^n$ are linearly independent, then $R^k\ni l\mapsto q(x^0+\sum_{i=0}^kl_id^i)$ is convex, too

Let $q:\mathbb R^n\to\mathbb R$ be strictly convex, $d^0,\ldots,d^k\in\mathbb R^n$ be linearly independent (for some $k\in\left\{0,\ldots,n-1\right\}$) and $$h:\mathbb R^k\to\mathbb R\;,\;\;\;\lambda\...
0
votes
1answer
74 views

Maximum of Sum of Strictly Concave Functions

If $g(x) = \sum_{i=1}^n g_i(x)$ where each $g_i(x)$ is a strictly concave function with maximum $x_i^* = \operatorname{argmax}\limits_x g_i(x)$, is it true that $$x^* = \operatorname{argmax}\limits_x ...
2
votes
0answers
37 views

Is difference of convex hulls a convex hull of differences?

Let $K \subset \mathbb{R}^n$ be an n-dimensional simplex. Let $e_i$ denote the $i^{th}$ standard unit vector. Define $K-K$ as follows: $$ K-K=\{x-y: x,y \in K\} $$ We know that $K=$ convex hull $\{e_1,...
1
vote
0answers
13 views

Regularity for the Feasible region

I have this problem $min -x +y $ $x-y^2\leq0 $ $\frac {(x-1)^2}{4} +y^2 \leq 1$ $y \geq -1/2$ Say if the feasible region is regular or not, analitically. I know that to check the KKT ...
1
vote
1answer
40 views

convex for two variables

Suppose we have the following optimization problem: $$\min_{X,Y}~L=\min_{X,Y}~\|A-XY\|_2^2,$$ where $X\in R^{m\times n}$, $Y\in R^{n\times p}$ and $A\in R^{m\times p}$. Could someone give me some ...
2
votes
1answer
146 views

Co-coercivity of gradient

If $f$ is convex with $dom$ $f$ $= R^{n}$ and $g(x) = x^{T}x - f(x)$ is convex, how to prove the Co-coercivity of gradient? $$(\nabla f(x) - \nabla f(y))^{T}(x - y) \leq 1/L \parallel \nabla f(x) - \...
1
vote
1answer
107 views

Can a smooth convex functions be non-differentiable?

Consider the definition of the $\beta$-smoothness (for some constant $\beta$): $$ \|\left. \nabla f \right|_{ y } - \left. \nabla f \right|_{ x } \| \leq \beta \| x - y \| $$ And convexity: $$ f(x)...
0
votes
1answer
139 views

How can linearize the product of decision variables in ILP?

Here, we have something like this: R + (1-R)T + (1-R)(1-T)S + (1-R)(1-T)(1-S)Q = 1 where R, T, S, Q are binary decision variable How can I convert this ...
3
votes
0answers
48 views

Center of mass of vertices without enumeration?

Given a $n$-dimensional convex polytope defined by $A x\leq b$ and $A_{eq} x = b_{eq}$, is there an efficient way to determine the average coordinates of all vertices without enumerating them? (As if ...
0
votes
0answers
45 views

Max-norm and Trace-norm matrix completion, which one is better?

Let $X$ be a matrix, then max-norm regularizes maximum of its singular values, $|X|_{\infty} = \max(\sigma_i$), while trace-norm penalizes sum of all singular values, $|X|_* = \sum_{i = 1}^m \sigma_i$....
0
votes
0answers
31 views

matrix optimization , low rank constraint

can anyone provide recommendation on how to go about solving this $\min_{W}$ $\|XW - YB\|^2_F$ + $\alpha\|W\|_2$ rank(W) $\leq$ k Matrix X, Y, B are known my attempt if i ignore the last ...
0
votes
1answer
44 views

Optimization of convex integral function

I have the following constrained optimization with the integral objective function $$ \min_{x_i\in D} \int_{t_1}^{t_2} \frac 1 {t - \sum\limits_{i = 1}^N x_i f_i (t)} \, dt $$ where $t - \sum\limits_{...
0
votes
1answer
33 views

Only one system of equation has solution

Let $A$ be a $m\times n$ real matrix. Show that only one of the following systems has solution: (I): $Ax > 0$ (II): $Ay = 0, y \geq 0, y \neq \theta$, where $\theta$ is zero vector. I ...
2
votes
1answer
51 views

Show that system $Ax\geq 0,$ and $A^Ty=0, y\geq 0$ has solution satisfies $Ax+y>0$.

Let $A$ be a $m\times n$ real matrix. Show that system (I): $Ax\geq 0,$ (II): $A^Ty=0, y\geq 0$ has solution satisfies $Ax+y>0$. I have no idea to prove above claim. Can you give me a ...
3
votes
1answer
64 views

minimization of sum of linear fractional functions

I have the following sum of fractional functions optimization problem $$ \begin{array}{l} \mathop {\min }\limits_{\bf{x}} \,\,\,\sum\limits_{i = 1}^p {\frac{1} { {b_i}-{{\bf{a}}_i^T{\bf{x}} }}} \\ ...
0
votes
0answers
36 views

Global optimization methods where constraints are lipschitz functions

Is there any global optimization methods where objective function is nonlinear (not lipschitz) but constraints are lipschitz functions?
0
votes
1answer
81 views

Optimizing sums of log det

I have a set of points $S$ which have to be clustered into $K$ cluster say, $S_k$, by minimizing the following function: $J = - \sum_{i=1}^{K} \log \det( \mathbf{I} + H_i H_i^T)$, Where $H_i$ is the ...
2
votes
1answer
91 views

The gradient of a function on a Banach space is an element of the dual space

Can somebody explain me why gradient descent in Banach space does not make sense? As pointed out by Sebastien Bubek in his blog, the gradient is an element of the dual space $\mathcal{B}^*$. But I ...
0
votes
1answer
39 views

Minimum of sum of squares over sums

I am trying to minimize $\phi(\alpha)$, where $\alpha \in \mathbb{R}^K$. $\phi(\alpha) = \frac{R^2 + G^2 \gamma \sum_{i=0}^{K} A_i \alpha_i^2}{\sum_{i=0}^{K} A_i \alpha_i} $ Where, $A_i = \gamma \...
1
vote
0answers
38 views

A question about minimizing the $\lambda_{max}$ over a set of diagonal perturbations

Say I have an off-diagonal symmetric $0,1,-1$ entry matrix $B$ and a set of $2k$ diagonal matrices, $D_{11}, D_{12}, D_{21}, D_{22},..,D_{k1},D_{k2}$. (if it helps you can assume that $(1)$ all the ...
0
votes
1answer
33 views

Combinatorial Convex Optimization: Russian paper

I'm looking for an electronic version of the paper: David Yudin and Arkadi Nemirovski. Informational complexity and effective methods of solution of convex extremal problems. Economics and ...
3
votes
2answers
68 views

Faster Algorithms for Convex Hulls

I was interested in the following: Given two polyhedra $P_1, P_2$ specified in the form: $$ P_1 = {x : A_1x \le b_1 } $$ $$ P_2 = {x : A_2x \le b_2 } $$ Whereas $ x \in R^n$ and $b_1, b_2$ are ...
2
votes
1answer
35 views

Multiplicative version of convex hull

The convex hull of a finite set of points, $(x_i,y_i) \in \mathbb{R_+}^2$ ($i=1,...,n$), is defined as: $$\left\{(\sum_{i=1}^{n} \alpha_i x_i,\sum_{i=1}^{n} \alpha_i y_i) \mathrel{\Bigg|} (\forall i: ...
1
vote
0answers
140 views

Convex optimization when Hessian is non-invertible

1) Are there any extensions to Newton's method for finding minimum of a convex function when the Hessian is singular ? (I have all positive eigenvalues in the Hessian except one which is zero) I ...
3
votes
0answers
44 views

Submodular function, square of which is also submodular?

A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $ for every $ ...
0
votes
1answer
39 views

about scaling property of proximal operator

If the proximal operator of $f(x)$ is $\text{prox}_{\lambda f}(x)$, what about $cf(x)$ and $f(cx)$, c is a scalar. For example, If $f(x) = ||x||_{1}$, $x \in \mathbb{R}^{n}$, how about the proximal ...
0
votes
0answers
86 views

Maximum volume inscribed ellipsoid inside nonconvex polyhedron

In Convex Optimization (Boyd, Vandenberghe), an algorithm for finding the maximum volume inscribed ellipsoid inside a convex polyhedron is given on p. 414 (8.4.2 Maximum volume inscribed ellipsoid) [I ...
0
votes
1answer
104 views

Dual problem of piecewise linear function

I would like to see the geometric interpretation of the relationship between the primal problem and the dual problem on the $x,y$-plane. So I am looking at an example of minimizing the maximum of some ...
3
votes
2answers
157 views

Is the minimum of a parametric convex function convex again?

Let $I$ and $J$ be compact intervals. Let $f:I\times J\to\mathbb R$ be differentiable and strictly convex. Is the function $g:I\to\mathbb R$ defined by $$ g(x) = \min_{y\in J} f(x,y) $$ ...
5
votes
2answers
155 views

Are these two optimization problems equivalent to each other?

Let $\mathbf{x}=[x_1,\ldots,x_K]^T$. For a fixed vector $\mathbf{a}$, I have the following optimization problem : \begin{array}{rl} \min \limits_{\mathbf{x}} & | \mathbf{a}^T \mathbf{x} | \\ \...
0
votes
0answers
31 views

Show that the set $\{y_1a_1+y_2a_2: -1\le y_1,y_2\le 1\}$ is a polyhedron

Show that the set is a polyhedron and express it in the form: $S = \{Ax\leq b, Fx = g\}$, $S=\{y_1a_1+y_2a_2 | -1\leq y_1\leq 1, -1\leq y_2\leq 1\}$ where $a_1,a_2\in\mathbb{R}^n$ My attempt: A set ...
0
votes
1answer
136 views

Can a convex function have local maxima?

I have read that a convex function can have local maxima. It seems that this must happen on the boundary of the domain, otherwise there should be a region in which the function is concave. Is this ...
0
votes
1answer
57 views

Finding extreme point of a set determined by two planes in $\mathbb R^3$

Problem asks to find a extreme point the set $\{(x,y,z) \mid x-2y \leq 3 , 2y+3z \geq 4 \}$. But I don't think it has a extreme point, because it is intersection of two hyper planes in 3D, which doesn'...
0
votes
1answer
79 views

Biconjugate of a nonconvex function

Is biconjugate of a non-convex function, the tightest lower bound on that function? If yes why?
-1
votes
2answers
131 views

Joint Convexity Proof

Let $x$ be $n \times 1$ vector and $Y$ be $n \times n$ matrix. Prove that $f(x,Y) = x'Y^{-1}x$ is jointly convex in $x$ and $Y$ when $Y \succ 0$.
3
votes
1answer
147 views

proximal operator of weighted L1 norm

I hope to solve this problem. $$\min \quad \left\| CX \right\|_{1} $$ $$ \text{s.t.}\quad AX=b, X >0 $$ where $C \in \mathbb{R}^{m \times m}$, $X \in \mathbb{R}^{m \times n}$, $A \in \mathbb{R}^{...
1
vote
1answer
54 views

Optimum is achieved when both variables are equal

Consider the problem $\max_{y,z:\|y\|_\infty,\|z\|_\infty \leq 1}y^TBz$, where $B$ is symmetric, positive semidefinite, $y,z\in \mathbb{R}^n$, $\|z\|_\infty=\max_{i\in\{1,\ldots,n\}}|z_i|$. It turns ...
1
vote
0answers
33 views

how to get orthogonal rank 1 approximations?

The situation: I have $k$ matrices $A_i$, which are all real and of size $m\times n$. Now I would like to find the matrices $\tilde{A}_i$ of $A_i$ so that 1) $\tilde{A}_i$ is of rank 1 (thus a rank 1 ...
1
vote
0answers
41 views

Finding a polynomial approximation of a PDF

I would like to find a polynomial $P(x)=\sum_{d=1}^D P_dx^d$ of degree $D$, where its derivative is larger than or equal to a given pdf $f(x)$ in $[0,1-\epsilon]$, for any $\epsilon>0$. Note that ...
0
votes
1answer
59 views

Fenchel Duality in Prof. Bertsekas' lecture

Please see this link, p.39-41 (sufficient to answer my question), before (1.47) for detailed. For convenience, the relevant part is shown as: I am confused in two things: The ...
0
votes
0answers
26 views

Extreme pts of a polyhedral feasible set

Consider a linear program $\min \{c^T x:Px=q,x\geq 0 \}$, where $P \in \mathbb{R}^{m \times n}$. $x\geq 0$ means each component of $x_i$ of x is nonnegative. The feasible set is $\{x:Px=q,x\geq 0\}$....
0
votes
0answers
36 views

Some problems in finding conjugate function

Ask the following fundamental problems: How to derive the conjugate function of $g(y)$ if given "$\underset{y \geq 0}{\text{sup}}\{g(y)-y^Tx\}$"? My attempt is as following: \begin{align*} &...
2
votes
1answer
73 views

Conjugacy relation in the primal and dual problem

The following is my derivation in the Conjugacy relation in the primal and dual problem. I am shaky in it; so hope for some advices. Consider the following problem, $f(x),g(x)$ are convex ...
0
votes
1answer
166 views

How can I solve a nonlinear optimization problem where constraint contains exponential term?

I have the optimization problem as below: $\hspace{10mm} \text{Maximize} \sum_{k} \alpha_k {R}_k $ $ \hspace{10mm}\text{subjcet to:} $ $ \hspace{10mm}\exp \left[ - (2^{{R}_k } -1) \left( \frac{\...
0
votes
0answers
29 views

Optimization problem: solving one implies solving the reverse?

I am looking to solve an optimazation problem $Maximize_{x} [A(x)]$ s.t. $B(x)\geq B_0$, where $B_0$ is a constant. If I solve this problem (i.e, finding the optimal $x^*$ that optmize while ...
0
votes
0answers
32 views

Minimizing the sum of the $4^\text{th}$ power of a matrix entries.

Consider a real $n\times n$ matrix $X$. Suppose I would like to minimize the sum of the squares of its entries as a penalty term in some convex minimization. I can write the term using the Frobenius ...
0
votes
1answer
20 views

Conditions of convergence of stochastic subgradient algorithm

It is well known that for appropriate step size, $E[g^t] \in \partial f(x^t)$ is sufficient conditions for this subgradient algorithm to converge. What I'm wondering is whether the requirement has to ...
1
vote
0answers
58 views

Condition for product of increasing and decreasing functions to be quasiconcave?

Is there any condition for product of increasing and decreasing functions to be quasiconcave? More specifically, I am having in mind a condition for $F(x)\cdot(1-G(x))$ to be quasi concave where $F$ ...
0
votes
2answers
38 views

Reference Request: Soft handed text on duality theory?

Can anyone recommend a text on duality theory which includes basic formulation of the primal and dual formulation and some introduction to minimax problems? Preferably having some computation in ...