The relation between convex conjugate and 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?

• Indeed. Neither convexity nor lower semi-continuity are necessary for this proposition. Commented Jun 21, 2022 at 18:56
• Which book is this from? Commented Jun 21, 2022 at 19:48
– user1054388
Commented Jun 22, 2022 at 0:49
• @littleO It's from this lecture note. Commented Jun 22, 2022 at 1:44
• why does the first iff statement hold? like switching equality to inequality. Commented Mar 9, 2023 at 20:41

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\}$$
• @LittleO I down-voted. The central assertion that the subdifferential requires convexity just to be defined is false. The subdifferential map has a perfectly sensible definition without convexity (and indeed, there sometimes is an occasion to define it independently of convexity, e.g. if you wish to show that $\partial f(x) \neq \emptyset$ for all $x \in \Bbb{R}^d$ implies convexity of $f$). The argument for this, to find a single non-convex function and a single point at which the subgradient is empty, does not support the thesis (and can even be done for certain convex functions). Commented Jun 22, 2022 at 3:15
• I have most definitely discussed subgradients of non-convex functions with my supervisor, the late Prof. Jon Borwein, who wrote a book on convex functions (actually he wrote a few on convexity and adjacent topics). He would point out that minor points like, $x$ minimises a function if and only if $0 \in \partial f(x)$ works even if $f$ is non-convex. I honestly don't understand why you cannot admit you are wrong on any of the points on which I have proven you wrong. Commented Jun 24, 2022 at 21:19