# Specifying a particular method to solve socp

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

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

1 Like

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.

2 Likes

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.