Dual Problem in Linear Programs

Consider the primal problem:
” Minimize over subject to ”
where , and is an matrix.
Now the Lagrangian is:

The set of Feasible Lagrange Multipliers is:

and finally, the Dual Problem function is:

So the dual problem is:
” Maximize over subject to ”
where .

Note that this is a Linear Program in General Form.

If we try to find the dual problem of the dual problem,
we should end up with the primal problem.

Lemma

In a Linear Program and its Dual Problem (as above)
Let be primal feasible,
and let be dual feasible

Then and are optimal
if and only if
Complimentary Slackness holds.

Proof

Complimentary Slackness is equivalent to:

Suppose and are optimal (feasible) solutions.
Due to Strong duality in linear programs:

Then substitute to find
Hence Complimentary Slackness holds.

Let be primal feasible, and dual feasible
and suppose
Then substitute to find
Due to Weak Duality,
this can only happen if and are optimal.