## Can you maximize the spectral norm of a matrix in a semidefinite program?

Consider the following optimization problem: Maximize $||X||$, subject to $X$ being Hermitian (or symmetric, if you prefer) and a bunch of semidefinite constraints on $X$. I want to know if this can be written as a semidefinite program (SDP). Here, $||X||$ is the spectral norm of $X$, which is just the largest eigenvalue of $X$ by magnitude since $X$ is Hermitian.

Instead of maximize $||X||$, if we had minimize $||X||$, then this would be easy. We could add a new variable $t$ and minimize $t$ subject to $||X|| \leq t$ and the semidefinite constraints on $X$. Finally, $||X|| \leq t$ can be written as the constraint $-tI \preceq X \preceq tI$, which makes this a valid SDP.

My question is whether this can be done for max $||X||$.

-
 The following slides might be of interest to you: leo.technion.ac.il/DelRob11/talks/Henrion.pdf – Markus Schweighofer Oct 24 at 11:10

 Thanks. But does that rule out the possibility that introducing new variables and changing variables will make it an SDP? For example, geometric programming (en.wikipedia.org/wiki/Geometric_programming) is in general non-convex, but a change of variables makes it convex. – Robin Kothari Oct 24 at 22:22 For example, suppose linear constraints leave you a one-dimensional feasible region, e.g. $\pmatrix{1 & t\cr t & 1\cr}$ which is positive semidefinite for $-1 \le t \le 1$. The maximum norm is $2$, attained at $t=-1$ and $t=1$. No one-to-one change of variables will make a two-point set into a convex set. – Robert Israel Oct 25 at 6:48 Right, that makes sense. Thanks. – Robin Kothari Oct 27 at 3:07