Help with relaxed SDP formulation and bounds on the optimal solution.

[Jack]

I would like to relax the following binary SDP problem

$$ \max_{A,x_i,y_i} \ trace(A) $$
$\quad \qquad \qquad $ subject to:
$$ A + \sum_{i=1}^N x_i D_i + \beta \sum_{i=1}^M y_i D_i \preceq \alpha .I $$
$$ A = A^T \succ 0 $$
$$ (x_i,y_i) = \{0,1\},  $$
$$ y_i \geq x_i, \  $$
$\ {\rm{for}} \ (i = 1,\dots,k)$, $0 \leq \beta \leq 1$ and $N\leq M \leq k$. $D_i=D_i^T \succ 0$ and  $\alpha \in \mathbb{R}$ given. I am hoping that the first constraint is an LMI hence I am calling this a binary-SDP.

I know that the binary constraints may be expressed as
$$x_i(x_i-1)=0 $$
$$y_i(y_i-1)=0 $$
if this helps, e.g., if Lagrangian dualization may be needed?

Any help would be much appreciated to formulate the relaxed version of this, along with a bound on the "closeness of the relaxed solution to the binary problem", e.g., if this can be cast in the max-cut formulation. Thanks.

[Jack]

This is a better version of the above:
http://math.stackexchange.com/questions/1870229/relaxation-of-boolean-sdp-and-optimality-bounds

I would sincerely appreciate any help on this!

[Johan Löfberg]

If you simply want to solve the SDP relaxation, send the model to YALMIPs relaxation solver solvemoment It will derive an SDP relaxation (the first order relaxation is simply to add the constraint  [1 x;x 1]>=0 and [1 y;y 1]>=0)

[Johan Löfberg]

should be [xi xi;xi 1]>= etc of course

[Johan Löfberg]

the first order relaxation is probably stronger, as the first moment matrix will be the relaxation of [1;x;y]*[1 x' y'], i.e, treating each variable independantly is probably sub-optimal. With the LMI, you can multiply that with terms x_i or y_i, and get additional SDP cuts. Problem will grow huge fast though

[Jack]

Thank you very much for your reply. Just to clarify, do you mean to replace the quadratic binary constraints with the schur complements, i.e.,
[xi xi;xi 1]>= 0
[yi yi;yi 1]>= 0
?
What do you mean by the first moment relaxation? Sorry, I am not too familiar with this.

Is it possible if you can advise as to how I can get some analytical bounds on the closeness of the relaxed solution to the true one, e.g., can this be put in anyway in the max cut formulation or can I derive it some way? Will the knapsack problem help, i.e., if there are bounds for this? Kind of stuck on this -- I really need an analytical bound.....I am free to adjust my objective function if it helps. Thanks again.

[Johan Löfberg]

Complete example, assuming x and y are scalars with

[1+x+y  x-y;x-y 2]>=0
y>=x
x^2=x, 0<=x<=1 (added to strengthen)
y^2=y, 0<=y<=1

Moment matrix 

[1 x   y;
 x x^2 xy
 y xy y^2]

Relaxation variables u v w relaxations of x^2, y^2 and xy, hence first order relaxation starts with

[1+x+y  x-y;x-y 2]>=0
u == x
v == y
[1 x y;
 x u w
y w v]>=0

However, as the constraints are linear, we can localize, e.g.

y-x>=0 and x>=0 means y*x-x^2>=0 i.e w-u>=0

LMI can also be localized

[1+x+y  x-y;x-y]>=0 and x>=0 means [x+x^2+xy x^2-xy;x^2-xy 2x]>=0 i.e. [x+u+w u-w;u-w 2x]>=0

There are loads of these (possibly) strengthening cuts if you've added 0<=x<=1 and <=y<=1 (and solvemoment will add these)

[Jack]

Hi,

Thank you for this...it really helps. You added the continuous 0<=x<=1 and 0<=y<1 constraints and said something about strengthening? I am not too familiar with this...can you kindly a bit elaborate on this? Also, when you do the localization step, is it ok if I instead choose to multiply each term of the LMI with y instead of x since y >= 0?

Finally, if I were to maximize this problem, then, I am hoping that the resulting relaxed solution would be an upper-bound to the 0/1-combinatorial one? Is this correct? Can you kindly suggest if there may be some ways for me to get a bound on how far the relaxed solution would be from the true combinatorial one, for my problem? For example, can I get some sort of rounding....as in the case of max-cut, i.e., the 2/pi bound? I really need the latter, analytically. Thank you again.

[Johan Löfberg]

If you have constraints g(z)>=0 and h(z)>=0, the constraint g(z)*h(z)>=0 is redundant, but the relaxation of the set {g(z)>=0, h(z)>=0, g(z)*h(z)>=0} might be a tighter relaxation of the original set, than the relaation of {g(z)>=0, h(z)>=0}. Localization is of course done with all combinations of constraints generally, I just gave an example

A relaxation will give you an upper bound when you maximize Actually extracting a solution if the relaxation is tight, or a sub-optimal from the relaxation, is another thing, might be impossible in some cases, and derivng an approximation guarantee is a reasearch topic

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.MomentRelaxations