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

learn more… | top users | synonyms

2
votes
1answer
34 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
0answers
77 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
6
votes
1answer
5k 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 ...
1
vote
2answers
3k 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 ...
3
votes
1answer
119 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|)$$
2
votes
1answer
131 views

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

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate? I have no idea how to start this. Anyone know any books with these kinds of questions (and ...
42
votes
4answers
5k 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 ...
19
votes
4answers
10k 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 ...
11
votes
5answers
2k 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: ...
4
votes
2answers
278 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 refernce to this paper [Olivier Chapelle, ...
3
votes
2answers
2k 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 ...
2
votes
1answer
156 views

Prove or disprove that the given expression is “always” positive

I have previously asked a question and I tried to solve it by my own and it led to the question below: Prove or disprove that ...
2
votes
1answer
260 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 ...
1
vote
0answers
71 views

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

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
27 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
0answers
34 views

can we prove that a certain supremum of affine functions is frechet differentiable or at least continuous?

Let $X$ be a Hilbert space. Let $A\colon \operatorname{dom} A\to X$ be linear operator with closed graph (not necessarily bounded). Define $$ g\colon \operatorname{dom}A\to \mathbb{R}:x\mapsto ...
1
vote
1answer
280 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
0answers
69 views

Linear Programming - Tableau Condition

The following tableau corresponds to an iteration of the simplex method: ...
0
votes
0answers
57 views

Fréchet normal cone

Given $x\in \Omega(\subset X)$ (X: Banach space) and $\varepsilon\geq 0$, the set of $\varepsilon-$normals to $\Omega$ at $x$ by \begin{align} \widehat N_\varepsilon(x;\Omega):=\left\{x^*\in X^*\mid ...
0
votes
2answers
55 views

To prove the existing and uniqueness of a solution

Let function $f$ be differentiable and convex in $R^{n}$. How can it be proved that $\forall \lambda > 0$ solution of system equations $f'(x) = -\lambda x$ exists exclusively ($\exists \hspace{3mm} ...
0
votes
1answer
74 views

How to solve this optimization problem?

Suppose I have the following problem: Maximize: $\quad\quad x_1+x_2+x_3+x_4$ Subject to: $\quad\quad \dfrac{\gamma\;a_1\;x_1}{\gamma\;a_2\;x_4+1}\geq1$, $\quad\quad\quad\quad\;\;\quad\quad ...
17
votes
1answer
774 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
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.
11
votes
5answers
1k 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 ...
5
votes
1answer
524 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 ...
3
votes
2answers
232 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 ...
2
votes
2answers
201 views

Optimize a log det function with respect to a matrix, and the saddle point analysis

Suppose I want to to find the local minima of a logdet function $\mathcal{L}$ with respect to a Matrix $\mathbf{A}$, $$ \mathcal{L} = \log\vert \mathbf{I} + \mathbf{A}\mathbf{S} \vert - ...
5
votes
3answers
533 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 ...
5
votes
1answer
6k 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 ...
3
votes
2answers
310 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 ...
10
votes
2answers
696 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 ...
4
votes
1answer
574 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
2answers
52 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$. ...
3
votes
1answer
86 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
376 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
616 views

When finding root, does Newton's method fail if the function is non-differentiable?

According to wikipedia's description, the Newton's method finding a root presumes a differentiable function. Then, will it fail when encountering non-differentiable function? For example, can it find ...
2
votes
1answer
52 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
2
votes
1answer
60 views

Hessian Related convex optimization question

My precise question is from an exercise; Let $f : \mathbb{R}^2 → \mathbb{R}$ be a twice differentiable function. Prove that there exists a $λ ∈ R$ such that $g : \mathbb{R}^2 → \mathbb{R}$ defined as ...
2
votes
1answer
65 views

normal cone to sublevel set

I came across the following interesting and important result: Let $f$ be a proper convex function and $\bar{x}$ be an interior point of ${\rm dom} f$. Denote the sublevel set $\{x:f(x)\leq ...
2
votes
3answers
129 views

Is this optimization problem solvable?

I have the following optimization problem: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~ \|\mathbf{y+Ax}\|_\infty \leq \beta\|\mathbf{y}\|_\infty ~~,~~ \|\mathbf{x}\|^2 \leq \alpha^2$$ where ...
2
votes
0answers
72 views

How to get the minimum and maximum of one convex function?

Condition: $h,f\in \mathbb{C}^{N\times1}, \text{where}f =\hat{f} + e \text{ and } e^H e \leq 1,\ \ \ Q=h^Hff^Hh$. The Lagrangian function of $Q$ is $\mathcal{L} = h^H(\hat{f} + e)(\hat{f} + e)^Hh + ...
1
vote
1answer
34 views

how to find the solution of this cost function?

I have the following cost function. $J = \sum_{i=1}^N a\, Trace(W^TX_iW) - b\, Trace(W^TY_iW)$ Where $X_i$ and $Y_i$ are symmetric matrices, $a$ and $b$ are scalars. How can I find W?
1
vote
2answers
67 views

Local optimality of a KKT point.

Consider the problem \begin{equation} \min_x f(x)~~~{\rm s.t.}~~~ g_i(x)\leq 0,~~i=1,\dots,I, \end{equation} where $x$ is the optimization parameter vector, $f(x)$ is the objective function and ...
1
vote
1answer
46 views

Dual Optimization Problem

I have the following optimization problem, $$ \text{minimize}_{X,Y} \ \lVert X\rVert_* + \lambda \lVert Y\rVert_1 \\ \text{subject to }X + Y = C$$ $C \in \mathcal{R}^{m \times n}$, $\lVert ...
1
vote
1answer
310 views

convexity of matrix “soft-max” (log trace of matrix exponential)

In convex optimization it is often convenient to use the following smooth approximation to $\max\{x_1, \ldots, x_n\}$: $$ f_\lambda(x_1, \ldots, x_n) = \frac{1}{\lambda}\log \sum_{i = 1}^n{e^{\lambda ...
1
vote
2answers
1k views

Explain `All polyhedrons are convex sets´

My teacher in course in Mat-2.3140 of Aalto University claims that 'All polyhedrons are convex sets' here. This premise was in a false-or-not-problem 'The feasible set of linear integer problem is ...
1
vote
1answer
128 views

Convex Combination of Hermitian Matrices

Assume all the matrices I discuss about are $N \times N$. Consider any two hermitian matrices $A_1$ and $A_2$ which are indefinite. The question is, In general, for any $A_1$ and $A_2$, does there ...
0
votes
1answer
198 views

a convex function on a 2 dimensional closed convex set

Let us say I have a closed compact convex set $\mathbb{S}$ on the 2-D plane (eg: a circle). Let any point $p$ in the 2-D plane be represented by $p=(x,y)$. I define the max function over 2-D plane ...
0
votes
1answer
122 views

Explain Complementary Slackness $\mu_i g_i(x^*)=0\forall i$

Wikipedia here explains it like this: I understand it so that either $\mu_i=0$ or $g_i=0$ but this answer here: "If μ1≠0 and μ2≠0, then x is one of the two points at the intersection of the two ...
6
votes
0answers
190 views

Optimization of relative entropy

Wondering if my following question is an application of information theory: Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream ...