What does this sentence mean? About SDP

#1

When I use the SDP3 solver to solve the SDP problem. The command window shows as follows:
SDPT3: Infeasible path-following algorithms.

What does the above sentence mean?

The status is “Unbound” and cvx_optval is “+Inf” .
However, I have checked the formulated problem. The cvx_optval cannot be “+Inf” as I analysed.

I have searched the corresponding problem, i.e., the problem of “Unbound”.
You have replied as follows:
The solver ran into numerical difficulty. Perhaps a different solver will do better. It may be that the scaling of your problem is bad, and the solver would work better if you changed the units in your problem to make the coefficients closer to 1 in magnitude (i.e., no very large or small exponents).

Actually, I have scaled of my problem. But I think that the scaling method I used is applicable, although the values of the introduced scaling variables may be samll.

Can I try to use the other solver? Which solver is better?

#2

Calling SDPT3 4.0: 96 variables, 12 equality constraints

num. of constraints = 12
dim. of sdp var = 30, num. of sdp blk = 3
dim. of linear var = 18
dim. of free var = 3 *** convert ublk to lblk

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|5.6e+02|2.3e+02|2.5e+07|-4.244762e+03 0.000000e+00| 0:0:00| chol 1 1
1|0.437|0.617|3.2e+02|8.8e+01|2.1e+07|-1.916034e+04 -5.197869e+05| 0:0:00| chol 1 1
2|0.842|0.884|5.0e+01|1.0e+01|3.6e+06|-2.293653e+04 -3.858250e+05| 0:0:00| chol 1 1
3|0.534|0.189|2.3e+01|8.5e+00|2.0e+06|-2.395065e+05 -3.783793e+05| 0:0:00| chol 1 1
4|0.034|0.168|2.2e+01|7.1e+00|2.8e+06|-6.320920e+04 -3.062078e+05| 0:0:00| chol 1 1
5|0.651|0.494|7.8e+00|3.6e+00|1.2e+06|-8.894887e+04 -2.569730e+05| 0:0:00| chol 1 1
6|0.038|0.336|7.5e+00|2.4e+00|1.5e+06|-3.232187e+05 -2.209654e+05| 0:0:00| chol 1 1
7|0.592|0.246|3.1e+00|1.8e+00|8.4e+05|-1.090681e+05 -2.205872e+05| 0:0:00| chol 1 1
8|0.906|0.860|2.9e-01|2.6e-01|1.5e+05|-9.970192e+03 -8.720764e+04| 0:0:00| chol 1 1
9|0.833|0.415|4.8e-02|1.5e-01|8.2e+04|-2.508827e+04 -6.456672e+04| 0:0:00| chol 1 1
10|0.861|0.045|6.7e-03|1.4e-01|2.1e+06|-3.077951e+06 -6.343900e+04| 0:0:00| chol 1 1
11|0.046|0.080|6.4e-03|1.3e-01|5.0e+06|-3.833606e+06 -8.333662e+04| 0:0:00| chol 1 1
12|1.000|0.091|1.7e-09|1.3e-01|2.5e+07|-1.210883e+07 -1.223668e+05| 0:0:00| chol 1 1
13|0.173|0.274|1.5e-09|9.1e-02|1.9e+07|-1.472461e+07 -7.904877e+05| 0:0:00| chol 1 1
14|0.874|0.509|1.3e-10|4.5e-02|5.3e+06|-4.607541e+07 -1.418443e+06| 0:0:00| chol 1 1
15|0.665|0.057|2.0e-10|4.5e-02|4.6e+09|-7.665094e+09 -1.510188e+06| 0:0:00| chol 1 1
16|0.006|0.010|9.4e-08|5.0e-02|1.1e+10|-7.944167e+09 -9.092146e+06| 0:0:00| chol 1 1
17|0.011|0.026|9.4e-08|6.0e-02|1.9e+10|-8.115083e+09 -4.178658e+07| 0:0:00| chol 1 1
18|0.096|0.080|8.7e-08|7.4e-02|2.9e+10|-8.940847e+09 -1.413946e+08| 0:0:00| chol 1 1
19|0.209|0.352|7.1e-08|4.8e-02|1.8e+10|-1.027442e+10 -4.470839e+08| 0:0:00| chol 1 1
20|0.766|0.371|4.1e-08|3.0e-02|1.7e+10|-2.192500e+10 -9.232431e+08| 0:0:00| chol 1 1
21|0.580|0.310|3.1e-08|2.1e-02|1.7e+10|-8.189288e+10 -1.361479e+09| 0:0:00| chol 1 1
22|0.688|0.144|5.8e-08|2.6e-02|1.4e+12|-2.286386e+12 -2.020061e+09| 0:0:00| chol 1 2
23|0.014|0.053|7.2e-08|3.7e-02|3.2e+12|-2.467452e+12 -1.371893e+10| 0:0:00| chol 1 2
24|0.109|0.076|6.8e-08|5.2e-02|6.3e+12|-3.040439e+12 -4.248004e+10| 0:0:00| chol 1 1
25|0.128|0.257|6.3e-08|3.9e-02|4.7e+12|-3.509175e+12 -1.600660e+11| 0:0:00| chol 1 1
26|0.842|0.384|2.8e-08|2.4e-02|4.4e+12|-9.988902e+12 -3.152352e+11| 0:0:00| chol 1 2
27|0.531|0.263|2.8e-08|1.8e-02|2.8e+12|-6.989020e+13 -4.605220e+11| 0:0:00| chol 1 2
28|0.695|0.027|2.2e-06|2.6e-02|3.2e+16|-5.381968e+16 -5.025646e+11| 0:0:00| chol 1 2
29|0.000|0.001|2.2e-06|4.1e-02|7.4e+16|-5.386291e+16 -5.253258e+12| 0:0:00| chol 1 2
30|0.002|0.001|2.2e-06|6.4e-02|1.3e+17|-5.405814e+16 -1.741432e+13| 0:0:00| chol 1 2
31|0.003|0.009|5.2e-05|9.8e-02|2.0e+17|-5.422649e+16 -9.013952e+13| 0:0:00|
sqlp stop: dual problem is suspected of being infeasible

