Prove the optimal value of this minimum is not smaller than the optimal value of this maximum

by user558377   Last Updated November 09, 2018 01:20 AM

$ min \langle c, x \rangle$ s.t. $Ax \geq b, x \geq 0$, where $x$ is an integer and $A$ has integer entries. Show the optimal value of this is no less than the optimal value of this maximum: $max \langle b^* , \lambda \rangle$ s.t. $A^T\lambda \leq c, \lambda \geq 0$, where $b^*$ denotes the roundup of vector $b$: the smallest integer vector greater than or equal to $b$.

I tried doing this using the dual problem, i.e $L = \langle c, x \rangle + \langle b-Ax, \lambda \rangle = \langle c -A^T\lambda, x \rangle + \langle b , \lambda \rangle$ so the minimum of this w.r.t $x$ is $-\infty$ if $c > A^T\lambda$ and $\langle b , \lambda \rangle$ if $c \leq A^T\lambda$. So the new problem because to maximize w.r.t $\lambda$ so its $max \langle b , \lambda \rangle$ s.t. $c \leq A^T\lambda, \lambda \geq 0$, which is obviously less equal the max we were looking to show greater or equal to.

What am I doing wrong? I tried using the dual problem to solve the original max, but also got nowhere.

Related Questions

How to obtain the dual of a Lagrangian?

Updated September 01, 2016 08:08 AM