Successive approximation method using cvx_quad


(Betty Nagy) #1

I would like to show you the results of the problem;
Calling SDPT3 4.0: 611425 variables, 12705 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 12705
dim. of sdp var = 384, num. of sdp blk = 192
dim. of socp var = 610560, num. of socp blk = 6272
dim. of linear var = 289


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|2.8e+02|1.7e+01|1.2e+08| 2.080584e+06 0.000000e+00| 0:0:03| spchol 1 1
1|0.017|0.079|2.8e+02|1.6e+01|1.1e+08| 2.058402e+06 -4.903973e+03| 0:0:05| spchol 1 1
2|0.323|0.448|1.9e+02|8.6e+00|6.3e+07| 1.635066e+06 -2.920055e+04| 0:0:16| spchol 1 1
3|0.464|0.508|1.0e+02|4.2e+00|3.1e+07| 1.300625e+06 -4.320787e+04| 0:0:27| spchol 1 1
4|0.671|0.602|3.3e+01|1.7e+00|1.2e+07| 1.040250e+06 -4.905231e+04| 0:0:36| spchol 1 1
5|0.598|0.750|1.3e+01|4.2e-01|3.6e+06| 8.437930e+05 -4.747795e+04| 0:0:46| spchol 1 1
6|0.604|0.650|5.3e+00|1.5e-01|1.4e+06| 5.613285e+05 -4.071215e+04| 0:0:56| spchol 1 1
7|0.349|0.515|3.4e+00|7.2e-02|7.5e+05| 4.104589e+05 -3.133960e+04| 0:1:06| spchol 1 1
8|0.487|0.531|1.8e+00|3.4e-02|3.6e+05| 2.348060e+05 -2.183505e+04| 0:1:16| spchol 1 1
9|0.470|0.489|9.3e-01|1.7e-02|1.8e+05| 1.318766e+05 -1.383730e+04| 0:1:25| spchol 1 1
10|0.468|0.501|4.9e-01|8.6e-03|9.0e+04| 7.291869e+04 -7.851289e+03| 0:1:35| spchol 1 1
11|0.290|0.730|3.5e-01|2.3e-03|5.6e+04| 5.226273e+04 -2.623489e+03| 0:1:44| spchol 1 1
12|0.513|0.864|1.7e-01|3.2e-04|2.6e+04| 2.552583e+04 -6.968502e+02| 0:1:54| spchol 1 1
13|0.736|0.969|4.5e-02|1.0e-05|6.7e+03| 6.540790e+03 -3.308004e+02| 0:2:03| spchol 1 1
14|0.380|0.479|2.8e-02|3.2e-03|4.6e+03| 3.970353e+03 -3.040804e+02| 0:2:13| spchol 1 1
15|0.656|0.488|9.6e-03|3.8e-03|1.8e+03| 1.238464e+03 -2.757137e+02| 0:2:23| spchol 1 1
16|0.483|0.547|5.0e-03|3.2e-03|9.7e+02| 5.410291e+02 -2.498089e+02| 0:2:32| spchol 1 1
17|0.574|0.736|2.1e-03|1.6e-03|4.1e+02| 1.075707e+02 -2.319582e+02| 0:2:42| spchol 1 1
18|0.465|0.508|1.1e-03|1.2e-03|2.3e+02|-3.800428e+01 -2.208648e+02| 0:2:51| spchol 1 1
19|0.674|0.529|3.7e-04|7.7e-04|9.5e+01|-1.512996e+02 -2.143710e+02| 0:3:01| spchol 1 1
20|0.434|0.621|2.1e-04|3.6e-04|4.9e+01|-1.748568e+02 -2.094696e+02| 0:3:10| spchol 1 1
21|0.423|0.666|1.2e-04|1.6e-04|2.6e+01|-1.878789e+02 -2.071801e+02| 0:3:19| spchol 1 1
22|0.414|0.825|7.0e-05|5.3e-05|1.3e+01|-1.952726e+02 -2.061776e+02| 0:3:29| spchol 1 1
23|0.762|0.902|1.7e-05|1.2e-05|3.0e+00|-2.033139e+02 -2.059188e+02| 0:3:39| spchol 1 1
24|0.702|0.926|5.0e-06|2.8e-06|8.7e-01|-2.051100e+02 -2.058830e+02| 0:3:49| spchol 1 1
25|0.752|0.940|1.2e-06|6.5e-07|2.2e-01|-2.056851e+02 -2.058792e+02| 0:3:58| spchol 1 1
26|0.712|0.849|3.6e-07|2.4e-07|6.5e-02|-2.058219e+02 -2.058785e+02| 0:4:08| spchol 1 1
27|0.584|0.794|1.5e-07|1.1e-07|2.8e-02|-2.058545e+02 -2.058782e+02| 0:4:17| spchol 1 1
28|0.650|0.808|5.2e-08|4.3e-08|9.9e-03|-2.058697e+02 -2.058781e+02| 0:4:27| spchol 2 1
29|0.746|0.729|1.3e-08|1.8e-08|2.9e-03|-2.058759e+02 -2.058781e+02| 0:4:37| spchol 2 1
30|0.772|0.815|3.0e-09|4.9e-09|6.9e-04|-2.058776e+02 -2.058781e+02| 0:4:46| spchol 2 2
31|0.822|0.814|5.4e-10|1.2e-09|1.4e-04|-2.058780e+02 -2.058781e+02| 0:4:56| spchol 2 2
32|0.475|0.835|2.8e-10|3.1e-10|5.9e-05|-2.058780e+02 -2.058781e+02| 0:5:07| spchol 2 2
33|0.474|0.909|1.5e-10|8.4e-11|2.8e-05|-2.058780e+02 -2.058781e+02| 0:5:17| spchol 2 2
34|0.473|0.943|7.8e-11|3.4e-11|1.4e-05|-2.058780e+02 -2.058781e+02| 0:5:27| spchol 2 2
35|0.473|0.943|4.1e-11|1.8e-11|7.6e-06|-2.058780e+02 -2.058781e+02| 0:5:37| spchol 2 2
36|0.473|0.943|2.2e-11|9.2e-12|4.0e-06|-2.058781e+02 -2.058781e+02| 0:5:47|
stop: max(relative gap, infeasibilities) < 1.49e-08

