3
$\begingroup$

I have a question I hope you might be able to answer.

Let's say we have an integer program for the stable set problem (or clique, not principal).

\begin{equation} \begin{aligned} & \text{maximize} & \sum_i x_i \\ & \text{subject to} & \\ %& & \sum_{i \in C} x_i \leq 1 \text{ for all cliques } C\\ & & x_i+x_j \leq 1 \text { for } i,j \in E \\ & & x_i \in \{0,1\} \end{aligned} \end{equation}

One can use relaxation to obtain upper bounds like linear programming (LP) relaxation (relaxing integer variables to be in $[0,1]$) or using SDP relaxation (Lovasz)

\begin{equation} \begin{aligned} & \text{maximize} & \sum_i \sum_j X_{ij} \\ & \text{subject to} & \\ & & \mbox{tr} (X) = 1 \\ & & X_{ij} = 0 \text{ if } \{i,j\} \in E(G) \\ & &X \succ 0 \end{aligned} \end{equation}

Is there a nice direct proof that the value of the SDP relaxation above is always at most the value of the LP relaxation of the integer program?

Any help and thoughts will be greatly appreciated.

Edit: formal description

So let's say the stable set number is $\alpha(G)$, the value of linear relaxation is $z^*_{LP}$, and the value of SDP is $z^*_{SDP}$. The formal statement about "better" would be that $\alpha(G) \leq z^*_{SDP} \leq z^*_{LP}$ for every graph $G$.

$\endgroup$
  • 1
    $\begingroup$ SDPs are more general than LPs (think in terms of suitable diagonal matrices), which explains the claim. $\endgroup$ – Suvrit Aug 31 '16 at 1:25
  • $\begingroup$ Thanks for the answer. Actually it does not explain even a thing of it. SDP problems include LP problems, not a single doubt about it. The question was, why the value of the particular SDP above is always not greater than the value of the particular LP. Some people claiming that, so I'd like to hear thoughts/ideas why is that. $\endgroup$ – Eugene Sep 1 '16 at 20:20
  • $\begingroup$ The stable set integer program you give is incorrect. You forgot to say that the inequality constraint is only for when $i$ and $j$ are adjacent (same for the constraint in your SDP). Even if you add this, the LP relaxation of this program is boring because assigning $1/2$ to every vertex gives you $n/2$ which is a bad bound on the size of a stable set in most cases. You need the inequality to hold when summing over any clique. After these fixes the LP is equal to the fractional packing number $\alpha^*$ and the SDP is equal to Lov\'{a}sz $\vartheta$, and $\vartheta \le \alpha^*$ is well known $\endgroup$ – David Roberson Sep 1 '16 at 21:59
  • $\begingroup$ I was assuming it's clear the inequalities are for some set of $i,j$. The question becomes even more interesting when one can ask what about quadratic relaxations in general? People usually say they are way much better, however I haven't seen neat and tidy proof of these claims. So, that's the main objective after all. The problem above appears to be the best one studied so I hoped for any neat proofs or justifications. The problem with the cliques constraint is known to be very tight (for example for perfect graphs it's tight and Lov\'{a}sz is tight too). $\endgroup$ – Eugene Sep 2 '16 at 3:29
  • 1
    $\begingroup$ Well the answer is that yes, the SDP is always better because it is equal to Lovasz theta and the (current) linear program is equal to fractional packing number/fractional chromatic number of the complement and it is well known that Lovasz theta is less than or equal to fractional packing number for all graphs. However, I do not know a nice direct proof of this fact using these formulations of these two parameters, which is why I edited the question, because I think it would interesting to see such a proof. $\endgroup$ – David Roberson Sep 4 '16 at 12:16
1
$\begingroup$

