Reducing Computation time for a SDP

Hello,

I am trying to solve a SDP relaxation of a non-convex problem, the relaxation looks as follows :

tic
cvx_begin sdp
variable z(n);
variable X(n,n) symmetric;
minimize ( trace(HX)-f’z+f’f)
subject to
Aeq
z == beq ;
LB <= z <= UB;
for i=1:n/7
trace(X
Vmatrix(:,:,i))==0;
trace(X
P(:,:,i))+q(:,1,i)’*z+f’*f<=0;
end
[X z; z’ 1] == semidefinite(n+1);
cvx_end
toc

This solution is the control input and states in order to avoid collision of two vehicles this is done at each sampling time so the program is run at each iteration. Therefore to be scalable and for experimental purposes the computation time should be lower than the sampling time. However, the solution is as follows:

Calling SDPT3 4.0: 741 variables, 101 equality constraints

num. of constraints = 101
dim. of sdp var = 36, num. of sdp blk = 1
dim. of linear var = 75


SDPT3: Infeasible path-following algorithms


version predcorr gam expon scale_data
HKM 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|4.1e+01|5.5e+00|1.5e+08| 1.081372e+07 0.000000e+00| 0:0:00| chol 1 1
1|0.969|0.843|1.3e+00|8.7e-01|1.8e+07| 6.657526e+06 5.312966e+05| 0:0:00| chol 1 1
2|0.969|0.978|4.0e-02|2.5e-02|1.6e+06| 1.596548e+06 2.494570e+05| 0:0:00| chol 1 1
3|0.422|0.918|2.3e-02|1.3e-02|1.0e+06| 1.184067e+06 3.803411e+05| 0:0:00| chol 1 1
4|0.930|0.946|1.6e-03|7.1e-03|1.4e+05| 5.626440e+05 4.460365e+05| 0:0:00| chol 1 1
5|0.923|0.980|1.2e-04|1.4e-03|1.2e+04| 5.128262e+05 5.030611e+05| 0:0:01| chol 1 1
6|0.926|0.965|9.2e-06|5.2e-04|3.0e+03| 5.089199e+05 5.064452e+05| 0:0:01| chol 1 1
7|0.924|0.913|7.0e-07|2.6e-04|5.4e+02| 5.081852e+05 5.077947e+05| 0:0:01| chol 1 1
8|1.000|0.931|4.0e-08|1.2e-04|2.0e+02| 5.081058e+05 5.079637e+05| 0:0:01| chol 1 1
9|0.943|1.000|4.0e-09|3.4e-05|3.3e+01| 5.080690e+05 5.080527e+05| 0:0:01| chol 1 1
10|0.920|0.957|3.2e-10|1.5e-06|1.8e+00| 5.080607e+05 5.080596e+05| 0:0:01| chol 1 1
11|1.000|0.943|2.1e-12|8.4e-08|3.3e-01| 5.080601e+05 5.080598e+05| 0:0:01| chol 1 1
12|0.974|0.982|1.1e-12|1.5e-09|6.4e-03| 5.080600e+05 5.080600e+05| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08

number of iterations = 12
primal objective value = 5.08060025e+05
dual objective value = 5.08060019e+05
gap := trace(XZ) = 6.45e-03
relative gap = 6.34e-09
actual relative gap = 5.65e-09
rel. primal infeas (scaled problem) = 1.08e-12
rel. dual " " " = 1.48e-09
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 4.8e+03, 1.5e+03, 1.6e+03
norm(A), norm(b), norm© = 2.5e+01, 5.6e+03, 3.6e+02
Total CPU time (secs) = 0.63
CPU time per iteration = 0.05
termination code = 0
DIMACS: 2.4e-12 0.0e+00 3.5e-09 0.0e+00 5.7e-09 6.3e-09


Status: Solved
Optimal value (cvx_optval): +510846

Elapsed time is 1.698546 seconds.

the elapsed time is too high for the required purposes , however i have observed that the most time is taken up launching the solver at each iteration and possibly printing the results. Could that be suppressed in order to increase computation time? Moreover is there a way in order to avoid launching the solver at each iteration.

Thank you for your help in advance

Printing can be suppressed using cvx_begin quiet. That might help a little, but not much for such a long running problem. Perhaps improving scaling (5e5 is a rather large optimal objective) will help some, as well as a faster solver, such as Mosek. But there is no way to avoid the CVX modeling time on every problem instance when using CVX.

To save on modeling time, you could use YALMIP’s optimizer object capability https://yalmip.github.io/optimizerupdates/, which eliminates much of the modeling time when used repeatedly on different input.data. I think the fastest way would be to use something like Parameterized Fusion for Mosek 9.2 (now in beta). https://themosekblog.blogspot.com/2020/03/parametrized-fusion-benchmarks.html - this will require more effort on your part compared to CVX,.

1 Like

You can have cvx output the code for input directly INTO sdpt3 and that would skip the cvx compile time. Or you can look at the sdpt3 manual and enter the problem directly there.

1 Like

hello,
Thank you for your reply, would you be able to tell me how it would be possible for cvx to input directly into sdpt3?

regards

I just Googled SDPT3 and quickly ended at

https://blog.nus.edu.sg/mattohkc/softwares/sdpt3/

I think there is a good chance that the user guide present at that page will provide the information you need.

1 Like