# Week 6¶

## Exercise 1¶

Exercise

Let $$A\in \mathbb S^n$$, $$B\in\mathbb S^m$$ be symmetric matrices and let $$X\in \mathbb R^{n\times m}$$. We consider the symmetric block matrix

$\begin{split}M = \begin{pmatrix}A & X \\ X^\top &B\end{pmatrix}\end{split}$

### Exercise 1a)¶

Exercise

Show that if $$M\succ 0$$ then $$A\succ 0$$ and $$B\succ 0$$. Similarly, show that if $$M\succeq 0$$ then $$A\succeq 0$$ and $$B\succeq 0$$

Let $$u\in \mathbb R^n$$ and $$v\in \mathbb R^m$$. First assume $$u\neq 0$$ and $$v=0$$, then

$\begin{split}u^\top A u = \begin{pmatrix}u\\ v\end{pmatrix}^\top M \begin{pmatrix}u\\ v\end{pmatrix} >0\end{split}$

hence $$A\succ 0$$. Similarly picking $$u=0$$ and $$v\neq 0$$ shows $$B\succ 0$$.

The result for $$M \succeq 0$$ follows by replacing the $$>$$ above by $$\geq$$.

### Exercise 1b)¶

Exercise

Assuming $$B\succ 0$$, define the $$\textit{Schur complement}$$ $$S$$ of $$A$$ in $$M$$ by

$S := A-X B^{-1} X^\top$

Find a non-singular lower triangular matrix $$C$$ of form

$\begin{split}C = \begin{pmatrix}I_n & 0 \\ E & I_m\end{pmatrix}\end{split}$

such that

$\begin{split}C^\top M C = \begin{pmatrix}S & 0 \\ 0 &B\end{pmatrix}\end{split}$

Pick

$\begin{split}C = \begin{pmatrix}I_n&0 \\ -B^{-1}X^\top & I_m\end{pmatrix}\end{split}$

Then

\begin{split}\begin{align} C^\top M C &= \begin{pmatrix}I_n& E^\top \\ 0 & I_m\end{pmatrix} \begin{pmatrix}A & X \\ X^\top &B\end{pmatrix} \begin{pmatrix}I_n&0 \\ E^\top & I_m\end{pmatrix}\\ &= \begin{pmatrix}A +E^\top X^\top & X+E^\top B \\ X^\top &B\end{pmatrix} \begin{pmatrix}I_n&0 \\ E & I_m\end{pmatrix}\\ &= \begin{pmatrix}A+E^\top X^\top +XE+E^\top B E & X+E^\top B \\ X^\top + BE & B \end{pmatrix} \end{align}\end{split}

This gives that $$E = -B^{-1} X^\top$$ ($$B$$ is invertible since $$B\succ 0$$). The top left entry is then

\begin{split}\begin{align} A+E^\top X^\top + XE+E^\top BE &= A-X B^{-1} X^\top - XB^{-1}X^\top + XB^{-1}BB^{-1}X^\top \\ &= A-X B^{-1} X^\top\\ &=S \end{align}\end{split}

as required.

### Exercise 1c)¶

Exercise

Let $$A\in\mathbb S^n$$ be a symmetric matrix, and let $$X\in R^{n\times n}$$ be a non-singular matrix. Show that

$A\succ 0 \quad\Leftrightarrow \quad X^\top A X \succ 0$

Similarly also show that

$A\succeq 0 \quad\Leftrightarrow \quad X^\top A X \succeq 0$

Suppose $$A\succ 0$$ and let $$x\neq 0$$, then

$x^\top X^\top A X x = (X x)^\top A (X x) >0$

since $$Xx\neq 0$$ by the fact that $$X$$ is non-singular. Hence $$X^\top A X\succ 0$$.

Now suppose $$X^\top A X\succ 0$$ and let $$x\neq 0$$. Then define $$y = X^{-1}x$$. We have,

$x^\top A x = (Xy)^\top A Xy = y^\top(X^\top A X) y >0$

we conclude that $$A\succ 0$$.

The statement for $$A\succeq 0$$ has the same proof, replacing $$>$$ with $$\geq$$.

### Exercise 1d)¶

Exercise

Assume $$B\succ 0$$.

Prove that $$M\succ 0$$ if and only if $$S\succ 0$$.

Similarly, prove that $$M\succeq 0$$ if and only if $$S\succeq 0$$.

By c) we have that $$M\succ 0$$ if and only if $$C^\top M C\succ 0$$. If $$C^\top M C\succ 0$$ then $$S\succ 0$$ by a).

