5.1. Fenchel conjugate#
We start by recalling the definition of a topological dual space \(X^*\) to a vector space \(X\).
Definition 5.1 (Continuous dual space)
Let \(X\) be a vector space over the field \(\R\). Then, we define the continuous dual space \(X^*\) of \(X\) as the set of all continuous, linear maps from \(X\) to \(\R\), i.e.,
Furthermore, we define the following bilinear form \(X \times X^* \to \R\) given as
as the dual pairing of \(f \in X^*\) and \(x \in X\).
Another useful definition in the context of the regarded variational problem (4.3) is given in the following.
Definition 5.2 (Dual norm)
Let \(X\) be a normed vector space with norm \(\Vert \cdot \Vert\) and let \(X^*\) denote its continuous dual space. The dual norm of a continuous linear functional \(f \in X^*\) is defined as:
Based on the definition of the dual space and the concept of convexity we are able to introduce a useful transformation that allows us to characterize convex functions with an alternative representation based on the dual pairing.
Definition 5.3 (Fenchel conjugate)
Let \(X\) be a real vector space and let \(X^*\) denote its topological dual space. Furthermore, let \(F \colon X \rightarrow \R \cup \{-\infty, +\infty\}\) be a function with values in the extended real number line.
Then we define the Fenchel conjugate \(F^*\) of \(F\) (also known as Legendre-Fenchel transformation or convex conugate) in a point \(p \in X^*\) as:
In the one-dimensional case the Fenchel conjugate can be interpreted geometrically as a transformation that maps the slope of a tangent line to \(F\) to its negative \(y\)-intercept. Hence, a curve can be characterized by its envelope of tangents instead of its function values.
Example 5.1 (Fenchel conjugates)
In the following we want to compute the Fenchel conjugate for two examples to make its definition more comprehensible. In particular the computations in the second example will be quite important for image processing later.
We regard an affine function \(F \colon \R^n \to \R\) of the following form:
\[F(x) \ \coloneqq \ \langle a, x \rangle - b.\]Here, \(a \in \R^n\) and \(b \in \R\) are two fixed parameters of the affine function \(f\).
We now compute the Fenchel conjugate \(F^*\) of \(F\) as:
\[\begin{split} F^*(p) \ &= \ \sup_{x \in \R^n} \langle p, x \rangle - F(x) \\ &= \ \sup_{x \in \R^n} \langle p, x \rangle - \langle a, x \rangle + b \\ &= \ \sup_{x \in \R^n} \langle p-a, x \rangle + b \\ &= \ \begin{cases} b, \quad &\text{ if p = a },\\ +\infty, \quad &\text{ else }.\end{cases} \end{split}\]We now discuss the Fenchel conjugate in the interesting case of a norm \(\Vert \cdot \Vert\) in the setting of a normed vector space \(X\), i.e.,
\[F(x) \ \coloneqq \ \Vert x \Vert.\]To compute the Fenchel conjugate \(F^*\) of \(F\) in a point \(p \in X^*\) we first recall Definition 5.2 of the dual norm:
\[\Vert p \Vert^* \ = \ \sup_{x \in X: \Vert x \Vert \leq 1} \langle p, x \rangle.\]We now consider two different cases.
Let us first assume a point \(p \in X^*\) with \(\Vert p \Vert^* > 1\). Then per definition, there exists a maximizing element \(y \in X\) such that \(\Vert y \Vert \leq 1\) and \(\langle p, y \rangle = \Vert p\Vert^* > 1\). Thus, we can write the Fenchel conjugate \(F^*\) of the norm \(F\) in \(p \in X^*\) as:
\[\begin{split} F^*(p) \ &= \ \sup_{x \in X} \langle p, x \rangle - F(x)\\ &= \ \sup_{x \in X} \langle p, x \rangle - \Vert x \Vert\\ &\geq \ \langle p, y \rangle - \Vert y \Vert\\ &= \ \Vert p\Vert^* - \Vert y\Vert \ > \ 0. \end{split}\]Instead of using the vector \(y \in X\), we can also use a scaled vector \(\lambda y\) for \(\lambda > 0\) and see that
\[\begin{split} F^*(p) \ &\geq \ \langle p, \lambda y \rangle - \Vert \lambda y \Vert\\ &= \ \lambda \cdot ( \Vert p\Vert^* - \Vert y\Vert) \ > \ 0. \end{split}\]Since we can choose the scaling factor \(\lambda > 0\) arbitrarily large it get clear that for \(p \in X^*\) with \(\Vert p\Vert^* > 1\) we get the Fenchel conjugate
\[F^*(p) \ = \ +\infty.\]Now we consider the complementary case of \(p \in X^*\) with \(\Vert p \Vert^* \leq 1\). By the definition of the dual norm we get:
\[\langle p, x \rangle - \Vert x\Vert \ \leq \ \Vert p\Vert^* \Vert x \Vert - \Vert x \Vert \ = \ (\Vert p\Vert^* - 1) \Vert x \Vert \ \leq \ 0.\]If we now regard the supremum of the left side of the inequality we see that
\[\sup_{x\in X} \langle p, x \rangle - \Vert x \Vert \ = \ 0,\]for \(\Vert x \Vert = 0\). Thus, for every point \(p \in X^*\) with \(\Vert p\Vert^* \leq 1\) we get the Fenchel conjugate
\[F^*(p) \ = \ 0.\]In summary, we get that the Fenchel conjugate \(F^*\) of the norm \(F(x) = \Vert x\Vert\) is given as the characteristic function of the dual unit ball:
\[F^*(p) \ = \ \chi_{\Vert \cdot \Vert^*} (p) \ \coloneqq \ \begin{cases} 0, \quad &\text{ if } \Vert p\Vert^* \leq 1,\\ +\infty, \quad &\text{ else}.\end{cases}\]
Lemma 5.1 (Properties of the Fenchel conjugate)
Let \(X\) be a real vector space and let \(X^*\) denote its topological dual space. Furthermore, let \(F \colon X \rightarrow \R \cup \{-\infty, +\infty\}\) be a function with values in the extended real number line.
Then the Fenchel conjugate \(F^* \colon X^* \to \R \cup \{-\infty, +\infty \}\) is convex and lower semi-continuous.
Proof. For each fixed point \(x \in X\), the function \(p \mapsto \langle p, x \rangle - F(x)\) is an affine function and thus convex. Since the supremum of any family of convex functions is convex, the Fenchel conjugate \(F^*\) is convex.
Moreover, since \(F^*\) is the pointwise supremum of closed (affine) functions, it is lower semi-continuous. ◻
From Definition 5.3 of the Fenchel conjugate, we can directly deduce the following inequality.
Corollary 5.1 (Fenchel-Young inequality)
For any function \(F \colon X \to \R\) and its Fenchel conjugate \(F^*\) the following Fenchel-Young inequality holds for every \(x \in X\) and \(p \in X^*\):
One can apply the Fenchel conjugate twice on a function \(F\) to compute a closed convex hull of it. We define this transformation in the following.
Definition 5.4 (Fenchel biconjugate)
Let \(X\) be a real vector space and let \(X^*\) denote its topological dual space. Furthermore, let \(F \colon X \rightarrow \R \cup \{-\infty, +\infty\}\) be a function with values in the extended real number line and \(F^*\) be the Fenchel conjugate of \(F\).
Then we define the Fenchel biconjugate \(F^{**} \colon X \rightarrow \R \cup \{-\infty, +\infty\}\) of \(F\) via:
Using the Fenchel-Young inequality in Corollary 5.1 it gets clear that \(F^{**} \leq F\) in general. Furthermore, one can show that the Fenchel biconjugate is always lower semi-continuous and convex, which leads to the fact that \(F^{**}\) is the closed convex envelope of any function \(F\). For certain conditions the Fenchel-Young inequality (5.1) gets an identity as we state in the following theorem.
Theorem 5.1 (Fenchel-Moreau theorem)
Let \(X\) be a real vector space and let \(X^*\) denote its topological dual space. Furthermore, let \(F \colon X \rightarrow \R \cup \{-\infty, +\infty\}\) be a function with values in the extended real number line.
Then for the Fenchel biconjugate it holds that, \(F^{**} = F\), if and only if \(F\) is lower semi-continuous and convex.
Proof. See [Roc70]. ◻