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

learn more… | top users | synonyms

1
vote
1answer
25 views

Factor space norm calculation when the subspace is finite-dimensional

Let $(X,\|\;\|_X)$ be a normed vector space and let $M$ be a closed finite-dimensional subspace of $X$. I want to prove that: $$ \forall x\in X\;\;\exists\;m\in M\text{ s.t. } ...
2
votes
1answer
15 views

Can we say anything about the minimum of a perspective function compared to that of the original function?

Given convex function $f(x)$, its perspective function is $g(x,t) = tf(x/t), t>0$ is also convex. Is the minimum of $g$ over $(x,t)$ always less than (or larger than) the minimum of $f(x)$? Note ...
0
votes
0answers
32 views

Transform a nonconvex problem into a convex problem using perspective function

Suppose I have the problem $$ \text{minimize } f_0(x)\\ \text{subject to } tf_1(x) \leq r $$ with variables $t,x \in \mathbb{R}$ and $f_0, f_1$ are convex. The constraint is not convex, so I was ...
0
votes
1answer
28 views

Convexity of n $4u^4x^{2.5}y^{-5}$ over $x>0, y >0$ and $u>0$

I am trying to find if the function $4u^4x^{2.5}y^{-5}$ is convex over $u>0, y>0$ and $x>0$. The thing which comes to my mind immediately is to check the positive semi-definiteness of the ...
3
votes
1answer
37 views

Least squares with multiple linear constraints

The method of direct elimination can be used to solve the constrained least squares problem \begin{equation} \min_{\mathbf{x}}\left\Vert \mathbf{Ax}-\mathbf{b}\right\Vert _{2} \end{equation} ...
0
votes
0answers
19 views

Can the low-rank approximation problem be formulated as the following convex model?

Given a three-order tensor $\mathcal{Y}$, our aim is to find a tensor $\mathcal{X}$ to approximate it and $\mathcal{X}$ should satisfy the following property: $\mathcal{X}$ can be well approximated ...
1
vote
2answers
474 views

when is the epigraph a convex cone?

The problem is from Stephen Boyd's textbook, which I couldn't solve. The question is "when is the epigraph of a function a convex cone?" The solution says that it is when the function is convex and ...
0
votes
2answers
47 views

Is the constraint $xy\leqslant 0.001$ convex?

I would like to ask whether the constraint $xy\leqslant 0.001$ ($x,y\geqslant0$) is convex. Since its Hessian matrix is positive semi-definite for $x,y\geqslant0$, the constraint $xy\leqslant 0.001$ ...
0
votes
0answers
37 views

Quasiconvexity of a function on the positive orthant using rays

It is seen in Boyd's book on Convex Optimization book that to show a function $f:\mathbf{R}^n\rightarrow \mathbf{R}$ is quasiconvex, it is enough to show that $f$'s restriction to a line is ...
0
votes
0answers
32 views

Proving equivalent optimization problems

Consider the problems $\min f(x) , x \in X$ and $\min g(x), x \in X$. two optimization problems are said to be equivalent if an optimal solution to one, is also optimal to another. I would like to ...
4
votes
2answers
156 views

Minimum of $\sum\limits_{k=0}^n { n \choose k} (1-x)^{n-k} x^k a_{n-k}b_k$ over $x \in [0,1] $

Given \begin{align} f(x)=\sum_{k=0}^n { n \choose k} (1-x)^{n-k} \cdot x^k \cdot a_{n-k} \cdot b_k \end{align} Find \begin{align} \min _{x \in [0,1] } f(x) \end{align} We can assume that $a_k$ and ...
0
votes
1answer
29 views

Are these two optimization problems equivalent?

I have two problems as follow. $min_x: ||x-y||_2^2 + \lambda_1 ||x|| \quad \ \ (1)$ and $min_x: ||x-y||_2^2 + \lambda_2 ||x||^2 \quad (2)$ Here $||\cdot||$ could be any norm and ...
0
votes
0answers
23 views

Complementary Slackness Condition clarification

So for the dual part of the complementary slackness, the theorem says this: If $y_i^* > 0$, then the $i^{th}$ constraint is binding in Primal $\ \ \ (1)$ If the $i^{th}$ constraint in Primal is ...
1
vote
2answers
36 views

Explain why for an extreme point some inequalities in the constraints become equalities

Suppose we have a linear program $$ \max_x c^Tx\\ \text{subject to } Ax \leq b $$ where $\leq$ denotes pairwise inequality, i.e. $a^T_i x \leq b_i, i = 1,..., n$. If $y$ is an extreme point, why is ...
0
votes
2answers
50 views

Combinations, vertices and LPs

This suggests the following (I know it is a very inefficient one) This will work but there would be many vertices. In fact for $Ax \leq b, \ x \geq 0$ there can be $\binom ...
0
votes
1answer
14 views

Brief explaination on convex optimization problem

I have following type optimization problem (I transformed original max-min problem into this kind), and I can show that all $g_1(l_1),\cdots,g_M(l_1,\cdots,l_M)$ functions are concave. ...
1
vote
1answer
37 views

