Stuck at edge of primal feasibility for small problem with one 3x3 matrix

[blegat]

I have found a small problem for which CSDP has issues with:

4
1
3
0.0 0.0 0.5 1.0
0 1 2 1 0.5
0 1 3 1 0.5
1 1 3 2 0.5
2 1 2 2 1.0
2 1 3 3 -1.0
3 1 1 1 1.0
4 1 2 2 0.5

The output is

CSDP 6.2.0
Iter:  0 Ap: 0.00e+00 Pobj:  0.0000000e+00 Ad: 0.00e+00 Dobj:  0.0000000e+00 
Iter:  1 Ap: 1.00e+00 Pobj:  1.7935973e-01 Ad: 1.00e+00 Dobj:  5.9340336e+01 
Iter:  2 Ap: 1.00e+00 Pobj:  1.9555776e-01 Ad: 1.00e+00 Dobj:  2.9776045e+01 
Iter:  3 Ap: 1.00e+00 Pobj:  2.9239941e-01 Ad: 1.00e+00 Dobj:  1.5082642e+01 
Iter:  4 Ap: 1.00e+00 Pobj:  6.4550917e-01 Ad: 9.00e-01 Dobj:  2.0892201e+00 
Iter:  5 Ap: 1.00e+00 Pobj:  1.2902364e+00 Ad: 1.00e+00 Dobj:  2.0120906e+00 
Iter:  6 Ap: 1.00e+00 Pobj:  1.3116437e+00 Ad: 1.00e+00 Dobj:  1.6725694e+00 
Iter:  7 Ap: 1.00e+00 Pobj:  1.4141438e+00 Ad: 9.00e-01 Dobj:  1.4399840e+00 
Iter:  8 Ap: 1.00e+00 Pobj:  1.4099274e+00 Ad: 1.00e+00 Dobj:  1.4228462e+00 
Iter:  9 Ap: 1.00e+00 Pobj:  1.4120666e+00 Ad: 1.00e+00 Dobj:  1.4185247e+00 
Iter: 10 Ap: 1.00e+00 Pobj:  1.4142136e+00 Ad: 9.00e-01 Dobj:  1.4146423e+00 
Iter: 11 Ap: 1.00e+00 Pobj:  1.4142136e+00 Ad: 1.00e+00 Dobj:  1.4142110e+00 
Stuck at edge of primal feasibility, giving up. 
Partial Success: SDP solved with reduced accuracy
Primal objective value: 1.4142136e+00 
Dual objective value: 1.4142111e+00 
Relative primal infeasibility: 6.90e-14 
Relative dual infeasibility: 4.77e-07 
Real Relative Gap: -6.47e-07 
XZ Relative Gap: 2.90e-17 
DIMACS error measures: 7.30e-14 0.00e+00 6.36e-07 0.00e+00 -6.47e-07 2.90e-17

[jerviedog]

I am learning optimization, so I don't know what the result mean.

But the csdp result said it solved your problem. Here is the output:

csdp input.txt

