10.10. Conjugate Duality

10.10.1. Fenchel’s Duality Theorem

Consider the minimization problem

(10.25)\[\inf_{\bx \in \VV} f(\bx) + g(\bx).\]

The problem can be rewritten as

\[ \inf_{\bx, \bz \in \VV} \{ f(\bx) + g(\bz) \ST \bx = \bz \}. \]

Construct the Lagrangian for this problem.

\[\begin{split} L (\bx, \bx; \by ) &= f(\bx) + g(\bz) + \langle \bz - \bx, \by \rangle\\ &= -[\langle \bx, \by \rangle - f(\bx)] - [\langle \bz, -\by \rangle - g(\bz)]. \end{split}\]

The dual objective is constructed by minimizing the Lagrangian with the primal variables \(\bx, \bz\).

\[ q(\by) = \inf_{\bx, \bz} L(\bx, \bz; \by) = - f^*(\by) - g^*(- \by). \]

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

(10.26)\[\sup_{\by \in \VV^*} \{ - f^*(\by) - g^*(- \by) \}.\]

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 : \VV \to \RERL\) be proper convex functions. If \(\relint \dom f \cap \relint \dom g \neq \EmptySet\), then

\[ \underset{\bx \in \VV}{\inf} \{f(\bx) + g(\bx) \} = \underset{\by \in \VV^*}{\sup} \{ - f^*(\by) - g^*(-\by) \}. \]

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