Spectral norm minimization via semidefinite programming

Solution 1:

Introducing variable $s > 0$ and rewriting the minimization problem in epigraph form,

$$\begin{array}{ll} \text{minimize} & s\\ \text{subject to} & \| \mathrm A (\mathrm x) \|_2 \leq s\end{array}$$

Note that $\| \mathrm A (\mathrm x) \|_2 \leq s$ is equivalent to $\sigma_{\max} \left( \mathrm A (\mathrm x) \right) \leq s$, which is equivalent to

$$\lambda_{\max} \left( (\mathrm A (\mathrm x))^{\top} \mathrm A (\mathrm x) \right) \leq s^2$$

Hence,

$$s^2 - \lambda_{\max} \left( (\mathrm A (\mathrm x))^{\top} \mathrm A (\mathrm x) \right) = \lambda_{\min} \left( s^2 \mathrm I_m - (\mathrm A (\mathrm x))^{\top} \mathrm A (\mathrm x) \right) \geq 0$$

and, thus, we obtain

$$s^2 \mathrm I_m - (\mathrm A (\mathrm x))^{\top} \mathrm A (\mathrm x) \succeq \mathrm O_m$$

Dividing both sides by $s > 0$,

$$s \mathrm I_m - (\mathrm A (\mathrm x))^{\top} \left( s \mathrm I_m \right)^{-1} \mathrm A (\mathrm x) \succeq \mathrm O_m$$

Using the Schur complement test for positive semidefiniteness, the inequality above can be rewritten as the following linear matrix inequality (LMI)

$$\begin{bmatrix} s \mathrm I_m & \mathrm A (\mathrm x)\\ (\mathrm A (\mathrm x))^{\top} & s \mathrm I_m\end{bmatrix} \succeq \mathrm O_{2m}$$

Thus, we obtain the following semidefinite program (SDP) in $\mathrm x \in \mathbb R^n$ and $s > 0$

$$\begin{array}{ll} \text{minimize} & s\\ \text{subject to} & \begin{bmatrix} s \mathrm I_m & \mathrm A (\mathrm x)\\ (\mathrm A (\mathrm x))^{\top} & s \mathrm I_m\end{bmatrix} \succeq \mathrm O_{2m}\end{array}$$

Alternatively, since $\mathrm A (\mathrm x)$ is symmetric for all $\mathrm x \in \mathbb R^n$, we can use the following SDP

$$\begin{array}{ll} \text{minimize} & s\\ \text{subject to} & -s \mathrm I_m \preceq \mathrm A (\mathrm x) \preceq s \mathrm I_m\end{array}$$

which can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & s\\ \text{subject to} & \begin{bmatrix} s \mathrm I_m - \mathrm A (\mathrm x) & \mathrm O_{m}\\ \mathrm O_{m} & s \mathrm I_m + \mathrm A (\mathrm x)\end{bmatrix} \succeq \mathrm O_{2m}\end{array}$$