Duality

Definition 40

A primal optimization problem is given by

The primal problem is essentially the standard form of optimization. There are no assumptions of convexity on any of the functions involved. We can would like to express primal problems as a min-max optimization with no constraints.

Definition 41

The Lagrangian achieves the goal of removing the constraints in the min-max optimization

Theorem 22 (Minimax Inequality)

Theorem 23 (Weak Duality)

What weak duality does is convert our minimization problem to a maximization problem.

Definition 42

The dual function of the primal problem is given by

  1. It removes constraints, potentially making the problem easier to solve.

  2. It can turn a non-convex problems into a convex one.

Even when there are no constraints, we can sometimes introduce constraints to leverage duality by adding slack variables that are equal to expressions in the objective.

Strong Duality

In some cases, duality gives not just a lower bound, but an exact value. When this happens, we have Strong Duality.

Theorem 24 (Sion's MiniMax Theorem)

If we focus on convex problems, then we can find conditions which indicate strong duality holds.

Theorem 25 (Slater's Condition)

If a convex optimization problem is strictly feasible, then strong duality holds

Theorem 26

  1. Lagrangian Stationarity If the lagrangian is differentiable, then

Last updated