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

learn more… | top users | synonyms

0
votes
0answers
17 views

Strict convexity of a non-differentiable multivariate function

Suppose $F: \mathbb{R}^N \mapsto \mathbb{R}$ is differentiable. In order to check for the convexity of $F$, we can restrict it to a line. Thus $F$ is convex iff the function $g: \mathbb{R} \mapsto ...
0
votes
1answer
23 views

Convex Optimization: minimize over unknown convex set starting in center

Essentially I am trying to develop an algorithm to minimize a function over a convex set that I don't know explicitly. However, I have a starting point "deepest in the set" (i.e. with largest norm ...
1
vote
1answer
24 views

Augmented Lagrangian with multiple constraints

I would like to minimise a function, with multiple constraints: $$ \frac{1}{2} \|y-Ax\|_2^2 + \beta \|z\|_1 $$ subject to $$ Bx = 0 $$ and $$ x - z = 0 $$ In my case $(B+I)$ is not a valid ...
1
vote
0answers
20 views

Strictly Concave Function over non-convex set

I have to optimize a function $f$ over a set $S \subset X$. We know that $f$ is non-negative, continuos and strictly concave over $X$. We have that $S$ is compact but not convex. By Extreme Value ...
0
votes
1answer
23 views

Test Convex Hull of Vectors

My mathematical background is generally not so great so please pardon me if my question appears silly. I am trying to test the convex hull of 3 vectors for an intersection with coordinate axes as ...
0
votes
1answer
21 views

show that $a^T\lambda + a_0$ is equivalen to $\lambda^T(1/2(ea^T + ae^T) + a_0 E)\lambda$

Affine function $f(\lambda)=a^T\lambda + a_0$ where $a, \lambda\in \mathbb{R}^n,a_0\in \mathbb{R}$ and $\lambda$ is in a unit simplex,i.e., $\sum\limits_{i=1}^n \lambda =1, \lambda\in \mathbb{R}^n_+$. ...
1
vote
4answers
65 views

Optimization of a quadratic function with qudratic constraints

I'm a Graduate student of Electrical Engineering. I have some basic knowledge on Convex Optimization. For my research, I cam across the following optimization program. With $\mu > 0$, find $\arg ...
0
votes
1answer
33 views

Why is any subspace a convex cone?

I am reading Convex Optimization written by Stephen Boyd. In page 27 of chapter 2, there is an example said 'Any subspace is affine, and a convex cone(hence convex).' Can anybody explain to me why ...
0
votes
0answers
18 views

How to minimize this sparse quadratic function?

There is a problem when I'm reading a paper. Equation: $min_p|p-p^*|^2+\alpha |R(p)|^2 + \beta |D(p)-\delta|^2$, where $p, p^*, R(p), D(p), \delta$ are all $M\times N$ matrices, and $p^*, R(), D(), ...
1
vote
0answers
20 views

Basis pursuit denoising

The Lagrangian form of basis pursuit denoising $\min_{w} ||w||_{\ell_{1}} + \lambda ||Aw-x||_{\ell_{2}}^{2}$ can be solved using proximal gradient descent. Proximal methods also can be used to ...
1
vote
2answers
522 views

Numerical optimization with nonlinear equality constraints

A problem that often comes up is minimizing a function $f(x_1,\ldots,x_n)$ under a constraint $g(x_1\ldots,x_n)=0$. In general this problem is very hard. When $f$ is convex and $g$ is affine, there ...
0
votes
0answers
47 views

Dictionary learning for sparse coding using ADMM

I'm trying to formulate an ADMM for performing dictionary learning (for sparse coding) on a set of data. Let's assume we have a data matrix of $X \in \mathbb{R}^{M \times N}$, a dictionary of $D \in ...
0
votes
0answers
23 views

Convex Constraint on Sine Wave Simularity

So lets say you have a vector X = [x1 x2 x3 ..... xn] You want to optimize a cost function over X. However you want to constrain the vector X to look like a sine wave. Say you can parameterize a ...
1
vote
0answers
83 views

Any example of strongly convex functions whose gradients are Lipschitz continuous in $\mathbb{R}^N$

Let $f:\mathbb{R}^N\to\mathbb{R}$ be strongly convex and its gradient is Lipschitz continuous, i.e., for some $l>0$ and $L>0$ we have $$f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{l}{2}||y-x||^2,$$ ...
0
votes
2answers
58 views

Does convex optimization belong to linear or nonlinear programming?

Does convex optimization belong to linear programming or nonlinear programming? Is convex optimization an undergraduate topic or a graduate topic?
4
votes
1answer
125 views

Closest Matrix with Specific Eigenvector

Consider a vector ${\bf x}$ and a matrix $A_0$ with $A_0(i,j)\ge0$. What is the best way of getting matrix $A$ s.t. $$A = \arg \min |A-A_0|$$ subject to $$A{\bf x} = \lambda {\bf x} \hspace{2mm} ...
4
votes
1answer
639 views

