Skip to main content
1 of 7

$$\begin{array}{ll} \text{minimize} & \| \mathrm X \mathrm a - \mathrm b \|_2 \\ \text{subject to} & \mathrm X \succeq \mathrm O_n\end{array}$$

Minimizing the squared $2$-norm instead, and writing in epigraph form, we obtain a minimization problem in $\rm X$ and $t$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \| \mathrm X \mathrm a - \mathrm b \|_2^2 - t \leq 0 \\ & \mathrm X \succeq \mathrm O_n\end{array}$$

Using the Schur complement, the inequality

$$\| \mathrm X \mathrm a - \mathrm b \|_2^2 - t = (\mathrm X \mathrm a - \mathrm b)^{\top} (\mathrm X \mathrm a - \mathrm b) - t \leq 0$$

can be written as the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm I_n & \mathrm X \mathrm a - \mathrm b\\ (\mathrm X \mathrm a - \mathrm b)^{\top} & t\end{bmatrix} \succeq \mathrm O_{n+1}$$

Thus, we have the following semidefinite program (SDP) in $\rm X$ and $t$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \begin{bmatrix} \mathrm I_n & \mathrm X \mathrm a - \mathrm b & \mathrm O_n\\ (\mathrm X \mathrm a - \mathrm b)^{\top} & t & 0_n^{\top}\\ \mathrm O_n & 0_n & \mathrm X\end{bmatrix} \succeq \mathrm O_{2n+1}\end{array}$$