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

learn more… | top users | synonyms

24
votes
4answers
2k 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 ...
17
votes
1answer
380 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 ...
10
votes
4answers
5k 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 ...
10
votes
2answers
523 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 ...
10
votes
5answers
708 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
1answer
344 views

invex functions and their usefulness?

An invex function $f$ is a differentiable function from $\Bbb R^n$ to $\Bbb R$ that for some function $\eta : \Bbb R^n \times \Bbb R^n \to \Bbb R^n$ satisfies for all $x, u$, $f(x) - f(u) \geq \eta(x, ...
10
votes
1answer
354 views

A (mathematically) sound investment strategy

It is common wisdom in the investment community that a long-term investor saving for his future would do well to invest in high-risk/high-return assets when he is young, slowly switching his portfolio ...
9
votes
2answers
275 views

On the convexity of element-wise norm 1 of the inverse

Let us define $\|A\|_1$ the element wise norm 1 of a matrix $A \in \mathbb{R}^{n \times m}$ as $$ \|A\|_1= \sum_{i,j} |A_{i,j}|. $$ Obviously, this function is convex over $\mathbb{R}^{n \times m}$. ...
8
votes
1answer
155 views

Stochastic gradient descent for convex optimization

What happens if a convex objective is optimized by stochastic gradient descent? Is a global solution achieved?
7
votes
2answers
980 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
2answers
106 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: ...
7
votes
1answer
150 views

How to understand convex duality intuitively

Is there an intuitive way to understand the convex duality? If the primal problem is minimization, the dual is maximization over another set of variables - but I would love to have a geometric ...
6
votes
4answers
653 views

Why is the affine hull of the unit circle $\mathbb R^2$?

In Boyd's "Convex Optimization" it defines the affine hull of a subset $C$ of $\mathbb R^n$ as $$\text{aff} C = \left\{\theta_1 x_1 + \ldots +\theta_k x_k \mid x_1, \ldots x_k \in C, \theta_1 + ...
6
votes
1answer
3k views

L1 norm and L2 norm

I was studying the Stephen Boyd's textbook on convex optimization. It says the following: The amplitude distribution of the optimal residual for the l1-norm approximation problem will tend to have ...
6
votes
1answer
96 views

Can we test whether a polynomial only takes non-negative values on the non-negative orthant?

EDIT: Feel free to replace "non-negative on the non-negative orthant" with "non-negative on a convex set, cone, or any other class of sets that includes the orthant". A popular way to establish that ...
6
votes
0answers
268 views

Is this question solvable? $2$ non-linear equations and the proof that the solution is unique (with asymmetric bounty option)

As mentioned in the title I want to show the uniqueness of the solution to $2$ non-linear equations. However, it seems that I can not solve this question with my current mathematical knowledge. More ...
6
votes
0answers
163 views

Subgradient of convex minimization duality

$$\min(f_0(x))$$ $$\text{s.t. }f_i(x) \le y_i \forall i, i = 1 ,\ldots, m$$ $$f_i : \text{convex};\quad x : \text{variable}$$ It is also considered that $g(y)$ is the optimal value of the problem ...
5
votes
3answers
919 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 ...
5
votes
1answer
2k 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 ...
5
votes
1answer
120 views

a conjecture on norms and convex functions over polytopes

Suppose one has a convex, bounded polytope P $\subset R^n$ and a strictly convex function $f$ defined everywhere on $R^n$. $f$ has a unique minimum; and suppose this minimum occurs somewhere strictly ...
5
votes
1answer
208 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 ...
5
votes
1answer
427 views

Minimizing l-infinity norm of complex vector

I have an $n$-dimensional complex vector space, and I want to minimize the $L_\infty$ norm of a point that is constrained to an $m$-dimensional affine subspace. That is, Given $\mathbf{z} \in ...
5
votes
0answers
141 views

Need advice: what should be my next step?

I am dealing with a quite algebraic question and I arrived at some good point. I had $2$ equations with $2$ unknowns and I was able to eleminate one of the variables. My final equation still seems ...
5
votes
0answers
162 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 ...
4
votes
2answers
171 views

Is the rising factorial function a convex function?

Let $(x)_p=x(x+1)\dots(x+p-1)$ be the rising factorial function. My question is: Is $(x)_p$ a convex function or not? And how to proof? And what is about the falling factorial function ...
4
votes
2answers
144 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 ...
4
votes
2answers
116 views

proving this inequality related to conjugate functions

For $x \in \mathbb{R}^n$ let us denote $x_{[i]}$ the $i$th largest component of $x$ s.t $$ x_{[1]} \geq x_{[2]} \geq x_{[3]}\ge\cdots $$ The function $$ f(x)= \sum_{i=1}^r x_{[i]} $$ is the sum of ...
4
votes
1answer
1k 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 ...
4
votes
1answer
865 views

How to prove this function is concave?

This is the function: $\displaystyle f(\vec x) = \log \frac{\exp(x_1)}{\sum_{i=1}^n \exp(x_i)} $
4
votes
3answers
1k views

Easy convex sets question

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 ...
4
votes
1answer
210 views

$L_1$ projection of sum of convex functions onto polytopes

Suppose I have a function $f(x) : \mathbb R^n \to \mathbb R$ that is the sum of a given strictly convex function $g : \mathbb R \to \mathbb R$ in a single variable, i.e. $f(x) = g(x_1) + g(x_2) + ...
4
votes
1answer
461 views

Solving a set of 3 nonlinear equations with constraints

Problem statement: I am given 3 sets of equations that govern the force $P$, and also the neutral axis, defined by two variables, the radius from the center $r$ and also the rotation degree in ...
4
votes
1answer
203 views

A conjecture of parallelogram inside convex and central symmetric curve

Assume Q is a convex central symmetric curve, whose area is $\displaystyle S$. The area of the maximum parallelogram inside Q is $\displaystyle S'$. How to prove the conjecture that $\displaystyle ...
4
votes
1answer
1k views

Proof of Hoeffding's inequality

The Hoeffding's inequality is $P(S_n - E[S_n] \geq \epsilon) \leq e^{-2\epsilon^2/k'}$, where $S_n = \sum_{i=1}^{n} X_i$, $X_i$'s are independent bounded random variables, and $k'$ depends on the ...
4
votes
2answers
112 views

