Strong Duality for LP
Consider the LP
where , , and .
Dual
Let us form the dual of this problem. The Lagrangian is the function with values
and the dual function is , with values
The above problem involves the minimization of an affine function without any constraints. The optimal value is thus
The dual problem reads
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.
|