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_precision low % Still extremely accurate, precision is [?^3/8 ?^1/4 ?^1/4], ?=2.22×10^?16 is the machine precision
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));
tabf = transpose(ABF);
for i = 1:size(tabf,2)
tabf(:,i) = tabf(:,i)/norm(tabf(:,i));
hPrime = H(:,:,ff) * tabf;
hPrime = H(:,:,ff);
%objective = objective + log_det(eye(nMsAnt) + (1/(actTxinvRho))hPrimediag(bulkSubset)*hPrime’);
objective = objective + log_det(eye(nMsAnt) + (1/dlNoise)hPrimediag(bulkSubset)hPrime’);
maximize( objective )
lb <= bulkSubset <= ub
%bulkSubsetones(nTxRf,1) == actTx
sum(bulkSubset) == actTx
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.
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
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.
Replace log_det(cvx_expression) >= t where cvx_expression is an n by n matrix
-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
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:
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.)