Strong Duality

Given a problem
” Minimize subject to ”
and its Dual Problem
” Maximize subject to ”
where is the Lagrangian
and is the set of Feasible Lagrange Multipliers
We say that strong duality holds if

for some feasible and

Note that by Weak Duality, this is optimal for both problems.

Theorem

Strong duality holds for any Linear Program.