I'm reading about convex conjugate and its relation to subdifferential.
In order to characterise subgradients we will use the convex conjugate defined below. This is essentially a special case of the Legendre-Fenchel transform we defined in Section 4.2. we recall that the Legendre-Fenchel transform (a.k.a. the convex conjugate) is defined as
$$
\varphi^{*}(y)=\sup _{x \in \mathbb{R}^{d}}(x \cdot y-\varphi(x)) .
$$
The following proposition characterises the subdifferential.
Proposition 6.4. Let $\varphi$ be a proper, lower semi-continuous, convex function on $\mathbb{R}^{d}$. Then for all $x, y \in \mathbb{R}^{d}$
$$
x \cdot y=\varphi(x)+\varphi^{*}(y) \quad \Leftrightarrow \quad y \in \partial \varphi(x) .
$$
Proof. Since $\varphi^{*}(y) \geq x \cdot y-\varphi(x)$ for all $x, y$ we have
$$
\begin{aligned}
x \cdot y=\varphi(x)+\varphi^{*}(y) & \Leftrightarrow x \cdot y \geq \varphi(x)+\varphi^{*}(y) \\
& \Leftrightarrow x \cdot y \geq \varphi(x)+y \cdot z-\varphi(z) \quad \forall z \in \mathbb{R}^{d} \\
& \Leftrightarrow \varphi(z) \geq \varphi(x)+y \cdot(z-x) \quad \forall z \in \mathbb{R}^{d} \\
& \Leftrightarrow y \in \partial \varphi(x)
\end{aligned}
$$
which proves the proposition.
In fact if $\varphi$ is convex then $\varphi$ is differentiable almost everywhere, hence we have that $\partial \varphi(x)=$ $\{\nabla \varphi(x)\}$ for almost every $x$.
In the proof, the author does not use the lower semi-continuity of $f$ nor its convexity. As such, I feel that the proposition holds for arbitrary proper function. Could you confirm if my understanding is correct?
Best Answer
Fenchel's inequality is TRUE for any function. Since we define $f^{\star }(p)=sup\left\{px-f(x) \right\}$ the inequality follows directly. Your proof is correct but there is no need for lower semicontinuity. However, in order to define a subdifferential we need a CONVEX function. I give an example. Let us define the subdifferential of the concave function $f(x)=-|x|$ at point zero. Then $-|x|-0\geq p(x-0)\Leftrightarrow -|x|\geq px$ for all x and hence for $x=p$. Therefore $-|p|\geq |p|^{2}$ which is true only for $ p=0$! Going back to the inequality defining the subdifferential, we get $-|x|\geq 0$ for all x, which is an obvious contradiction. So we conclude, Fenchel's inequality is true for any function, but the subdifferential is defined ONLY for convex functions! Of course there are other types of subdifferentials as eg Clarke's subgradient which is defined in a completely different way and for locally Lipschitz functions, not necessarily convex! The subdifferential can also be defined as $\partial f(x)=\left\{lim\triangledown f(y) ,\,y\to x \right\} $