number of iterations = 31
residual of dual infeasibility
certificate X = 8.45e-14
reldist to infeas. <= 6.08e-18
Total CPU time (secs) = 0.46
CPU time per iteration = 0.01
termination code = 2
DIMACS: 1.2e-04 0.0e+00 1.1e-01 0.0e+00 -1.0e+00 3.7e+00

Status: Unbounded
Optimal value (cvx_optval): +Inf

#3

If you have Mosek available as solver, use that, becasue it it the most (numer8ically) robust solver and provides the best warning and diagnostic information. Otherwise try SeDuMi. I predict Mosek will give a warning about large magnitude numbers, which are likely making the solution of your problem unrelaible.

If after fixing the problem scaling, the problem is still reported to be unbounded, please read https://yalmip.github.io/debuggingunbounded/ , which, other than some syntax differences, applies to CVX as well as to YALMIP.

Regarding “The command window shows as follows SDPT3: Infeasible path-following algorithms.” Don’t worry about it. That is just a generic description of SDPT3’s algorithm. It says nothing about what happened when SDPT3 was invoked to solve the problem CVX provided it.

#4

OK!
I will check my code. And the YALMP cannot declare the complex variables. Or YALMP can support complex variables, but I have not found.

#5

Both can support complex.

#6

Sir!
I think the problem is not resulted by the introduced scaling variables. Although the scaling variables is small, I have adopted the similar scaling method in my previous cvx code which is about the SOCP problem and it worked.
The difference is that this problem is about the SDP problem.

#7

