How to speed up run time?


(Tom) #1

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/(actTx
invRho))hPrimediag(bulkSubset)*hPrime’);
objective = objective + log_det(eye(nMsAnt) + (1/dlNoise)hPrimediag(bulkSubset)hPrime’);
end
maximize( objective )
subject to
lb <= bulkSubset <= ub
%bulkSubset
ones(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
%%%%%%%%

Thanks in advance!
Tom


(Mark L. Stone) #2

Try CVXQUAD CVXQUAD: How to use CVXQUAD's Pade Approximant instead of CVX's unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD's Quantum (Matrix) Entropy & Matrix Log related functions .

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.


(Tom) #3

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?


(Mark L. Stone) #4

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

  1. Try Gurobi
    or
  2. 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.


(Mark L. Stone) #5

Mosek 9.0 Beta is now available https://www.mosek.com/content/version-9-beta/

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.


(Erling D.Andersen) #6

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.


(Mark L. Stone) #7

@Erling When log_det is reformulated for CVXQUAD, CVX sends SOCP to the solver (Mosek), not SDP.

From my write up in CVXQUAD: How to use CVXQUAD's Pade Approximant instead of CVX's unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD's Quantum (Matrix) Entropy & Matrix Log related functions

+++++++++++++++++++++++++
+++++++++++++++++++++++++

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.


(Erling D.Andersen) #8

For both SOCP and SDPs v9 will on average provide a bit higher accuracy than v8. It might help the pade approximation.


(Michael C. Grant) #9

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.)


(Mark L. Stone) #10

@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.


(Erling D.Andersen) #11

You can now feed conic affine constraints i.e. Ax+b \in K directly. That might be convenient.