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

learn more… | top users | synonyms

5
votes
3answers
659 views

How to solve $\min \limits_{\mathbf{x}} \| \mathbf{Ax}-\mathbf{b} \|^2$?

Let $\mathbf{x}=[x_1,\ldots,x_K]$. I have the following optimization problem: \begin{array}{rl} \min \limits_{\mathbf{x}} & \| \mathbf{Ax}-\mathbf{b} \|^2 \\ \mbox{s.t.} & x_k\ge 0, \forall ...
10
votes
1answer
8k views

Convexity of the product of two functions in higher dimensions

Exercise 3.32 page 119 of Convex Optimization is concerned with the proof that if $f:\mathbb{R}\rightarrow\mathbb{R}:x\mapsto f(x)$ and $g:\mathbb{R}\rightarrow\mathbb{R}:x\mapsto g(x)$ are both ...
2
votes
2answers
7k views

Derivation of soft thresholding operator

I was going through the derivation of soft threholding at http://dl.dropboxusercontent.com/u/22893361/papers/Soft%20Threshold%20Proof.pdf. It says the three unique solutions for $\operatorname{arg ...
86
votes
4answers
13k views

Please explain the intuition behind the dual problem in optimization.

I've studied convex optimization pretty carefully, but don't feel that I have yet "grokked" the dual problem. Here are some questions I would like to understand more deeply/clearly/simply: 1) How ...
5
votes
3answers
1k views

Is inverse matrix convex?

I wonder a generalization of Jensen's inequality: let $\mathbf{X,Y}$ be two positive definite matrices, can we obtain the following Jensen like inequality $$(1-\lambda)\mathbf{X}^{-1}+\lambda\mathbf{Y}...
3
votes
1answer
146 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
129 views

Legendre transform of a norm

Let $||\cdot||$ be a norm on $\mathbb{R}^n$, with dual norm $||x||_* :=\max_\limits{y:||y||\leq 1}y^T x$. I'd like to show $$\max_{x \in \mathbb{R}^n}(x^T d-||x||)=\begin{cases} 0 & \text{ if } ||...
23
votes
4answers
18k views

Difference between supremum and maximum

Referring to this lecture , I want to know what is the difference between supremum and maximum. It looks same as far as the lecture is concerned when it explains pointwise supremum and pointwise ...
3
votes
1answer
129 views

minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$
3
votes
1answer
888 views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \...
2
votes
1answer
342 views

Simple resource for Lagrangian constrained optimization?

Just had an optimization lecture. I understand unconstrained methods like Newton and Gradient descent just fine, as well as the ideas that give rise to them. I don't really understand the ideas that ...
12
votes
6answers
6k views

Derivative of nuclear norm