Well, maybe you got away with bad scaling in your SOCP, and didn’t get away with bad scaling in your SDP problem. SDP can be (numerically) trickier and more difficult to solve than SDP, so it could be more sensitive to being adversely affected by bad scaling.

When you see numbers like 5e16 in the solver output, that generally a sign of bad scaling, and could result in the solver getting in great difficulty and being unreliable.

As i wrote in my previous reply, try Mosek if you can, and pay attention to its warning messages.

#9

I have try Mosek. But it still doesn’t work!

The command window shows as follows:
MOSEK Version 8.0.0.60 (Build date: 2017-3-1 13:09:33)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 12
Cones : 0
Scalar variables : 21
Matrix variables : 3
Integer variables : 0

Optimizer started.
Conic interior-point 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. - number : 0
Presolve terminated. Time: 0.05
Interior-point optimizer terminated. Time: 0.06.

MOSEK DUAL INFEASIBILITY REPORT.

Problem status: The problem is dual infeasible
Optimizer terminated. Time: 0.17

Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: -1.0000000000e+000 nrm: 2e+003 Viol. con: 0e+000 var: 0e+000 barvar: 0e+000
Optimizer summary
Optimizer - time: 0.17
Interior-point - iterations : 0 time: 0.06
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: Unbounded
Optimal value (cvx_optval): +Inf
[/quote]

#10

And I uptaded the cvx. It still does not work!

Calling Mosek 9.1.9: 96 variables, 12 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 : 12
Cones : 0
Scalar variables : 21
Matrix variables : 3
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.02
Lin. dep. - number : 0
Presolve terminated. Time: 0.08
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 12
Cones : 0
Scalar variables : 21
Matrix variables : 3
Integer variables : 0

Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 12
Optimizer - Cones : 1
Optimizer - Scalar variables : 16 conic : 4
Optimizer - Semi-definite variables: 3 scalarized : 165
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 : 72 after factor : 78
Factor - dense dim. : 0 flops : 3.06e+04
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.0e+03 3.6e+03 1.0e+00 0.00e+00 0.000000000e+00 0.000000000e+00 1.0e+00 0.11
1 4.6e+02 8.4e+02 4.8e-01 -9.99e-01 -7.703072540e+03 -7.699781910e+03 2.3e-01 0.33
2 1.3e+02 2.4e+02 2.6e-01 -9.96e-01 -6.750433937e+03 -6.736668859e+03 6.7e-02 0.34
3 4.1e+01 7.4e+01 1.4e-01 -9.68e-01 -7.360032523e+03 -7.316636161e+03 2.0e-02 0.34
4 6.5e+00 1.2e+01 4.4e-02 -8.65e-01 -5.203370783e+03 -5.023068649e+03 3.3e-03 0.34
5 1.1e+00 1.9e+00 7.6e-03 -3.63e-01 -2.055060652e+03 -1.853079394e+03 5.3e-04 0.36
6 1.2e-01 2.2e-01 4.0e-04 4.97e-01 -3.205786140e+02 -2.767346673e+02 6.1e-05 0.38
7 5.6e-02 1.0e-01 1.4e-04 8.21e-01 -2.210255158e+02 -1.967483525e+02 2.8e-05 0.38
8 3.0e-02 5.4e-02 2.7e-04 -4.57e-01 -4.814875001e+03 -4.494382419e+03 1.5e-05 0.39
9 3.7e-03 6.7e-03 6.2e-05 -4.27e-01 -2.277898975e+04 -2.165699360e+04 1.9e-06 0.41
10 7.2e-04 1.3e-03 2.1e-05 -8.82e-01 -8.298030857e+04 -7.962035671e+04 3.6e-07 0.41
11 1.0e-05 1.9e-05 1.8e-06 -1.01e+00 -2.866949748e+06 -2.754380846e+06 5.3e-09 0.42
12 3.4e-06 6.2e-06 1.0e-06 -9.77e-01 -9.300273992e+06 -8.963265590e+06 1.7e-09 0.44
13 1.6e-07 2.9e-07 2.1e-07 -9.89e-01 -2.033848844e+08 -1.962551861e+08 7.9e-11 0.44
14 5.3e-11 9.7e-11 3.7e-09 -9.99e-01 -5.853803397e+11 -5.649401513e+11 2.7e-14 0.45
15 2.5e-14 4.5e-14 1.7e-10 -1.00e+00 -7.840834949e-01 -7.567050802e-01 2.4e-19 0.47
Optimizer terminated. Time: 0.61

Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: -7.8408349493e-01 nrm: 4e+01 Viol. con: 2e-14 var: 0e+00 barvar: 0e+00
Optimizer summary
Optimizer - time: 0.61
Interior-point - iterations : 15 time: 0.48
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: Unbounded
Optimal value (cvx_optval): +Inf

