Interpretation of Dimacs

[Luuk LeLe]

Hello,

I am busy optimizing over the semidefinite cone, or more precisely over the semidefinite plus nonnegative cone and I have been getting some answers I do not understand. In short I have a matrix M which is comprised of several matrices containing a number of variables (e.g. the kronecker product of S (the variables) and the identity I). I am then trying to find a matrix M which is semidefinite plus nonnegative and has another linear constraint that wants some linear 'objective function' to be larger or equal to 0.5.

That is it looks something like

Max 1
s.t. M(x) - K semidefinite
      K >= 0
      f(x) >= 0.5

The constraint K>=0 btw has been formulated as

F = [F, triu(K0) >= 0];

due to the K0 >= 0 being a semidefinite constraint if I am correct.

I tried a 'small' example where M is of size 144x144. This got solved by SDPT3 with no problems. But now I moved on to bigger examples and I keep getting output that looks like this.

 num. of constraints = 65722
 dim. of sdp    var  = 361,   num. of sdp  blk  =  1
 dim. of linear var  = 65342
 number of nearly dependent constraints = 1
 To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 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|7.3e+004|7.0e+002|6.1e+009| 2.880652e+005  0.000000e+000| 0:0:31|
ans =

    yalmiptime: NaN
    solvertime: NaN
          info: [1x138 char]
       problem: 9
        dimacs: [NaN NaN NaN NaN NaN NaN]

I think I solved the smaller one on matlab2013, whereas the later larger examples were tried on a different computer that has matlab2009b (don't know if this could influence anything). I also tried sedumi and then on advice from someone else BMIBNB. I get similar output using these solvers.

What does this mean? Is the problem infeasible? is something wrong with the formulation of the problem? How am I to interpret this?

Any help would be appreciated! If any extra information would be needed please let me know.

[Johan Löfberg]

First, the title has nothing at all to do with the question.

Secondly, you most be using an old version of YALMIP since the dimacs no longer are returned by default (since they never are used or understood)

Third: BMIBNB. No idea why anyone would suggest that. It is a solver for global nonconvex optimization

Fourth. You should look at the field info in the output. Most likely it says memory issues. Or turn on the debug flag through sdpsettings. Problem code 9 means  "Unknown problem in solver" (see yalmiperror)

However, your main question regarding proving co-positivity using semidefinite programming. Since I don't know what f(x) is, or what the dimension of x is compared to the size of M, I'll answer an even easier question

How can I efficiently prove co-positivity of the constant matrix M by decomposing it as N+P where N is non-negative and P is positive semidefinite?

Short answer: You cannot. This class of semidefinite problems is known to scale poorly.

Long answer. The problem can be formulated in various ways. The most obvious would be

M == N + P

Nij >= 0 i<=j

P psd

This is, when interpreted as a representation of standard primal form, a problem with n(n+1)/2 equalities, one SDP constraint of size n, and n(n+1)/2 LP cones. Very bad, since a quadratic number of equalities, corresponding to a quadratic number of dual variables, means the line searches etc will have n^6 complexity (solving for the Hessian which is of size n^2 etc). Horrible.

So can we do better. Not really. An obvious step is to eliminate the cone representation P, and simply write it as

M-N psd

Nij >= 0 i<=j

This can be interpreted as a model in standard dual form if we assume N is parameterized by its elements, i.e, these are the variables in the dual..Hence, it has n(n+1)/2 variables in the dual, one SDP constraint of size nxn and n(n+1)/2 LP constraints. Yep, this is exactly the same complexity as the representation as above. In other words, the co-positive formulation has as bad complexity despite how you try to model it (in contrast to e.g. maxcut which is very efficient when looked upon as a problem in standard primal form, but horribly bad when mistakingly modeled from a dual point of view with explicit parameterization of a big matrix.

To conclude, 144x144 is simply not that small for these models. To solve problems involving the intersection of the SDP cone and the non-negative orthant, you need a dedicated solution strategy. Standard SDP solvers do not scale gracefully.