global optimal of a MISDP

[Ach T]

Hello Johan,

I have posed the following problem:
______________________________________

x = binvar(N,1) ;
con = G ;
constraint = [ ] ;
sdpvar z
obj = z ;

for i = 1:N    
      con = con + ( x(i,1) * f(i).Gi  ) ; 
end

constraint = [ constraint, (con'+con)/2 <= (z*eye(2*N)) ] ;
constraint = [ constraint, (con'+con)/2 >= eye(2*N) ] ;
constraint = [ constraint, sum(x) <= 12 ] ; 

sdpsettings('solver','bnb','bnb.solver','sedumi') ;
optimize(constraint, obj, sdpsettings)
___________________________________________________

where practically I am trying to minimize the max eigenvalue z of the matrix ´con´ choosing a specific number of group of the elements `f(i).G´ !
The problem is a MISDP (convex) but because the variable ´x´ is binary is a combinatorial one, correct ?

I would like to ask if the ´bnb´method with the solver sedumi is going to give a global optimal.

Thank you in advance !

[Johan Löfberg]

Yes, it is a mixed-integer SDP, so basically only solvable if it is really small, or if you are lucky

The possible options are bnb + sdp solver (sedumi etc, although mosek is preferred), or cutsdp + milp solver (such as mosek)

https://yalmip.github.io/cutsdpsolver

[Ach T]

Thanks !

So, any chance to have the global optimal with this solvers ?

[Johan Löfberg]

They are global yes. But as always with these problems, you might have to wait until the universe collapses until it has finished.

[Ach T]

Thank you,

In general, I have small size problems, so I don´t have comptational time issues.

Thanks again !