#11

All points to the conclusion that your problem actually is unbounded. In fact note that the older Mosek 8 determined dual infeasibility already in presolve, which is pretty strong evidence. It can also indicate that you made some simple mistake in the code, like optimizing a wrong variable etc.

If you are concerned then please save the problem data to a file and contact support@mosek.com. https://docs.mosek.com/9.2/faq/faq.html#how-do-i-dump-the-problem-to-a-file-to-attach-with-my-support-question

With MOSEK 9 you can also save the problem to filename.ptf to get something human-readable you can analyze.

1 Like
#12

OK!

I will check the formulated problem!

Thank you!!!

#13

@Michal_Adamaszek Well I’ll be (to use a Southern U.S. expression). Mosek did not issue a warning about large coefficients. Is it “normal” that SDPT3 (i know it is not your product) could have such large numbers as 5e16 in its iteration log output for a problem which is “only” unbounded", but is well-scaled?

@Michal_Adamaszek How were you able to determine what Mosek 8 would have done on this problem? You don’t have a repoodicuble problem to run, as far as I know.

#14

There is a Mosek v8 log posted above.

#15

@Erling So you can determine from the Mosek 9.1.9 log what Mosek 8 would have done differently? That’s what I was wondering about.

I am actually set up to easily switch between Mosek 9.2.x and Mosek 8.1.0.80 because I know there were major changes from Mosek 8.1 to Mosek 9.0 and there is a chance Mosek 8.1 might work better on some problems than Mosek 9.2.

#16

I do not know why v8 find it dual infeasible v9 does not. Could be that v8 dualize before presolve and v9 does not. Presolve is not 100% symmetric.

#17

@Erling Senior moment.

#18

:slightly_smiling_face:

Sir!
I will try to use the YALMIP to solve the problem.
Does the YALMIP has the similar command , i.e., “expression holder” as shown in the cvx toolbox!

#19

[quote=“NWPU_Xiu, post:18, topic:7542, full:true”]
:slightly_smiling_face:

Sir!
I will try to use the YALMIP to solve the problem.
Does the YALMIP has the similar command , i.e., “expression holder” as shown in the cvx toolbox!

#20

You would very likely have gotten much further by now if you had shared reproducible code.

#21

YALMIP has irs own different way of dealing with the situation covered by CVX’s expression holders. Both CVX and YALMIP need workarounds to deal with a limitation caused by how MATLAB works under the hood, forcing users into less natural commands than seem ideally necessary.

If you have detailed YALMIP questions, I suggest you ask at the YALMIP forum https://groups.google.com/forum/?fromgroups#!forum/yalmip .AFTER reading the YALMIP wiki online entries at https://yalmip.github.io/tutorials/ . The YALMIP forum has the advantage over the CVX forum that the developer (Johan Lofberg) answers the questions, unlike the CVX forum, where users such as myself, and Mosek developers such as @Michal_Adamaszek and @Erling are doing most of the answering, and the developer only rarely answers questions on the board nowadays (YALMIP is also in a much more active state development than CVX)…