4.1. Duality

Duality

Duality in optimization is the framework that associates every optimization problem, known as the primal problem, with another similar problem on the dual space called the dual problem. Let $F:X\times Y\to \mathbb{R}\cup \{+\infty \}$ be a perturbation function (i.e., $F(x,0)=f(x)$), and $p^{\ast }$ be the solution to the primal problem
$p^{\ast }={\inf }_{x\in X}f(x).$
Then, $p^{\ast }$ can be associated with an always convex dual optimization problem on the dual space $Y^{\ast }$, such that
$d^{\ast }={\sup }_{y^{\ast }\in Y^{\ast }}\{-F^{\ast }(0,y^{\ast })\}.$
The values between these problems are always related via the weak duality principle, such that $p^{\ast }\ge d^{\ast }.$
Moreover, strong duality holds (i.e., $p^{\ast }=d^{\ast }$) if certain constraint qualifications are met.

Example

Sion's Minimax Theorem