Complimentary Slackness

Given a primal problem
” Minimize over subject to ”
we can rewrite it, by adding slack variables, to:
” Minimize over and subject to ”
This now introduces the Dual Problem
” Maximize over subject to ”
where

and is the Lagrangian:

and is the set of Feasible Lagrange Multipliers

Given some feasible and
and a feasible
we say that complimentary slackness holds if for any :

Intuition

Suppose we are minimizing (over and ) the Lagrangian

with , subject to the Feasible Lagrange Multipliers
(which we have to do in order to calculate )

Now suppose for some .
Then and thus .

Hence we have to have
and thus for any
But then also
As is freely chosen, we can always pick it so that
so either or for any (because )
This is called complimentary slackness.