Similarly if $$S\succ 0$$ then $$C^\top M C\succ 0$$ since $$B\succ 0$$, and hence $$M\succ 0$$.

Again, the proof for $$M\succeq 0$$ is identical.

### Exercise 1e)¶

Exercise

Suppose $$M\succ 0$$. Using the results of a)-d), prove by induction that $$M$$ admits a decomposition

$M = L^\top D L$

where $$L$$ is non-singular and lower triangular, and $$D$$ is diagonal.

If $$M$$ is a $$1\times 1$$ matrix, the result is trivial. Assume the result holds if $$M$$ is an $$n\times n$$ matrix, and write it in block form:

$\begin{split}M = \begin{pmatrix}A & X \\ X^\top &B\end{pmatrix}\end{split}$

Then since $$M\succ 0$$, we have $$B\succ 0$$ (exercise 1a), hence we can use

$\begin{split}C^\top M C = \begin{pmatrix}S & 0 \\ 0 &B\end{pmatrix}\end{split}$

with $$C$$ as in 1b) lower-triangular and non-singular. By 1d) we have that $$S\succ 0$$, and both $$S$$ and $$B$$ are of size $$\leq n$$. By induction we can thus write

\begin{split}\begin{align} \begin{pmatrix}S & 0 \\ 0 &B\end{pmatrix} &= \begin{pmatrix}L_1^\top D_1 L_1 & 0 \\ 0 &L_2^\top D_2 L_2\end{pmatrix}\\ &=\begin{pmatrix}L_1 & 0\\ 0 & L_2\end{pmatrix}^\top\begin{pmatrix} D_1& 0 \\ 0 &D_2\end{pmatrix}\begin{pmatrix}L_1 & 0\\ 0 & L_2\end{pmatrix} \end{align}\end{split}

Then finally we have $$M = L^\top DL$$ with $$D = \operatorname{diag}(D_1,D_2)$$ and

$\begin{split}L = \begin{pmatrix}L_1 & 0\\ 0 & L_2\end{pmatrix}\begin{pmatrix}I_n&0 \\ -B^{-1}X^\top & I_m\end{pmatrix}.\end{split}$

## Exercise 2¶

Exercise

Recall that a semidefinite programming (SDP) problem is of form

$\min\left\{\langle C,\,X\rangle\mid X\in \mathbb S_+^n,\quad \langle A_i,\,X\rangle = b_i,\quad i=1,\dots, m\right\},$

where $$n,m\in \mathbb N$$, $$C,A_1,\dots, A_m\in \mathbb S^n$$ are symmetric matrices, $$X\in \mathbb S_+^n$$ is symmetric positive semidefinite, and $$b_i\in \mathbb R$$.

A linear programming problem (LP) is a problem of form

$\min\left\{\langle c,\,x\rangle\mid x\geq 0,\quad \langle a_i,\,x\rangle = b_i,\quad i=1,\dots,m\right\}$

with $$c,x,a_1,\dots,a_m\in \mathbb R^n$$ and $$b_1,\dots,b_m\in \mathbb R$$.

We will show that an LP is equivalent to an SDP with $$C=\operatorname{diag} c$$ and $$A_i=\operatorname{diag} a_i$$. We do this by showing that a solution to the LP problem also solves the associated SDP (and vice versa).

### Exercise 2a)¶

Exercise

1. Show that if $$x\in \mathbb R^n$$ is feasible for the LP, then $$X = \operatorname{diag} x \in \mathbb R^{n\times n}$$ is feasible for the SDP.

2. Show that if $$X\in \mathbb R^{n\times n}$$ is feasible for the SDP, then $$x = \operatorname{diag} X \in \mathbb R^{n}$$ is feasible for the LP.

1. Let $$x\in \mathbb R^n$$ be feasible for the LP. Then $$x\geq 0$$ implies that $$X = \operatorname{diag} x$$ is positive semidefinite. Furthermore note that since

$\langle \operatorname{diag} a_i, \operatorname{diag} x \rangle = \langle a_i, x \rangle = b_i$

we have that $$X$$ is feasible for the SDP.

1. Let $$X\in \mathbb R^{n\times n}$$ be feasible for the SDP. Then since $$X_{ii} = e_i^\top X e_i\geq 0$$, we have that $$\operatorname{diag} X \geq 0$$. By the same reason as above , we have that $$\langle a_i,\operatorname{diag} X \rangle = b_i$$, and $$x$$ is feasible for the LP.

