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

$\endgroup$
1
3
$\begingroup$

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

$\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 Oct 24 '12 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 Oct 25 '12 at 6:48

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.