4.3. Fenchel Duality

Fenchel Duality

Fenchel duality is a framework in convex analysis that creates a dual optimization problem using the concept of convex (Fenchel) conjugates. Let $f:X\to \mathbb{R}\cup \{+\infty \}$, $g:Y\to \mathbb{R}\cup \{+\infty \}$, and $A:X\to Y$ be a linear map. Consider the primal problem
$p^{\ast }={\inf }_{x\in X}\{f(x)+g(Ax)\}.$
Then, the Fenchel dual is given as
$d^{\ast }={\sup }_{y^{\ast }\in Y^{\ast }}\{-f^{\ast }(A^T{y}^{\ast })-g^{\ast }(-y^{\ast })\}.$
If $f$ and $g$ are convex and $\exists x_0\in \mathrm{dom}f\cap \mathrm{dom}(g$

Proof

Consider the perturbation function $F(x,y)=f(x)+g(Ax-y)$. Then, the primal problem is given on the function $F(x,0)$. Taking the convex conjugate of $F(x,0)$, we get:
$F^{\ast }(x^{\ast },0)={\sup }_{x\in X}\{⟨x^{\ast },x⟩-F(x^{\ast },x)\}$