Convex Optimization problem with lots of matrix 2-norm constraints

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

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

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.

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.

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