SDPT3 fails in apparently simple problem


(Jesús Briales García) #1

Hi everyone, I’m experiencing some numerical problems
when using the SDPT3 solver for a (apparently) fairly simple SDP problem.

The problem under consideration is
$$ \min_X tr(MX), ; s.t. X\succcurlyeq0, X(end,end) = 1 $$

This problem is just the lifted relaxation of
$$ \min_\tilde{x} \tilde{x}^\top M \hat{x}, ; s.t. \tilde{x}(end)^2=1 $$
which in turn corresponds to a simple Least Squares (linear) problem:
$$ min_x ||A x - b|| $$

Obviously, this is just a testing problem before proceeding to the relaxation
of a more complex one which is not a Least Squares problem.

The curious fact is that Sedumi is working well, but SDPT3 fails to converge.
I know I should just stick with the solver working (it’s what I usually do)
but since this seems (to me) like a very simple problem
I was a little surprised that the usual SDP solvers could have any difficulty with it.
Furthermore, I’m concerned that I might be missing part of the complexity of the problem
since this could become the source of many headaches when things don’t work
in the more complex problem extending this one.

I’ve tried looking for some theoretical background that may
explain in which situations a SDP problem could get ill-conditioned
or something related, but couldn’t find anything straightforward
in the context of this specific model.
I would appreciate if any of the experts here
could share their impressions about this :slight_smile:

Just to do some simple tests, I’m providing a simple test code:

% generate positive semidefinite matrix
m = 10;
n = 3;
A = randn(m,n);
b = randn(m,1);
M = [A,-b]'*[A,-b];
cvx_solver SDPT3
% cvx_solver sedumi
% cvx_precision low
cvx_begin SDP
variable X(n+1,n+1) semidefinite
X(end,end) == 1
minimize(trace(M*X))
cvx_end

It seems sometimes (rarely) the SDPT3 solver worked,
but in general any random problem will fail.
You can easily check that apparently there are no conditioning
issues with the data matrix M.
I tried different precisions, by the way.


(Mark L. Stone) #2

I did not duplicate your experience.

I ran 1000 random instances in both SDPT3 and SeDuMi using the same A and b for each SDPT3 and SeDumI pair. All instances were solved by both solvers, with maximum absolute value of the difference in cvx_optval between SDPT3 and SeDuMi of 4.4e-7 over the 1000 instances.

CVX version 2,.1 build 1113 running under MATLAB R2014A WIN64.


(Jesús Briales García) #3

Ok,
I forgot to share information on my version too!
Currently, it’s:
Version 2.1, Build 1110 (66e9a9c) Wed Jun 10 21:43:38 2015
Under MATLAB R2015b Linux64

I tried to download the last one, which is build 1113 (the same you used)
and it still didn’t worked! Same behavior as with build 1110.

Then I also tried to download an independent version of SDPT3
from the official webpage and calling it from CVX as an additional solver.
In this case, the SDPT3 solver worked fine!!

So, in conclusion, either there is some strange conflict within my own CVX library,
or there is something wrong in the Linux version I’m working with…
But it’s strange as it didn’t work with the clean installation with the newest version either.

This is the (cropped) screen output just in case it could give any hint:

Calling SDPT3 4.0: 10 variables, 1 equality constraints
------------------------------------------------------------

 num. of constraints =  1
 dim. of sdp    var  =  4,   num. of sdp  blk  =  1
*******************************************************************
   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|4.5e+00|1.4e+00|1.4e+03| 5.194500e+02  0.000000e+00| 0:0:00| chol 
  linsysolve: Schur complement matrix not positive definite
  switch to LU factor. lu 30  30 
 1|1.000|1.000|2.2e+00|5.8e-03|1.2e+02| 1.206473e+02  0.000000e+00| 0:0:00| lu 30  30 
...
100|0.999|1.000|5.0e-01|0.0e+00|1.1e-192| 1.074255e-192  0.000000e+00| 0:0:02|
  sqlp stop: maximum number of iterations reached
-------------------------------------------------------------------
 number of iterations   = 100
 primal objective value =  1.43324924e-02
 dual   objective value =  0.00000000e+00
 gap := trace(XZ)       = 1.43e-02
 relative gap           = 1.41e-02
 actual relative gap    = 1.41e-02
 rel. primal infeas (scaled problem)   = 5.00e-01
 rel. dual     "        "       "      = 5.83e-05
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 1.4e-03, 0.0e+00, 3.3e+01
 norm(A), norm(b), norm(C) = 2.0e+00, 2.0e+00, 3.4e+01
 Total CPU time (secs)  = 1.57  
 CPU time per iteration = 0.02  
 termination code       = -6
 DIMACS: 5.0e-01  0.0e+00  1.3e-04  0.0e+00  1.4e-02  1.4e-02
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Failed
Optimal value (cvx_optval): NaN
 

(Mark L. Stone) #4

Some semi-random links to look at:

Perhaps this is a bug in SDPT3 which maybe you get away with or not depending on the exact configuration?


(Jesús Briales García) #5

Thanks for the links!
Well… it’s difficult to know what it could be from so little practical cases.
However, the comment in the Github issue by Johan Löfberg is quite worrying
as this means plenty of bad behavior might occur without any kind of feedback,
discouraging the use of SDPT3 in newer versions of Matlab?


(Mark L. Stone) #6

I’ve had better “luck” with SeDuMi than SDPT3 (and I haven’t used a newer version of MATLAB than R2014A). Your mileage (that’s American slang) may vary. I use SDPT3 mainly as a back up solver.


(Royi) #7

@mcg,

Does the current CVX uses the latest SDPT3?

It seems they made a very recent compatibility fix.


(Michael C. Grant) #8

I’ve experimented with the latest version, but haven’t updated it. It does indeed improve compatibility with later versions of MATLAB but it does not solve any numerical issues.