What is the time complexity of conjugate gradient method

I have been trying to figure our the time complexity of conjugate gradient method I have to solve a system of linear equations given by $$ Ax=b $$ where A is sparse and positive definite symmetrix ...
3
votes
3answers
108 views

Geometric interpretation of duality and Slater's condition

I am trying to study about optimization problems, Lagrange duality and related topics. I came across some presentation on the net, which claims to show the geometric interpretation of the duality and ...
0
votes
1answer
42 views

Schatten p norm p>1

The Schatten p norm is differentiable away from the origin for p> 1. Does a stronger condition of Lipschitz continuity of the gradient also hold?
1
vote
1answer
24 views

Logistic Regression is convex proof

I am trying to make sense of this paper qwone.com/~jason/writing/convexLR.pdf "Regularized Logistic Regression is Strictly Convex" by Jason D. M. Rennie. I am following the proof and formula (1) is ...
0
votes
1answer
84 views

Show that the dual norm of spectral norm is Nuclear norm.

Could someone help to understand that the dual norm of spectral norm is Nuclear Norm ? We can focus on the real field. Given a matrix $X \in \mathbb{R}^{mn},$ then the spectral norm is defined by: ...
2
votes
1answer
31 views

A Variant of Gradient Descent

Suppose I have some objective function $f(\beta)$ which I would like to minimize for $\beta$. A standard gradient descent would be $\beta^{(t+1)}=\beta^{(t)}-\alpha \nabla f(\beta^{(t)})$, where ...
0
votes
0answers
39 views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
0
votes
1answer
33 views

is this a convex optimization problem?

Can someone clarify is this a convex optimization problem or not. $min \| X-UV\|_{F}\quad $ s.t $ \quad U \geq ,V\geq0$ . If not , what makes the problem non-convex?
1
vote
0answers
104 views

Linear programming optimization problem formulation

I need help in formulating an optimization problem. I have a system of equations as follows: $c_1x_1+c_2x_2+c_3x_3=1$ $b_1x_1+b_2x_2+b_3x_3=1$ $a_1x_1+a_2x_2+a_3x_3=1$ In my case the ...
3
votes
1answer
110 views

Newton's method vs. gradient descent with exact line search

tl;dr: When is gradient descent with exact line search preferred over Newton's method? I simply don't understand why exact line search is ever useful, and here's my reasoning. Let's say I have a ...
1
vote
1answer
384 views

Generalization of soft threshold operator?

For certain $\ell_1$-regularized optimization problems, a critical computational step is the soft threshold operator: $\mathcal{S}_t(x) = \mathrm{sgn}(x)\circ \mathrm{max}(|x|-t)$ where $\circ$ is ...
0
votes
1answer
30 views

Determining corners of this convex set

Let $N \geq 2$ be an integer. Let $P:= \{ (a_1, \ldots, a_N) \in [0, 1]^N : \sum_n a_n = 2 \}$. Is $P$ the convex hull of $P \cap \{0, 1\}^N$? Edit: This is apparently true, see the beginning of ...
0
votes
0answers
54 views

Nonsmooth optimization

Now I have a chance taking a course in nonsmooth optimization, the course outline writes: convex analysis, subdifferential calculus and proximal mapping. various numerical algorithms to solve ...
1
vote
0answers
29 views

sup is bounded or not?

The sup is as following: $c_f = sup_{x,s\in D} \ f(y) - f(x) - (y-x)^Tb$ where $y=x+\alpha(s-x)$, $\alpha \in (0,1 )$ is constant and $b$ is a constant vector. $D$ is a convex compact set and ...
1
vote
1answer
33 views

Proving a function of matrix is convex

I have a function of a matrix and a vector $f(A,b)=y^\top (I-A)^{-1} b$ and I want to know the conditions under which it is convex. For functions of a vector, the positive definiteness of the Hessian ...
0
votes
1answer
29 views

Steepest Descent Sequence

How can I compute the first three iterates for the steepest descent sequence $f(x_1,x_2) = \frac{(x_1^2+3x_2^2)}{2}$ beginning at $x_0 = (\frac{\sqrt{3}}{2}, \frac{1}{2 \sqrt{3}})^T$ $\nabla ...
1
vote
1answer
36 views

Convexity proof - can I get some pointers?

Prove that $C \subset \mathbb{R}^n$ is convex iff $\forall m \in \mathbb{N}$ and every set of $m$ points $\{x_1,...,x_m\} \subset C$ we have that $\sum_{i=1}^m \lambda_i x_i \in C$ Where ...
1
vote
1answer
19 views

Show the following statements are equivalent - convexity

Let $C \subset \mathbb{R}^n$ be a set. Show the following are equivalent: (a) The set $C$ is convex. (b) The function $\delta_C : \mathbb{R}^n \to \mathbb{R} \cup \infty$ defined as: ...
1
vote
0answers
22 views

