Convex Optimization problem with lots of matrix 2-norm constraints

1

Hi all,

I’m formulating a convex optimization problem using CVX that involves numerous matrix 2-norm constraints (let’s say thousands or more), which consumes significant time during problem initialization.

To illustrate, here’s a simplified code example:

cvx_begin
	variable X(100,100)

	minimize norm(X,1)

	subject to

	for i = 1:50
        norm(X(2*i-1:2*i, :), 2) <= 2;
	end
cvx_end

As shown, the constraints require calculating 2-norms for every pair of rows in decision matrix X using a for-loop. This initialization process is time-consuming and takes much more time compared to the problem-solving phase. Given that my actual problem involves larger scales and far more constraints, accelerating this loop is crucial.

I attempted using the Parallel Toolbox with ‘parfor’, but encountered compatibility issues with CVX variables(which has been proved in some other posts). Additionally, while vector 2-norm constraints can utilize the ‘norms’ function for vectorized calculation, there appears to be no equivalent vectorized-based method for matrix 2-norms.

Has anyone encountered similar challenges or have suggestions for optimizing this constraint initialization process?

Thanks in advance!

Yizheng

2

To the best of my knowledge you cannot use parfor or any other parallel construct while building the model.

3

Thank you, Erling! I think you are right, that parallel construct are not appropriate. Still wondering if there’s any vectorized method that can accelerate the calculation.

4

The model of each spectral 2-norm constraint requires a new semidefinite matrix variable. Even if you introduce a thousand of those by hand in the best possible vectorized fashion, for instance

variable U(102,102,1000) semidefinite

then already this is slow, so I can’t see if there could be any better prospects for your full more complicated model. Maybe some other tool can do it better, or the native interface of a solver.

5

Hi Michal, thank you for your suggestion. I guess i’ll have to try some other tool, otherwise i must endure the computational inefficiency :cry: