I have to express the following problem as a semidefinite program

$$\begin{array}{ll} \text{minimize} & F(x,y) := x + y +1\\ \text{subject to} & (x-1)^2+y^2 \leq 1 \tag{1}\end{array}$$

Only affine equality conditions should be used. The hint was to examine the structure of $\mathbb{S}^2_+$, the cone of symmetric positive semidefinite matrices.

The characteristic polynomial of such a matrix is

$$C=\lambda^2-(a_{11}+a_{22})\lambda - a_{12}a_{21}$$

which has a similar form to the rewritten condition (1) $x^2-2x+y^2\leq0$. If $a_{11}=a_{22}=1,\lambda = x$ and $a_{12}=-a_{21}=y$ the characteristic polynomial would be $x^2-2x+y^2=0$. Is this useful?

My problem is, that I have no clue how to formulate a $\leq$ with equality conditions.

  • $\begingroup$ I'm not sure what you mean with only equality conditions (surely you must have a positive semidefiniteness conditions). Hint: Schur complement $\endgroup$ – Johan Löfberg Nov 28 '14 at 19:28
  • $\begingroup$ I think what he is referring to is the standard practice of using slack variables to convert inequalities to equations. That is: $x+y\le z$ becomes $x+y+s=z$, $s$ nonnegative. $\endgroup$ – Michael Grant Nov 28 '14 at 23:33
  • $\begingroup$ In other words, he needs an SDP in primal, equality-constrained standard form. If I were not traveling I would answer it ;-) $\endgroup$ – Michael Grant Nov 29 '14 at 3:14

First of all, let's simplify a bit: $$(x-1)^2+y^2\leq 1 \quad\Longleftrightarrow\quad x^2-2x+1+y^2\leq 1 \quad\Longleftrightarrow\quad x^2+y^2\leq 2x$$ Note that this implies that $x\geq 0$, which makes sense since the original inequality describes a disc centered at $(1,0)$ with radius $1$. Let's go a bit further: add $2xy$ to both sides and rewrite: $$x^2+2xy+y^2\leq 2x+2xy \quad\Longleftrightarrow\quad (x+y)^2 \leq 2x(y+1)$$ Now we have the implication that $2x(y+1)\geq 0$, which combined with the previous gives us $y+1\geq 0$ or $y\geq -1$. Again, this follows from the geometry of the disc, but both of these facts are important for the next step.

Now let's look at the structure of a $2\times 2$ semidefinite cone. A matrix is positive semidefinite iff all of its principal minors are nonnegative. For the $2\times 2$ case, that simply means that the diagonal elements are nonnegative, and the determinant is nonnegative: $$\begin{bmatrix} z_{11} & z_{12} \\ z_{12} & z_{22} \end{bmatrix} \succeq 0 \quad\Longleftrightarrow\quad z_{11} \geq 0, ~ z_{12} \geq 0, ~ z_{11}z_{12} \geq z_{12}^2$$ Hmm, there is some familiar structure there. Let's do some substitution: $$\begin{bmatrix} 2x & x+y \\ x+y & y+1 \end{bmatrix} \succeq 0 \quad\Longleftrightarrow\quad 2x \geq 0, ~ y+1 \geq 0, ~ 2x(y+1) \geq (x+y)^2$$ Bingo! Now we can write out the solution by inspection. $$\begin{array}{ll} \text{minimize} & x + y + 1 \\ & \begin{bmatrix} z_{11} & z_{12} \\ z_{12} & z_{22} \end{bmatrix} \succeq 0 \\ & 2x = z_{11} \\ & x+y = z_{12} \\ & y+1 = z_{22} \end{array}$$ Another way to do it would be to eliminate $x$ and $y$ altogether, and recover them after the fact from the equations $x=z_{11}/2$, $y=z_{22}-1$: $$\begin{array}{ll} \text{minimize} & z_{11} / 2 + z_{22} \\ & \begin{bmatrix} z_{11} & z_{12} \\ z_{12} & z_{22} \end{bmatrix} \succeq 0 \\ & z_{11} / 2 - z_{12} + z_{22} = 1 \end{array}$$

  • $\begingroup$ I can follow your explanation to the point where you examine the structure of the cone. Could you please clarify how you obtain the assumptions that $z_{11} \leq 0$, $z_{12} \leq 0$ and $z_{11}z_{12} \leq z_{12}^2$ $\endgroup$ – tilman151 Nov 30 '14 at 9:40
  • $\begingroup$ Question edited to add the principal minors definition. $\endgroup$ – Michael Grant Nov 30 '14 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.