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

learn more… | top users | synonyms

0
votes
0answers
20 views

Be C a matrix n x n positive semi definite. proof x'Cx is convex and sqrtroot(x'Cx) is convex.

Hi I have a homework from optimization and I want to know how to do the following exercise: Be C a matrix n x n positive semi definite. proof that: (1)$x^tCx$ is convex. (2)$\sqrt{x^tCx}$ is convex. ...
0
votes
0answers
22 views

equality constraints and conic constraints in Sedumi (SOCP)

I´m starting playing with Sedumi. I want to solve a problem in the form $$ \min c_0' x $$ s.t. $$ A_1 x = b_1$$ $$ ||A_2 x + b_2|| <= c_2'x+d_2 $$ where $x \in R^n$, $ A_1 \in R^{m_1,n}$, $ ...
2
votes
1answer
108 views

Solution for $\min_{x^Tx=1} x^TAx-c^Tx$

$\min_{x^Tx=1} x^TAx-c^Tx$ looks like a simple QPQC problem. If $A$ is positive semi-definite, can I get the solution by first getting $x=A^{-1}c$ and then projecting $x:=\dfrac{x}{||x||}$ to make ...
0
votes
0answers
13 views

Joint convexity through expected value and max operators

I am trying to minimize the following function by choosing $q$ and $z$, where $X$ and $Y$ are random variables, and $r$, $a$, and $b$ are constants. $C(q,z)=E_{X}[a \cdot max(0,X - q)] + E_{Y}[b ...
0
votes
0answers
15 views

Convert Quadratically constrained basis pursuit to LASSO

The Quadratically constrained basis pursuit is to solve \begin{align} \hat{\boldsymbol{x}} &= \arg\min \|\boldsymbol{x} \|_1 \\ s.t. & \| \boldsymbol{Ax} - \boldsymbol{y} \|_2^2 < \eta ...
1
vote
1answer
43 views

Existence of unique maximizer in R^n

This sounds like a very basic question, but I have a hard time pinpointing the necessary and sufficient conditions... Let $f : \mathbf{R}^n \to \mathbf{R}$ be a function. I want to prove that there ...
1
vote
1answer
33 views

Properties of convex function with Lipshitz continuous gradient (Prof. Nesterov's textbook)

I am reading the Prof. Nesterov's textbook: Introductory lectures on convex optimization - a basic course p.57 I have problem in the following: My ...
0
votes
1answer
53 views

Adding constraints in a constrained problem

Consider a simplified version of a problem I am looking at: $$\min_{x, y, z, t_1, t_2, t_3} x - x^2 - y + y^2 - z + z^2 + t_1$$ subject to: $$ -x + x^2 \leq a + t_1$$ $$ -y + y^2 \leq b - t_2$$ $$ -z ...
1
vote
1answer
26 views

Proximal-type support function properties - nonnegative & strongly convex (proof)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The following part confuses me: $\\$ $\\$ ...
2
votes
0answers
69 views

LASSO constrained and penalised forms: first - order conditions?

The LASSO problem can be formulated in two ways: 1) Constrained formulation: $$ \|Xw-y\|^2\to\min_{w}\\ \text{s.t. } \sum_{i}|w_i|\leq{t}. $$ 2)Penalised formulation: $$ ...
1
vote
1answer
33 views

