Vectorize SDP Constraints

[Dan Molzahn]

Hello YALMIP users,

The "cone" function in YALMIP has the very useful ability to simultaneously define a set of second-order cone constraints (vectorized SOCP constraint definition). Is there a similar functionality for defining positive semidefinite matrix constraints? I am currently constructing a set of positive semidefinite matrix constraints within a for loop, but this is relatively slow.

Specifically, is there an alternative to

constraints = [];
for i=1:n
     constraints = [constraints; X{i} >= 0];
end

for a structure X where each element X{i} contains a matrix?

Thank you,
Dan

[Johan Löfberg]

No.

If you have some code for me to use as a performance test, I could take a look at it. Make sure you are running the latest version of YALMIP, as this case was improved upon recently.

[Johan Löfberg]

...and I might add such functionality. I think it would be pretty easy. I just have to think about how it should work.

[Johan Löfberg]

Hmm, I will have to see a specific example, because on my machine it takes 0.01 seconds to append 10000 5x5 constraints, which is nothing compared to the time it will take to solve the problem.

[Dan Molzahn]

I've looked into the issue a little more, and the slowness seems to be due to constructing the matrices rather than driven by constructing the constraints. I have a large sparse matrix, and I constrain submatrices from this large matrix to be positive semidefinite. In my actual code, I both index into the large matrix to construct the smaller matrices and add the positive semidefinite constraints to the smaller matrices in the same line of code. Splitting these operations up onto their own lines showed me that the indexing operation actually took over half of the time.

To make this more concrete, I can write the code in the form

constraints = [];
for i=1:n
     Y{i} = X(ind{i},ind{i});
     constraints = [constraints; Y{i} >= 0]
end

where X is a predefined large sparse matrix and ind is a structure containing the indices of the submatrices. The MATLAB profiler reveals that the first line in the for loop takes, in total, 0.3 seconds and the second line takes 0.2 seconds for a moderate-size instance of my problem. The optimization problem is solved in about 6 seconds, so setting up the positive semiefinite constraints takes about 8% of the total time. This certainly isn't terrible, but I'm trying to optimize my code as much as possible and this is the last place where I might be able to squeeze out better performance.

The code for building the matrices is somewhat involved, so I don't know if sending you more complex code is worth your time. What might be helpful is if you have some insight into the best way to construct submatrices from a large matrix. Is there a better way to do it than I have shown above?

Thank you,
Dan

[Johan Löfberg]

I doubt I can remove that overhead, but you are welcome to send me a test-case. Complexity is no problem, as long as it is self-contained and can be run without any guesswork from me