5.2. Subdifferential#
Definition 5.5 (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:
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.
Example 5.2 (Subdifferentials)
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.,
\[\partial F(x) \ = \ \{ \nabla F(x) \}.\]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:
\[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.,
\[\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.,
\[\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.,
\[\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.
Theorem 5.2 (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})\).
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:
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:
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.
Lemma 5.2 (Characterization of 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 and \(F^*\) the Fenchel conjugate of \(F\).
Then the subdifferential of \(F\) in \(x \in X\) can be characterized as:
Proof. We prove the characterization by showing the equivalence of the two statements for an arbitrary \(p \in X^*\). That is, we show:
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\):
By rearranging the terms in equation (5.2) and using the linearity of the dual pairing, we obtain for all \(y \in 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:
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:
Conversely, assume that the inequality \(F(x) + F^*(p) \leq \langle p, x \rangle\) holds. We can rewrite this as:
From the general definition of the supremum in the Fenchel conjugate, the Fenchel-Young inequality always holds by default:
Combining this universal property with our assumption in equation (5.3), we get for all \(y \in X\):
Focusing on the outermost sides of this chain of inequalities, we have:
Isolating \(F(y)\) on the left-hand side by rearranging terms results in:
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.
Theorem 5.3 (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:
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 Lemma 5.2 it follows that \(\langle p, x \rangle \ \geq \ F(x) + F^*(p)\) and thus
At the same time the definition of the Fenchel conjugate yields:
Combining both inequalities above, we get the following condition for the subdifferential of \(F\) in \(x \in X\):
Since \(F\) is assumed to be lower semi-continuous and convex, we know from the Fenchel-Moreau theorem in Theorem 5.1 that \(F = F^{**}\). For this reason we can write
To establish the relation for the subdifferential of \(F^*\) in \(p \in X^*\), we apply Lemma 5.2 to the function \(F^* \colon X^* \rightarrow \R \cup \{-\infty, +\infty\}\), which gives us for a subgradient \(x \in \partial F^*(p)\)
In consequence, this leads to the following characterization of the subdifferential:
Using the Fenchel-Young inequality from Corollary 5.1 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 (5.6) holds if and only if it holds with equality:
Comparing this with the equivalence established in (5.5), 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:
◻