I'm trying to take the derivative of nuclear norm with respect to its argument. nuclear norm is defined in the following way: $$\|x\|_*=\mathrm{tr}(\sqrt{x^Tx})$$ I'm trying to calculate: $$\frac{...
5
votes
1answer
1k views

Dual to the dual norm is the original norm (?)

I have the following questions about dual norms : How do you prove that the dual of the dual norm is in fact the original norm? This is what I have so far: If I have $\|y\|_* $ as the norm dual of ...
4
votes
1answer
433 views

Convert Semidefinite program forms

How do I convert the following SDP problem (written in the standard inequality form): $$\min c^T x$$ $$\text{s.t. }F(x)\succeq0$$ When $F(x)\equiv F_{0}+\sum_{i=1}^{m}x_{i}F_{i}$ when $F_{i}\in S^{n}...
1
vote
1answer
911 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: ...
3
votes
1answer
123 views

Projection of $z$ onto $\{x\mid Ax = b\}$

Suppose $A$ is fat(number of columns > number of rows) and full row rank. The projection of $z$ onto $\{x\mid Ax = b\}$ is (affine) $$P(z) = z - A^T(AA^T)^{-1}(Az-b)$$ How to show this? ...
6
votes
2answers
438 views

Optimization problem using Reproducing Kernel Hilbert Spaces

I am encountering a problem concerning Reproducing Kernel Hilbert Spaces (RKHS) in the context of machine learning using Support Vector Machines (SVMs). With refernece to this paper [Olivier Chapelle,...
4
votes
2answers
5k views

Second derivative positive $\implies$ convex

In proof of the following theorem; If $f$ has a second derivative that is non-negative (positive) over an interval then $f$ is convex (strictly convex). $f$ is in real number space., the book I ...
3
votes
1answer
3k views

Prove the supremum of the set of affine functions is convex

Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by ...
2
votes
1answer
74 views

Conjugacy relation in the primal and dual problem

The following is my derivation in the Conjugacy relation in the primal and dual problem. I am shaky in it; so hope for some advices. Consider the following problem, $f(x),g(x)$ are convex ...
1
vote
1answer
280 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, $f:2^{\Omega}\...
2
votes
1answer
82 views

Prove that a polytope is closed

Let the polytope defined by $$S:=co \left\{ x_1,x_2,...,x_k \right\}$$ where $x_1,x_2,...,x_k \in \mathbb{R^n}$ and $co \left \{... \right \}$ is the convex Hull. Prove that S i closed. I tried the ...
1
vote
1answer
71 views

Examples of $f$ strictly convex, either with one minimizer or with no minimizer.

Let $f\colon X \to [ -\infty, +\infty]$ be proper and strictly convex. Show that $f$ has at most one minimizer. Give examples where $f$ is strictly convex, and either (i) $f$ has one minimizer; or (ii)...
1
vote
0answers
168 views

Showing convexity of a function with the restriction over an arbitrary line

Let $f : \mathbb{R}^n → \mathbb{R}_∞$ be a function and let $C ⊂ dom f$ be a convex set. $$**Part I**$$ Prove that $f$ is a convex function if and only if $f$ is convex over every line $L_{v,x_0}$ ...
1
vote
0answers
32 views

Confusion related to proximal newton method

I was reading this method related to proximal newton methods http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2012_0388.pdf. I came across this page I didn't get what this part means $ \...
1
vote
1answer
81 views

Armijo rule intuition and implementation

I am minimizing a convex function $f(x,y)$ using the steepest descent method: $$\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma \nabla F(\mathbf{x}_n),\ n \ge 0$$ My function is defined over a specific domain $...
1
vote
1answer
299 views

Maximizing a function by finding derivative

I want to find the value of $\vec{p}$, $p_s$, $p_t$ each of which is a function of the form $f:\mathbb{R}^2 \to \mathbb{R}$ that maximize the following function : $$\begin{align} \int_\mathbb{R^2} \...
0
votes
1answer
43 views

Convexity of set

If $C\subset\mathbb{R}^m$ is a convex set, $A$ is an $m\times n$-matrix and $b\in\mathbb{R}^m$, how do I prove that the set $S=\{x\in\mathbb{R}^m|Ax+b\in C\}$ is convex? I know that the definition of ...
0
votes
1answer
61 views

Gordan’s lemma equivalent statement

Let $A$ be an $m × n$ matrix. Recall that Gordan’s lemma states that the system $$\{d : Ad < 0\}$$ is inconsistent if and only if the system $$λ ≥ 0 ∈ R ^m , λ \not= 0, A ^T λ = 0$$ is consistent. ...
0
votes
2answers
112 views

Constraint minimization of sum of Non-symmetric matrices

I am trying to find closed form solution to following problem \begin{equation} \begin{array}{c} \text{min} \hspace{4mm} \big(\lambda_1\left( \mathbf{y}^T V^{(1)}\mathbf{x} \right)^2 + \lambda_2\...
21
votes
1answer
1k views

Properties of the Cone of Positive Semidefinite Matrices

The set of positive semidefinite symmetric real matrices form a cone. We can define an order over the set of matrices by saying $X\geq Y$ if and only if $X-Y$ is positive semidefinite. I suspect that ...
11
votes
2answers
8k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value (...
12
votes
5answers
2k views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
10
votes
4answers
3k views

Convexity and Affineness

In reading about convex optimization, the author states that all convex sets are affine. Are affinity and convexity equivalent? If I understand, both definitions incorporate the notion that a set is ...
6
votes
2answers
717 views

What numerical methods are known to solve $L_1$ regularized quadratic programming problems?

What numerical methods are suitable to solve the following problem $$\min_x \tfrac{1}{2}x^T A x + b^Tx + \lambda ||x||_1$$ where $x,b\in\mathbf{R}^n$, and $A\in \mathbf{R}^{n\times n}$ is positive ...
14
votes
2answers
6k views

What is the difference between minimum and infimum?

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

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
5
votes
1answer
573 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 ...
3
votes
2answers
1k views

Gradient-descent algorithm always converges to the closest local optima?

Assume $f(\vec x)$, which is Lipschitz continuous, has two local optima $\vec x_1^*$ and $\vec x_2^*$( $\vec x_1^*$ is the global minimum). We start the gradient-descent algorithm from $\vec x_0$ and $...
5
votes
1answer
2k 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 ...
5
votes
1answer
3k views

prove this is a strongly convex function

The definition of strongly convex from Wikipedia: It is not necessary for a function to be differentiable in order to be strongly convex. A third definition for a strongly convex function, with ...
2
votes
2answers
1k 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?
14
votes
3answers
871 views

If the Minkowski sum of two convex closed sets is a Euclidean ball, then can the two sets be anything other than Euclidean balls?

If for two convex closed sets $S_1$ and $S_2$, the Minkowski sum is a Euclidean ball then can $S_1$ and $S_2$ be anything other than Euclidean balls themselves. I suspect they can be but I haven't ...
5
votes
2answers
257 views

Proving that $\text{ri rge}\,A=\text{ri conv rge}\,A$

"If $A:\mathbb R^n\rightrightarrows\mathbb R^n$ is maximal monotone,then $\text{ri rge}\,A$ is convex". This is a proposition in auslender's book about the asymptotic cones. We can prove that $$\text{...
5
votes
2answers
3k views

Why does a positive definite matrix defines a convex cone?

I've been working on convex optimization and got stuck. What exactly does a positive definite(p.d) matrix represent geometrically ? what kind of vector space it forms ? If I have a p.d matrix which ...
5
votes
1answer
1k views

A property of the minimum of a sum of convex functions

Let $g_1(x), \ldots, g_k(x)$ be convex functions from $\mathbb{R}^n$ to $\mathbb{R}$, and lets assume that global minimum of each $g_i$ is unique and is achieved, denoting $$x_i = \arg \min_{x \in \...
3
votes
0answers
111 views

If this problem is not unbounded, what's wrong in this dual derivation?

In a paper with 100 citation, Robust Support Vector Machine Training via Convex outlier Ablation, a convex relaxation is used. In this paper, a form of robust svm proposed: \begin{align} \min_{0\leq \...
3
votes
2answers
1k views

Recovering the solution of optimization problem from the dual problem

In the context of (most of the times convex) optimization problems - I understand that I can build a Lagrange dual problem and assuming I know there is strong duality (no gap) I can find the optimum ...
3
votes
2answers
105 views

Fourier coefficient of convex function

On $I = [0, 2π]$ consider the function $f : I → \mathbb{R}$ to be convex. Define: $$a_k\pi := \int_0^{2\pi}f(x) \cos(kx)\,dx$$ Show that the convexity of $f$ implies that $a_k ≥ 0$ when $k ≥ 1$. ...
2
votes
1answer
253 views

Proximal mapping of $f(U) = -\log \det(U)$

This is an assignment problem which I failed to solve in a couple of days. Denote the set of all $n \times n$ symmetric matrices and the set of all $n \times n$ symmetric positive definite matrices ...