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

learn more… | top users | synonyms

0
votes
0answers
6 views

Convergence of backtracking and gradient descent.

I am thinking a bit about the following exercise: Let $f(x) = x_1^2 + x_2^2$ with dom $f = \{ (x_1,x_2):x_1 > 0 \}$. The optimal value of this problem is $p^* =1$, but it is never attained since ...
2
votes
1answer
14 views

Check if convex polygon is completely contained completely within another convex polygon.

How can I determine if a convex polygon is completely contained within another convex polygon where speed is critical? I've thought about doing this, which will only use inequalities: pcp = ...
-4
votes
0answers
50 views

Positive solutions to $A^T A x \geq 0$

Find a positive solution $x$ to the linear inequality $A^T A x \geq 0$. Progress. One special solution is when $A^TA$ is row diagonally dominant, then the column vector $1$ satisfies $A^T A x ...
0
votes
1answer
560 views

convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
0
votes
1answer
11 views

If a quadratic form $f$ takes the minimum on a triangle in a vertex, what can I say about min of $f$ on edges of a subdivision?

Let $f(x)=x^2+y^2$ be the Euclidean square-norm and $A,B,C\in\mathbb{R}^2$ be vertices of a triangle $\Delta$ such that $f$ takes the maximum on $\Delta$ in $C$, the minimum in $A$ and takes the ...
0
votes
1answer
16 views

Solving Constrained Least-Squares

I need to solve a constrained least-squares (LS) problem as follows $min_X \text{ } ||Y-AX||_F^2$ $s.t. \text{ } {X\in \chi}$ where $A\in R^{n\times m}$, $(n\ge m)$ , $X\in R^{m\times k}$ and ...
0
votes
0answers
21 views

Using semidefinite programming to solve the following problem

I am struggling with the following problem, and wonder is SDP can help: $$\mathrm{maximize\ } \alpha_{10}+\alpha_5+(\alpha_2+\alpha_8)/2 \mathrm{\ subjected\ to\ } \mathrm{T_1}\succeq0, ...
1
vote
1answer
18 views

How can I compute fast the minimum of a linear plus Kulback-Leibler on the unit simplex?

