Conjugate Duality
Contents
9.10. Conjugate Duality¶
9.10.1. Fenchel’s Duality Theorem¶
Consider the minimization problem
(9.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:
(9.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 (9.25) and (9.26).
Theorem 9.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.