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.