Convexity Proof with constraints on the gradient

Consider a minimization problem $(P)$ : minimize $f(x)$ subject to $\delta_C(x) \leq 0$ Now assume that $\emptyset \neq C \subset \mathbb{R}^n$ is convex and let $f: \mathbb{R}^n \to \mathbb{R}$ be ...
1
vote
1answer
114 views

Sub-gradient of the “$\ell_0$ norm”

I am trying to characterize the sub-gradient of l0-norm ($f(x) = ||x||_0=\sum_{i=1}^n 1\{{x_i \neq 0}\}$). At first, I thought l0-norm is a convex non-smooth function since it satisfies the triangle ...
0
votes
1answer
22 views

Projection on Epigraph of a convex function

Given a convex function $h:\mathbb{R}^n \mapsto \mathbb{R}$, and a point $(x,\alpha) \in \mathbb{R}^n \times \mathbb{R}$, how can I find a closed formula to compute the projection of $(x,\alpha)$ in ...
7
votes
3answers
2k views

Disjoint Convex Sets That Are Not Strictly Separated

Question 2.23 out of Boyd and Vanderberghe: Give an example of two closed convex sets that are disjoint but cannot be strictly separated. The obvious idea is to take something like unbounded sets ...
1
vote
1answer
50 views

How to derive the solution in quadratic optimization

I'm reading the book "Convex Analysis and Optimization" written by Prof. Bertsekas. In Example 2.2.1, there are the following description: I don't know how to ...
11
votes
2answers
3k views

What is the difference between minimum and infimum?

What is the difference between minimum and infimum? I have a great confusion about this.
3
votes
1answer
301 views

Why does the non-negative matrix factorization problem non-convex?

Supposing $\mathbf{X}\in\mathbb{R}_+^{m\times n}$, $\mathbf{Y}\in\mathbb{R}_+^{m\times r}$, $\mathbf{W}\in\mathbb{R}_+^{r\times n}$, the non-negative matrix factorization problem is defined as: ...
0
votes
1answer
47 views

How to solve this convex resource allocation problem numerically? CVX doesn't work.

I got a resource allocation problem as follows: \begin{eqnarray} \min &\sum_{i=1}^M \frac{1}{1 + \text{exp}(C_i + \frac{r_i}{1+r_i})} ;\\ &\sum_{i=1}^M r_i \le R;\\ &r_i \ge 0 ...
0
votes
1answer
43 views

What's the difference between interior and relative interior?

As defined in Convex Optimization written by Stephen Boyd, both interior and relative interior seems to describe a same thing: a set that peels away it's boundary points. So what on earth is the ...
0
votes
0answers
14 views

How do I show that expected squared error stochastic optimization problem has a global optimum?

I was interested in showing that minimizing the following had a global optimum: $$ \mathbb{E}_{ (x , y) \sim P_{x,y}}[(\hat{x}(y) - x]$$ where $\hat{x}(y)$ is a linear function i.e. $\hat{x}(y) = ...
0
votes
1answer
30 views

Verifying stationary points - check my answer please - Has a hessian

Can someone check this for me; For $f(x_1,x_2,x_3) = x_1^2 + x_2^2 + x_3^2-x_1x_2+x_2x_3-x_1x_3-x_1+x_2$ the stationary point occurs at $\nabla f(x)^T =\left[ \begin {array}{c} 0\\ 0\\ 0\\ ...
0
votes
1answer
25 views

Why is a local min also a global min for convex functions?

As the title states, for an unconstrained minimizaton problem, of a convex function, why is it that the local minimum is also the global solution?
2
votes
0answers
57 views

the continuity of argmin on convex funtion

Define $$x'=\text{argmin}_{x_1}f(x_1,\lambda),$$ where $f$ is a strictly convex function on $x_1$ and $\lambda$. I would like to ask if there is any theorem about the continuity of $x'$ w.r.t ...
0
votes
0answers
39 views

How to prove that convex function has an increasing slope?

A function $f(x)$ in some domain $a\leq x \leq b$ is convex if and only if for any $x_1 < x_2 < x_3$ from domain $[a,b]$, $$\frac{(f(x_2)-f(x_1))}{(x_2-x_1)} \leq ...
0
votes
0answers
23 views

Optimize log functions over polytopes

Let's consider the following optimization problem min $\sum_{i=1}c_i\log x_n $ subject $Ax\leq b$ ie, it is to optmize a weighted sum of logarithms over a polytope ($Ax\leq b$). Clearly if $c_i$'s ...
0
votes
1answer
25 views

Is this a convex program?

I have a nonlinear optimization problem $\min \sum_{i=1}^n \sum_{j=1}^n y_{i,j}$ subject to $x_i- y_{i,j}x_j\leq 0$ $0\leq x_i\leq 1$ $y_{i,j}>0$ The question is whether this is a convex ...