Expressing sum of largest eigenvalues as LMI

(Savyasachi Singh) #1

Minimizing r largest eigenvalues of A(x) can be solved by the program
minimize rt + Trace(X)
s.t. tI + X - A(x) >= 0
X >= 0
The variables are x(in R^k), t (in R) and X=X’ (in R^{pxp}).
This SDP can be expressed as LMI with 2p x 2p matrices. How do I express the constraints tI + X - A(x) >= 0 as a 2p x 2p matrix inequality.

Is the following constraint matrix correct
[ I X ]
[ X^T tI - A ]

I would appreciate if someone can give me a hint on the solution. Thanks

(Mark L. Stone) #2

Your problem statement refers to A(x), but you only show A. Please clarify. The code below is based on A being a symmetric matrix, not a matrix function of x.

Presuming X is p by p, so would be the LMIs tI + X - A >= 0 and X >= 0. Perhaps the 2p by 2p is based on putting both LMIs on the block diagonal of a single 2p by 2p LMI. But it is better to write them as separate p by p LMIs.

You can do

variable X(p,p) semidefinite
t*eye(p) + X - A == semidefinite(p)

or use sdp mode and write it as
t*eye(p) + X - A >= 0

Please read http://cvxr.com/cvx/doc/sdp.html

(Savyasachi Singh) #3

I forgot to define A(x) in my post. A(x) is a function of x in R^k
A(x) = A0 + x(1)*A1 + … + x(k)*Ak

So the dimensions of the SDP in my previous post is 1+k+p(p+1)/2 and the dimensions of the constraint matrices is 2p x 2p.

(Mark L. Stone) #4

Each of A0, A1, …, Ak must be the same dimension as X', i.e. p by p. SO the dimensions as as I wrote. Is there some relation between the elements ofxandX`? If so, you will want to take that into account. And if not, your problem seems peculiar.

(Savyasachi Singh) #5

I am trying to solve the problem of minimizing r largest eigenvalues of a p x p symmetric matrix A(x) as described in the following reference
L. Vandenberghe and S. Boyd, “SEMIDEFINITE PROGRAMMING,” SIAM Review,
vol. 38, no. 1, pp. 49, 1996.

There seems to be no relationship between x and X. The only constraint on X is that it is psd.

I am learning about SDP. So I am trying to solve different SDP problems in MATLAB. I am trying to express this problem as a 2p x 2p LMI as described by the author of the reference paper.

(Savyasachi Singh) #7

I think I have found the solution. The constraint can be expressed as a 2p x 2p block diagonal matrix
\begin{bmatrix} X & \mathbf{0} \\ \mathbf{0} & t\mathbf{I} + X - A(x) \end{bmatrix} is psd

(Mark L. Stone) #8

You might find it easier to read the subsequent book by the same authors https://web.stanford.edu/~boyd/cvxbook/ .

(Savyasachi Singh) #9

Great. Thanks for sharing the book.