The quickest proof I know uses a different (but equivalent) formulation of the above SDP. If I had to prove it using the above version I would probably first convert it the other one. Here is a rough sketch: Let $X$ be a solution to the SDP above, and let $D$ be the diagonal matrix with the entries of $X$ on its diagonal. Consider $Y = D^{-1/2}XD^{-1/2}$ and note that this is PSD with 1's on the diagonal and zero where $X$ was zero. Let $d$ be the vector of the square roots of the diagonal entries of $X$. Then $d^TYd = \sum_{i,j}X_{ij}$ and $d$ is a unit vector. So the max eigenvalue of $Y$ is at least the objective value of $X$. Since $Y$ is PSD, it is the Gram matrix of some (unit) vectors $v_1, \ldots, v_n$. The max eigenvalue of $Y$ is the same as that of the matrix $Z = \sum_{i} v_iv_i^T$. Let $c$ be a max eigenvector of $Z$ with eigenvalue $\mu$. If we assign the value $(v_i^Tc)^2$ to the vertex $i$, then this will be a feasible solution for the linear relaxation of the above integer program since on any clique the $v_i$ are a subset of some orthonormal basis and $c$ is a unit vector. Moreover, the value of this solution is equal to $\sum_{i} (v_i^Tc)^2 = c^TZc = \mu \ge \sum_{i,j} X_{ij}$. Thus the linear relaxation has greater value than the SDP.

As you can see, this is not so nice. At first I thought you could maybe prove that if you take any solution $X$ to the SDP, and then assign to vertex $i$ the sum of the $i^\text{th}$ row of $X$, that this would be a feasible solution to the linear relaxation. But this doesn't work (some row sums can be greater than 1). But maybe it works for optimal solutions to the SDP?

Another way to prove it is to consider a Gram factorisation $u_1, \ldots, u_n$ of a feasible solution $X$ to the SDP. So $X_{ij} = u_i^Tu_j$. Let $v_i$ be the unit vector parallel to $u_i$. Also let $c$ be the unit vector parallel to $\sum_i u_i$. Then assigning $(v_i^Tc)^2$ to vertex $i$ is a feasible solution to the linear relaxation, and its value is at least the objective value of $X$. This last part requires a proof which is part of the proof of Theorem 5 from Lovasz' original paper (http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1055985). There are a lot of other useful equivalent formulations of the above SDP in his paper. There is also a paper by Knuth about these things (http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1a1).

It would be nice to have a more direct proof than those above.

| cite | improve this answer | |
$\endgroup$
-3
$\begingroup$

I will also write my answer to the problem above based on my research.

The solution will involve several steps. I'll present the sketch here. Let me know if somebody is interested in more details.

Step 1. Write the MIP (or one can say just formulate the problem) as quadratic non-convex program. The one will have $x_ix_j=0$ instead of $x_i+x_j \leq 1$ in MIP and $x_i(1-x_i)=0$ to enforce belonging to $\{0,1\}$ set.

Step 2. Perform the SDP relaxation of the quadratic program. One can try to look for Wolkovicz and Poljak papers. The basic idea is to define new variables $X_{ij} = x_ix_j$ and than relax the constraint $X = xx^T$ to $X \succ 0$ (I'm skipping details, but that's the usual trick).

Step 3. By Wolkovicz and Poljak, and this is the only step which I believe should be verified carefully, the value of Lagrangian Dual Relexation for non-convex QP is equal to SDP.

Step 4. Prove that the value of the Lagrangian Dual Relaxation is not greater than the value of LP relaxation. This is the homework problem for a math class. The idea is to write the Lagrangian estimate and then for example for 0-1 constraint in QP $x_i(1-x_i)=0$ say let's enforce dual multipliers to be only positive. This will correspond to a QP with constraint $x_i(1-x_i)\leq0$ or $x_i \in [0;1]$.

If anyone has any thoughts, I'd be more than pleased to hear them.

Thanks.

Edit: Ok for step 4 there is a special step too (still pretty technical). You add the redundant constraint to QP $(x_i +x_j)^2 - (x_i + x_j) = 0$ and then with the same idea described in the step 4 above you get desirable $x_i + x_j \leq 1$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.