(subdifferential)=
# Subdifferential

````{prf:definition} Subdifferential
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 proper, lower
semi-continuous, convex function with values in the extended real number
line.

We can then define the **subdifferential** of $F$ in a point $x \in X$
as:
```{math}
\partial F(x) \ \coloneqq \ \{p \in X^* \, : \, F(y) \geq F(x) + \langle p, y-x \rangle, \forall y \in X\}.
```
We say that $F$ is **subdifferentiable** at $x \in X$, if the
subdifferential is not empty in this point, i.e.,
$\partial F(x) \neq \emptyset$.

We call any element $p \in \partial F(x)$ a **subgradient** of $F$ at
$x \in X$.

````

We illustrate the concept of the subdifferential on several examples in
the following.

````{prf:example} Subdifferentials
:label: ex:subdifferentials

1.  Let $F \coloneqq \R^n \to \R$ be a function that is differentiable
    in a point $x \in \R^n$. Then, the subdifferential of $F$ in $x$ is
    a singleton, which is simply given by the gradient of the function,
    i.e.,
    ```{math}
    \partial F(x) \ = \ \{ \nabla F(x) \}.
    ```

2.  Let $f_1, f_2 \colon \R \to \R$ be two convex, differentiable
    functions, which intersect in a point $\hat{x} \in \R$. We compose
    these two functions via the maximum operation as:
    ```{math}
    g(x) \ \coloneqq \ \max \{ f_1(x), f_2(x) \}.
    ```
    Then for the subdifferential of $g$ we have three different cases
    depending on the point $x \in \R$:

    -   $\mathbf{f_1(x) > f_2(x)}$: In this case the subdifferential of
        $g$ is simply given as the derivative of $f_1$, i.e.,
        ```{math}
        \partial g(x) \ = \ \{ f_1'(x) \}.
        ```

    -   $\mathbf{f_1(x) < f_2(x)}$: In this case the subdifferential of
        $g$ is simply given as the derivative of $f_2$, i.e.,
        ```{math}
        \partial g(x) \ = \ \{ f_2'(x) \}.
        ```

    -   $\mathbf{f_1(x) = f_2(x)}$: At the intersection of the two
        graphs of $f_1$ and $f_2$ the subdifferential of $g$ is not a
        singleton, but takes the whole range of slopes restricted by
        $f_1'$ and $f_2'$, i.e.,
        ```{math}
        \partial g(x) \ = \ [ \min \{f_1'(x), f_2'(x)\}, \max \{f_1'(x), f_2'(x)\} ].
        ```

````

The subdifferential can be used to generalize the formulation of
optimality conditions to the non-differentiable case.

````{prf:theorem} Optimality condition
Let $X$ be a real vector space and let
$F \colon X \rightarrow \R \cup \{-\infty, +\infty\}$ be a function with
values in the extended real number line.

A point $\hat{x} \in X$ is a minimizer of $F$, if and only if
$0 \in \partial F(\hat{x})$.

````

````{prf:proof} 
We show both implications separately in the following.

Let us assume $0 \in \partial F(\hat{x})$ first. Then by the definition
of the subgradient it follows that for all $y \in X$ we have:
```{math}
F(y) \ \geq \ F(\hat{x}) + \langle 0, y - \hat{x} \rangle \ = \ F(\hat{x}).
```
Since $F(y) \geq F(\hat{x})$ for all $y \in X$, we see by definition
that $\hat{x} \in \operatorname{argmin}_{x \in X} F(x)$.

Now let us assume that $\hat{x} \in X$ is a minimizer of $F$, i.e.,
$\hat{x} \in \operatorname{argmin}_{x \in X} F(x)$. Then by definition
we have for all $y \in X$ the following inequality:
```{math}
F(y) \ \geq \ F(\hat{x}) \ = \ F(\hat{x}) + \langle 0, y - \hat{x} \rangle.
```
Since $F(y) \geq F(\hat{x}) + \langle 0, y - \hat{x} \rangle$ for all
$y \in X$, we see by definition that $0 \in \partial F(\hat{x})$. ◻

````

One can characterize the subdifferential also via the Fenchel conjugate
as the following lemma shows.

````{prf:lemma} Characterization of subdifferential
:label: lem:subdifferential_characterization
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 proper, lower
semi-continuous, convex function with values in the extended real number
line and $F^*$ the Fenchel conjugate of $F$.

Then the subdifferential of $F$ in $x \in X$ can be characterized as:
```{math}
\partial F(x) \ = \ \{ p \in X^* \, : \, F(x) + F^*(p) = \langle p, x \rangle\}.
```

````

````{prf:proof} 
We prove the characterization by showing the equivalence of the two
statements for an arbitrary $p \in X^*$. That is, we show:
```{math}
p \in \partial F(x) \iff F(x) + F^*(p) \leq \langle p, x \rangle.
```

Assume that $p \in \partial F(x)$. By the definition of the
subdifferential, this means that the subgradient inequality holds for
all $y \in X$:
```{math}
:label: eq:subgrad_def

F(y) \geq F(x) + \langle p, y - x \rangle.
```
By rearranging the terms in equation {eq}`eq:subgrad_def` and using the
linearity of the dual pairing, we obtain for all $y \in X$:
```{math}
\langle p, y \rangle - F(y) \leq \langle p, x \rangle - F(x).
```
Since this inequality holds for every $y \in X$, it remains valid when
taking the supremum over all $y \in X$ on the left-hand side:
```{math}
\sup_{y \in X} \left\{ \langle p, y \rangle - F(y) \right\} \leq \langle p, x \rangle - F(x).
```
By definition, the Fenchel conjugate is given by
$F^*(p) = \sup_{y \in X} \{ \langle p, y \rangle - F(y) \}$.
Substituting this into the left-hand side yields:
```{math}
F^*(p) \leq \langle p, x \rangle - F(x) \iff F(x) + F^*(p) \leq \langle p, x \rangle.
```

