Nyuwa mends the epigraph

Nyuwa, Hsiao Yun-ts'ung
Nyuwa, Hsiao Yun-ts'ung

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 KRnK\subseteq\mathbb{R}^n be non-empty, convex and open. Let f:KRf:K\to\mathbb{R} be continuous. Its biconjugate, or the convex envelope, is f(x)=supg affineyK:g(y)f(y)g(x).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(f)={(x,y)yf(x)},\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(f)=Conv(epi(f))\epi\left(f^{\ast\ast}\right)=\overline{\operatorname{Conv}\left(\epi\left(f\right)\right)}. See the figure below for a classical illustration.

Convex envelopeConvex envelopeConvex envelopeConvex envelopeConvex envelope
Convex envelope

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 neighborhood, 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:KRf:K\to\mathbb{R} (KK is a convex and open subset of some Euclidean space) is continuous and has its biconjugate ff^{\ast\ast} defined everywhere in KK. If ff^{\ast\ast} is strictly convex, then f=ff=f^{\ast\ast}.

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

Corollary Using the same notations, if ff is not convex, then its biconjugate ff^{\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=ff^{\ast\ast}=f if ff is ‘already’ convex.

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

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

Write t=min{ε,s}>0t=\min\left\{{\varepsilon,s}\right\}>0. Consider any xKx\in K. If xy<δ\left|{x-y}\right|<\delta, we have f(x)>f(x)+εg(x)+t.f\left(x\right)>f^{\ast\ast}\left(x\right)+\varepsilon\geq g\left(x\right)+t. Otherwise, xyδ\left|{x-y}\right|\geq\delta, let λ=δxy1\lambda=\frac{\delta}{\left|{x-y}\right|}\leq 1 and z=y+λ(xy)z=y+\lambda\left({x-y}\right). Note that zy=δ\left|{z-y}\right|=\delta. By the convexity of fgf^{\ast\ast}-g and that f(y)=g(y)f^{\ast\ast}\left(y\right)=g\left(y\right), we have f(x)g(x)f(x)g(x)λ(f(x)g(x))=λ(f(x)g(x))+(1λ)(f(y)g(y))f(z)g(z)st.\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(x)g(x)+tf\left(x\right)\geq g\left(x\right)+t for all xKx\in K. Since the biconjugate takes a supremum, f(y)g(y)+t=f(y)+t,f^{\ast\ast}\left(y\right)\geq g\left(y\right)+t=f^{\ast\ast}\left(y\right)+t, but t>0t>0. {\to}\hspace*{-2pt}{\parallel}

Please enable JavaScript to view the comments powered by Disqus.