This page just lists the basic properties for reference, and does not give any intuition or proofs. This is based on chapter 5 of Boyd and Vandenberghe’s (outstanding) Convex Optimization. I have emphasized the terminology here because this is necessary to read most work using Lagrange duality.
Take an optimization problem:
subject to ,
The Lagrangian is
The Lagrange dual function is
The Lagrange dual function gives lower bounds on the optimal value of the original problem.
(This is very easy to check: if is a feasible solution to the original problem, observe that )
Whenever we bound some quantity with regards to some adjustable parameters, the obvious idea is to adjust the parameters so as to make the bound as good as possible. This is the Lagrange dual problem.
subject to .
Call the optimal value of the Lagrange dual problem . It is obvious that
always, called weak duality. When is , i.e. when does strong duality hold? The answer is that is usually does when the original problem is convex. (i.e. convex, linear).
Slater’s theorem removes the “usually”. Strong duality holds if the original problem is convex, and there exists a strictly feasible point, i.e. there exists an such that the inequalities are strictly satisfied:
Actually, a slightly stronger result holds: if some are affine, only is necessary for those constraints.