Weak 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
The following holds:

Proof

Note:

Thus