Conjugates of norms

How would one find the conjugate of the following : $$f(x) = \|x\|^2 /2$$ The conjugate function is defined as $ f^*(y) = \max_x y^Tx - f(x)$ I am stuck at how I can derive the explicit form for ...
4
votes
1answer
777 views

Convexity of log det X???

In Boyd's book on convex optimization he proves convexity of log det X by proving it to be concave along a line i.e. he proves that the Hessian of the function $g(t) = f(Z+tV)$ is negative therefore ...
4
votes
3answers
648 views

Batch vs incremental gradient descent

I am studying Machine Learning, but I believe you guys should be able to help me with this! Basically, we have given a set of training data $\{(x_1,y_1), x(x_2,y_2), ..., (x_n, y_n)\}$, and we need ...
4
votes
0answers
143 views

Properties of the square norm in Banach spaces

Let $X$ be a Banach space with its dual $X^*$. Consider the mapping $f: X\rightarrow \mathbb{R}$ given by $$ f(x)=\frac{1}{2}\|x\|^2. $$ We have know that when $X$ is a real Hilbert space ($X=X^*$) ...
4
votes
0answers
90 views

On a version of gradient descent

I am trying to read this paper and have gotten stuck. The author considers the problem of minimizing a convex function whose gradient has coordinate-wise Lipschitz constant $M$ (meaning that for all ...
4
votes
0answers
77 views

Primal-Dual pair in SDP

Let's we have a primal model like $\max~~ x + Z $ $s.t. ~~~Ax + y I - Z \preceq B$ $~~~~~~~~~Z \succeq 0, ~X \geq 0, ~~y ~free$ where $A, B \in {\mathbb R^{n \times n}}$. The capital letters ...
4
votes
0answers
106 views

When can the optimal value of a SDP be achieved?

Looking at semidefinite programs, are there any sufficient conditions for the solvability (i.e. the optimal value can be achieved, that is infimum=minimum)? Obviously if the problem is unbounded, the ...
3
votes
3answers
783 views

Prove $ax - x\log(x)$ is convex?

How do you prove a function like $ax - x\log(x)$ is convex? The definition doesn't seem to work easily due to the non-linearity of the log function. Any ideas?
3
votes
4answers
1k views

Difference between Fritz John and Karush-Kuhn-Tucker conditions

I am a student of Computer Science and currently learning about optimization. We've been introduced to the Fritz-John and Karush-Kuhn-Tucker conditions for convex optimizations. I think I understand ...
3
votes
1answer
51 views

Prove that $e^{tx} \le xe^t + 1-x$

Prove that $$e^{tx} \le xe^t + 1-x$$ for $t \ge 1$ and $0 \le x \le 1$ I think I need to use the fact that e is convex? But I can't quite see it. Any help appreciated Thanks.
3
votes
2answers
633 views

What is an example of non-convex cone

I was studying Stephen Boyd's textbook on convex optimization. It says "A set C is called a cone or nonnegative homogeneous, if for every x $\in$ C, we have $\theta x \in $ C. A set C is a convex cone ...
3
votes
4answers
469 views

Summary of Optimization Methods.

Context: So in a lot of my self-studies, I come across ways to solve problems that involve optimization of some objective function. (I am coming from signal processing background). Anyway, I seem to ...
3
votes
1answer
117 views

Lower bound of a function

Given $x \geq y > 0$ and an integer $n$. We want to minimize the following term $\sum_{i=1}^n (x_i^2 - x_iy_i)$ over $(x_1,\ldots,x_n)$, $(y_1,\ldots,y_n)$ non-negative such that $\sum_{i=1}^n x_i ...
3
votes
2answers
206 views

Adding Elements to Diagonal of Symmetric Matrix to Ensure Positive Definiteness.

I have a symmetric matrix $A$, which has zeroes all along the diagonal i.e. $A_{ii}=0$. I cannot change the off diagonal elements of this matrix, I can only change the diagonal elements. I need this ...
3
votes
2answers
61 views

why is argmin $\|w\|^2$ equivalent to $\operatorname{argmax} 1/\|w\|$

I was wondering why the maximization of $1/\|w\|$ is equivalent to minimizing the squared norm of $w$. Shouldn't it be equivalent to just minimizing the norm of $w$? This is a very basic optimization ...
3
votes
2answers
372 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 ...