Proving certificate of optimality

convex optimizationlinear algebralinear programming

suppose we have the following linear program max{$c^Tx+z: Ax=b, x \geq0$} and that B is an optimal basis with $\bar{x}$ being the basic feasible solution corresponding to B. How would I be able to prove that $y=A_B^{-T}c_B$ is a certificate of optimality for $\bar{x}$?

I know that I have to show

1) $A^Ty \geq c$

2) $c^Tx=y^Tb$

I have been able to show 2) but am struggling on showing 1)

Best Answer

From $y=A_B^{-T}c_B$ you multiply with $A_B^T$ to get $A_B^Ty = c_B$.

The tableau is optimal, so $c_B^T A_B^{-1} A_N - c_N^T \geq 0$, so $y^T A_N \geq c_N^T$.

Combining the two you get $A^Ty \geq c$.

Related Question