Speedup CVX

I’ve been using Matlab to solve a MIMO filter optimization problem in the frequency domain using the standard least squares formula. I tried converting the code to use CVX, so I can use more advanced constraints, but I’m finding that it is MUCH slower.

The slowness seems to be caused by the overhead of the cvx_begin and cvx_end commands, because even if I comment out the “minimize” command, so it’s basically doing nothing, the code is still almost as slow. And the matrices I’m using are very small (5x2), so that shouldn’t be a problem. I also turned on quiet mode and set the precision to low, but that didn’t seem to make a big difference.

My original code is roughly as follows:

for n=1:16384
    b = bBuf(n);
    A = ABuf(n);
    
    x = ((A'*A)^-1)*A'*b;
    
    xBuf(n) = x;
end

As a test I converted this simple least squares example to use CVX. It works, but instead of taking a couple seconds to solve it now takes about an hour.

for n=1:16384
    b = bBuf(n);
    A = ABuf(n);
    
    cvx_begin
        variable x(2) complex;
        minimize(norm( A*x - b ));
    cvx_end
    
    xBuf(n) = x;
end

I’m wondering if there is a way to reformulate the code to minimize the overhead of calling cvx_begin and cvx_end thousands of times? Or is there some other way to optimize the processing time?

Thanks,
Chris

The least squares formulation uses a non-iterative linear systems algorithm. CVX, on the other hand, uses an interior-point method designed to solve a much wider variety of problems. A single iteration of that method is more expensive than the previous least-squares problem.

The point is: this is not a problem with CVX, but a reflection of simple practical reality: general purpose solvers are slower than specialized solvers. CVX is necessarily going to be slower for a given subclass of problems, like least squares or LPs, than an algorithm specifically designed for that subclass.

Of course, as you point out, once you start adding more advanced constraints, the ability to compare with least squares goes away.

As for your appeal to the use of “small” problems: that just makes things worse, not better. Using the modeling features of CVX incurs a fixed overhead, so it slows down smaller problems even more, on a percentage basis, than larger problems.

For just about any model, it will be possible to implement a custom solver, tailored for that very specific problem, that is significantly faster than CVX. Once you’re happy with the numerical results you’re getting, if you need to speed things up, you may consider writing your own algorithm.

By the way, ((A'*A)^-1)*A'*b is actually a very poor way to solve the least-squares problem. Just use A \ b instead, it will be faster and more accurate.

Thanks Michael, that’s very helpful. I don’t need CVX to be equivalently fast as a custom solver. For my needs maybe 10 to 100 times slower is acceptable, but I’m seeing about 1000 times slower. Any optimization you can do in future versions will definitely be appreciated, especially for this type.

Also, the formula I wrote is a bit simplified from what I’m actually doing. I’m using weighting and regularization.
x = (A’WeightA + Regularization)^-1 * (A’*Weight) * b;

Can this formula be written in the A\b form? Thanks!

CVX is as fast as it is likely to get in the forseeable future, Chris… Sounds like you may need to implement your own solver.

As for the least squares problem, the most important thing is to avoid ^-1, so do something like this: (A'*W*A+R)\(A'*W)*b. Yes it’s possible to write it without squaring up the A matrix, but it requires more information about W and R to determine that.

Dear all,
Hope you are doing well.

My cvx program is too slow when I increase N in my code below. How can I speed up this code?

              cvx_begin quiet 
              cvx_solver Mosek

                  variable Phi_eA(N,N) Hermitian ;
                  variable Phi_eB(N,N) Hermitian ;
                  maximize real(trace(C1_et* Phi_eA)) + real(trace(C1_er* Phi_eB)) ;
                  subject to

                  for i=1:N
                      AA(i) = Phi_eA(i,i);
                      BB(i) = Phi_eB(i,i);
                  end

                  AA + BB == ones(1,N); 
                  Phi_eA == hermitian_semidefinite(N);
                  Phi_eB == hermitian_semidefinite(N);
                  regularization_term = norm(Phi_eA - Phi_eB, 'fro');
                  regularization_term <= 10^-3; 
              cvx_end

Thanks

Run time can be broken down into CVX modeling time and solver time. In this case, I suspect solver time is what is making the program too slow.

Nevertheless, you can speed up model formulation time a little (maybe not noticeable, though) by replacing the for loop with the vectorized code:

AA = diag(Phi_eA);
BB = diag(Phi_eB);

As for solver time, solution of large SDPs can be computationally intensive and long running. Remove quiet, then post all the CVX and solver output for perhaps at least two different values of N (tell us what the values are). Then perhaps one of the Mosek people who read this forum can comment when they get a chance.

Note to OP: Please do not post the same item in more than one topic, let alone in 3 topics. As for CVXQUAD, that is only applicable and beneficial for exponential cone related functions (log, exp and variants); and is not beneficial if Mosek is used as solver. If using Mosek, the only value nowadays of CVXQUAD is for its matrix (quantum) log, entropy, and related functions which are not provided in CVX at all.

Thanks for your prompt reply!

The problem is about regularization constraints!
When I remove it, the solver is much faster than before!
I have no idea how I can define it in an efficient way!

Then show all the CVX and solver output with and without the regularization constraint. Perhaps 10^-3 is too tight?

Without regularization constraint:

Calling Mosek 10.1.25: 8192 variables, 64 equality constraints

MOSEK Version 10.1.25 (Build date: 2024-2-14 13:03:04)
Copyright (c) MOSEK ApS, Denmark WWW: mosek.com
Platform: MACOSX/aarch64

Problem
Name :
Objective sense : minimize
Type : CONIC (conic optimization problem)
Constraints : 64
Affine conic cons. : 0
Disjunctive cons. : 0
Cones : 0
Scalar variables : 0
Matrix variables : 2 (scalarized: 16512)
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - primal attempts : 1 successes : 1
Lin. dep. - dual attempts : 0 successes : 0
Lin. dep. - primal deps. : 0 dual deps. : 0
Presolve terminated. Time: 0.00
Optimizer - threads : 8
Optimizer - solved problem : the primal
Optimizer - Constraints : 64
Optimizer - Cones : 0
Optimizer - Scalar variables : 0 conic : 0
Optimizer - Semi-definite variables: 2 scalarized : 16512
Factor - setup time : 0.00
Factor - dense det. time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 2080 after factor : 2080
Factor - dense dim. : 0 flops : 2.05e+05
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 3.0e+00 1.6e+00 2.8e+00 0.00e+00 1.808834443e+00 0.000000000e+00 1.0e+00 0.01
1 7.5e-01 3.9e-01 1.4e+00 -4.55e-01 -2.204374333e+02 -2.197263906e+02 2.5e-01 0.02
2 1.7e-01 9.0e-02 1.8e-01 5.31e-01 -3.187016970e+02 -3.183270713e+02 5.7e-02 0.02
3 8.4e-02 4.4e-02 6.2e-02 1.02e+00 -3.221578513e+02 -3.219559479e+02 2.8e-02 0.03
4 3.7e-02 1.9e-02 1.9e-02 8.03e-01 -3.503811205e+02 -3.502623471e+02 1.2e-02 0.04
5 7.7e-03 4.0e-03 1.9e-03 9.02e-01 -3.688835871e+02 -3.688530579e+02 2.6e-03 0.04
6 1.0e-03 5.4e-04 9.7e-05 9.72e-01 -3.743281008e+02 -3.743237039e+02 3.4e-04 0.05
7 5.8e-05 3.0e-05 1.3e-06 9.96e-01 -3.750863946e+02 -3.750861462e+02 1.9e-05 0.06
8 6.6e-06 3.4e-06 5.0e-08 1.00e+00 -3.751240209e+02 -3.751239925e+02 2.2e-06 0.07
9 7.9e-07 4.1e-07 2.1e-09 1.00e+00 -3.751281046e+02 -3.751281012e+02 2.6e-07 0.07
10 9.5e-08 5.0e-08 8.7e-11 1.00e+00 -3.751285903e+02 -3.751285898e+02 3.2e-08 0.08
11 1.5e-08 8.1e-09 5.6e-12 1.00e+00 -3.751286510e+02 -3.751286510e+02 5.0e-09 0.09
12 1.8e-09 1.4e-08 2.2e-13 1.00e+00 -3.751286621e+02 -3.751286621e+02 5.9e-10 0.10
Optimizer terminated. Time: 0.10

Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -3.7512866210e+02 nrm: 1e+00 Viol. con: 1e-08 barvar: 0e+00
Dual. obj: -3.7512866209e+02 nrm: 2e+01 Viol. con: 0e+00 barvar: 8e-10
Optimizer summary
Optimizer - time: 0.10
Interior-point - iterations : 12 time: 0.10
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00

Status: Solved
Optimal value (cvx_optval): +383.88

With regularization constraint

Calling Mosek 10.1.25: 12290 variables, 4161 equality constraints

MOSEK Version 10.1.25 (Build date: 2024-2-14 13:03:04)
Copyright (c) MOSEK ApS, Denmark WWW: mosek.com
Platform: MACOSX/aarch64

Problem
Name :
Objective sense : minimize
Type : CONIC (conic optimization problem)
Constraints : 4161
Affine conic cons. : 0
Disjunctive cons. : 0
Cones : 1
Scalar variables : 4098
Matrix variables : 2 (scalarized: 16512)
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - primal attempts : 1 successes : 1
Lin. dep. - dual attempts : 0 successes : 0
Lin. dep. - primal deps. : 0 dual deps. : 0
Presolve terminated. Time: 0.00
GP based matrix reordering started.
GP based matrix reordering terminated.
Optimizer - threads : 8
Optimizer - solved problem : the primal
Optimizer - Constraints : 4160
Optimizer - Cones : 1
Optimizer - Scalar variables : 4097 conic : 4097
Optimizer - Semi-definite variables: 2 scalarized : 16512
Factor - setup time : 0.67
Factor - dense det. time : 0.31 GP order time : 0.00
Factor - nonzeros before factor : 8.65e+06 after factor : 8.65e+06
Factor - dense dim. : 0 flops : 2.44e+10
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 3.0e+00 1.8e+00 1.1e+01 0.00e+00 -1.228262601e+01 -1.000000000e-03 1.0e+00 0.69
1 1.6e+00 9.3e-01 7.3e+00 2.76e-02 -6.887374825e+01 -5.639138993e+01 5.2e-01 1.07
2 1.1e-01 6.8e-02 2.6e-01 3.26e-01 -1.823992254e+02 -1.806958591e+02 3.8e-02 1.49
3 3.3e-02 2.0e-02 4.0e-02 1.02e+00 -1.861808069e+02 -1.856864780e+02 1.1e-02 1.85
4 4.6e-03 2.7e-03 2.1e-03 9.65e-01 -1.919514408e+02 -1.918810844e+02 1.5e-03 2.20
5 1.1e-04 6.8e-05 7.7e-06 9.97e-01 -1.927576260e+02 -1.927559279e+02 3.8e-05 2.60
6 1.1e-05 6.8e-06 2.5e-07 1.01e+00 -1.927688119e+02 -1.927686395e+02 3.8e-06 3.01
7 1.8e-06 1.1e-06 1.7e-08 1.00e+00 -1.927709096e+02 -1.927708812e+02 6.2e-07 3.38
8 9.3e-08 5.6e-08 1.9e-10 1.00e+00 -1.927712946e+02 -1.927712932e+02 3.1e-08 3.76
9 1.2e-08 7.3e-09 9.2e-12 1.00e+00 -1.927713104e+02 -1.927713102e+02 4.1e-09 4.18
Optimizer terminated. Time: 4.18

Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -1.9277131036e+02 nrm: 1e+00 Viol. con: 4e-08 var: 0e+00 barvar: 0e+00 cones: 8e-09
Dual. obj: -1.9277131017e+02 nrm: 1e+01 Viol. con: 0e+00 var: 4e-12 barvar: 2e-08 cones: 0e+00
Optimizer summary
Optimizer - time: 4.18
Interior-point - iterations : 9 time: 4.18
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00

Status: Solved
Optimal value (cvx_optval): +197.632

Also, I tried for another tolerance and it made the solver even slower!

Introducing a regularization constraint may or may not make the optimizer slower. Most likely it will make it slower.

Thank you for your reply!
Indeed, regularization is the problem. I just define the regulation in another way.