3 votes

Exchanging the sum and the min in double sum

There are really only two cases to consider, for linear functions $f(x)$: If $f(x) = 0$ is constant, clearly its minimum is $0$; If $f(x)$ is not the zero constant function, then its minimum does not ...
  • 46.8k
2 votes
Accepted

Proving the optimal values to minimize a function with a symmetric matrix?

Here's a complete answer of what I had in the comments. You are given a function \begin{equation} f(x) = \frac{1}{2}x^TAx + y^Tx + c, \end{equation} and an unconstrained minimization problem: \begin{...
  • 1,807
2 votes

Optimization problem on the inner product of two probability vectors

You can solve the problem via linear programming as follows. Introduce variable $r$ to represent the $k$th smallest $p_i p'_i$ and nonnegative variable $z_i$ to represent $\max(r-p_i p'_i,0)$. The ...
  • 36k
1 vote

Is the difference of two concave functions non-convex/non-concave?

$(-x^2)-(-x^4)$ is neither convex nor concave. $(-2x^2)-(-x^2)$ is concave. $(-x^2)-(-2x^2)$ is convex. $(-x^2)-(-x^2)$ is both.
  • 3,753
1 vote
Accepted

Reference for convex optimization

Sorry, such a reference doesn't exist, because the result isn't true. The method you're describing is known as "coordinate descent". In the Wikipedia page, there is an example showing how ...
  • 45.3k
1 vote

Why must all of the sublevel sets of a real, continuous function 𝑓 in Rn, where 𝑓(𝑥)→ +∞ as ‖𝑥‖→+∞, be compact?

A sublevel set $f^{-1}[(-\infty,c]]$ is closed since $f$ is continuous and $(-\infty,c]\subseteq\mathbb{R}$ is closed. The condition that $\lim\limits_{\lVert x\rVert\to\infty}f(x)=\infty$ enforces ...
  • 3,435
1 vote
Accepted

Is a perspective of a quasiconvex function still a quasiconvex function?

Not true. Let $f(x) = \sqrt{|x|}$. Its perspective is $$ g(x,t) = \sqrt{|x|}\sqrt t, $$ which is not quasiconvex as $$1=g(1,1) > \max (g(2,0),g(0,2)) = 0.$$
  • 43.4k
1 vote

Why do linear constraints always form a convex set?

If $Ax_1 = b, Ax_2 =b$ i.e $x_1,x_2$ belongs to the set then for $0<=k<=1$ $kAx_1 + (1-k)Ax_2 = kb + (1-k)b$ or $A(kx_1 + (1-k)x_2) = b$ i.e $kx_1 + (1-k)x_2 $ also belongs to the set. Therefore ...

Only top scored, non community-wiki answers of a minimum length are eligible