Maximizing the volume of the convex hull of $N$ points in the unit ball

Suppose we are given an integer $N\ge4$, and we have to pick $N$ points in a unit ball in $\mathbb R^3$ to maximize the volume of their convex hull. Are those points necessarily on the surface of the ...
2
votes
1answer
52 views

what is the closed form solution for $\min_x ||y-x||^2_2+\lambda ||x||_2$

$y$ and $x$ are vectors. $\|\cdot\|_2$ is Euclidean norm. In one paper I read, they say the closed form solution is $x=\max\{y-\lambda \frac{y}{\|y\|_2}, 0\}$. I don't know why $x$ need to be ...
0
votes
1answer
49 views

Proximity operator for logistic function

I am reading the ADMM paper by S. Boyd et al: http://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf I'm interested in implementing a L1-regularized feature-wise distributed multinomial ...
3
votes
0answers
34 views

Reference for elementary result in optimization

Let $U(\mathbf{z})$ be a convex, twice differentiable function, and $F(\mathbf{z},\mathbf{q})$ be convex and twice differentiable separately in $\mathbf{z}$ and $\mathbf{q}$. Consider the problem of ...
1
vote
1answer
26 views

How to find a realisable starting point with the Simplex algorithm?

Let be the following linear program: \begin{equation*} \begin{cases} \max f(x_1,x_2) =3x_1+2x_2\\ 5x_1 + 2x_2 \ge 8\\ x_1 - x_2 \le 1\\ x_1 + x_2 \le 3\\ ...
11
votes
2answers
9k views

L1 norm and L2 norm

I was studying the Stephen Boyd's textbook on convex optimization. It says the following: The amplitude distribution of the optimal residual for the l1-norm approximation problem will tend to have ...
0
votes
0answers
20 views

Strong Duality for Euclidean distance

i have an optimization problem in the form: $min ||x - y||$ sbj to: $A.x = 0$ $A.y = 0$ $l_x \leq x \leq u_x, l_y \leq y \leq u_y$ I'm trying to find the dual form of this optimization problem, ...
1
vote
0answers
38 views

Generalizations of Positive Definiteness

What, if any, notions of positive definiteness can be extended to 3rd order tensors (and beyond)? The reason I ask is because the Hessian matrix of a convex function is positive semi-definite, but ...
2
votes
1answer
37 views

Matrix optimization over a quadratic function

I want to find matrices $F$, $G$, and $H$ minimizing $\begin{bmatrix} x^T & y^T& z^T \end{bmatrix} \begin{bmatrix} I & 0& 0 \\ 0 & F &0 \\ 0 & G &H ...
0
votes
0answers
26 views

Proof of convergence of coordinate descent for non differentiable function

Prove that a function $f(x)$ given by: $$ f(x) = g(x) + \sum_{i=1}^{n} h_{i}(x_{i}) $$ where $g(x)$ is convex and differentiable, and each $h(x)$ is convex, can be minimized by co-ordinate descent ...
2
votes
0answers
28 views

Theoretically understanding the algorithmic solution to this Quadratically Constrained Quadratic Optimization Problem

I have a simple QCQP problem to solve: $\min_{t} x(t)^{T}Ax(t)$ subject to constraints $x(t)^{T}Ax(t) > 1 $ where A is a positive definite matrix and $x(t) \in \mathbb{R}^2$ is some time ...
0
votes
1answer
30 views

Show that that optimal Ridge Regression beta is minimizing

I have the constrained regression (Ridge) of the form $$S(\beta)=(y-X\beta)'(y-X\beta)+\lambda(\beta'\beta)$$ where $\lambda$ is just a scaler. I am able to find an optimizing solution for the beta ...
0
votes
0answers
30 views

A supremum problem

Let $a=\underset{\|u\|_c\leq 1, \|v\|_r\leq 1}{\sup}v^TY^Tu$. If $\lambda<a$, $\underset{u_m, v_m}{\sup}v_m^TY^Tu_m-\lambda\|u_m\|_c\|v_m\|_r=+\infty$. While if $\lambda > a$, then ...
2
votes
0answers
20 views

Duality between $Ax<b$ and another system, but Gordan's just misses

I am trying to show that $$Ax < b$$ Is feasible iff $$ A^T y =0 , b^Ty + s = 0, (y,s) \ge 0, (y,s) \ne 0$$ Is infeasible. Work So Far Now when I try to hit this with Gordan's Lemma I seem ...
0
votes
0answers
34 views

How can the ADMM algorithm be distributed?

I am reading Boyd's tutorial paper on ADMM. One question I had after I reached the formulation of the algorithm on pp.14 is: how can the alternating or sequential fashion of x-minimization step and ...
0
votes
0answers
50 views

Computing Direction of Descent for General Fermat Problem

Suppose that $k \geq 3$, and let $X_1, \dots , X_k$ be $k$ points in $\mathbb{R}^2$, and let $w_1, \dots , w_k$ be $k$ positive real-valued constant weights. Given this, consider the function $g(p) = ...
1
vote
1answer
44 views

Is there Any Benefits for Casting a Convex Program Problem into Linear Program Problem?

