most recent 30 from http://mathoverflow.net 2013-05-22T13:18:33Z http://mathoverflow.net/feeds/question/110496 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/110496/can-you-maximize-the-spectral-norm-of-a-matrix-in-a-semidefinite-program Robin Kothari 2012-10-24T01:39:38Z 2012-10-24T02:01:19Z

<p>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.</p> <p>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.</p> <p>My question is whether this can be done for max $||X||$.</p>

http://mathoverflow.net/questions/110496/can-you-maximize-the-spectral-norm-of-a-matrix-in-a-semidefinite-program/110497#110497 Robert Israel 2012-10-24T02:01:19Z 2012-10-24T02:01:19Z

<p>No: maximizing the norm makes it a non-convex problem.</p>