Proof of unique solution of strongly convex function (Prof. Nesterov Paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems I am confused about the green part of the following: $\\$ ...
1
vote
0answers
32 views

How to prove this function is quasi-concave? [closed]

Consider the function $f(x,y) = x(1-y)\log(1+y/x^2)$, where $0\le x, y\le1$. Is this function quasi-concave?
0
votes
1answer
26 views

Convex hull of halfspace and point is not a polyhedron

Let $S=conv(H \cup\{x\} )$ denote the convex hull of $H \cup\{x\}$ where $H \subset \Bbb{R}^n$ is a halfspace and $x\in\Bbb{R}^n, x\notin H$. I need to prove that $S$ is not a polyhedron and my ...
0
votes
0answers
28 views

Can we solve minimax in this way?

I am working to use proximal operators for solving a minimax optimization problem. It is known that if you use alternative optimization, the algorithm cycles, see an answer to this question ...
1
vote
1answer
41 views

How can I solve this as an optimization problem?

I would like to find x such that (Ax).^2 + (Bx).^2 == I (using Matlab syntax). A, B are matrices and I is a vector, all with real values. The number of equations is less than the number of variables, ...
0
votes
3answers
38 views

Convexity of $y\geqslant\frac{1}{x}$ and $xy\geqslant 1$

I would like to ask the convexity of $y\geqslant\frac{1}{x}$ and $xy\geqslant1$. We know that $y\geqslant\frac{1}{x}$ is convex for $x>0$. But if we transform the inequality into ...
0
votes
1answer
31 views

If we know the convex conjugate of $f(x,y)$, what can we say about the conjugate of $f$ in $x$?

Say $f^*(x,y)$ is the convex conjugate of $f(x,y)$. Now take $g_{y_0}(x) := f(x, y_0)$. Is there any relationship between $g^*_{y_0}(x)$ and $f^*(x, y_0)$?
0
votes
1answer
28 views

Solving nonconvex problem by iterating convex ones

I have a convex problem with the following properties: -The energy to be minimized is convex - it is basically a norm. -The domain is defined by a set of convex cone constraints inequalities. I am ...
0
votes
1answer
17 views

Optimality condition

I was looking at a few results of convex optimization and I'm stuck with a part of a proof. Consider the following minimization problem: \begin{align} \text{minimize} \quad &\Phi(x) \\ ...
1
vote
1answer
36 views

Problem to prove function is convex or not?

How do I plot function $f(x1,x2)=x^4_1+x^4_2$ such that $x^2_1+x^2_2=1$ and $x_1,x_2\in(0,1)$? Does it possible to plot in MATLAB so that I can visualize the function? Also I am trying to check ...
0
votes
1answer
32 views

Convexity, Hessian matrix, and positive semidefinite matrix

I would like to ask whether my understanding of convexity, Hessian matrix, and positive semidefinite matrix is correct. For a twice differentiable function $f$, it is convex iff its Hessian $H$ is ...
1
vote
0answers
21 views

How to perform a quasiconvex optimization

I have a quasiconvex objective function $f:\mathbf{R}^n\rightarrow \mathbf{R}$ which I would like to minimize over a simplex $S\subseteq \mathbf{R}^n$. I have looked pretty hard but have been unable ...
1
vote
1answer
31 views

Is a global optimal solution of a convex problem always unique?

I do not have a specific problem. Could a convex optimization problem (not strictly convex) have alternate solutions?
0
votes
0answers
18 views

ADMM Formulation for L1 minimization with equality or inequality constraints

A simple ADMM formulation exists to minimize $||Ax - b||_1$ (L1 norm minimization): http://web.stanford.edu/~boyd/papers/admm/least_abs_deviations/lad.html How do I extend this formulation to work ...
1
vote
0answers
45 views

Can we use simple alternating optimization for minimax (saddle point) problems?

Consider a function $f(x,y)$, convex in $x$ and concave in $y$. we are interested in the following optimization problem, \begin{align} \min_{x \in D_x} \max_{y \in D_y} f(x,y) \end{align} Because of ...
0
votes
1answer
24 views

Boundary of a convex body

I need your help in defining a boundary for a given convex body, $P$ without knowing the shape of $P$ meaning that I can't say that $P$ is a polygon or any shape which is convex. Meaning that by ...
0
votes
1answer
66 views

A light solution of a quadratic programming problem

I have a simple and light quadratic programming problem that I need to solve, as following: \begin{align} & \underset{x}{\arg\min} & & \dfrac{1}{2}x^T x-z^T x\\ & \text{subject ...
0
votes
1answer
45 views

Prove a set is convex

I have problems to make proof for below two statements. Let Γ be the LP max cᵀx s.t. Ax ≤ b. prove that set of all optimal solutions to Γ is a convex set Let x' be a basic feasible solution of Γ. ...
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. } ...
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 ...
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
26 views

Convex function and convex optimization

I would like to ask something about convex function and convex model. For example, the function $f(x,y)=\frac{x^2}{y}$ is convex when $x\geqslant0$ and $y>0$. For a convex model (minimization), ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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
40 views

Strong duality of SDPs

On pp. 654 of Boyd's book, it is claimed that strong duality holds between the SDPs B.2 and B.3 (at the bottom of this page). Does it require additional assumption that one of them is strictly ...
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 ...
0
votes
0answers
25 views

Need optimal tableaus be unique assuming unique solution?

If so, why? If not, do they differ by some ERO/s? That is, they are row equivalent? This is the problem (taken from Chapter 2 here): My classmate gave an optimal tableau that is different ...
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 ...
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 ...
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\\ ...