Nyuwa mends the epigraph

Nyuwa, the mother goddess of Chinese mythology, mends the sky according to an ancient Chinese legend. Today, Nyuwa is asked to mend the epigraph of a continuous function over an open set so that the function becomes convex. What can we say about this?

Let $K\subseteq\mathbb{R}^n$ be non-empty, convex and open. Let $f:K\to\mathbb{R}$ be continuous. Its biconjugate, or the convex envelope, is $f^{\ast\ast}\left(x\right)=\hspace*{-16pt}\sup_{\tiny\begin{array}{c}g\text{ affine}\\\forall y\in K:g(y)\leq f(y)\end{array}}\hspace*{-16pt}{g\left(x\right)}.$ The convex envelope of a function is the largest convex function that lower bounds it. The convex envelope can also be characterized using the epigraphs. The epigraph of a function is $\epi\left(f\right)=\left\{{\left({x,y}\right)\mid y\geq f\left(x\right)}\right\},$ i.e., everything above the function’s graph. Taking the convex envelope of a function turns its epigraph into the closed convex hull, i.e., $\epi\left(f^{\ast\ast}\right)=\overline{\operatorname{Conv}\left(\epi\left(f\right)\right)}$. See the figure below for a classical illustration.

We can imagine Nyuwa is mending the epigraph of a function to make it closed and convex with the least effort. In the illustration, ‘where the function is not convex’, it is replaced with a segment, or an affine function. It is tempting to assume that anywhere a continuous function does not agree with its convex envelope, it is affine within some neighbourhood, which is not generally true for 2- or higher-dimensional spaces. The correct generalisation is that the convex conjugate will be affine on some segment of the domain.

Proposition Suppose $f:K\to\mathbb{R}$ ($K$ is a convex and open subset of some Euclidean space) is continuous and has its biconjugate $f^{\ast\ast}$ defined everywhere in $K$. If $f^{\ast\ast}$ is strictly convex, then $f=f^{\ast\ast}$.

Remarks The assumption of $f$ being continuous simplifies the exposition. This requirement can be relaxed to $f$ being lower semi-continuous. However, completely removing the assumption falsifies the conclusion. For example, the function $f\left(x\right)=\begin{cases}1,&x=0;\\x^2,&x\neq 0;\end{cases}$ has convex envelope $x^2$ and they do not agree at 0, yet the convex envelope cannot be affine within any open set. The fault is due to $f$ not being lower semi-continuous at 0.

Corollary Using the same notations, if $f$ is not convex, then its biconjugate $f^{\ast\ast}$ must be affine on some segment. In other words, it always suffices to just make any non-convex function non-strictly convex, and Nyuwa will not waste her effort.

Remarks The strict convexities of such a function and its biconjugate are equivalent. The other direction isn’t particulary interesting, because we know $f^{\ast\ast}=f$ if $f$ is ‘already’ convex.

Proof We prove by contradiction. Suppose $f\left(y\right)\neq f^{\ast\ast}\left(y\right)$ for some $y\in K$. Define $\varepsilon=\frac12\left({f\left(y\right)-f^{\ast\ast}\left(y\right)}\right)>0.$ Note that $f-f^{\ast\ast}$ is continuous in $K$, therefore, there exists some $\delta>0$ such that $f\left(x\right)-f^{\ast\ast}\left(x\right)>\varepsilon$ whenever $\left|{x-y}\right|<2\delta$.

Let $g$ be a supporting hyperplane of $f^{\ast\ast}$ at $y$. Since $f^{\ast\ast}$ is strictly convex, we have $f^{\ast\ast}\left(x\right)-g\left(x\right)>0$ whenever $\left|{x-y}\right|=\delta$. The sphere centered at $y$ with radius $\delta$ is compact and is a subset of $K$, whence the function $f^{\ast\ast}-g$ has positive minimum, say $s$, over that sphere.

Write $t=\min\left\{{\varepsilon,s}\right\}>0$. Consider any $x\in K$. If $\left|{x-y}\right|<\delta$, we have $f\left(x\right)>f^{\ast\ast}\left(x\right)+\varepsilon\geq g\left(x\right)+t.$ Otherwise, $\left|{x-y}\right|\geq\delta$, let $\lambda=\frac{\delta}{\left|{x-y}\right|}\leq 1$ and $z=y+\lambda\left({x-y}\right)$. Note that $\left|{z-y}\right|=\delta$. By the convexity of $f^{\ast\ast}-g$ and that $f^{\ast\ast}\left(y\right)=g\left(y\right)$, we have $\begin{aligned}f\left(x\right)-g\left(x\right)&{}\geq f^{\ast\ast}\left(x\right)-g\left(x\right)\\&{}\geq\lambda\left({f^{\ast\ast}\left(x\right)-g\left(x\right)}\right)\\&{}=\lambda\left({f^{\ast\ast}\left(x\right)-g\left(x\right)}\right)+\left({1-\lambda}\right)\left({f^{\ast\ast}\left(y\right)-g\left(y\right)}\right)\\&{}\geq f^{\ast\ast}\left(z\right)-g\left(z\right)\\&{}\geq s\geq t.\end{aligned}$ Summarised, $f\left(x\right)\geq g\left(x\right)+t$ for all $x\in K$. Since the biconjugate takes a supremum, $f^{\ast\ast}\left(y\right)\geq g\left(y\right)+t=f^{\ast\ast}\left(y\right)+t,$ but $t>0$. ${\to}\hspace*{-2pt}{\parallel}$