### Exercise 2b)¶

Exercise

1. Show that if $$x\in \mathbb R^n$$ solves the LP, then $$X=\operatorname{diag} x$$ solves the SDP.

2. Show that if $$X\in \mathbb R^{n\times n}$$ solves the SDP, then $$x=\operatorname{diag} X$$ solves the LP.

1. Consider $$x$$ solving the LP and let $$X = \operatorname{diag} x$$. Then if $$X'$$ is any feasible point for the SDP, we have that $$\operatorname{diag} X'$$ is feasible for the LP. Note that therefore

$\langle \operatorname{diag} x,\operatorname{diag} c \rangle = \langle x,c \rangle \leq \langle \operatorname{diag} X' , c\rangle = \langle X' , \operatorname{diag} c\rangle$

where the inequality in the middle is because of optimality of $$x$$. We conclude that $$X$$ solves the SDP.

1. Consider $$X$$ solving the SDP and let $$x=\operatorname{diag} X$$. Then if $$x'$$ is any feasible point for the LP, we have that $$\operatorname{diag} x'$$ is feasible for the SDP. Then note that

$\langle x, c\rangle = \langle X, \operatorname{diag} c\rangle \leq \langle \operatorname{diag} x', \operatorname{diag} c\rangle = \langle x', c\rangle$

The inequality in the middle is again by optimality of $$X$$. This implies that $$x$$ solves the LP.

## Exercise 3¶

Exercise

Recall that a second-order cone program (SOCP) uses a constraint on the variable $$x\in \mathbb R^n$$ of form

$\| Dx+b\|_2 \leq c^\top x +d$

with $$D\in \mathbb R^{l\times n}$$, $$b \in \mathbb R^l$$, $$c\in \mathbb R^n$$ and $$d\in \mathbb R$$.

We will show that an SOCP constraint is a special case of an SDP constraint.

### Exercise 3a)¶

Exercise

Show that this constraint is equivalent to the constraint $$X(x)\succeq 0$$ with

$\begin{split}X(x) = \begin{pmatrix}c^\top x+ d & (Dx+b)^\top \\ Dx+b & (c^\top x +d)I_l \end{pmatrix}\end{split}$

Hint: compute the Schur complement of this block matrix, and use the result of 1d). Consider the case where $$c^\top x +d =0$$ and $$c^\top x+ d >0$$ seperately.

First of all $$X(x)\succeq$$ only if $$c^\top x+d\geq 0$$, which is also implied by the SOCP constraint.

Now suppose first of all that $$c^\top x+d = 0$$, then in particular the diagonal of $$X(x)$$ is zero, so $$X(x)\succeq 0$$ if and only if $$X(x)=0$$. This is because any princpial submatrix of a PSD matrix is PSD, this means in particular that the submatrix given by the first and $$(i+1)$$st column/roms is PSD, i.e.

$\begin{split}\begin{pmatrix}0 &(Dx+b)_i \\ (Dx+b)_i & 0\end{pmatrix} \succeq 0\end{split}$

which happens if and only if $$Dx+b=0$$, which is the SOCP constraint in this case.

Now assume $$c^\top x+d> 0$$. Then $$X(x)\succeq 0$$ if and only if $$S\succeq 0$$ with $$S$$ the Schur complement. The Schur complement is given by

$S = c^\top x+d - (Dx+b)^\top \left((c^\top x+d)I\right)^{-1}(Dx+b) = c^\top x+d - \frac{\|Dx+b\|^2}{c^\top x + b}$

Since $$S$$ is just a number, we have that $$S\succeq 0$$ if and only if

$(c^\top x +d)^2 \geq \|Dx+b\|^2$

which is equivalent to the SOCP constraint. Hence the SOCP constraint and the constraint $$X(x)\succeq 0$$ are equivalent.

### Exercise 3b)¶

Exercise

We will see later in the course that an SDP constraint is equivalent to a Linear matrix inequality (LMI) constraint. An LMI constraint is a constraint on $$x\in \mathbb R^n$$ is a constraint of form

$A_0 + \sum_i x_i A_i \succeq 0$

where $$A_i\in \mathbb S^n$$ are all symmetric matrices.

Show that the constraint $$X(x)\succeq 0$$ is an LMI.

Write $$D_i$$ the $$i$$th column of $$D$$. Then note that

