I am solving an SOCP problem via CVX. I am trying same problem with different solvers. When I am specifying “cvx_solver sedumi”, the output is “No sensible solution found.” and “Run into numerical problems.”. However, the same problem when solved with sdpt3 or mosek gives me an answer. I am unable to come to a conclusion as to where the problem exactly lies. Should I recheck my code for any errors? I know from (this), that mosek is a more robust solver. But my problem is socp, hence polynomially solvable. I don’t have very large system (1118 variables, 323 equality constraints), yet sedumi does not give the output. Can someone please suggest as to why this is happening?
Also, is it possible in cvx to specify the method of solving? (like infeasible path-following algorithm or potential reduction algorithm)
Perhaps you can show the output from all the solvers. Did Mosek issue any warnings?
For Sedumi
Calling SeDuMi 1.3.4: 1118 variables, 323 equality constraints
SeDuMi 1.3.4 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 323, order n = 915, dim = 1120, blocks = 3
nnz(A) = 6137 + 10200, nnz(ADA) = 4335, nnz(L) = 2347
Handling 102 + 2 dense columns.
it : by gap delta rate t/tP t/tD* feas cg cg prec
0 : 1.16E+02 0.000
1 : -4.90E+00 3.42E+01 0.000 0.2964 0.9000 0.9000 0.85 1 1 6.8E+02
2 : -3.37E+01 9.47E+00 0.000 0.2767 0.9000 0.9000 -0.66 1 1 7.9E+02
3 : -8.87E+02 6.34E-01 0.000 0.0670 0.9900 0.9900 -0.86 1 1 1.0E+03
4 : -2.57E+03 4.33E-02 0.000 0.0682 0.9900 0.9900 -0.62 1 1 2.0E+02
5 : -1.21E+03 1.21E-02 0.000 0.2787 0.9000 0.9000 1.81 1 1 3.6E+01
6 : -2.82E+02 3.74E-03 0.000 0.3106 0.9000 0.9000 2.16 1 1 6.6E+00
7 : -1.05E+02 2.01E-03 0.000 0.5362 0.9000 0.9000 2.29 1 1 2.1E+00
8 : -2.42E+01 9.34E-04 0.000 0.4650 0.9000 0.9000 2.88 1 1 4.9E-01
9 : -3.09E+00 4.25E-04 0.000 0.4551 0.9000 0.9000 1.99 1 1 1.6E-01
10 : 5.13E-01 1.69E-04 0.000 0.3976 0.9000 0.9000 1.28 1 1 6.1E-02
11 : 9.23E-01 8.91E-05 0.000 0.5276 0.9000 0.9000 1.04 1 1 3.2E-02
12 : 1.27E+00 4.69E-05 0.000 0.5264 0.6854 0.9000 1.03 3 3 1.7E-02
13 : 1.45E+00 2.09E-05 0.000 0.4449 0.9000 0.9000 1.01 2 2 7.7E-03
14 : 1.52E+00 9.25E-06 0.000 0.4432 0.9000 0.9000 1.00 2 2 3.4E-03
15 : 1.55E+00 3.74E-06 0.000 0.4040 0.9000 0.9000 1.00 2 2 1.4E-03
Run into numerical problems.
iter seconds digits cx by
15 0.7 Inf 1.5458679730e+00 1.5466154449e+00
|Ax-b| = 1.4e-02, [Ay-c]_+ = 4.0E-07, |x|= 7.3e+02, |y|= 8.8e+08
No sensible solution found.
Detailed timing (sec)
Pre IPM Post
7.300E-02 6.110E-01 1.100E-02
Max-norms: ||b||=1.492009e+01, ||c|| = 1,
Cholesky |add|=0, |skip| = 1, ||L.L|| = 266.447.
Status: Failed
Optimal value (cvx_optval): NaN
For sdpt3
Calling SDPT3 4.0: 1118 variables, 323 equality constraints
num. of constraints = 323
dim. of socp var = 101, num. of socp blk = 1
dim. of linear var = 910
dim. of free var = 107 *** convert ublk to lblk
number of nearly dependent constraints = 1
To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 1.
SDPT3: Infeasible path-following algorithms
version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime
0|0.000|0.000|6.4e+03|7.2e+04|1.1e+09| 6.875609e-09 0.000000e+00| 0:0:00| chol 1 1
1|0.912|0.977|5.6e+02|1.6e+03|5.4e+06|-1.278348e-01 -1.716929e+02| 0:0:00| chol 1 1
2|0.489|0.823|2.9e+02|2.9e+02|6.1e+05|-7.163421e-01 -3.016529e+02| 0:0:00| chol 1 1
3|0.796|0.854|5.9e+01|4.3e+01|1.1e+05|-1.902006e+00 -3.302369e+02| 0:0:01| chol 1 1
4|0.863|0.819|8.1e+00|7.7e+00|1.6e+04|-4.473941e+00 -2.731975e+02| 0:0:01| chol 1 1
5|0.671|0.275|2.6e+00|5.6e+00|5.6e+03|-5.063160e+01 -2.391456e+02| 0:0:01| chol 1 1
6|0.507|0.390|1.3e+00|3.4e+00|3.6e+03|-1.894977e+02 -1.829175e+02| 0:0:01| chol 1 1
7|0.798|0.551|2.6e-01|1.5e+00|8.9e+02|-6.299369e+00 -1.169230e+02| 0:0:01| chol 1 1
8|0.564|0.333|1.2e-01|1.0e+00|5.2e+02| 6.745044e+01 -1.100913e+02| 0:0:01| chol 1 1
9|0.827|0.582|2.0e-02|4.3e-01|1.8e+02| 4.102604e+01 -7.552875e+01| 0:0:01| chol 1 1
10|0.910|0.361|1.8e-03|2.7e-01|9.1e+01| 3.312408e+01 -5.041166e+01| 0:0:01| chol 1 1
11|0.944|0.339|1.0e-04|1.8e-01|6.3e+01| 2.467530e+01 -3.565208e+01| 0:0:01| chol 1 1
12|0.946|0.285|5.4e-06|1.3e-01|4.7e+01| 1.898468e+01 -2.693749e+01| 0:0:01| chol 1 1
13|1.000|0.354|2.9e-08|8.3e-02|3.4e+01| 1.469213e+01 -1.839893e+01| 0:0:01| chol 1 1
14|1.000|0.325|2.3e-08|5.6e-02|2.4e+01| 1.094045e+01 -1.263117e+01| 0:0:01| chol 1 1
15|1.000|0.324|9.8e-09|3.8e-02|1.7e+01| 8.427820e+00 -8.449583e+00| 0:0:01| chol 1 1
16|1.000|0.328|7.0e-09|2.6e-02|1.2e+01| 6.506948e+00 -5.393694e+00| 0:0:01| chol 1 1
17|1.000|0.329|3.5e-09|1.7e-02|8.5e+00| 5.056121e+00 -3.223875e+00| 0:0:01| chol 1 1
18|1.000|0.335|2.3e-09|1.1e-02|5.7e+00| 3.947999e+00 -1.674089e+00| 0:0:01| chol 1 1
19|1.000|0.343|1.4e-09|7.5e-03|3.8e+00| 3.127322e+00 -5.873891e-01| 0:0:01| chol 1 1
20|1.000|0.355|9.1e-10|4.8e-03|2.4e+00| 2.532563e+00 1.694268e-01| 0:0:01| chol 1 1
21|1.000|0.360|5.6e-10|3.1e-03|1.5e+00| 2.142824e+00 6.723943e-01| 0:0:01| chol 1 1
22|1.000|0.365|3.4e-10|2.0e-03|9.2e-01| 1.901479e+00 9.999754e-01| 0:0:01| chol 1 1
23|1.000|0.367|2.0e-10|1.2e-03|5.6e-01| 1.757613e+00 1.209147e+00| 0:0:01| chol 1 1
24|1.000|0.378|1.3e-10|7.8e-04|3.3e-01| 1.669455e+00 1.345081e+00| 0:0:01| chol 1 1
25|1.000|0.378|1.9e-10|4.8e-04|1.9e-01| 1.620520e+00 1.428842e+00| 0:0:01| chol 1 1
26|1.000|0.384|6.1e-11|3.0e-04|1.1e-01| 1.592933e+00 1.481154e+00| 0:0:01| chol 1 1
27|1.000|0.369|1.0e-10|3.0e-04|6.9e-02| 1.579113e+00 1.511536e+00| 0:0:01| chol 1 1
28|1.000|0.769|1.1e-11|1.7e-04|2.2e-02| 1.571851e+00 1.550759e+00| 0:0:01| chol 1 1
29|0.854|0.825|9.5e-12|5.4e-05|9.6e-03| 1.568627e+00 1.559183e+00| 0:0:01| chol 1 1
30|0.795|0.560|2.3e-11|2.4e-05|5.9e-03| 1.565778e+00 1.559986e+00| 0:0:01| chol 1 1
31|0.445|0.445|5.6e-11|1.5e-05|4.7e-03| 1.564863e+00 1.560275e+00| 0:0:01| chol 1 1
32|1.000|0.863|6.0e-12|1.2e-05|1.1e-03| 1.561682e+00 1.560604e+00| 0:0:01| chol 1 1
33|1.000|0.967|1.3e-12|2.8e-06|1.0e-04| 1.560762e+00 1.560663e+00| 0:0:01| chol 2 2
34|1.000|0.987|1.5e-13|2.6e-07|1.6e-06| 1.560668e+00 1.560667e+00| 0:0:01| chol 2 2
35|0.998|0.988|3.1e-14|3.9e-09|2.1e-08| 1.560667e+00 1.560667e+00| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08
number of iterations = 35
primal objective value = 1.56066682e+00
dual objective value = 1.56066681e+00
gap := trace(XZ) = 2.07e-08
relative gap = 5.03e-09
actual relative gap = 4.34e-09
rel. primal infeas (scaled problem) = 3.07e-14
rel. dual " " " = 3.85e-09
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 8.3e+00, 7.5e+05, 7.5e+05
norm(A), norm(b), norm© = 8.2e+02, 3.0e+01, 2.4e+00
Total CPU time (secs) = 1.14
CPU time per iteration = 0.03
termination code = 0
DIMACS: 5.8e-14 0.0e+00 4.7e-09 0.0e+00 4.3e-09 5.0e-09
Status: Solved
Optimal value (cvx_optval): +1.56067
for mosek
Calling Mosek 9.1.9: 1118 variables, 323 equality constraints
MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 323
Cones : 1
Scalar variables : 1118
Matrix variables : 0
Integer variables : 0
Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 2
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 1
Presolve terminated. Time: 0.25
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 323
Cones : 1
Scalar variables : 1118
Matrix variables : 0
Integer variables : 0
Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 308
Optimizer - Cones : 2
Optimizer - Scalar variables : 1105 conic : 202
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 2.13e+04 after factor : 2.28e+04
Factor - dense dim. : 0 flops : 3.92e+06
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 1.2e+00 9.9e+01 2.6e+00 0.00e+00 1.644853627e+00 0.000000000e+00 1.0e+00 0.38
1 1.5e-01 1.2e+01 9.3e-01 -9.99e-01 -2.670074730e+01 -2.132826734e+01 1.2e-01 0.91
2 1.1e-02 8.9e-01 2.5e-01 -9.96e-01 -4.645266071e+02 -3.593380807e+02 8.9e-03 0.95
3 6.8e-04 5.4e-02 1.4e-02 -7.28e-01 -8.274301220e+02 -7.333445064e+02 5.5e-04 0.98
4 1.4e-04 1.1e-02 7.4e-04 1.90e+00 -1.351714710e+02 -1.290601784e+02 1.1e-04 1.00
5 6.0e-05 4.8e-03 1.2e-04 3.08e+00 -1.731477001e+01 -1.648581008e+01 4.8e-05 1.03
6 1.1e-05 8.9e-04 9.0e-06 1.70e+00 -4.528467103e-01 -3.106484129e-01 9.0e-06 1.06
7 2.3e-06 1.8e-04 5.6e-07 1.06e+00 1.160814286e+00 1.173671551e+00 1.9e-06 1.09
8 2.9e-07 2.3e-05 2.3e-08 1.01e+00 1.516251692e+00 1.517585687e+00 2.4e-07 1.11
9 3.6e-08 2.9e-06 6.5e-10 1.00e+00 1.557939894e+00 1.558008242e+00 2.9e-08 1.13
10 1.2e-08 9.5e-07 1.2e-10 1.00e+00 1.559716085e+00 1.559736542e+00 9.6e-09 1.16
11 3.3e-09 2.7e-07 1.7e-11 1.00e+00 1.560389868e+00 1.560395264e+00 2.7e-09 1.17
12 3.2e-10 2.5e-08 4.9e-13 1.00e+00 1.560660313e+00 1.560660798e+00 2.5e-10 1.20
13 2.8e-11 1.4e-11 5.7e-18 1.00e+00 1.560666803e+00 1.560666803e+00 1.4e-13 1.23
Optimizer terminated. Time: 1.61
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 1.5606668029e+00 nrm: 1e+01 Viol. con: 1e-09 var: 4e-12 cones: 0e+00
Dual. obj: 1.5606668031e+00 nrm: 2e+03 Viol. con: 0e+00 var: 6e-10 cones: 0e+00
Optimizer summary
Optimizer - time: 1.61
Interior-point - iterations : 13 time: 1.27
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00
Status: Solved
Optimal value (cvx_optval): +1.56067
MOSEK didn’t issue any warnings, but in sdpt3 output, there is one dependent constraints. I think this is causing error. Because when I reduce the problem size and solve with sedumi, i get a warning “Warning: Rank deficient, rank = 142, tol = 3.844559e-10. The coefficient matrix is not full row rank, numerical problems may occur.”
But given that the problem is huge and I cannot manually convert it into a problem with one coefficient matrix, I am unable to move forward.
Sedumi gets close, but can’t quite make it. Well, that happens. You still have two solvers, and Mosek output shows that everything about your problem looks nicely scaled. Mosek’s presolve also removes 1 linear dependency and everything works. So I don’t see a reason to worry.
It would be really helpful if anyone suggests the second part of the question (is it possible to specify which method to particularly apply in CVX?).
The method solving is “determined” by specifying the solver, and if you want other than default options for that solver, to use advanced_solver_settings. to specify non-default solver parameter values, which may not work out well if you don’t know what you’re doing. You should use Mosek as solver unless you have a good reason not to.
As far as I know, each of the solvers used by CVX has only one algorithm to solve a conic problem, so there is nothing to specify here. You can specify some tuning of the algorithm using solver-specific settings as @Mark_L_Stone says. The solver’s documentation should tell you what can be adjusted this way.
Maybe for linear problems there could be some choice (say simplex vs. interior point) and that would have to be determined by solver-specific settings again.