CSDP 6.2.0
Iter:  0 Ap: 0.00e+00 Pobj:  0.0000000e+00 Ad: 0.00e+00 Dobj:  0.0000000e+00 
Iter:  1 Ap: 1.00e+00 Pobj:  2.5000000e-01 Ad: 1.00e+00 Dobj:  3.5599997e+01 
Iter:  2 Ap: 1.00e+00 Pobj:  4.9431970e-01 Ad: 9.00e-01 Dobj:  4.0048851e+00 
Iter:  3 Ap: 1.00e+00 Pobj:  1.2559060e+00 Ad: 1.00e+00 Dobj:  3.0111874e+00 
Iter:  4 Ap: 1.00e+00 Pobj:  1.2032799e+00 Ad: 1.00e+00 Dobj:  2.0809193e+00 
Iter:  5 Ap: 1.00e+00 Pobj:  1.2948698e+00 Ad: 1.00e+00 Dobj:  1.7336882e+00 
Iter:  6 Ap: 1.00e+00 Pobj:  1.3483481e+00 Ad: 1.00e+00 Dobj:  1.5677560e+00 
Iter:  7 Ap: 1.00e+00 Pobj:  1.3795159e+00 Ad: 1.00e+00 Dobj:  1.4892185e+00 
Iter:  8 Ap: 1.00e+00 Pobj:  1.3964008e+00 Ad: 1.00e+00 Dobj:  1.4512508e+00 
Iter:  9 Ap: 1.00e+00 Pobj:  1.4051896e+00 Ad: 1.00e+00 Dobj:  1.4326133e+00 
Iter: 10 Ap: 1.00e+00 Pobj:  1.4142136e+00 Ad: 9.00e-01 Dobj:  1.4160512e+00 
Iter: 11 Ap: 1.00e+00 Pobj:  1.4139070e+00 Ad: 1.00e+00 Dobj:  1.4148245e+00 
Iter: 12 Ap: 1.00e+00 Pobj:  1.4140602e+00 Ad: 1.00e+00 Dobj:  1.4145177e+00 
Iter: 13 Ap: 1.00e+00 Pobj:  1.4142136e+00 Ad: 9.00e-01 Dobj:  1.4142416e+00 
Iter: 14 Ap: 1.00e+00 Pobj:  1.4142125e+00 Ad: 1.00e+00 Dobj:  1.4142137e+00 
Iter: 15 Ap: 1.00e+00 Pobj:  1.4142135e+00 Ad: 1.00e+00 Dobj:  1.4142136e+00 
Iter: 16 Ap: 1.00e+00 Pobj:  1.4142136e+00 Ad: 9.00e-01 Dobj:  1.4142136e+00 
Success: SDP solved
Primal objective value: 1.4142136e+00 
Dual objective value: 1.4142136e+00 
Relative primal infeasibility: 2.35e-16 
Relative dual infeasibility: 1.31e-09 
Real Relative Gap: 1.78e-09 
XZ Relative Gap: 3.56e-09 
DIMACS error measures: 2.49e-16 0.00e+00 1.75e-09 0.00e+00 1.78e-09 3.56e-09
Elements time: 0.004010 
Factor time: 0.000036 
Other time: 0.065974 
Total time: 0.070020 

[blegat]

It may depend on the system in which you are running it. On my system (64-bit ArchLinux), I installed the coin-or-csdp ArchLinux package which uses the lapack ArchLinux package.
As you can see in my initial post, I get the status

Stuck at edge of primal feasibility, giving up. 
Partial Success: SDP solved with reduced accuracy

[jerviedog]

But your primal-dual gap was quite small though.

[blegat]

Indeed, it is quite small but the status indicates that it could not get it smaller which is surprising for such a simple problem. It might indicate something wrong in the implementation of CSDP and as the problem is quite simple, I thought it would provide a nice minimal reproducing example for chasing the bug.

[jerviedog]

FYI:
My compilation process was:

1. modified the Makefile:
   export CFLAGS=-m64 -march=native -mtune=native -Ofast -fopenmp -ansi -Wall -DBIT64 -DUSEOPENMP -DSETNUMTHREADS -DUSESIGTERM -DUSEGETTIME -I../include
   export LIBS=-L../lib -lsdp -Wl,--no-as-needed -lmkl_intel_lp64 -lmkl_intel_thread -lmkl_core -liomp5 -lpthread -lm -ldl

2. make:
   make -j4
   make unitTest

Maybe you could try to link to different LIBS?

[blegat]

Thanks for sharing. It might be thanks to the use of intel MKL but this test is used to check the implementation of the MOI interface on Travis. I don't think we can use intel MKL on travis.

[siko1056]

Does this problem still persist for you @blegat ? I solved your problem on OpenSUSE 15.1 using CSDP with the systems reference BLAS, a self compiled OpenBLAS, and lntel_mkl_2019.4.243. SeDuMi and SDPT3 can compute the solution as well. All seems to work as described in the second comment. There is no bug to chase in this repository, more in the way ArchLinux builds it with it's dependencies, I think.

The problem is feasible and the optimal primal solution is

    [     1/2       1/sqrt(2)   1/sqrt(2) ]
X = [ 1/sqrt(2)       2           0       ]
    [ 1/sqrt(2)       0           2       ]

with optimal value sqrt(2).