How do I interpret the output from two solvers which gave inconsistent results

1

Hi, I am new to CVX. Recently, I was trying to solve an SDP problem with mainly linear matrix inequality constraints and found that the CVX is an ideal tool for expressing the problem. However, CVX can be worked with several internal and external SDP solvers. I didn’t know which one is the best for me so I tried them all: SDPT3, SeDuMi, and Mosek. SDPT3 simply didn’t work for most of the time. The main issue is that the SeDuMi and Mosek gave inconsistent results. And, I could not tell which one is close to the real optimized value.

Here is the code I implemented using both SeDuMi and Mosek:

cvx_solver SeDuMi
% cvx_solver MOSEK_3

cvx_begin sdp
variable x(n)
expression M_psd_exp(Nk,Nk)
variable M_psd(Nk,Nk,NQ) complex hermitian semidefinite
minimize( f * x );
subject to
lb <= x <= ub;
A * x <= b;
Aeq * x == beq;

    for i = 1:NQ
        for j = 1:Nk
            M_psd_exp(:,j) = D(:,:,j,i)*x;
        end
        M_psd(:,:,i) == M_psd_exp;
    end

cvx_end

Here the for-loop is used to generate NQ numbers of positive semidefinite constraints stored in the variable M_psd claimed to be complex hermitian semidefinite (yes, I am solving a complex SDP problem). In my implementations, I have n = 325, Nk=NQ=49, A is a matrix with dimension 2401x325, and Aeq is a 1x325 vector.

This is what the SeDuMi solver gave me after the optimization:

Calling SeDuMi 1.3.4: 175973 variables, 27373 equality constraints
For improved efficiency, SeDuMi is solving the dual problem.

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
Split 55273 free variables
eqs m = 27373, order n = 115999, dim = 348896, blocks = 50
nnz(A) = 37069641 + 0, nnz(ADA) = 32617321, nnz(L) = 16322347
it : by gap delta rate t/tP t/tD* feas cg cg prec
0 : 2.64E+02 0.000
1 : 1.69E-01 2.19E+02 0.000 0.8295 0.9000 0.9000 4.44 1 1 3.4E+01
2 : 1.20E-01 1.86E+02 0.000 0.8523 0.9000 0.9000 2.66 1 1 2.6E+01
3 : 8.02E-02 1.22E+02 0.000 0.6531 0.9000 0.9000 2.71 1 1 1.1E+01
4 : 8.23E-02 5.31E+01 0.000 0.4356 0.9000 0.9000 2.88 1 1 2.4E+00
5 : 8.64E-02 2.06E+01 0.000 0.3874 0.9000 0.9000 2.92 1 1 5.8E-01
6 : 9.08E-02 6.30E-01 0.000 0.0307 0.9900 0.9900 1.41 1 1 1.1E-01
7 : 1.35E-01 5.25E-02 0.000 0.0833 0.9900 0.9900 1.46 1 1 6.8E-02
8 : 2.07E-01 1.03E-02 0.000 0.1966 0.9000 0.9000 1.06 1 1 4.3E-02
9 : 2.35E-01 5.50E-04 0.000 0.0533 0.9900 0.9900 1.01 1 1 4.6E-03
10 : 2.36E-01 3.02E-05 0.000 0.0550 0.9900 0.9900 1.00 3 2 2.7E-04
Run into numerical problems.

iter seconds digits cx by
10 38.1 2.5 2.3645714125e-01 2.3556829304e-01
|Ax-b| = 5.8e-07, [Ay-c]_+ = 1.5E-06, |x|= 2.4e+01, |y|= 4.3e+02
No sensible solution found.

Detailed timing (sec)
Pre IPM Post
5.748E+00 1.381E+02 1.200E-01
Max-norms: ||b||=1.066859e-03, ||c|| = 3.888980e+02,
Cholesky |add|=0, |skip| = 93, ||L.L|| = 979.611.

Status: Failed
Optimal value (cvx_optval): NaN

