Skip to main content

Can youone maximize the spectral norm of a matrix in avia semidefinite programprogramming?

Consider the following optimization problem: 

Maximize $||X||$$\|X\|_2$, 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||$$\|X\|_2$ is the spectral norm of $X$, which is justi.e., the largest eigenvalue of $X$ by magnitude since (since $X$ is Hermitian).

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

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

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

Can one maximize the spectral norm of a matrix via semidefinite programming?

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

Source Link
Robin Kothari
  • 1.3k
  • 9
  • 16

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