3
$\begingroup$

Given $\mathrm A \in \mathbb R^{m \times n}$,

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \| \mathrm X \|_2 \leq 1\end{array}$$


Since $\| \mathrm X \|_2 \leq 1$ is equivalent to $\sigma_{\max} (\mathrm X ) \leq 1$, which is equivalent to $\lambda_{\max} (\mathrm X^\top \mathrm X) \leq 1$, we have

$$1 - \lambda_{\max} (\mathrm X^\top \mathrm X) = \lambda_{\min} (\mathrm I_n - \mathrm X^\top \mathrm X)\geq 0$$

and, thus,

$$\mathrm I_n - \mathrm X^\top \mathrm X \succeq \mathrm O_n$$

Using the Schur complement test for positive semidefiniteness, we obtain the following linear matrix inequality (LMI)

$$\begin{bmatrix} \mathrm I_m & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}$$

Hence, we have the following semidefinite program (SDP)

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A , \mathrm X \rangle\\ \text{subject to} & \begin{bmatrix} \mathrm I_m & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{m+n}\end{array}$$

Is this correct? Any feedback would be highly appreciated. Thank you.

$\endgroup$
  • 1
    $\begingroup$ You reformulate an inequality constraint. The equality constraint is not convex and can therefore not be cast as an LMI. $\endgroup$ – LinAlg Oct 11 '16 at 12:21
  • $\begingroup$ @LinAlg Would the equality constraint define the boundary of the spectrahedron defined by the LMI? $\endgroup$ – Rodrigo de Azevedo Oct 11 '16 at 12:25
  • $\begingroup$ Yes. The key here is the formula following "and, thus,". $\endgroup$ – LinAlg Oct 11 '16 at 12:30
  • 2
    $\begingroup$ $A=0$ is a nasty case which destroys a claim that it is correct, but the maximum in non-trivial case is attained at the border of the feasible set which means you can replace the equality with an inequality in this simple program $\endgroup$ – Johan Löfberg Oct 11 '16 at 13:10
  • 1
    $\begingroup$ Yes, it is correct and the standard approach to address this using semidefinite programming. $\endgroup$ – Johan Löfberg Oct 11 '16 at 13:28
7
$\begingroup$

This can be computed in closed-form via SVD. Indeed, given a matrix norm $\|.\|$ on $\mathbb C^{n,m}$, there is always a corresponding dual norm (i.e on the dual space $\mathbb C^{m,n}$) given by

$$\|A\|^{D} := \max_{\|X\| \le 1}\langle A, X\rangle_{\text{F}}, $$ where $\langle A, X\rangle_{\text{F}} := \text{trace}(AX^T)$ is the Frobenius / Hilbert-Schmidt inner product. In particular, it's not hard to show that $\|A\|_2^D = \|A\|_* := \sum_{k}\sigma_k(A)$, the nuclear norm of $A$.

$\endgroup$
  • 2
    $\begingroup$ Nice answer. Here's a question that asks to show the dual of the spectral norm is the nuclear norm: math.stackexchange.com/questions/1158798/… $\endgroup$ – littleO Oct 12 '16 at 8:25
  • $\begingroup$ Nice pointer. This bails me out of the debt of having to write that part of the solution. Also, the algebra therein contained is really instructive. $\endgroup$ – dohmatob Oct 12 '16 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.