I'm curious a relative broad question: Suppose I have a convex program problem in hand. (hence, I could use many well-developed software packages to solve this problem for sure; e.g., CVX..) But ...
1
vote
3answers
39 views

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$?

$sup_x [ f(x)+sup_x g(x)]= sup_x[f(x)+g(x)]$ is the statement correct? Can I prove like this: $sup_x [ f(x)+sup_x g(x)] = sup_x[f(x)] + sup_x[g(x)] = sup[f(x)+g(x)]$.
0
votes
0answers
33 views

Why Gradient Descent Runs Away from Possible Solution?

I am trying to solve a multivariate optimization problem (actually trying to minimize a first order objective function) using gradient descent. The objective function is simple: ...
4
votes
0answers
123 views

Conditions under which the damped Newton method is globally convergent?

Consider the problem of minimizing a convex function over $\mathbb{R}^n$ \begin{align} \min_{x\in\mathbb{R}^n}f(x) \end{align} Consider the damped Newton method (from Nesterov's book Introductory ...
1
vote
0answers
27 views

Converting a norm-computation SemiDefinite program to standard SDP form.

I'm trying to express this norm-computation semidefinite program: for given $A \in R^{m \times n}$ and a scalar $\epsilon \in (0,1)$ $$\gamma_{2}^{\epsilon}(A):= \min\,t\,\, subject\, to\, \left( ...
1
vote
0answers
20 views

Boyd & Vandenberghe's proof that all simplexes are polyhedra.

On page 33 of B&V's convex optimization book, during the proof that any simplex can be represented as a polyhedron, they discuss a $n \times k$ matrix $B$ with full column rank and conclude that: ...
0
votes
0answers
66 views

matrix optimization in diagonal and orthonormality constraint

I'd like to solve the following optimization problem. Y is a CxN matrix A is a CxC and diagonal matrix Q is a CxC and orthonormal matrix X is a CxN matrix $$ min_{A,Q} {|| Y − AQX ||}^2_F $$ The ...
0
votes
0answers
15 views

Convexity of Maximum Inscribed Ellipsoid Problem

I am confused about the problem of finding the ellipsoid of maximum volume inscribed in a polyhedron as discussed in section 8.4.2 of Convex Optimization by Boyd and Vandenberghe. I've followed the ...
1
vote
0answers
35 views

Logarithmic Function Behaivour

I have read about Logarithmic function. We can use the second-order condition to show that the $f(x)=\log_2(1+x), x \geq 0$ is a concave function. Now, is $g(x)$ a concave function? How can I prove ...
1
vote
0answers
48 views

Convex Conjugate of Log Sum Exp Function

Convex Optimization Snippet In showing the convex conjugate of log-sum-exp function, $f(x) = \log(\sum_{i=1}^n e^{x_i})$, Boyd argues that the domain of the convex conjugate, $$f^*(y) = \sup_{x \in ...
0
votes
0answers
13 views

Two way partitioning problem's lower bound

In the two-way partitioning problem (as laid out in Slide 7 here), as an example, one possible value for $\nu$ is $-\lambda_{min}(W)1$ which gives the bound as $p^* \ge n\lambda_{min}(W)$. My ...
15
votes
6answers
6k views

Derivative of nuclear norm

I'm trying to take the derivative of nuclear norm with respect to its argument. nuclear norm is defined in the following way: $$\|x\|_*=\mathrm{tr}(\sqrt{x^Tx})$$ I'm trying to calculate: ...
3
votes
3answers
85 views

How to find a counter example for non convexity?

Consider a simple function $f(x,y)=\frac{x}{y}, x,y \in (0,1]$, the Hessian is not positive semi definite and hence it is a non convex function. However, when we plot the function using Matlab/Maxima, ...
0
votes
0answers
25 views

Optimization related to reduced SVD

The reduced SVD of $B_{m\times n}$ is $USV^T$ and we know the columns of $U$ and $V$ are orthonormal. $e_i$ is the $i$th standard basis vector. I want to know the range of the following optimization ...
0
votes
1answer
32 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 ...
2
votes
1answer
39 views

Convolution of convex function and Gaussian is convex

Let $f:\mathbb{R}\to\mathbb{R}$ be a convex function, i. e., for all $x_1, x_2 \in \mathbb{R}$ and $t \in [0, 1]$, $$ \qquad f(tx_1+(1-t)x_2)\leq t f(x_1)+(1-t)f(x_2).$$ I want to prove that the ...
1
vote
0answers
14 views

Condition on linearly separable datasets

I am trying to understand linear classification with hyperplanes. So far I understood that for a binary classifier with labels $y_i \in \lbrace -1, 1\rbrace$ points $(x_i, y_i)$ are separable if ...
3
votes
1answer
81 views

Climbing a hill with increasing & concave marginals. As you climb, do all coordinates go to $\infty$?

$f_1,\dots,f_N:\mathbb{R}^+\rightarrow\mathbb{R}^+$ are strictly increasing, bounded functions whose derivatives monotonically decrease to $0$ as their argument increases. (Picture the shape of the ...