$\begin{split}X(x) = \begin{pmatrix} d+\sum_i c_i x_i & b^\top + \sum_i D_i^\top x_i \\ b + \sum_i D_i x_i & \left(d+\sum_i c_i x_i\right)I \end{pmatrix}\end{split}$

Hence $$X(x)\succeq 0$$ is equivalent to the LMI with

$\begin{split}A_0 = \begin{pmatrix} d & b^\top \\ b & d I_l \end{pmatrix},\qquad A_i = \begin{pmatrix} c_i & D_i^\top \\ D_i & c_i I_l\end{pmatrix}\end{split}$

## Exercise 4¶

Exercise

Prove the following problems are convex optimization problems. In all these problems $$x\in\mathbb R$$ is a scalar variable.

### Exercise 4a)¶

Exercise

Let $$p,q$$ be posynomials. Prove the following problem is convex.

$\min_{x> 0}\max\{p(x),q(x)\}$

The problem is equivalent to the following GP:

$\begin{split}\begin{array}{ll} \text{Minimize} & t\\ \text{Subject to} & p(x) / t\leq 1 \\ & q(x) / t \leq 1 \end{array}\end{split}$

Any GP is in particular convex.

### Exercise 4b)¶

Exercise

Let $$p,q$$ be posynomials, and let $$r(x) = x^\alpha$$ for some $$\alpha\in \mathbb R$$. Prove the following problem is convex

$\begin{split}\begin{array}{ll} \text{Minimize} & \dfrac{p(x)}{r(x)-q(x)} \\ \text{Subject to} & r(x) > q(x) \end{array}\end{split}$

The problem is equivalent to

$\begin{split}\begin{array}{ll} \text{Minimize} & t\\ \text{Subject to} & p(x) \leq t(r(x)-q(x)) \end{array}\end{split}$

Since the left hand side of the inequality is strictly positive, this in particular implies $$r(x)>q(x)$$. This problem is then equivalent to the GP

$\begin{split}\begin{array}{ll} \text{Minimize} & t\\ \text{Subject to} & \dfrac{p(x)/t + q(x)}{r(x)} \leq 1 \end{array}\end{split}$

since any GP is in particular convex, we conclude that the problem is convex.

### Exercise 4c)¶

Exercise

Let $$p,q$$ be posynomials. Prove the following problem is convex

$\min_{x> 0} \exp(p(x)) + \exp(q(x))$

Hint: Consider the equivalent problem

$\begin{split}\begin{array}{ll} \text{Minimize} & \exp(t_1)+\exp(t_2)\\ \text{Subject to} & p(x) \leq t_1 \\ & q(x) \leq t_2 \end{array}\end{split}$

Then use the transformation $$x=e^y$$, and make use of the fact that $$p$$ and $$q$$ are posynomials to write the constraints as an inequalities involving log-sum-exp.

The problem is equivalent to the following:

$\begin{split}\begin{array}{ll} \text{Minimize} & \exp(t_1)+\exp(t_2)\\ \text{Subject to} & p(x) \leq t_1 \\ & q(x) \leq t_2 \end{array}\end{split}$

We do the transformation $$x = \exp(y)$$. Let $$p(x) = \sum_i a_i x^{\alpha_i}$$ and $$q(x) = \sum_i b_i x^{\beta_i}$$ then $$p(x) = \sum_i \exp(\alpha_i y+\log(a_i))$$, and $$q(x) = \sum_i\exp(\beta_i y+\log(b_i))$$. We then get equivalent the problem

$\begin{split}\begin{array}{ll} \text{Minimize} & \exp(t_1)+\exp(t_2) \\ \text{Subject to} & \sum_i \exp(\alpha_i y+\log(a_i)) \leq t_1 \\ & \sum_i \exp(\beta_i y+\log(b_i)) \leq t_2 \end{array}\end{split}$

Since the left hand sides are positive, we can we take $$\log$$ on both sides of the inequalities to get the problem below. We denote by $$\operatorname{lse}$$ the log-sum-exp function.

$\begin{split}\begin{array}{ll} \text{Minimize} & \exp(t_1)+\exp(t_2) \\ \text{Subject to} & \operatorname{lse}(\alpha y + \log(a)) - \log(t_1) \leq 0 \\ & \operatorname{lse}(\beta y + \log(b)) - \log(t_2) \leq 0 \end{array}\end{split}$

where $$\alpha,\beta,a,b$$ are the vectors given by the respective values $$\alpha_i,\beta_i,a_i,b_i$$. Since $$\exp$$, $$\operatorname{lse}$$ and $$-\log$$ are convex, this is a convex problem.