which actually failed. However, it did give me a final obj value: 2.2901e-04.

Then for MOSEK, I got the following results:

Calling Mosek_3 9.1.9: 175973 variables, 27373 equality constraints
For improved efficiency, Mosek_3 is solving the dual problem.

MOSEK Version 10.1.24 (Build date: 2024-1-31 14:16:39)
Copyright (c) MOSEK ApS, Denmark WWW: mosek.com
Platform: Windows/64-X86

MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #288 (nearly) zero elements are specified in sparse col ‘’ (1) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #248 (nearly) zero elements are specified in sparse col ‘’ (2) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #248 (nearly) zero elements are specified in sparse col ‘’ (3) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #248 (nearly) zero elements are specified in sparse col ‘’ (4) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #248 (nearly) zero elements are specified in sparse col ‘’ (5) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #316 (nearly) zero elements are specified in sparse col ‘’ (6) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #297 (nearly) zero elements are specified in sparse col ‘’ (7) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #248 (nearly) zero elements are specified in sparse col ‘’ (8) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #248 (nearly) zero elements are specified in sparse col ‘’ (9) of matrix ‘A’.
MOSEK warning 710 (MSK_RES_WRN_ZEROS_IN_SPARSE_COL): #248 (nearly) zero elements are specified in sparse col ‘’ (10) of matrix ‘A’.
Warning number 710 is disabled.
Problem
Name :
Objective sense : minimize
Type : CONIC (conic optimization problem)
Constraints : 27373
Affine conic cons. : 0
Disjunctive cons. : 0
Cones : 0
Scalar variables : 58324
Matrix variables : 49 (scalarized: 237699)
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.03
Lin. dep. - primal attempts : 1 successes : 1
Lin. dep. - dual attempts : 0 successes : 0
Lin. dep. - primal deps. : 0 dual deps. : 0
Presolve terminated. Time: 0.75
Optimizer - threads : 24
Optimizer - solved problem : the primal
Optimizer - Constraints : 27373
Optimizer - Cones : 1
Optimizer - Scalar variables : 28848 conic : 27814
Optimizer - Semi-definite variables: 49 scalarized : 237699
Factor - setup time : 0.95
Factor - dense det. time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 1.63e+07 after factor : 1.63e+07
Factor - dense dim. : 2 flops : 1.15e+10
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 1.0e+00 2.9e+02 3.7e+02 0.00e+00 3.728979592e+02 0.000000000e+00 1.0e+00 2.08
1 7.4e-01 2.1e+02 3.2e+02 -9.88e-01 3.719304136e+02 -7.828392432e-05 7.4e-01 2.34
2 1.2e-01 3.4e+01 1.3e+02 -9.87e-01 3.514496629e+02 1.700256345e-03 1.2e-01 2.58
3 1.8e-02 5.3e+00 3.6e+01 -8.54e-01 2.045420898e+02 2.866275053e-02 1.8e-02 2.83
4 3.7e-03 1.1e+00 5.9e+00 -1.07e-01 5.941925152e+01 6.496061270e-02 3.7e-03 3.03
5 5.2e-04 1.5e-01 2.3e-01 1.74e+00 4.495914487e+00 8.784223341e-02 5.2e-04 3.28
6 1.6e-06 4.6e-04 2.0e-05 1.12e+00 1.041667567e-01 8.860669003e-02 1.6e-06 3.55
7 1.1e-07 3.2e-05 3.8e-07 1.00e+00 1.838516726e-01 1.827591160e-01 1.1e-07 3.78
8 6.6e-09 1.3e-06 3.0e-09 1.00e+00 2.343853251e-01 2.343393361e-01 4.6e-09 4.03
9 6.5e-09 1.3e-06 2.9e-09 9.97e-01 2.344226642e-01 2.343781053e-01 4.5e-09 5.06
10 6.5e-09 1.3e-06 2.9e-09 9.97e-01 2.344226642e-01 2.343781053e-01 4.5e-09 5.59
11 6.5e-09 1.3e-06 2.9e-09 9.97e-01 2.344226642e-01 2.343781053e-01 4.5e-09 6.16
Optimizer terminated. Time: 6.77

