SDP using SDPT3 and positive semidefinite constraint is not satisfied

Dimakis · March 26, 2023, 1:07am

Hello everyone.
I am using SDPT3 to solve a SDP problem, and the code is as follows.

% C1, C2,C3, A0, a0 are fixed and given matrices (or vectors) 
% XY and xy are two variables.
cvx_solver SDPT3;
cvx_precision best
cvx_begin
variable XY(I*(N+M),I*(N+M)) symmetric;
variable xy(I*(N+M),1);
minimize (sum(sum(XY.*A0)) + a0'*xy)
subject to
[XY xy; xy' 1] == semidefinite(I*(N+M)+1);
diag(XY) <= xy;
C1'*xy == ones(I,1);
C2'*xy <= A(:,1);
C3'*xy <= A(:,2);
cvx_end

val0 = min(eig([XY xy; xy' 1]));
fprintf("minimum eig val = %d \n", val0)

The putouts are as follows.

Calling SDPT3 4.0: 1128761 variables, 1611 equality constraints
------------------------------------------------------------

 num. of constraints = 1611
 dim. of sdp    var  = 1501,   num. of sdp  blk  =  1
 dim. of linear var  = 1510
*******************************************************************
   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|3.9e+02|3.9e+04|5.1e+11| 4.847802e+05  0.000000e+00| 0:0:00| spchol  1  1 
 1|0.964|0.987|1.4e+01|4.9e+02|6.7e+09| 4.835398e+05 -1.199672e+05| 0:0:01| chol  1  1 
 2|0.428|1.000|8.0e+00|1.6e-01|1.9e+09| 3.935624e+05 -1.673203e+05| 0:0:02| chol  1  1 
 3|0.970|1.000|2.4e-01|7.8e-02|5.6e+07| 1.145968e+04 -1.606939e+05| 0:0:02| chol  1  1 
 4|0.964|1.000|8.6e-03|3.9e-02|2.1e+06| 4.427794e+02 -8.775351e+04| 0:0:03| chol  1  1 
 5|0.872|0.944|1.1e-03|2.2e-02|3.0e+05| 1.054392e+02 -3.956068e+04| 0:0:03| chol  1  1 
 6|0.808|0.981|2.1e-04|1.0e-02|9.5e+04| 6.539402e+01 -3.846192e+04| 0:0:04| chol  1  1 
 7|0.833|0.978|3.5e-05|3.1e-03|2.2e+04| 5.930145e+01 -1.625699e+04| 0:0:05| chol  1  1 
 8|1.000|1.000|3.8e-09|3.0e-04|1.6e+03| 5.535553e+01 -1.522037e+03| 0:0:06| chol  1  1 
 9|0.652|0.925|4.9e-09|5.0e-05|1.7e+02| 4.743061e+01 -1.216209e+02| 0:0:07| chol  1  1 
10|0.120|0.056|4.3e-09|4.7e-05|1.7e+02| 5.061420e+01 -1.181791e+02| 0:0:07| chol  1  1 
11|0.169|0.601|3.6e-09|1.9e-05|1.7e+02| 4.641198e+01 -1.252287e+02| 0:0:08| chol  1  1 
12|0.161|0.300|3.0e-09|1.3e-05|1.6e+02| 4.486425e+01 -1.105422e+02| 0:0:09| chol  1  1 
13|0.572|0.320|1.3e-09|9.1e-06|1.2e+02| 4.205362e+01 -8.266648e+01| 0:0:09| chol  1  1 
14|0.825|0.441|2.2e-10|5.1e-06|9.5e+01| 4.125676e+01 -5.324270e+01| 0:0:10| chol  1  1 
15|0.826|1.000|3.9e-11|7.4e-11|4.9e+01| 3.839184e+01 -1.014214e+01| 0:0:11| chol  1  1 
16|0.664|1.000|1.3e-11|1.1e-11|2.9e+01| 3.706018e+01  8.314410e+00| 0:0:11| chol  1  1 
17|0.652|1.000|4.5e-12|2.9e-12|1.9e+01| 3.484752e+01  1.558909e+01| 0:0:12| chol  1  1 
18|0.479|1.000|2.3e-12|1.0e-12|1.4e+01| 3.320794e+01  1.904632e+01| 0:0:13| chol  1  1 
19|0.517|1.000|1.1e-12|1.0e-12|1.0e+01| 3.150533e+01  2.129196e+01| 0:0:13| chol  1  1 
20|0.720|1.000|3.2e-13|1.0e-12|6.8e+00| 2.955117e+01  2.279828e+01| 0:0:14| chol  1  1 
21|0.687|1.000|9.4e-14|1.0e-12|4.5e+00| 2.836813e+01  2.384265e+01| 0:0:15| chol  1  1 
22|0.646|1.000|3.3e-14|1.0e-12|3.3e+00| 2.765410e+01  2.437920e+01| 0:0:16| chol  1  1 
23|0.542|1.000|4.8e-14|1.0e-12|2.3e+00| 2.703918e+01  2.472423e+01| 0:0:16| chol  1  1 
24|0.634|0.830|1.0e-14|1.2e-12|1.6e+00| 2.644548e+01  2.487199e+01| 0:0:17| chol  1  1 
25|0.853|1.000|6.6e-14|1.0e-12|9.4e-01| 2.589774e+01  2.495966e+01| 0:0:18| chol  1  1 
26|0.718|1.000|1.6e-13|1.0e-12|7.1e-01| 2.571937e+01  2.500509e+01| 0:0:18| chol  1  1 
27|1.000|0.928|9.3e-14|1.1e-12|3.9e-01| 2.541629e+01  2.502754e+01| 0:0:19| chol  1  1 
28|1.000|0.894|1.4e-12|1.1e-12|1.7e-01| 2.521113e+01  2.504434e+01| 0:0:20| chol  1  1 
29|1.000|1.000|1.3e-13|1.0e-12|8.2e-02| 2.513290e+01  2.505124e+01| 0:0:21| chol  1  1 
30|1.000|1.000|1.1e-11|1.0e-12|1.4e-02| 2.506893e+01  2.505522e+01| 0:0:21| chol  1  1 
31|0.919|0.986|3.7e-11|1.5e-12|1.9e-03| 2.505785e+01  2.505593e+01| 0:0:22| chol  1  1 
32|1.000|1.000|2.0e-11|2.2e-12|1.7e-04| 2.505614e+01  2.505597e+01| 0:0:23| chol  2  2 
33|1.000|1.000|3.2e-11|3.4e-12|9.0e-06| 2.505599e+01  2.505598e+01| 0:0:24| chol  2  2 
34|1.000|1.000|1.8e-11|5.1e-12|2.1e-07| 2.505598e+01  2.505598e+01| 0:0:24| chol  2  2 
35|1.000|0.983|5.2e-11|1.6e-12|2.4e-08| 2.505598e+01  2.505598e+01| 0:0:25| chol  2  2 
36|0.929|0.985|9.0e-12|2.2e-13|3.1e-09| 2.505598e+01  2.505598e+01| 0:0:26| chol  2  3 
37|0.035|0.910|1.4e-11|2.2e-13|3.1e-09| 2.505598e+01  2.505598e+01| 0:0:26| chol  2  3 
38|0.157|0.919|1.5e-11|2.1e-13|3.1e-09| 2.505598e+01  2.505598e+01| 0:0:27|
  stop: progress is bad
-------------------------------------------------------------------
 number of iterations   = 38
 primal objective value =  2.50559824e+01
 dual   objective value =  2.50559824e+01
 gap := trace(XZ)       = 3.06e-09
 relative gap           = 5.98e-11
 actual relative gap    = 4.89e-11
 rel. primal infeas (scaled problem)   = 1.53e-11
 rel. dual     "        "       "      = 2.09e-13
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 4.3e+02, 3.4e+01, 1.0e+02
 norm(A), norm(b), norm(C) = 1.9e+05, 1.6e+04, 8.7e+01
 Total CPU time (secs)  = 26.91  
 CPU time per iteration = 0.71  
 termination code       = -5
 DIMACS: 3.1e-11  0.0e+00  7.7e-12  0.0e+00  4.9e-11  6.0e-11
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +25.056
 
minimum eig val = -9.980510e-01

Since the minimum eig val = -9.980510e-01 is negative, the positive semidefinite constraint is not satisfied. I am wondering if there are any problems with my code. Thanks so much if you have any suggestions.

Mark_L_Stone · March 26, 2023, 3:44am

That does look suspicious.

First of all, make sure you are using CVX 2.2, not CVX 3.0beta, which has many bugs, including incorrectly handling constraints.

Do not use cvx_precision best. No good will come of that. Some harm might come of that , although I doubt that explains the result.

Try a different solver. At least sedumi. If you have Mosek available try that, and see whether it issues any warnings.Because you haven’t shown us what A0 or ao are, or the optimal variable values, we have no idea whether there might be some very large values in the matrix being constrained to be psd, which if there were, could result in a big absolute min eigenvalue violation, even though the violation could be small relative to the matrix elements.

Dimakis · March 26, 2023, 3:28pm

Mark, thank you very much. I will try your suggestions.
In addition, SeDuMi can work properly. The minimum eigenvalue under SeDuMi is -1.449357e-09, and I guess the negative sign is from computational precision. However, SeDuMi takes like 20 minutes to terminate, while SDP3 takes less than 1 minute.

Update:

my cvx version is Version 2.2
removing “precision best” does not help.
Mosek can solve the problem in around 1 minute, and the semidefinite constraint holds (minimum eigenvalue = 1.088697e-10).

Mark_L_Stone · March 26, 2023, 3:44pm

Yes, -1.449357e-09 is within solver tolerance, and not indicative of anything going wrong in the solution process.

Something is going wrong with the SDPT3 result, but I don’t know what.

Dimakis · March 26, 2023, 6:08pm

Thank you, Mark.
Yes, there is something wrong with the SDPT3 solver.
Mosek can solve the problem properly in around 1 minute which is acceptable, and the semidefinite constraint holds (minimum eigenvalue = 1.088697e-10).

Mark_L_Stone · March 26, 2023, 6:13pm

To be fair, we don’t know the problem is with the SDPT3 solver, it could be with the CVX interface to it.

I suggest you open a new MATLAB session, reinstall CXX 2.2, and try again. Perhaps your MATLAB installation has a function conflicting with SDPT3’s version, but which does not cause an error message to be generated, but causes a wrong answer to be produced.