(fenchel-conjugate)=
# Fenchel conjugate

We start by recalling the definition of a topological dual space $X^*$
to a vector space $X$.

````{prf:definition} 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.,
```{math}
X^* \ \coloneqq \ \{ f \colon X \to \R \, : \, f \text{ is linear and continuous }\}.
```

Furthermore, we define the following bilinear form $X \times X^* \to \R$
given as
```{math}
(x, f) \ \mapsto \ \langle x, f \rangle \, \coloneqq \, f(x),
```
as the **dual pairing** of $f \in X^*$ and $x \in X$.

````

Another useful definition in the context of the regarded variational
problem {eq}`eq:tv_denoising` is given in the following.

````{prf:definition} Dual norm
:label: def: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:
```{math}
||f||^* \ \coloneqq \ \sup_{x \in X: x\neq 0} \frac{\vert f(x)\vert}{\Vert x\Vert} \ = \ \sup_{x \in X: \Vert x \Vert \leq 1} \vert f(x) \vert \ = \ \sup_{x \in X: \Vert x \Vert \leq 1} \vert \langle f, x \rangle \vert.
```

````

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.

````{prf:definition} Fenchel conjugate
:label: def:convex_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:
```{math}
F^*(p) \ \coloneqq \ \sup_{x \in X} \, \langle p, x \rangle - F(x).
```

````

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.

````{prf:example} 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.

1.  We regard an affine function $F \colon \R^n \to \R$ of the following
    form:
    ```{math}
    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:
    ```{math}
    \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}
    ```

2.  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.,
    ```{math}
    F(x) \ \coloneqq \ \Vert x \Vert.
    ```
    To compute the Fenchel conjugate $F^*$ of $F$ in a point $p \in X^*$
    we first recall {prf:ref}`def:dual_norm` of the dual norm:
    ```{math}
    \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:
    ```{math}
    \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
    ```{math}
    \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
    ```{math}
    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:
    ```{math}
    \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
    ```{math}
    \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
    ```{math}
    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**:
    ```{math}
    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}
    ```

````

````{prf:lemma} 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.

````

````{prf: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 {prf:ref}`def:convex_conjugate` of the Fenchel conjugate, we can
directly deduce the following inequality.

````{prf:corollary} Fenchel-Young inequality
:label: cor:fenchel_young
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^*$:
```{math}
:label: eq:fenchel_young_inequality

\langle p, x \rangle \ \leq \ F^*(p) + F(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.

````{prf:definition} 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:
```{math}
F^{**}(x) \ = \ \sup_{p \in X^*} \langle x, p \rangle - F^*(p).
```

````

Using the Fenchel-Young inequality in {prf:ref}`cor:fenchel_young` 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
{eq}`eq:fenchel_young_inequality` gets an identity as we state in the
following theorem.

````{prf:theorem} Fenchel-Moreau theorem
:label: thm:fenchel_moreau
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.

````

````{prf:proof} 
See {cite:p}`rockafellar_1970`. ◻

````