# Spectral norm minimization via semidefinite programming

Given symmetric matrices $A_0, A_1, \dots, A_n \in \mathbb R^{m \times m}$, let $A(x) := A_0 + x_1 A_1 +\cdots + x_n A_n$. How to formulate the following unconstrained spectral minimization problem as a semidefinite program?

$$\min_{x \in \mathbb R^n} \|A(x)\|_2$$

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

• why is there suddenly a $\lambda_{min}$ Aug 26, 2018 at 9:42
• @SridharThiagarajan $$s^2 - \max \{ \lambda_1, \lambda_2, \dots, \lambda_m \} = \min \{ s^2 - \lambda_1, s^2 - \lambda_2, \dots, s^2 - \lambda_m \}$$ Would you agree? Aug 27, 2018 at 14:33