Interior-point solution summary
Problem status : UNKNOWN
Solution status : UNKNOWN
Primal. obj: 2.3442266423e-01 nrm: 3e+01 Viol. con: 2e-07 var: 1e-07 barvar: 0e+00
Dual. obj: 2.3437810532e-01 nrm: 3e+02 Viol. con: 0e+00 var: 3e-05 barvar: 2e+53
Optimizer summary
Optimizer - time: 6.77
Interior-point - iterations : 12 time: 6.75
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: Inaccurate/Solved
Optimal value (cvx_optval): +0.00141919

which gives an inaccurate/solved result. The obj value is much larger.

Although SeDuMi failed on this task, I actually cannot see why it failed and the results obtained from SeDuMi fit better to my expectations.

Can anyone please tell me how to read the output from both solvers and how I can improve the implementation?

2

It shows there is something numerically very fishy about your problem. One solver fails, another one claims to give up, and Mosek spits out warnings and then almost solves it but the solution summary looks weird with the large dual violation. Only you can interpret the solutions, ie. take them and check which suits you better, because you know your data and your model. You would have to show a fully reproducible example with all input data because the numerical data seems to be the problem here. You can dump the Mosek problem to a task file and contact Mosek support, then maybe we can say something about what happens in Mosek. (1 Technical Issues — MOSEK FAQ 10.1.24)

4

Thanks very much for your reply and your advice. I will also attach the input data here dump.task.gz - Google Drive in case you or anyone else could tell me what goes wrong with the input parameters. Probably, the problem is related to the warnings indicated in the output of MOSEK. I have tried to rescale the matrix ‘A’ but it didn’t work.

5

I can only confirm that it stalls. It behaves as if there was a plateau of similarly good almost optimal solutions and it is not able to make a good step at the end, ie. the problem is not robust enough. I don’t have any great advice, unfortunately.

6

Thanks again for your reply. After searching a little bit on the internet, I think I might find the solution to my problem and it is worthwhile to share it here for those who may encounter the same problem in their implementations. All I did was a simple modification to my original implementations: change

M_psd(:,:,i) == M_psd_exp;

to

M_psd(:,:,i) == (M_psd_exp+M_psd_exp’)/scaling_factor;

By this modification, the M_psd variable is now explicitly hermitian. Previously, it was hermitian by definition, but due to the limited precision of the numbers stored in matrix D, the solver seemed not to see M_psd as a hermitian matrix and gave me warnings. I also introduced a scaling factor to make the convergence faster (or more reliable). Now, with scaling_factor = 50 (I am not sure if this is something reasonable to do), I have converged results:

Calling Mosek_3 9.1.9: 120701 variables, 325 equality constraints
For improved efficiency, Mosek_3 is solving the dual problem.

MOSEK Version 10.1.24 (Build date: 2024-1-31 14:16:39)
Copyright (c) MOSEK ApS, Denmark WWW: mosek.com
Platform: Windows/64-X86

