Constraints in my SDP: $(X^TWX)_{ii} <= c$

1

Hey guys!

When solving my SDP, there are some problems encountered. So I come here for some solutions.

  1. Suppose my variable is X. One of my constraints goes like (X’WX)_{i,i} <= c, the i-th diagonal of the matrix X’WX with W given. But since X is to be determined, how can I write such constraints in CVX?

  2. Following the first question, I have k such constraints, that is, (X’WX)_{i,i} <= c, for i = 1,…,k. Should I go with a for-loop or writing each and every one of them inside CVX?

Thanks much!

2

Can we assume W is positive definite? Otherwise I doubt this is convex.

3

@mcg Yes, W is PD. More precisely, at very first iteration, W is PSD, then from 2nd iteration on, it becomes PD, assuming we can find such X.

4

What you need to do here is compute a square root W^{1/2} of W, then compute Y=W^{1/2}X. Once you do that, then you have
$$(X^TWX){ii} = (Y^TY){ii} = |Y_{:i}|2^2 = |W^{1/2} X{:i}|_2^2 $$
where X_{:i} denotes the $i$th column of X. So if Wsqrt is the variable that holds W^{1/2}, each of these quantities is just sum_square( Wsqrt * X(:,i) ).

And while you can indeed use a for loop, note that you can get all n elements of this with the command sum_square( Wsqrt * X ). This is a row vector, so if c is a column vector, you’ll need a transpose; i.e.

sum_square( Wsqrt * X ) <= c'
5

Thank you much, @mcg! That is quite helpful. I will try that and come back if there is any error. (Sorry I could not find the place to add comments to your answer, so I put it here)

6

Positive semidefinite will do, but that does make it a bit more difficult to compute the necessary square root. You’ll have to do a full eigenvalue decomposition instead of a Cholesky.