Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
The following slides might be of interest to you: leo.technion.ac.il/DelRob11/talks/Henrion.pdf –  Markus Schweighofer Oct 24 '12 at 11:10
add comment

1 Answer

up vote 2 down vote accepted

No: maximizing the norm makes it a non-convex problem.

share|improve this answer
    
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 '12 at 22:22
1  
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 '12 at 6:48
    
Right, that makes sense. Thanks. –  Robin Kothari Oct 27 '12 at 3:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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