10.10. Conjugate Duality

10.10.1. Fenchel’s Duality Theorem

Consider the minimization problem

(10.25)$$\underset{\mathbf{x}\in \mathbb{V}}{inf}f(\mathbf{x})+g(\mathbf{x}).$$

The problem can be rewritten as

$$\underset{\mathbf{x},\mathbf{z}\in \mathbb{V}}{inf}\{f(\mathbf{x})+g(\mathbf{z})|\mathbf{x}=\mathbf{z}\}.$$

Construct the Lagrangian for this problem.

$$\begin{array}{rl}L(\mathbf{x},\mathbf{x};\mathbf{y})& =f(\mathbf{x})+g(\mathbf{z})+⟨\mathbf{z}-\mathbf{x},\mathbf{y}⟩\\ & =-[⟨\mathbf{x},\mathbf{y}⟩-f(\mathbf{x})]-[⟨\mathbf{z},-\mathbf{y}⟩-g(\mathbf{z})].\end{array}$$

The dual objective is constructed by minimizing the Lagrangian with the primal variables $\mathbf{x},\mathbf{z}$.

$$q(\mathbf{y})=\underset{\mathbf{x},\mathbf{z}}{inf}L(\mathbf{x},\mathbf{z};\mathbf{y})=-f^{\ast }(\mathbf{y})-g^{\ast }(-\mathbf{y}).$$

We thus obtain the following dual problem, known as the Fenchel’s dual:

(10.26)$$\underset{\mathbf{y}\in {\mathbb{V}}^{\ast }}{sup}\{-f^{\ast }(\mathbf{y})-g^{\ast }(-\mathbf{y})\}.$$

Fenchel’s duality theorem provides the conditions under which strong duality holds for the pair of problems (10.25) and (10.26).

Theorem 10.85 (Fenchel’s duality theorem)

Let $f,g:\mathbb{V}\to (-\mathrm{\infty },\mathrm{\infty }]$ be proper convex functions. If $\mathrm{ri}\mathrm{dom}f\cap \mathrm{ri}\mathrm{dom}g\ne \varnothing$, then

$$\underset{\mathbf{x}\in \mathbb{V}}{inf}\{f(\mathbf{x})+g(\mathbf{x})\}=\underset{\mathbf{y}\in {\mathbb{V}}^{\ast }}{sup}\{-f^{\ast }(\mathbf{y})-g^{\ast }(-\mathbf{y})\}.$$

The supremum of R.H.S. (the dual problem) is attained whenever it is finite.