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

learn more… | top users | synonyms

0
votes
0answers
9 views

Lower bound of averaging gradient method (Prof. Yurii Nesterov's paper)

I am reading the paper of Prof. Yurii Nesterov: Primal-dual subgradient methods for convex problems The last inequality confuses me: (p.231) Note: 1. The ...
2
votes
0answers
26 views

How to efficiently solve a quadratic program repeatedly?

I have a quadratic problem, \begin{align} \min_{x\in [0,1]^n} x^T p+ \frac{1}{2\lambda} x^T Q x \end{align} ($Q$ is semidefinite) which I want to solve repeatedly, with the slight change of p and Q, ...
0
votes
1answer
26 views

A ratio of two convex functions with different minima cannot be monotone. Proof?

Let $\lambda(x)=\frac{f(x)}{g(x)}$ where $f(x)$ is a differentiable function minimized at $x=x_1$ and $g(x)$ is a differentiable function minimized at $x=x_2\neq x_1$. How can I show that $\lambda(x)$ ...
2
votes
1answer
42 views

What aspects of convex optimization are used in artificial intelligence, if any?

I work on convex optimization with Stephen Boyd's book. As an example, support vector machines are mentioned as an application of separating hyperplanes theorem. I am wondering if there is any other ...
0
votes
0answers
8 views

Who proved that the equilibrium problem is equivalent to a monotone inclusion problem?

I'm looking for the original reference where it was proved that given a subset $X$ of a space $E$ and a function $f:E \times E \mapsto \mathbb{R}$, the equilibrium problem of finding $x \in X$ such ...
1
vote
0answers
23 views

Expressing $\forall$ in linear programing

I'm doing a linear program to a game and I don't know how to express $\forall$ in linear programing (or if I had the right intuition to do it). Here is the problem: I have several vessels that are ...
0
votes
1answer
36 views

Show non-convexity of a function with vector input

How does one go about proving non-convexity of the function d? $$ d(v) = 1/2*||F(v)- p||^2 $$ $$ F(v)=\sum_{i=1}^n l_i*\begin{pmatrix} cos(\sum_{j=1}^i v_j) \\ sin(\sum_{j=1}^i v_j \end{pmatrix} $$ ...
0
votes
1answer
32 views

Gradient and Hessian of a function defined in terms of matrix inverse

Let $\mathbf{I}_m$ be the $m$-dimensional identity matrix and $\mathbf{0}_m$ be the $m$-dimensional zero matrix. The matrix $D(\mathbb{x})$, where $\mathbb{x} = (x_1, \dots, x_n)^T$, is defined as: $$ ...
0
votes
0answers
24 views

Subdifferential optimality conditions

I need help with subdifferential optimality. Let $f(x_1, x_2)=x_1^2 + x_2^2 + |x_1 -x_2 - y|$. Find: \begin{align} \min_{x_1, x_2} f(x_1, x_2) \end{align} This is convex, so must have unique ...
0
votes
0answers
21 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
25 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
109 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
14 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
16 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
46 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
35 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
27 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: $\\$ $\\$ ${\color{red}{E}}\...
2
votes
0answers
72 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: $$ \|Xw-y\|^2+\lambda\left(\...
1
vote
1answer
35 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
33 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 convex-...
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
39 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 $$xy\geqslant1(x,...
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) \\ \text{...
1
vote
1answer
38 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
34 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
25 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
34 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
49 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
25 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
67 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
49 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. } \|[x]_M\|_{X/M}=\|x+m\|...
0
votes
0answers
33 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
16 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
1answer
31 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
43 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} \begin{...
0
votes
0answers
20 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
39 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
40 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
31 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 ...