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?
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!
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.