Show that the graph of a convex function is above any tangent plane

Question

In proving jensen inequality one use that the graph of a convex function is above any tangent plane. I've been reading Property of convex functions and Tangent line of a convex function. But what about the non differential case. I think it should be something about existence of subgradients to convex functions? Can anyone come up with a modified proof? thanks

Answer 1

Hope I am interpreting the question correctly, here is my attempt of a proof of the following result:

Let $A\subseteq\mathbb{R}^n$ be an open convex set. Then $f:A\to\mathbb{R}$ is a convex function iff for any $\mathbf a\in A$, $\exists\mathbf m\in\mathbb{R}^n$ such that $f(\mathbf x)\geq f(\mathbf a)+\mathbf m\cdot(\mathbf x-\mathbf a)$ for all $\mathbf x\in A$.

(Forward)

First we prove the case $n=1$. Pick any $a\in A$. Note that if $f(x)$ is convex then so is $h(x)=f(x+\mu)-\lambda$. So wlog let $a=0$ and $f(0)=0$. Now let $m=\inf\left\{f(x)/x:x\in A, x>0\right\}$.

Suppose $m=-\infty$. Pick $y<0$ with $y\in A$. Let $\alpha=f(y)/y$. We can find $x>0$ such that $f(x)/x<\alpha-1$. We have $$0=f(0)\leq\left(\frac{-y}{x-y}\right)f(x)+\left(\frac{x}{x-y}\right)f(y)<\left(\frac{-y}{x-y}\right)(\alpha-1)x+\left(\frac{x}{x-y}\right)y\alpha<0$$ Contradiction, so $m\not=-\infty$ (ie. $m$ is finite). So we must have $f(x)\geq mx$ for all $x\geq 0$. Suppose $\exists y<0$ with $f(y)<my$. Define $g:A\to\mathbb{R}$ by $g(x)=f(x)-mx$, then $g$ is convex. We have $g(y)<0$, let $\varepsilon=g(y)/y$, then $\varepsilon>0$. We can find $x>0$ such that $m\leq f(x)/x\leq m+\varepsilon/2$, so $0\leq g(x)/x\leq\varepsilon/2$. Now by convexity $$0=g(0)\leq\left(\frac{-y}{x-y}\right)g(x)+\left(\frac{x}{x-y}\right)g(y)<\left(\frac{-y}{x-y}\right)\frac{x\varepsilon}{2}+\left(\frac{x}{x-y}\right)(y\varepsilon)<0$$ Contradiction, so we have $f(x)\geq mx$ for all $x\in A$.

Now we prove the general statement by induction. Suppose it's true for $n=k$. Let $A\subseteq\mathbb{R}^k\times\mathbb{R}=\mathbb{R}^{k+1}$ be an open and convex set and $f:A\to\mathbb{R}$ a convex function. Pick $\mathbf a\in A$, wlog assume $\mathbf a=(\mathbf 0,0)$ and $f(\mathbf 0,0)=0$. By induction assumption we can find $\mathbf m\in\mathbb{R}^k$ such that $f(\mathbf x,0)\geq \mathbf m\cdot\mathbf x$ for all $(\mathbf x,0)\in A$. By openness $\exists (\mathbf x,y)\in A$ with $y>0$ and $y<0$. Define $g:A\to\mathbb{R}$ by $g(\mathbf x,y)=f(\mathbf x,y)-\mathbf m\cdot\mathbf x$, note that $f$ is convex iff $g$ is convex. Let $$M=\inf\left\{\frac{g(\mathbf x,y)}{y}:y>0, (\mathbf x,y)\in A\right\}$$ Suppose $M=-\infty$. Pick $(\mathbf w, z)\in A$ with $z<0$. Let $\alpha=g(\mathbf w, z)/z$. We can find $(\mathbf x,y)\in A$ with $y>0$ such that $g(\mathbf x,y)/y<\alpha-1$. We have $$0\leq g(\mathbf u,0)\leq\frac{-zg(\mathbf x,y)}{y-z}+\frac{yg(\mathbf w,z)}{y-z}<\left(\frac{-z}{y-z}\right)(\alpha-1)y+\left(\frac{y}{y-z}\right)z\alpha<0$$ where $\mathbf u=(y\mathbf w-z\mathbf x)/(y-z)$. Contradiction, so $M\not=-\infty$. So we must have $g(\mathbf x,y)\geq My$ for all $y\geq 0$. Suppose $\exists (\mathbf w,z)\in A$ with $z<0$ such that $g(\mathbf w,z)<Mz$. Define $h:A\to\mathbb{R}$ by $h(\mathbf x,y)=g(\mathbf x,y)-My$, then $h$ is convex. We have $h(\mathbf w,z)<0$, let $\varepsilon=h(\mathbf w,z)/z$, then $\varepsilon>0$. We can find $(\mathbf x,y)\in A$ with $y>0$ such that $M\leq g(\mathbf x,y)/y\leq M+\varepsilon/2$, so $0\leq h(\mathbf x,y)/y\leq\varepsilon/2$. Now by convexity $$0\leq h(\mathbf u,0)\leq\frac{-zh(\mathbf x,y)}{y-z}+\frac{yh(\mathbf w,z)}{y-z}<\left(\frac{-z}{y-z}\right)\frac{y\varepsilon}{2}+\left(\frac{y}{y-z}\right)(z\varepsilon)<0$$ Contradiction, so we have $g(\mathbf x,y)\geq My$ for all $(\mathbf x,y)\in A$. So $f(\mathbf x,y)\geq(\mathbf m,M)\cdot(\mathbf x,y)$ for all $(\mathbf x,y)\in A$. Hence the result by induction.

(Backward)

We have $f(\mathbf{y}) \geq f(\mathbf{z}) + (\mathbf{y} - \mathbf{z})\cdot \mathbf m$ and $f(\mathbf{x}) \geq f(\mathbf{z}) + (\mathbf{x} - \mathbf{z})\cdot \mathbf m$. So let $\mathbf z=(1-t)\mathbf{x}+t\mathbf{y}$, we have $$(1-t)f(\mathbf{x})+tf(\mathbf{y})\geq f(\mathbf{z})+((1-t)\mathbf{x}+t\mathbf{y}-\mathbf{z})\cdot\mathbf m= f((1-t)\mathbf{x}+t\mathbf{y})$$