Tag Info

Hot answers tagged

2

No. The KKT point is $(x^*,\lambda^*)=(0,1)$. $\lambda=0$ is not dual feasible. The Lagrangian is $L(x,\lambda)=x-\lambda x$, and the dual problem is $$\begin{array}{ll} \text{maximize} & 0 \\ \text{subject to} & \lambda = 1 \\ & \lambda \geq 0 \end{array}$$ So clearly, $\lambda^*=1$ is the optimal dual point. It's actually not difficult to ...


2

Let us enter in the Karush–Kuhn–Tucker framework, with $$ f(x,y) = -\max(x,y);\\ g_1(x,y) = 2x+y-1;\\ g_2(x,y) = x+3y-1. $$ The Lagrangian is $$ L(x,y,\lambda) = -\max(x,y) + \lambda\cdot g(x,y) $$ and the solution is, in the region $x\neq y$ (where $L$ is smooth): $$ \begin{cases} 0&=&-1_{x>y} + 2\lambda_1 + \lambda_2 \\ ...


2

Hint:The probably your objective is either log-convex or log-quasi convex. My suggestion is to take $\log$ and then solve it. Note, that even by doing so your problem is non-convex because of $\|x\|=1$ (especially if $\|x\|=\|x\|_2$, then you can either relax the problem by converting the constraint $\|x\|=1$ to $\|x\|\leq 1$. If the relaxation is not ...


1

For general convex sets, the sorts of simple relationships you're suggesting don't exist. I find it helps to draw two dimensional pictures to see why. (Even if the space is dimension higher than 2, we could restrict the problems to the plane spanned by $x_1,x_2,x$ and none of the answers to your questions would change.) Here's an example of what can happen ...


1

The problem is affine, so we might as well assume the $T_i$ are the standard basis vectors: $T_i=e_i$. Then: \begin{align*} C(S) &= \left\{\lambda_0\cdot 0 + \sum_{i=1}^n\lambda_i e_i\;\colon\; \text{all $\lambda_i\ge 0$ and } \sum_{i=0}^n \lambda_i = 1 \right\} \\ &= \left\{\sum_{i=1}^n\lambda_i e_i \;\colon\; \text{all $\lambda_i\ge 0$ and } ...


1

I'm going to use the notation where a $t$ or $w$ subscript represents partial differentiation on that variable; e.g., $x_{tw}\triangleq \partial^2 x(t,w) / \partial t\partial w$. In order for $t$ to be the local minimum for fixed $w$, you must have $$2(x-c_x)x_t+2(y-c_y)y_t=0$$ This equation is satisfied for all $t_0(w)$. Differentiating implicitly I get ...


1

In general, the answer is no to both questions. Of course, you could always try a finite number of test points, including $x=0$, $x=c$, to see if they happen to satisfy $Ax=b$; and you can try the minimum-norm solution $x=A^T(AA^T)^{-1}b$, to see if it happens to satisfy $0\preceq x\preceq c$. If any of these tests hold, then you've found a closed form ...


1

Here's a perfect reference (PDF): "Interior-point method for nuclear norm approximation with application to system identification". One approach would be to convert the problem to a semidefinite program $$\begin{array}{ll} \text{minimize} & \frac{1}{2}\left(\mathop{\textrm{Tr}}(W_1)+\mathop{\textrm{Tr}}(W_2)\right) \\ \text{subject to} & ...


1

Some stuff can be said about the case $g(X,Z)=Z^TX=∑_iZ_iX_i$ where $AX\le b$. For a given value of $X$, if $\min_Z Z^TX$ is bounded, then the minimizing value of $Z$ will be one of the vertices of the simplex/polyhedron $AZ\le b$. The number of vertices is at most $K-1$, where $K$ is the number of constraints in $AZ\le b$. Thus in $(Z^*)^TX$, where $Z^* = ...


1

Example 3.10 of Boyd is already presenting you with a proof! Ok, let us revisit: what is eigenvalue of $X$? Given a vector $y$, if $$Xy = \lambda y \ldots (1)$$ then $\lambda$ is called the eigenvalue of X. Multiplying (1) by $y^{\top}$ we get, $$y^{\top}Xy = \lambda y^{\top}y = \lambda \|y\|^2$$ So, if we restrict ourselves to all $y$'s of norm $1$, then ...


1

The difference is that one condition is algebraic and one is geometric. both are needed to develop intuition of both kinds. The correct geometric condition, by the way, is that the epigraph of $f$ be convex, not the range. Consider, e.g. $f(x) = -|x|$ with a perfectly convex range $(-\infty,0]$ (but the function, of course, is concave, not convex). EDIT As ...


1

I'm sure the link @AC_MOSEK offers here will give you the instructions you need. I'm also fond of Optimization by Vector Space Methods by David Luenberger. It's a bit dated in some respects, but its treatment of Lagrange multipliers is particularly well suited for conic and semidefinite programming, in my view. But what the heck, I'll do it for you right ...


1

The statement is clearly false: just think about a vertex of a square! By the way, you guys got it wrong: by definition the empty set and a single point are convex set. The latter is indeed an affine set of dimension 0. A set $S$ is convex iff $$ \forall x,y \in S \Rightarrow \theta x + (1-\theta)y \in S, \quad \forall \theta \in [0,1]$$ an it doesn't ...


1

I'd say a projected gradient method is likely going to work well for a simple problem like that. That is, alternate between gradient steps $$X_+ = X - \alpha \nabla f(X)$$ and projection steps: $$X_{++} = \mathop{\text{arg}\,\text{min}}_{X\succeq 0} \|X-X_+\|_F$$ The projection is relatively simple: given a Schur decomposition $X_+=U\Sigma U^T$, then ...


1

The fact that dual to dual norm is equal to the original norm in case of finite-dimensional spaces is equivalent to the fact that the corresponding Banach space is reflexive. By James' theorem, a Banach space $B$ is reflexive if and only if every continuous linear functional on $B$ attains its maximum on the closed unit ball in $B$. That is surely true for ...


1

You can find such notation and how it relates with the one you are used to in the classic book Ben-Tal, Aharon, and Arkadi Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Vol. 2. Siam, 2001. or more in brief in http://docs.mosek.com/generic/modeling-a4.pdf You basically introduce variables so that ...



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