number of iterations = 36
primal objective value = -2.05878052e+02
dual objective value = -2.05878056e+02
gap := trace(XZ) = 4.03e-06
relative gap = 9.77e-09
actual relative gap = 9.06e-09
rel. primal infeas (scaled problem) = 2.17e-11
rel. dual " " " = 9.22e-12
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 2.3e+02, 2.1e+02, 3.3e+02
norm(A), norm(b), norm© = 9.3e+02, 6.3e+01, 1.7e+03
Total CPU time (secs) = 346.77
CPU time per iteration = 9.63
termination code = 0
DIMACS: 1.5e-10 0.0e+00 1.4e-11 0.0e+00 9.1e-09 9.8e-09


Status: Solved
Optimal value (cvx_optval): +101.821

It can be seen from the first step that the dual and primal have a very large difference in their optimal values and then it takes many steps until they are the same value. Is the problem in the input parameters or the model or the size ? given into consideration that the same model with same input parameters but with smaller size the problem takes much less amount of time ?
thanks a lot for your patience and help.


(Mark L. Stone) #2

You should be happy. the problem was solved.

The successive approximation method was not used. As to whether CVXQUAD’s Pade approximations were used, we’ll have to take your word for it, as you don’t show either the pre-solver output which would show that or the CVX code.

The problem might be solved faster using Mosek or Gurobi as solver (Gurobi can only be used only if there are no SDP constraints or matrix log (quantum entropy) family functions).

If you show a reproducible problem (input data and CVX code), perhaps someone can make more specific suggestions. it is not unusual, however, for larger problems of a given type to take longer to solve than smaller problems.