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

learn more… | top users | synonyms

0
votes
0answers
19 views

general framework for proof of convexity in least square problem

Let $f(x_i,\theta) : X \times \Theta \rightarrow Z$ be a parametric function with parameter $\theta$ that we wish to fit to set of samples $S =\{(x_i,z_i)\}_{i=1}^N$, where $(x_i, z_i) \in X \times ...
3
votes
1answer
44 views

Convex set: extreme points and distance to the origin

I'm fairly sure the following is true, although I wouldn't mind being proven wrong. If true, I would like to see an elegant proof, as my attempts are kind of messy. Let $K\subset\mathbb R^2$ be a ...
0
votes
0answers
13 views

Equality constraints into inequalities constraints through elimination

I read here in Section 10.1.2 of this text that a way to eliminate linear equality constraints of the type $$Ax = b$$ in convex optimization problems is to parameterize the related affine space as a ...
0
votes
0answers
24 views

Are the constrained optimization problem equal to the unconstrained one?

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{x} & \|Ax-b\|_2\\ \mathrm{s.t.} & \|x\|_1\le \epsilon \end{array} \end{equation} (2) ...
1
vote
0answers
24 views

Why the trace norm of a tensor is a good approximation to its rank?

In many literature, they use the trace norm of a tensor to approximate its rank, which is defined as follows: $$\|\mathcal{X}\|_{\ast}:=\sum_{i=1}^{n}\alpha_i\|X_{(i)}\|_{\ast}$$ where ${\alpha_i}'s$ ...
0
votes
0answers
8 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
22 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
21 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
35 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
5 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 ...
0
votes
0answers
20 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
32 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
28 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
23 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
19 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
20 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
102 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
12 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
12 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
40 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
29 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
24 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
68 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
27 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
24 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
37 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
25 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
33 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
26 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
20 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
27 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
16 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
42 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
22 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
64 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
41 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
23 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
34 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
15 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
27 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 ...