Problem
Name :
Objective sense : minimize
Type : CONIC (conic optimization problem)
Constraints : 325
Affine conic cons. : 0
Disjunctive cons. : 0
Cones : 0
Scalar variables : 3052
Matrix variables : 49 (scalarized: 237699)
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - primal attempts : 1 successes : 1
Lin. dep. - dual attempts : 0 successes : 0
Lin. dep. - primal deps. : 0 dual deps. : 0
Presolve terminated. Time: 0.08
GP based matrix reordering started.
GP based matrix reordering terminated.
Optimizer - threads : 24
Optimizer - solved problem : the primal
Optimizer - Constraints : 325
Optimizer - Cones : 1
Optimizer - Scalar variables : 1036 conic : 2
Optimizer - Semi-definite variables: 49 scalarized : 237699
Factor - setup time : 0.14
Factor - dense det. time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 5.30e+04 after factor : 5.30e+04
Factor - dense dim. : 0 flops : 4.45e+09
Factor - GP saved nzs : 0 GP saved flops : 3.55e+07
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 1.0e+00 2.9e+02 1.6e+01 0.00e+00 1.491591837e+01 0.000000000e+00 1.0e+00 0.53
1 7.4e-01 2.1e+02 1.4e+01 -9.88e-01 1.453760187e+01 -3.365156268e-05 7.4e-01 0.72
2 1.3e-01 3.7e+01 5.5e+00 -9.87e-01 7.912636872e+00 1.485300683e-03 1.3e-01 0.88
3 2.7e-02 7.8e+00 2.1e+00 -8.73e-01 -1.167882117e+01 1.993867892e-02 2.7e-02 1.03
4 4.6e-04 1.3e-01 4.0e-02 -4.27e-01 -2.834902422e+01 7.606807237e-02 4.6e-04 1.19
5 1.1e-04 3.3e-02 2.2e-03 1.39e+00 -1.243830432e+00 8.414148298e-02 1.1e-04 1.36
6 2.3e-05 6.6e-03 1.1e-04 2.75e+00 1.709708426e-02 9.188444496e-02 2.3e-05 1.52
7 2.0e-06 5.7e-04 2.7e-06 1.06e+00 1.077385283e-01 1.138962121e-01 2.0e-06 1.66
8 6.0e-07 1.7e-04 4.3e-07 1.01e+00 1.871594592e-01 1.888632671e-01 6.0e-07 1.83
9 5.8e-08 1.7e-05 1.2e-08 1.00e+00 2.323203452e-01 2.324670529e-01 5.8e-08 1.97
10 2.3e-09 3.3e-07 3.4e-11 1.00e+00 2.355189343e-01 2.355218657e-01 1.2e-09 2.12
11 2.3e-09 3.3e-07 3.4e-11 1.00e+00 2.355189343e-01 2.355218657e-01 1.2e-09 3.11
12 2.3e-09 3.3e-07 3.4e-11 1.00e+00 2.355194808e-01 2.355223896e-01 1.1e-09 3.53
13 2.3e-09 3.3e-07 3.4e-11 1.00e+00 2.355196164e-01 2.355225196e-01 1.1e-09 3.97
14 2.2e-09 3.3e-07 3.4e-11 1.00e+00 2.355196502e-01 2.355225520e-01 1.1e-09 4.44
15 2.2e-09 3.3e-07 3.4e-11 1.00e+00 2.355196671e-01 2.355225682e-01 1.1e-09 4.92
16 2.2e-09 3.3e-07 3.4e-11 1.00e+00 2.355196714e-01 2.355225723e-01 1.1e-09 5.45
17 2.2e-09 3.3e-07 3.4e-11 1.00e+00 2.355196735e-01 2.355225743e-01 1.1e-09 5.99
18 2.2e-09 3.3e-07 3.4e-11 1.00e+00 2.355196737e-01 2.355225745e-01 1.1e-09 6.56
19 2.2e-09 3.3e-07 3.4e-11 1.00e+00 2.355196739e-01 2.355225747e-01 1.1e-09 7.14
20 2.2e-09 3.3e-07 3.4e-11 1.00e+00 2.355196739e-01 2.355225747e-01 1.1e-09 7.72
Optimizer terminated. Time: 8.42

Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: 2.3551967387e-01 nrm: 3e+01 Viol. con: 6e-08 var: 2e-08 barvar: 0e+00
Dual. obj: 2.3552257467e-01 nrm: 3e+02 Viol. con: 0e+00 var: 9e-06 barvar: 3e-08
Optimizer summary
Optimizer - time: 8.42
Interior-point - iterations : 21 time: 8.41
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): +0.000274725

Notice that the warnings are all gone. If anyone has other ideas on how to improve this implementation, please let me know.

1 Like