Vtyjkyuk

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

Can anyone please help on this problem? Thanks!

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

$$beginarrayll textminimize & s\ textsubject to & | mathrm A (mathrm x) |_2 leq sendarray$$

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)

$$beginbmatrix s mathrm I_m & mathrm A (mathrm x)\ (mathrm A (mathrm x))^top & s mathrm I_mendbmatrix succeq mathrm O_2m$$

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

$$beginarrayll textminimize & s\ textsubject to & beginbmatrix s mathrm I_m & mathrm A (mathrm x)\ (mathrm A (mathrm x))^top & s mathrm I_mendbmatrix succeq mathrm O_2mendarray$$

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

$$beginarrayll textminimize & s\ textsubject to & -s mathrm I_m preceq mathrm A (mathrm x) preceq s mathrm I_mendarray$$

which can be rewritten as follows

$$beginarrayll textminimize & s\ textsubject to & beginbmatrix s mathrm I_m - mathrm A (mathrm x) & mathrm O_m\ mathrm O_m & s mathrm I_m + mathrm A (mathrm x)endbmatrix succeq mathrm O_2mendarray$$