Cvx sdp mode and cell arrays


#1

Hi,
I am trying to solve a problem using an SDP relaxation. That involves having both an array of matrices (I basically just need to store k X_k, where X_k are 2D matrice) and a matrix of matrices defined. I am having problems declaring these as variables, as cvx accepts cell arrays only as dual variables. If I, instead, just use a 3D and a 4D matrix, I then don’t know how to impose for them to be symmetric (as I only need the X_k 2D matrices to be symmetric, not the whole structure).
Thanks.


#2

To the best of my knowledge, I’m not sure there’s a way of doing this elegantly inside CVX. (I’d be curious to know what problem you’re trying to solve.)

You can always add the constraint as follows

for k = 1:n,
    X(:,:,k) == X(:,:,k)';
end

This will manually constrain the matrices to be symmetric.

Although the notation appears to be elegant, I believe that if you declare a matrix variable to be symmetric, CVX makes sure to only store / use the upper triangular or lower triangular part. So this notation actually increases (roughly double) the number of variables that CVX will use. If these matrices are small enough, you should be fine, but just something to keep in mind.

Here’s a silly example to prove my point:

cvx_begin
    variable X(2,2) symmetric
    minimize norm(X,'fro')
    subject to
    X >= 1
cvx_end

The call to SeDuMi reads

Calling sedumi: 7 variables, 3 equality constraints

If you instead wrote

cvx_begin
    variable X(2,2)
    minimize norm(X,'fro')
    subject to
    X >= 1
    X == X'
cvx_end

the call to SeDuMi reads

Calling sedumi: 9 variables, 5 equality constraints

The 2 extra variables come up from having to treat the lower right (or upper right) variable explicitly.

Just use that for loop with caution.


Update: I just realized that you’re trying to solve an SDP. In that case, you can also write the for loop as

for k = 1:n,
    X(:,:,k) == semidefinite(m)
end

assuming that you also want X_k to be PSD.


Semidefinite Optimization with Linear Constraint
Variables and objective value zero:how to analyze the results from CVX (solver sdpt3)
(Michael C. Grant) #3

Actually, you can declare N-D arrays with symmetric structure. For instance,

variable X(4,4,10) symmetric

creates an 3-D array of 4x4 symmetric matrices. In general, the structure keywords apply to each of the 2-D slices of the N-D array. Then you can access each slice for further processing using array notation X(:,:,3), for instance.


#4

I didn’t know that! (Then again, I’ve not had to try this before.)


#5

Thanks for the answers! Echu, I’m modelling the pooling problem, or trying to!
I gave a try to the two approaches you suggested. Cvx does accept them, but when then it tries to solve the optimisation, it still returns infesible (which isn’t the case, it’s a small problem and I have modelled it before writing out explicitely all the X_k, in which case it solves it). It also complains that some inequalities are not symmetric, which it didn’t use to when I was declaring them explicitely.

I will try to play around with it a bit and see if I get anywhere!