2
$\begingroup$

Consider the following optimization problem:

Maximize $\|X\|_2$, subject to $X$ being Hermitian (or symmetric) and a bunch of semidefinite constraints on $X$. Here, $\|X\|_2$ is the spectral norm of $X$, i.e., the largest eigenvalue of $X$ by magnitude (since $X$ is Hermitian).

Can this be written as a semidefinite program (SDP)?

Instead of maximizing $\|X\|_2$, if we minimized $\|X\|_2$, then this would be easy. We could add a new variable $t$ and minimize $t$ subject to $\|X\|_2 \leq t$ and the semidefinite constraints on $X$. Finally, $\|X\|_2 \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 when maximizing $\|X\|_2$.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Commented Oct 24, 2012 at 22:22
  • 1
    $\begingroup$ 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. $\endgroup$
    – Robert Israel
    Commented Oct 25, 2012 at 6:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .