Lagrangian duality (${\sup }_{\lambda \ge 0,\mu }{\inf }_{u}L(u,\lambda ,\mu )$)

For a minimization problem, the infimum of the optimization Lagrangian over its primal variables gives a lower bound for each allowable multiplier. Maximizing these lower bounds is the Lagrangian dual problem. Weak duality always holds; strong duality requires further hypotheses and holds for feasible bounded linear programs.