Given the boolean LP:
$$\text{Minimize}\;\; c^Tx$$
$$\text{Subject to}\;\; Ax \leq b$$
$$\hspace{57mm} x_i(1-x_i)=0\;\; i=1,…,n$$
Show that the LP relaxation:
$$\text{Minimize}\;\; c^Tx$$
$$\text{Subject to}\;\; Ax \leq b$$
$$\hspace{51mm} 0\leq x_i\leq1\;\; i=1,…,n$$
and the Lagrange relaxation:
$$\text{Maximize}\;\; g(\lambda,v)=\inf_x\Big(c^Tx + \lambda^T(Ax-b) + \sum_{i=1}^nv_ix_i(1-x_i)\Big)$$
$$\text{Subject to}\;\; \lambda \geq 0$$
give equivalent lower bounds on the boolean LP.
My method is to first rewrite the LP relaxation's second constraint as $-x_i(1-x_i)\leq0$, and then to show that its dual can be written as:
$$\text{Maximize}\;\; g(\lambda,v)=\inf_x\Big(c^Tx + \lambda^T(Ax-b) + \sum_{i=1}^nv_ix_i(1-x_i)\Big)$$
$$\text{Subject to}\;\;\lambda\geq0, v \leq 0$$
Since the Lagrange relaxation and the dual of the LP relaxation maximize the same function, with the only difference being the latter has a smaller domain, we can immediately conclude that the Lagrange relaxation is greater than or equal to the dual of the LP relaxation.
What I would like to do is show that they are equal, and then use Slater's condition on the LP relaxation and its associated dual to show strong duality holds, thus proving that both relaxations give identical lower bounds. However I have not been able to prove that they are equal.
I tried finding the value of $x$ as a function of $(\lambda, v)$, but seemed to be getting a resulting function $g(\lambda, v)$ which wasn't concave, which doesn't make sense, can someone help me out with this?
Best Answer
$g(x, \lambda, v)$ as a function of $x$ is convex only if $v\leq 0$ (the hessian is diagonal positive semidefinite), otherwise it has at least one negative eigenvalue. Hence for $v\nleqslant0$, $\inf_{x}g(x,\lambda,v)=-\infty$, and thus the max of $g(\lambda, v)$ must be at a point where $v\leq0$.
Therefore the Lagrange relaxation and the dual of the LP relaxation give equivalent lower bounds, and since by Slater's condition the dual of the LP relaxation exhibits strong duality, we can conclude that both relaxations give the same lower bound.