"Solver not applicable" error using SDPT3 and CPLEX from YALMIP

[Seebach Erstrasse]

Hello all,

I am using YALMIP in the course of developing hybrid MPC controllers based on SDP and QP relaxations of MIQPs.

I wrote 2 codes, one with QP relaxation, the other with SDP. The codes are 99% the same, and they are parameterized wrt prediction horizon in terms of cycles N_cycle.

This is because intersampling is used in the MPC, in which the MPC runs every M samples (M=cycle length in terms of samples), but its prediction horizon is N=N_cycle*M.

In my case, I am using N_cycle=2 and M=5, so the MPC is solving a 10 step problem.

The optimization variable is the control sequence u, u=sdpvar(3*N,1), and 3 because there is 1 continuous and 2 binary components for every step.

The only difference between the 2 codes is that:

In the QP relaxation the integer constraint on controls is relaxed to 0<=u_i<=1 where i denotes the index of binary controls.

Whereas in the SDP relaxation [U_SDP u;u' 1]=>0 and U_SDP(i,i)==u_i where i the same as before, and U_SDP=sdpvar(3*N,3*N). 

The notation can be found on page 235 of 251 from the PhD thesis of Daniel Axehill, at http://liu.diva-portal.org/smash/record.jsf?pid=diva2:17358. On page 219 of 251 

in the same thesis it is proven that the feasible sets for QP and SDP relaxations are the same, so losing feasibility etc when using SDP instead of QP is not an issue.

My problem here is that I want to run the MPC for longer horizons to compare the solution times of the 2 relaxations. The QP relaxation (solver quadprog) works without any

problems at all for virtually any N_cycle (I tried 3,4,5,15). 

Where it gets interesting is that both QP (solver cplex) and SDP (solver sdpt3) only work for N_cycle=1 or 2, with 3 YALMIP 

gives these error:

    solvertime: 0

          info: 'Solver not applicable (cplex)'

       problem: -4

    yalmiptime: 0.094999999999999

and

    solvertime: 0

          info: 'Solver not applicable (sdpt3)'

       problem: -4

    yalmiptime: 0.148000000000000

for the QP and SDP relaxation based MPC codes, respectively.

If the QP (with quadprog) also did not work for N_cycle=>3, I would guess that there is a problem regarding the parameterization of the code wrt N_cycle, but since it works, I

cannot track down the issue. If anybody has any ideas as to where I should look at, I would be very grateful. Any help will be tremendously appreciated.

General note: By "working" of the SDP code above I mean giving a meaningful output that can be applied to the controlled system. sdpt3 always gives some "numerical errors" or

"lack of progress" type errors, but since it gives a good enough output that manages to control the system, I disregard these. Side question: Can the positive semidefinite matrix variable U_SDP

(in the SDP relaxation code) that is output by sdpt3 as the solution having a terrible condition number (ratio of the largest to the smallest singular value) of 1e13 have anything to do with this?

I am sorry for my long question, and will be very happy to hear any comments or ideas. Thanks a lot in advance.

[Adkitta]

Quick reply regarding the SDP relaxation, try using 

U_SDP>=1e-8*eye(3*N)

instead of the strict condition. You may have to tweak the tolerance (here, 1e-8) for your problem. Also, you can try SeDuMi as the solver.

[Johan Löfberg]

Most likely, you are creating a quadxratic objective function which isn't convex (positive semidefinite). quadprog does not care about this, it works also for indefinite and negative definite problems (returning local soluttions only of course) whereas CPLEX only allows positive semidefinite quadratics, and the same when you use sdpt3 (since it has to be factored to a norm expression)

Note, you can easily generate models which are positive semidefinite in theory, but are indefinite in practice due to numerical tolerances. The following quadratic term is trivially positive semidefinite (this would arise when using (x1+x2+x3+...+xn)^2) but is indefinite in practicve

>> r = ones(1,10)*1000;
>> min(eig(r'*r))
ans =

  -1.2166e-09

YALMIP has some internal tolerances to clean up slightly indefinite quadratics, but in a case such as the one above, it would not do that (since 1e-9 is a relatively large number)

Without code, I cannot give any more specific help.

[Johan Löfberg]

There are no strict conditions here so I don't understand why you would propose this. Adding a lower bound on the eigenvalues would only force the solution away from the exact solution if the relaxation is tight (then the matrix must be rank-1, i.e., smallest eigenvalue 0)

[Seebach Erstrasse]

Thanks a lot for the help and comments, Adkitta and Johan Löfberg.

Your comment was spot on, Dr. Löfberg, I appreciate it tremendously, thanks a million.

After your remark, I realized that for the optimization problem MPC solves, with cost J=u^T*Qu*u+P*u, my code was indeed building 

the Qu matrix such that some of its eigenvalues are slightly negative, thus it is indeed slightly indefinite-negative definite.

For N_cycle=2, the negative eigenvalue pair with the largest abs value is -1.082e-11+-1.07e-11i, so as you

said YALMIP was, I think, taking care of these with internal tolerances. But for N_cycle=3, the pair is -3.187e-11+-35.38e-11i, and

it gets worse with increasing N_cycle, the worst case I saw being N_cycle=9, where the pair is -1949.063e-11.

Anyway, in the formulation of Qu, for the terminal state weight P, I was using P=dlyap(A^T,B). I switched to using

P=dlqr(A^T,B,Q,R), and the problem disappeared, It now seems to work even for N_cycle=5, albeit it takes lots of time.

The worst negative pair for N_cycle=5 is -1.25e-17+-8.3e-18i, so I guess these do not harm the convexity of the cost function.

[Adkitta]

I take back my comment as it doesn't apply to this case.