What is the standard SDP form of this eigenvalue optimization?

Question

The following are two pictures in a lecture note:

I know how to formulate this problem into the second to last problem, but I am confused about how to write this problem into the standard SDP problem.

I have tried slack variable and diagonal matrix but they did not work. Could anyone tell me what is the standard form of SDP? Thanks in advance!

Answer 1

The short answer to your question is that the dual of the second to last problem is (more or less- see below) in the last form. The longer answer is to actually find the dual problem.

First, you should be aware that there is a lot of confusion about standard primal and dual forms of SDP. Different authors use different conventions for maximization/minimization and sometimes swap the primal and dual labels. It is possible to switch back and forth between the various conventions without too much trouble, but you need to be careful in doing this.

If your SDP primal problem is (as stated in your question)

$\min C \bullet X$

subject to

$A_{i} \bullet X= b_{i}$, $i=1, 2, \ldots, m$

$X \succeq 0$

then the dual of the SDP is:

$\max b^{T}y$

subject to

$C-A^{T}(y) \succeq 0$

where

$A^{T}(y)=y_{1}A_{1}+\ldots+y_{m}A_{m}$.

Your LMI problem is not quite in the proper dual form, but it is easy to manipulate it into the proper form.

Start with

$\min t$

subject to

$tI-x_{1}A_{1}-\ldots -x_{k}A_{k} \succeq 0$

Let $A_{k+1}=I$, and let $y=[x_{1}, x_{2}, \ldots, x_{k}, -t]$.

Your problem is now

$\min -y_{k+1}$

subject to

$0-A^{T}(y) \succeq 0$

or (after flipping the objective sign and max/min)

$\max b^{T}y$

subject to

$0-A^{T}(y) \succeq 0$

where

$b=[0, 0, \ldots, 0, 1]^{T}$.

The dual of this problem is

$\min C \bullet X$

$A_{i} \bullet X= b_{i}$, $i=1, 2, \ldots, k, k+1$

$X \succeq 0$

where $C=0$.

Assuming that strict duality holds, an optimal primal-dual solution will give you both $y$ and $X$.

You could also find the dual by writing down the Lagrangian and setting up the dual problem explicitly. The dual constraints are implicit in the objective function, but you can easily enough work them out.