I am doing convex optimization in a simulation that now takes 1.5 days to run, whereas before the convex stuff was added, it’d take less than an hour. Further, this is an abbreviated simulation. The full-up simulation will be 200 times longer, so 1 year doing the math… cannot do.
Ways to speed this up? I am running the following code:
%%%%%%%%%%%%%%
cvx_begin
cvx_precision low % Still extremely accurate, precision is [?^3/8 ?^1/4 ?^1/4], ?=2.22×10^?16 is the machine precision
variable bulkSubset(nTxRf)
objective = 0;
for ff = 1:size(H,3)
%objective = objective + log_det(eye(nTxRf) + (1/(actTx*invRho))*H(:,:,ii)*diag(bulkSubset)H(:,:,ii)’)
%hPrime = obj.getHPrime(ABF,H(:,:,ff));
if(~isempty(ABF))
tabf = transpose(ABF);
for i = 1:size(tabf,2)
tabf(:,i) = tabf(:,i)/norm(tabf(:,i));
end
hPrime = H(:,:,ff) * tabf;
else
hPrime = H(:,:,ff);
end
%objective = objective + log_det(eye(nMsAnt) + (1/(actTxinvRho))hPrimediag(bulkSubset)*hPrime’);
objective = objective + log_det(eye(nMsAnt) + (1/dlNoise)hPrimediag(bulkSubset)hPrime’);
end
maximize( objective )
subject to
lb <= bulkSubset <= ub
%bulkSubsetones(nTxRf,1) == actTx
sum(bulkSubset) == actTx
cvx_end
%%%%%%%%%%%%%%
Obviously, changing anything changes the underlying problem I am solving… but what to poke at that will change the optimization the most? Or approximations of note? or ??
Here’s a run-time note I get from cvx:
%%%%%%%%%%%%%
Successive approximation method to be employed.
For improved efficiency, SDPT3 is solving the dual problem.
SDPT3 will be called several times to refine the solution.
Original size: 28593 variables, 7728 equality constraints
16 exponentials add 128 variables, 80 equality constraints
%%%%%%%%
Which solver are you using? Try Mosek if you can. When using CVXQUAD, Mosek and Gurobi might be the fastest solvers.
Also, once you get CVXQUAD up and running, you couldl experiment with the Pade Approximation parameters, m and k, and determine whether you can use smaller values to get a speedup without degrading the solution accuracy beyond acceptable limits. In or4der to understand how these parameters work, you should carefully read “Semidenite approximations of the matrix logarithm” by CVXQUAD authors Hamza Fawzi, James Saunderson, Pablo A. Parrilo . https://arxiv.org/abs/1705.00812 . Note that the “matrix” dimension n, as used in that paper, is 1 for this problem.
Am back on this problem… things have evolved a bit. In brief, I get things to simulate fine, but need orders of magnitude improvement to make things implementable in real-time. Using CVXQUAD seems to be a healthy “tweak”, but not a restructuring of my problem.
I’m aware of the CVXGEN project, that applies to quadradic problems, which is not me… but am wanting this kind of idea… something that exploits the structure of my problem for greatly reduced complexity.
My problem has evolved from what I stated earlier, simplified a bit, but still sum of logs.
Please advise?
In my previous post, I suggested you consider experimenting with the CVXQUAD Pade Approximation parameters, m and k `` - please re-read the last paragraph of that post.
The other things I can think of are
Try Gurobi
or
Request Mosek people to provide you with Mosek 9.0 beta, which might perhaps be faster than Mosek 8.1. I don;t know whether you will encounter any difficulties installing and using Mosek 9.0 beta under CVX 2.1 - I don’'t recall hearing of anyone trying to do that yet.
CVX was not designed for speed. If you have real-time requirements which can not be achieved by CVX, then use something else. What that something else should be is out of scope of this forum.
I have no idea whether it can be successfully installed or used under CVX 2.1 (or CVX 3.0 beta, which I don’t recommend).
Even though Mosek 9.0 Beta has native support for the exponential cone, CVX will not (currently, and for all I know, ever) use that native support for the exponential cone under Mosek 9.0 Beta. So that means that id you do use Mosek 9.0 Beta under CVX, you should still use CVXQUAD. CVX 3.0 beta does use the native support for the exponential cone under SCS and ECOS, but CVX 3.0beta is so riddled with serious bugs, that I don’t recommend it.
If you try to install and use Mosek 9.0 beta under CVX, please report your excperience.
I do not know if CVX will be able to work with MOSEK v9.
For sure CVX will not exploit the new power and exponential cone stuff until @mcg do some work to support it in CVX.
MOSEK v9 is unlikely to be faster for log(det(matrix)) stuff. Since the SDP part of Mosek is not (much) faster in v9. Note Mosek cannot deal with log(det(matrix)) natively.
Replace log_det(cvx_expression) >= t where cvx_expression is an n by n matrix
with
variable u
-rel_entr(1,u) >= t/n
det_rootn(cvx_expression) >= u
+++++
Replace log_det(cvx_expression) , where cvx_expression is an n by n matrix
with z
and add
variables u z % this line must be before u or z are used
-rel_entr(1,u) >= z/n
det_rootn(cvx_expression) >= u
+++++
Note: A simpler to write reformulation (NOT RECOMMENDED) can be used:
Replace log_det(cvx_expression)
with -quantum_rel_entr(eye(size(cvx_expression)),cvx_expression)
However, as discussed below, use of quantum_rel_entr is computationally demanding. Formulation using quantum_rel_entr consumes much more computational resources than that used by preceding formulations.
CVXQUAD actually formulates 2 by 2 LMIs for the above (scalar) cases, and these are sent to the solver (Mosek) by CVX as SOCPs. As described in my linked write up, CVXQUAD only sends LMIs (SDPs) to the solver when Quantum (Matrix) Entropy and Matrix Logarithm related functions, such as quantum_rel_entr, are used.
I am really excited about the exponential cone support. I can’t make any promises here but I really am going to try and find the time to make v9 and CVX 2.1 play nice. (It would be easier in 3.0beta but there are other bugs there I’m not confident I will be able to fix soon.)
@mcg Can you extract the native exponential cone support for SCS and ECOS from CVX 3.0btea, add native exponential cone support for Mosek 9.0, and release it as CVX 2.2 ?
I.e. my proposed CVX 2.2 = CVX 2.1 + native exponential cone support for SCS, ECOS, Mosek 9.
Hi! I have tried MOSEK 7.0 and CVXQUAD seperately and also together. Neither will speed up CVX programming with log. I guess no way can speed up this if there is no native log support.
If you are referring to all the Pade Approximation messages, not that I know of. I suspect it shouldn’t be difficult to modify the CVQUAD source code, which is written in MATLAB, to do that.
cvx_begin quiet should work with CVXQUAD the same as without to not show any solver or CVX output.