Conversely, assume that the inequality
$F(x) + F^*(p) \leq \langle p, x \rangle$ holds. We can rewrite this as:
```{math}
:label: eq:voraussetzung_dual

F^*(p) \leq \langle p, x \rangle - F(x).
```
From the general definition of the supremum in the Fenchel conjugate,
the *Fenchel-Young inequality* always holds by default:
```{math}
F^*(p) = \sup_{y \in X} \left\{ \langle p, y \rangle - F(y) \right\} \geq \langle p, y \rangle - F(y) \quad \forall y \in X.
```
Combining this universal property with our assumption in equation
{eq}`eq:voraussetzung_dual`, we get for all $y \in X$:
```{math}
\langle p, y \rangle - F(y) \leq F^*(p) \leq \langle p, x \rangle - F(x).
```
Focusing on the outermost sides of this chain of inequalities, we have:
```{math}
\langle p, y \rangle - F(y) \leq \langle p, x \rangle - F(x).
```
Isolating $F(y)$ on the left-hand side by rearranging terms results in:
```{math}
F(y) \geq F(x) + \langle p, y \rangle - \langle p, x \rangle = F(x) + \langle p, y - x \rangle \quad \forall y \in X.
```
This matches the exact definition of $p$ being a subgradient of $F$ at
the point $x$. Therefore, $p \in \partial F(x)$.

Since both directions are proven, the characterization is complete. Note
that because the strict inequality
$\langle p, x \rangle < F(x) + F^*(p)$ is always impossible due to the
Fenchel-Young inequality, the condition
$F(x) + F^*(p) \leq \langle p, x \rangle$ is equivalent to the exact
equality $F(x) + F^*(p) = \langle p, x \rangle$. ◻

````

The following theorem states an important relationship between the
subdifferential of a convex function and the subdifferential of its
Fenchel conjugate.

````{prf:theorem} Subdifferential inversion
:label: thm:subdifferential_inversion
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 proper, lower
semi-continuous, convex function with values in the extended real number
line and $F^*$ the Fenchel conjugate of $F$.

Then, the following subdifferential inversion formula holds:
```{math}
:label: eq:subdifferential_inversion

p \in \partial F(x) \quad \Longleftrightarrow \quad x \in \partial F^*(p).
```

````

````{prf:proof} 
Let us first assume that $p \in X^*$ is a subgradient of $F$ in
$x \in X$, i.e., $p \in \partial F(x)$. Then, from
{prf:ref}`lem:subdifferential_characterization` it follows that
$\langle p, x \rangle \ \geq \ F(x) + F^*(p)$ and thus
```{math}
F^*(p) \ \leq \ \langle p, x \rangle - F(x).
```
At the same time the definition of the Fenchel conjugate yields:
```{math}
F^*(p) \ = \ \sup_{y \in X} \langle p, y \rangle - F(y) \ \geq \ \langle p, x \rangle - F(x).
```

Combining both inequalities above, we get the following condition for
the subdifferential of $F$ in $x \in X$:
```{math}
p \in \partial F(x) \quad \Longleftrightarrow \quad F^*(p) \ = \ \langle p, x \rangle - F(x).
```

Since $F$ is assumed to be lower semi-continuous and convex, we know
from the Fenchel-Moreau theorem in {prf:ref}`thm:fenchel_moreau` that
$F = F^{**}$. For this reason we can write
```{math}
:label: eq:fenchel_equality_star

p \in \partial F(x) \quad \Longleftrightarrow \quad F^*(p) + F^{**}(x) \ = \ \langle p, x \rangle.
```

To establish the relation for the subdifferential of $F^*$ in
$p \in X^*$, we apply {prf:ref}`lem:subdifferential_characterization` to
the function $F^* \colon X^* \rightarrow \R \cup \{-\infty, +\infty\}$,
which gives us for a subgradient $x \in \partial F^*(p)$
```{math}
F^*(p) + F^{**}(x) \ \leq \ \langle x, p \rangle.
```
In consequence, this leads to the following characterization of the
subdifferential:
```{math}
:label: eq:fenchel_inequality_star

x \in \partial F^*(p) \quad \Longleftrightarrow \quad F^*(p) + F^{**}(x) \ \leq \ \langle p, x \rangle.
```

Using the Fenchel-Young inequality from {prf:ref}`cor:fenchel_young` on
the function $F^*$, the reverse inequality
$F^*(p) + F^{**}(x) \geq \langle p, x \rangle$ is universally true for
all $x \in X$ and $p \in X^*$. Consequently, the inequality in
{eq}`eq:fenchel_inequality_star` holds if and only if it holds with
equality:
```{math}
x \in \partial F^*(p) \quad \Longleftrightarrow \quad F^*(p) + F^{**}(x) \ = \ \langle p, x \rangle.
```

Comparing this with the equivalence established in
{eq}`eq:fenchel_equality_star`, we see that both $p \in \partial F(x)$
and $x \in \partial F^*(p)$ are equivalent to the exact same identity.
This yields the stated subdifferential inversion formula:
```{math}
p \in \partial F(x) \quad \Longleftrightarrow \quad x \in \partial F^*(p).
```
 ◻

````