Given $a, x^0 \in \mathbb{R}^n$ I wish to compute $$\min_{x \in \Delta_n} a^t x + \sum_{i=1}^n x_i\log(x_i/x^0_i) - x_i +x^0_i $$ where $\Delta_n$ is the unit simplex $\{x \in \mathbb{R}^n \mid ...
1
vote
1answer
9 views

Convex combination and convex set

From where does $tx + (1-t)x'$ originate from? I am selfstudying an economists book, and this is popping up all of a sudden. I get that it's a line between $x$ and $x'$, but why? And is $tx' + (1-t)x$ ...
1
vote
1answer
21 views

For a non-convex function f, how to find a function g such that $g\circ f$ is strictly convex?

The following function $f(x)={1\over (1+e^{-x})}$ is non-convex but $\ln(f(x))$ is convex. Given a non-convex function $f$, can we find a function $g$ such that $g\circ f$ is strictly convex? If yes, ...
2
votes
0answers
69 views
+100

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
0
votes
0answers
17 views

How to convert the following optimization problem to quadratic program?

Given positive constants $C$ and $\epsilon$ and points $\{ (x^i,b_i)\} _{i=1}^I \subset \mathbb{R}^{n+1}$, how can we rewrite the following optimization problem as minimizing a convex quadratic ...
4
votes
2answers
53 views

does this convex set have a specific name?

Let $x_1,\dots,x_N$ be points of $\mathbb{R}^n$. Define the following set: $\mathcal{A} = \left\{\sum_{j=1}^N a_j x_j : -1 \le a_j \le 1, \, \, \forall j=1,...,N\right\}$. It is an easy exercise to ...
0
votes
0answers
16 views

Book on duallity and sensitivity in nonlinear optimization

I am looking for a recommended book on duallity and sensitivity in nonlinear optimization, as duallity and sensitivity is a well studied topic in LP , I am struggeling to find books in this subject ...
0
votes
0answers
18 views

Continuity of optimisation problem

Consider $$F(z)=\min ae^{-x}+b e^{-y} s.t. x\ge 0, y\ge 0\text{ and } x+y=z$$ I checked if this function is continuous, but it is not at $z=0$. $F(z)=2\sqrt{ab}e^{-z/2}$ when $z\ne 0$, and ...
1
vote
1answer
28 views

Convergence rate - Convex optimization

What is the best known algorithm in terms of convergence rate for unconstrained convex optimization and under what assumptions? $\min_{x} f(x)$ where $f(x)$ is a given twice differentiable convex ...
-2
votes
0answers
18 views

Pos of Matrix is a closed set? [on hold]

"Pos of matrix" $:= \{ \sum_{i=1}^n \lambda_i *a_i \mid \lambda_i \geq 0 ,\ a_i \text{ are columns of matrix, } 1\leq i \leq n\}$ that matrix have $n$ columns. Prove that "Pos of matrix" is a closed ...
0
votes
0answers
20 views

pos of matrix is close [on hold]

"Pos of matrix" := $\{ \sum_{i=1}^{m}\lambda_i *a_i |\ \lambda_i \geq 0 ,\ a_i\ \text{are columns of matrix,}\ 1\leq i \leq n\}$ that Matrix have $n$ columns. prove that "Pos of matrix" ...
0
votes
0answers
11 views

Optimization with KL-divergence in CVX [closed]

I am trying to solve an optimization problem whose objective is KL-divergence (there are only linear equality constraints and nonnegativity constraints). In particular, my goal is to obtain a solution ...
1
vote
1answer
26 views

Augmented Lagrangian Method for Inequality Constraints

Augmented Lagrangian Method can be used with inequality constraints. The question is how. One approach (according to Numerical Optimization Book by Nocedal and Wright; page 522), is linearly ...
1
vote
1answer
19 views

Show the Gini Coefficient is Quasiconvex

The Gini-coefficient is defined as $$ G(x) = \sum_{i = 1}^n \frac{i}{n} - \sum_{j=1}^{i} \frac{x_{(j)}}{\mathbb{1}^{T}x}, $$ where $x_{i} $ is nonnegative numbers with positive sum. $x_{(j)}$ denotes ...
0
votes
1answer
56 views

intuition behind subspace of $R^n$

Hi: I've been reading an optimization text by Charles Byrne, "A First Course In Optimization". I'm currently going through the chapter where he explains things about convex sets and convex functions ...
0
votes
0answers
29 views

Formulate an optmization problem as a convex optmization problem

Let $P$ be a polyhedron, i.e. $P = \{ x \in \mathbb{R}^{n}\, |\,\, a_{i}^{T}x \leq b_{i} \}$. Define $R$ as the rectangle given by $\{ x \in \mathbb{R}^{n}\, \mid\, \, l \preceq x \preceq u \}$. Find ...
2
votes
5answers
330 views

Compressive sensing with non square matrices

I'm implementing the algorithm in the following paper: "Compressive sensing for wideband cognitive radios" http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04218361 However I've run into a ...
0
votes
2answers
20 views

Finding when a function is concave [closed]

Given the function below $f=e^{ax^2+bx}$ what are the conditions on $a$ and $b$ such that $f$ wil be concave Thanks
0
votes
0answers
28 views

strong convex implies exp-concave

Prove that if f is strong convex (for some m>0) $\mbox(\nabla f(\mathbf{x})-\nabla f(\mathbf{y}))^{T}(\mathbf{x}-\mathbf{y})\geq m||\mathbf{x}-\mathbf{y}||_{2}^{2} $ then f is also ...
3
votes
1answer
46 views

$\arg\max$ of an increasing function grows as the region grows.

$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 ...
0
votes
1answer
34 views

proof that length of difference of projections implies equality of length of normals

Hi: I'm reading a book on optimization and there is an interesting stated theorem but I don't know how to prove it. Notation: Let $P_{c}(x)$ denote the projection of onto a convex set c which is a ...
1
vote
1answer
515 views

proximal operator of infinity norm

What is the proximal operator of $\|x\|_\infty $? I know we have to take the subgradient and compute it but I am a bit stuck. Can anyone show me steps?
-1
votes
3answers
133 views

Is $f(x_1,x_2)=x_1x_2$, with $x_1,x_2 \in \mathbb{R}_+$, a convex function?

Let $f(x_1,x_2)=x_1x_2$, with $x_1,x_2 \ge 0$. Is $f$ a convex function? Why? $\ \\$ Edit (in view of the comments below) The Hessian matrix is $H=[0\, 1; \,1 \,0]$, which is indefinite (in ...
1
vote
2answers
402 views

Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
0
votes
0answers
40 views

Non-convex function with global minimum [duplicate]

I am working on a complicated objective function which I suppose is not convex. But when I use a global optimization tool that can find all its local minimums, it will always converge to the same ...
0
votes
0answers
28 views

How can I minimize a quadratic on the unit simplex?

How can I compute $$ \min_{x \in \Delta_n} \frac{1}{2}\lVert Bx\rVert^2 + x^tAy$$ with $x \in \mathbb{R}^n, y \in \mathbb{R}^m, A_{m \times n}$, $B_{n \times n}$ where $\Delta_n$ is the unit simplex ...
1
vote
0answers
29 views

Proximal operator of spectral norm of a matrix

How can I calculate the proximal operator of spectral norm for any general matrix, $X\in R^{m\times n}$ i.e., $X^* = \arg \min_X ||X||_2 + \frac{1}{2\tau} ||X-Y||_F^2$ I understand that the proximal ...
-1
votes
0answers
19 views

Help understanding the specification of constraints for cvxopt

This is an example from the cvxopt documentation and I am trying to understand how the L2 constraints are specified to the solver. The problem is specified as: ...
0
votes
0answers
19 views

How can I solve $\min \{ \langle A(x),y\rangle + f(y) \text{ s.t. } y \in S^n, \operatorname{tr}(y) =1, y \geq 0\}$?

I'm trying to solve the problem $$\min \{ \langle A(x),y\rangle + f(y) \mid y \in S^m, \operatorname{tr}(y) =1, y \geq 0\}$$ where $x \in \mathbb{R}^n$, $y \in S^M$, that is, it's a symmetric $m$ by ...
0
votes
0answers
27 views

Krein Milman Property

If a closed bounded (not compact) set $X$ in a Banach space $B$ (like $L^1$) has extreme point(s), must the max of a linear functional defined on $X$ occur at one of them? I suppose it depends on $B$. ...
1
vote
1answer
419 views

Using gradient descent and Newton's method combined

I have this function $f(\mathrm{X})$ where $\mathrm{X=A+B+C}$ where $\mathrm{A}$ is a diagonal element with variable $a$ on its diagonal. $\mathrm{B}$ is another diagonal matrix with variable $b$ on ...
0
votes
0answers
15 views

How to solve this entropy optimization problem with gradient projection method?

The problem is defined as $$ \min_{w} = \sum_{i=1}^{n} \sum_{j=1}^{n}\left\{ \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \log \left(\sum_{k=1}^{3}w_kP_{ij}^{(k)}\right) \right\} + \gamma \|w\|_2^2\\ $$ ...
0
votes
0answers
16 views

Minimizing a function known to have a unique local and global minimum

Quasi-convex functions are a class of functions known to have a unique local and global minimum, which can minimized over convex sets using numerical methods with convergence guarantees. A function is ...
1
vote
0answers
27 views

Proximal operator for the nuclear norm of Hankel (x)

I have a problem in hand for which I need to compute the proximal operator of the composite function $||Hankel(x)||_{nuc}$ where $x \in R^N$ and $||.||_{nuc}$ denotes the matrix nuclear norm. For a ...
2
votes
1answer
54 views

linear approximation with respect to L1 norm

I am trying to solve this problem: Find the best $L^1$ linear approximation of $e^x$ on [0,1] i.e. minimize $\int_0^1|e^x-\alpha-\beta x| dx$ any hints how to proceed
0
votes
0answers
24 views

How to solve the least square with $L_2$ norm constraint directly?

I answered the question Why are additional constraint and penalty term equivalent in ridge regression? earlier, but I myself still have some questions on it. To solve \begin{align} \min_{\beta} ...
0
votes
1answer
378 views

relation between size of matrix and condition number

I have a matrix A of size NxM. Is there any relationship between size of a matrix A with the condition number ? I am computing the pseudo inverse (pinv in matlab ) ...
0
votes
0answers
28 views

Find an optimal solution for $\min_{x} F(x)$ analytically

I want to find an analytical solution (exact/closed-form) for $x$ of the following minimization problem: $$\min_{x} b x \left[e^\left(\frac{a}{x}\right)-1\right]+d (1-c-x) \left[e^ ...
0
votes
1answer
43 views

Step-by-step example of solving a quadratic program with linear inequality constraints

I'm doing an exercise work about Support Vector Machines which involves solving a quadratic program of the form $$\begin{aligned} & \underset{\boldsymbol\alpha \in \mathbb{R}^N}{\text{minimize:}} ...
2
votes
1answer
39 views

Constructing a quasiconvex function

Let $C\subset\mathbb{R}^2$ be a nonempty convex set. A function $f:C\rightarrow\mathbb{R}$ is called convex if $$ f(\lambda u+(1-\lambda)v)\leq\lambda f(u)+(1-\lambda)f(v), \quad\forall u,v\in C, ...
1
vote
2answers
195 views

(Updated) Geometric Illustration of Monotone and Maximal Monotone Maps

I am writing a note about the Monotone and Maximal Monotone maps from the following book http://link.springer.com/book/10.1007%2Fb97594 In this book we read a map ...
0
votes
1answer
420 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
1
vote
2answers
46 views

Is the optimum of this problem unique?

I have a convex optimisation problem: $$\min_{x_i} \sum_{i=1}^N a_i \exp(-x_i/b_i)\quad\text{ s.t. }\sum_{i=1}^N x_i=x\text{ and } x_i\ge 0$$ The KKT conditions are: $$\lambda=\begin{cases} ...