Lagrangian and Lagrange Dual

The Dual Problem

Lagrangian and Lagrange Dual Function

For an optimization problem: Define the Lagrangian as: Define the Lagrange dual function as:

Theorem

For any optimization problem, the Lagrange dual function is concave.

Lower Bound Property

If , then the Lagrange dual function is a lower bound for the original objective function: .

Lagrange Dual Problem

For any optimization problem, the dual problem is to maximize the dual function:

Proposition

The dual problem is always a convex optimization problem.

Weak and Strong Duality

We call an optimization problem with strong duality if the dual optimal equals to the primal optimal. Conversely, we call it weak duality. e.g. A nonconvex problem with strong duality, suppose :

Slater’s Condition

Strong duality holds for a convex problemif it is strictly feasible:

Theorem

Thrm Complementary Slackness Assume strong duality holds, is primal optimal, is dual optimal, then

KKT Conditions

Theorem: Karush-Kuhn-Tucker (KKT) Conditions

The following conditions hold for a problem with differentiable and such that strong duality holds and are optimal:

1. Primal feasible:
2. Dual feasible:
3. Complementary slackness:
4. Gradient of Lagrangian with respect to vanishes:

Theorem

If satisfy the KKT conditions for a convex problem, then they are optimal.

Proposition

If Slater’s condition is satisfied, then is optimal if and only if there exists that satisfy the KKT conditions.