Strong Duality for LP

Consider the LP

where $c in mathbf{R}^n$ , $A in mathbf{R}^{m times n}$ , and $b in mathbf{R}^m$ .

Dual

Let us form the dual of this problem. The Lagrangian is the function $L : mathbf{R}^n times mathbf{R}^m rightarrow mathbf{R}$ with values

and the dual function is $g : mathbf{R}^{m} rightarrow mathbf{R}$ , with values

g(lambda) = min_x : L(x,lambda) = min_x : c^Tx + lambda^T(Ax-b).

The above problem involves the minimization of an affine function without any constraints. The optimal value is thus

$g(lambda) = left{ begin{array}{ll} -lambda^Tb & mbox{if } A^Tlambda = 0 -infty & mbox{otherwise.} end{array} right.$

The dual problem reads

$d^ast = max_{lambda ge 0} : g(lambda) = max_{lambda} : -lambda^Tb ~:~ lambda ge 0, ;; A^Tlambda = 0.$

The dual, just like the primal, is an LP. We note that the feasible set has a particularly simple form, in contrast to the primal, the feasible set of which is a generic polytope.

Strong duality result

It can be shown that strong duality always holds for LPs, provided either the primal or the dual is feasible. In contrast with Slater's condition for generic convex problems, strict feasibility is not required.