Express this linear optimization problem subject to a circular disk as a semidefinite program

Question

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.

Answer 1

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}$$