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.