Dual Infeasibility to solve SOS

[HSS]

Hi,

I am currently trying to use Yalmip with the solver mosek to solver a SOS optimization problem. However, I am currently facing a dua infeasibility problem. As I am not a specialist on SOS optimization I decided to seek for more advice in this forum.

Below, I provide the minimal working example:

x = sdpvar;
y = sdpvar;


t = monolist([x;y],2);
M = rand(length(t));
M = M'*M;
eig(M)


p_x = t'*M*t;


t1 = monolist(x,2);
t2 = monolist(y,2);
Q = sdpvar(length([t1;t2]));
p_y = [t1;t2]'*Q*[t1;t2];


Constraints = [Q>=0;coefficients(p_x-p_y,[x,y])==0];
Options = sdpsettings('solver','mosek','verbose',1);
Objective = norm(Q-M,'fro');
DiagnosticMI = optimize(Constraints,Objective,Options);

Running this program (on Matlab 2015b), I obtain the following output

MOSEK Version 7.1.0.53 (Build date: 2016-5-11 17:32:32)
Copyright (c) 1998-2016 MOSEK ApS, Denmark. WWW: http://mosek.com
Platform: Windows/64-X86


Computer
  Platform               : Windows/64-X86  


Problem
  Name                   :                
  Objective sense        : min            
  Type                   : CONIC (conic optimization problem)
  Constraints            : 22              
  Cones                  : 1              
  Scalar variables       : 52              
  Matrix variables       : 1              
  Integer variables      : 0              


Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator - tries                  : 0                 time                   : 0.00            
Eliminator - elim's                 : 0              
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0              
Presolve terminated. Time: 0.00    
Interior-point optimizer terminated. Time: 0.00.




MOSEK DUAL INFEASIBILITY REPORT.


Problem status: The problem is dual infeasible
Optimizer terminated. Time: 0.00    


Interior-point solution summary
  Problem status  : DUAL_INFEASIBLE
  Solution status : DUAL_INFEASIBLE_CER
  Primal.  obj: -2.4788969501e+000  Viol.  con: 0e+000   var: 0e+000   barvar: 0e+000   cones: 0e+000
Optimizer summary
  Optimizer                 -                        time: 0.00    
    Interior-point          - iterations : 0         time: 0.00    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
        Clean primal-dual   - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
      Primal-dual simplex   - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00

Does someone would know the reason for dual infeasibility?

Kind regards,

[Johan Löfberg]

It's infeasible as you're trying to enforce some constant non-zero numbers to be equal to 0

>> sdisplay(coefficients(p_x-p_y,[x,y]))

ans = 

    '1.825530839-Q(1,1)-2*Q(4,1)-Q(4,4)'

    '2.734724775-2*Q(5,1)-2*Q(5,4)'

    '4.14812165-2*Q(6,1)-2*Q(6,4)-Q(5,5)'

    '2.602265749-2*Q(6,5)'

    '1.178725704-Q(6,6)'

    '2.841212022-2*Q(2,1)-2*Q(4,2)'

    '7.578565571-2*Q(5,2)'

    '6.603986994-2*Q(6,2)'

    '3.389900506'

    '5.122595068-2*Q(3,1)-Q(2,2)-2*Q(4,3)'

    '7.216932875-2*Q(5,3)'

    '4.916315274-2*Q(6,3)'

    '2.477784465-2*Q(3,2)'

    '3.352384106'

    '1.69212821-Q(3,3)'

[Joachim Dahl]

Please upgrade to MOSEK 8.0, if possible.  The SDP solver is much better in that version.

[Johan Löfberg]

Agree.

But just so the original poster doesn't misunderstand anything: The problem is trivially infeasible, and upgrading the solver will not help.

[Erling Andersen]

Indeed it is dual infeasible because the solution summary shows a perfect certificate is computed.

[Johan Löfberg]

Yes, finding out that 3.389900506 == 0 is infeasible should probably not be to numerically demaning

[HSS]

Thank you all for the discussion.