Invertible Legendre-Fenchel transform of non-convex function

Question

According to a number of source I've found online, including this very popular document, the Legendre-Fenchel transformation is an involution iff it is applied to a convex function. However, take the function $f(x) = x^3 + 1$, which is non-convex on $[-1, 1]$. Let $y = f(x)$. Since it is differentiable, we can use the simpler Legendre transform. Starting with $p = \frac{d f}{dx} = 3x^2$ and $x = \pm \sqrt{\frac{p}{3}}$, we find that the transform is (up to a negative): \begin{equation} \begin{split} f^*(p) &= f(x) - px \\ &= \frac{\pm p^{3/2}}{3\sqrt{3}} + 1 \mp \frac{p^{3/2}}{\sqrt{3}} \\ &= \mp \frac{2p^{3/2}}{3\sqrt{3}} + 1 \end{split} \end{equation}

If we then take the Legendre transform of the this function, using $-x = -\frac{df^*}{dp} = \pm\sqrt{\frac{p}{3}}$, we find that: \begin{equation} \begin{split} f^{**}(x) &= f^*(p) - xp \\ &= \mp \frac{2p^{3/2}}{3\sqrt{3}} + 1 \pm \sqrt{\frac{p}{3}} p \\ &= \pm \frac{p^{3/2}}{3\sqrt{3}} + 1\\ &= x^3 + 1 \\ &= y \end{split} \end{equation}

There is obviously the issue of $f^*(p)$ being a multifunction rather than a function, but that could easily be fixed by just defining the square root as a mapping onto the positive reals instead of the whole set of real numbers, and the result would be the same. So why, in this case, is the LF transform an involution despite the input function not being convex?

Answer 1

The problem is that $\sup_x (px-f(x))$ is not always achieved when $f'(x)=p$: this may be a maximum or a minimum. Indeed, the second derivative of the quantity to be maximised is $-f''(x)$, so if $f''(x)<0$ where $f'(x)=p$, that point is a minimum. Moreover, even if a point is a maximum, the derivative only checks that it is a local maximum: the global maximum/supremum can occur elsewhere.

Another problem is that $f^*$ is always a convex function (and in turn, so is $f^{**}$), so if your calculation doesn't produce a convex function, it can't be right.

---

Let's look graphically at what's happening.

Here we have graphs of $px-(x^3+1)$ when $p=0$ (blue), $p=3/4$ (orange) and $p=1$ (green). When $p=0$, the supremum clearly occurs at $x=-1$ (and is zero). As we increase $p$, this remains the case, so the value of $px-(x^3+1)$ is $-p$. This continues until $p=3/4$, where we see the local maximum on the other side becomes level with the value at $x=-1$ (how did I get this? I found the value of $p$ for which a line through $(-1,0)$ of gradient $p$ became a tangent; I recommend you think about why this works yourself). From then on, the supremum occurs at the local maximum you found, and since this is positive, it must be at $x=+\sqrt{p/3}$, so $px-f(x) = 2(p/3)^{3/2}-1$. Putting all this together, the Legendre–Fenchel transform looks like this:

This is clearly convex. One can compute $f^{**}$ as well: the affine part on the left vanishes into the point $x=-1$, the point at $p=3/4$ becomes an affine piece $\frac{3}{4}(x-1)$, and the other part returns to itself since it is convex and we find this:

where $f$ is blue and $f^{**}$ is orange: we see in particular that $f^{**}$ is the convex hull of $f$: the largest convex function no larger than $f$.