# 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.