# Tag Info

## Hot answers tagged convex-optimization

4

As the Hessian is positive semidefinite (even if not invertible), the function remains convex (but maybe not strictly convex). A trivial example is $$X = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$ where $$|y - X'w|^2 = (y_1 - w_1)^2 + y_2^2$$ is a convex function, even if it is constant in the direction $\{ w_1 = const. \}$.

2

The process of minimizing $\mathcal{L}$ to construct the dual results in a formula for $\alpha$ as a function of $\beta$ and $\eta$. This is exactly the connection between the optimal primal and dual variables.

2

I assume you can prove, by definition, that $x^2$ is strictly convex. Now, you use this result twice: \begin{aligned} ((1-t)x + ty)^4 &= (((1 - t)x + ty)^2)^2 \\ &< ((1-t)x^2 + ty^2)^2 &\quad (x^2 \text{ is strictly convex})\\ &< (1-t)(x^2)^2 + t(y^2)^2 &\quad (x^2 \text { is strictly ... 2 Actually, from your relation, just apply "ri" to get\rm{ri\,conv\,rge}A=\rm{ri}(\rm{ri\,conv\,rge}A)\subset \rm{ri\,rge}A\subset\rm{ri\,conv\,rge}A,$$from which \rm{ri\,rge}A=\rm{ri\,conv\,rge}A is convex. 2 If you're going to apply multivariable calculus tools to the distance function, it's best to use the squared distance function:$$f(\omega)=\|x-\omega\|^2,\quad g(\omega)=\langle a,\omega\rangle$$The minimum is attained in the same place, but this f expands as inner product, allowing for simpler computations: \nabla f(\omega) = 2(\omega-x). So, the ... 2 Here is one proof of (\operatorname{aff} C - \operatorname{aff} C) \subset \operatorname{aff} (C - C). Note that S is affine iff S can be written as \{x_0\}+L for some linear space L. Let \operatorname{aff} C = \{x_0\} +L. Then \operatorname{aff} C - \operatorname{aff} C = \{x_0\} +L + \{-x_0\} +(-L) = L, hence \operatorname{aff} C - ... 2 Let C be a cone and let x \in C. Suppose x \neq 0. Then x is a convex combination of the points y_1 = \frac12 x and y_2 = \frac32 x, both of which belong to C. Explicitly, x = \frac12 y_1 + \frac12 y_2. This shows that x is not an extreme point of C. It follows that the origin is the only possible extreme point of C. (We don't ... 2 As a function of c, it is convex. As a function of \alpha, it is convex. But it is not jointly convex in \alpha and c. 2 For sure:$$ \sin x = \sin^+(x)+\sin^-(x) = \max(0,\sin x)+\min(0,\sin x) \tag{1}and now we just have to integrate twice the previous line to decompose \sin x as a sum of a convex and a concave function. 1 If x \mapsto f(x,t) is convex for each t, and \mu is a positive measure, then x \mapsto \int f(x,t) d\mu(t) is convex. It follows that convex combinations of convex functions are convex. Hence \alpha \to J(c,\alpha) is convex. In particular, since (\alpha,x) = ( \alpha c-I(x))^2u is convex for each x, then (\alpha,x) = \int_\Omega ( \alpha ... 1 For a convex optimization problem, the KKT conditions are sufficient for a point to be a global minimizer. And your optimization problem is convex when f is convex and g_1 and g_2 are affine. Consider the convex optimization problem \begin{align*} \text{minimize} & \quad f(x) \\ \text{subject to} & \quad Ax = b. \end{align*} Here f:\mathbb ... 1 A convex polygon can be given either by its vretices or, often more adequate, by inequalities a_ix+b_iy\ge c_i describing the half planes whose intersection is the polygon. With the latter form, a point of the plane is inside the polygon iff all iniequalities hold for its coordinates (or possibly on the boundary if we have equality in at least one of the ... 1 Geometric Intuition of Extreme Point: According to your definition of extreme point, geometric intuition of an extreme point in a convex are all corners. For example, in a triangle you extreme points are just the corners. However, in some other convex sets like disk (filled circle), extreme points are all the points on the border. Geometric Intuition of ... 1 We prove that if A and B are linear manifolds then A+B is also a linear manifold. Indeed, let x,y\in A+B and \lambda\in\mathbb{R}. Then there exist x_a,y_a\in A and x_b,y_b\in B such that x_a+x_b=x and y_a+y_b=y. Then \lambda x+(1-\lambda)y=\lambda(x_a+x_b)+(1-\lambda)(y_a+y_b)=[\lambda x_a+(1-\lambda)y_a]+[\lambda x_b+(1-\lambda)y_b]. ...

1

It's maybe a little too late, but as I had the same doubt, I decided to write an answer for future reference. The key is to understand that one supposes your solution is a vertex. If it is not one, is not too hard to find a vertex that is optimal starting from your optimal solution. I shall use the notation Oliver introduced in his comment to the other ...

1

Here is a rather tedious solution, I suspect a cleaner solution could be obtained using Michael's remark above, but it doesn't leap out at me at present. Let $f(x) = (\sum_k \lambda_k x_k )(\sum_k {1 \over \lambda_k} x_k)$, and $\Sigma = \{ x | x_k \ge 0, \sum_k x_k = 1 \}$. Since $\Sigma$ is compact and $f$ is continuous, we know the various extrema ...

1

Zonotope. (I have nothing more to say, but say more to satisfy the computer.)

1

You are not saying what constitutes too long in your case or what the dimensions are, but with a standard nonlinear solver such as ipopt, a random problem with $n=1000$ is solved in 0.2 seconds on an old laptop. I guess you could reduce that by a factor of 10 if you manually code a solver for this particular problem. Tested with this snippet of YALMIP code ...

1

The orthogonal projection of $D_\gamma$ onto any line is a connected, compact set with nonempty interior: thus, a closed interval of positive length. The endpoints of this interval correspond to supporting lines. The interior points of the interval correspond to lines $L$ such that $D_\gamma\setminus L$ is disconnected: since $D_\gamma$ is a topological ...

1

Simply specifying that a function is twice differentiable is not enough to guarantee a complexity rate. The best theoretical treatment of second-order methods---that is, methods that exploit both first- and second-derivative information---is probably by Yurii Nesterov and Arkadii Nemirovskii. Their work requires an assumption of self-concordance, which in ...

1

I assume $A$ is symmetric. Your dual manipulation is incorrect when $A$ does not have full rank. To see why, let's try to compute the dual function (using your notation): \begin{align} g(\eta, \beta) &= \sup_{\alpha \in \mathbb{R}^k} [-c\alpha^TA\alpha + d^T\alpha+\eta^T(\alpha + p) - \beta^T(\alpha -r)] \\ &= \sup_{\alpha \in \mathbb{R}^k} ...

1

No, it is not symmetric unless $X$ is a Hilbert space. In the conjectural formula $$\langle x, j(y)\rangle = \langle y, j(x)\rangle\quad (?)$$ the left hand side is linear in $x$, but the right hand side is not, unless $j$ is a linear map. Concrete example: in $\ell^4$, the duality map $j:\ell^4\to \ell^{4/3}$ is $$j(x) = (x_1^3,x_2^3,x_3^3,\dots)$$ ...

1

There are many methods. Here I will suggest one - formulating it as a sum of two non-smooth functions with (relatively) easily computable proximal operators. Then, you can use any method for optimizing a sum of two non-smooth functions, such as Douglas-Rachford. You can re-formulate it as: $$\min_{x,y} ||y||_{\infty} \quad \mathrm{s. t.} ~ Bx = c, y = Ax ... 1 Assuming 0\leq \lambda \leq 1,$$||\lambda x_1 + (1-\lambda)x_2 - y|| = ||\lambda x_1 + (1-\lambda)x_2 - (\lambda + (1-\lambda))y||\leq ||\lambda x_1 - \lambda y|| + ||(1-\lambda)x_2 - (1-\lambda)y|| = \lambda||x_1 - y|| + (1-\lambda)||x_2 - y|| = \lambda||x_1 - y|| + (1-\lambda)||x_1 - y|| = ||x_1 - y||1 Take C=\{(a_n )_{n\in\mathbb{N}} \in \ell_{\infty} :\forall_{j\in\mathbb{N}}\hspace{0.5cm} 0\leqslant a_j \leqslant j\}. Then \mbox{recc} (C)=\{0\} but C is unbounded. 1 Unfortunately, determining a solution with the smallest number of non-zeros is intractable. It can be expressed as the following binary linear program: \begin{array}{ll} \text{minimize}_{x,y} & \sum_i y_i \\ \text{subject to} & A x = b \\ & 0 \leq x \leq M y \\ & y \in \{0,1\}^n \end{array} where M is a ... 1 This doesn't directly answer your question, but here is a different algorithm you could possibly use to solve the optimization problem \begin{align} \text{minimize} & \quad \frac12 x^T A x + b^T x \\ \text{subect to} & \quad y^T x = 0 \\ & \quad 0 \leq x \leq c \end{align} where the matrix A is symmetric positive semidefinite. Let U = \{x ... 1 Let \mathcal{Q}^{n_i}\subseteq\mathbb{R}^{n_i}\times\mathbb{R} be the second-order cone of dimension n_i+1. Then using your notation, we have c=f, Q=F, r=g, andM=-\begin{bmatrix} A_1 \\ c_1 \\ A_2 \\ c_2 \\ \vdots \\ A_m \\ c_m \end{bmatrix} \quad p=-\begin{bmatrix} b_1 \\ d_1 \\ b_2 \\ d_2 \\ \vdots \\ b_m \\ d_m \end{bmatrix} \quad K = ...

1

(I know this question is ancient, but I happened to run into it while looking for something else.) While I am not sure if $S_{n,k}$ is concave on the probability simplex, you can prove the result you want and many other similar useful things using Schur concavity. A sketch follows. A vector $y\in \mathbb{R}_+^n$ majorizes $x \in \mathbb{R}_+^n$ if the ...

1

I assume you mean the constraint $x^T Px + 2c^Tx + s \leq 0$. For intuition on the difficulty of this constraint, let us assume we also have constraints $x_i \in [0,1]$ for all $i \in\{1, \ldots, n\}$. Now consider your single constraint in the special case $P=-I$, $c=(1/2, \ldots, 1/2)$, $s=0$: $$-x^Tx + 1^Tx \leq 0$$ This is equivalent to saying: ...

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