# Equivalent definitions of convexity for $f\in\mathcal C^1(\mathbb R^n)$

I noticed many identical questions on this site relating to equivalent definitions of convexity, see for example 668679, 740938, 318692, 1717542, 1761801, 3019331, 3047518 and there might be more.

So I wanted to create a "big list" of equivalent definitions of convex functions, I will start with some equivalent definitions and post my proofs in my answer below. Feel free to add any other equivalent definitions. This question can then serve as an abstract duplicate.

Claim. Let $$n\in\mathbb N$$ and $$f\in\mathcal C^1(\mathbb R^n)$$. Then the following are equivalent:

1. $$f$$ is convex, i.e. $$f(\lambda x_1 + (1-\lambda x_2))\le\lambda f(x_1)+(1-\lambda)f(x_2)$$ for all $$\lambda\in[0,1]$$ and $$x_1,x_2\in\mathbb R^n$$.
2. For all $$x,y\in\mathbb R^n$$, $$\langle\nabla f(x)-\nabla f(y),x-y\rangle\geq0$$.
3. For every $$x,y\in\mathbb R^n$$, $$f(y)\geq f(x)+\langle y-x,\nabla f(x)\rangle$$.
• (1) Note your 2nd item holds even if $f$ is not $C^1$ -- more generally the subdifferential $\partial f$ needs to only be maximally monotone (which is precisely that inequality). (2) some books have "function convexity" inherited from the definition of "set convexity", in the following way: $f$ is said to be convex if the epigraph of $f$ is convex. Then, it is shown that definition actually implies the other ones. (3) Your first item could be fixed to have minimal assumptions, in that convexity is guaranteed even when $\lambda\in\left]0,1\right[$.
– Zim
Commented Jan 23, 2021 at 1:44

Proof of equivalence of 1., 2. and 3.
1.$$\implies$$3. Let $$f$$ be convex. Then, by definition of the gradient, for every $$x,y\in\mathbb R^n$$, \begin{align} \langle y-x, \nabla f(x)\rangle &= \lim_{h\to0}\frac{f(x+h(y-x))-f(x)}{h}\\&=\lim_{h\to0}\frac{f((1-h)x+hy)-f(x)}{h}\\&=\lim_{h\to0, h>0}\frac{f((1-h)x+hy)-f(x)}{h} \\&\overset{\text{convexity}}\le \lim_{h\to0, h>0}\frac{hf(y)-hf(x)}h\\&=f(y)-f(x). \end{align}

3.$$\implies$$2. By assumption 3., we have, for every $$x,y\in\mathbb R^n$$, $$$$\label1\tag1f(y)\geq f(x)+\langle y-x,\nabla f(x)\rangle$$$$ but also $$$$\label2\tag2f(x)\geq f(y)+\langle x-y,\nabla f(y)\rangle.$$$$

\eqref{2} is equivalent to $$-f(y)+\langle y-x,\nabla f(y)\rangle\geq -f(x),$$ which added to \eqref{1} yields $$\langle y-x,\nabla f(y)\rangle\geq\langle y-x,\nabla f(x)\rangle$$ and thus the desired result.

2.$$\implies$$1. Suppose that 2. is true and define $$g:[0,1]\to\mathbb R$$, $$g(t)\overset{\text{Def.}}=f(x+t (y-x))$$. Then $$g$$ is convex as, for $$t\in[0,1]$$, $$$$g'(t)=\lim_{h\to0}\frac{f(t y +(1-t)x + h(y-x))- f(t y+(1-t)x)}{h} = \langle y-x, \nabla f(t y +(1-t)x)\rangle,$$$$ so that, for $$0\le t_1< t_2\le 1$$, \begin{align} g'(t_2)-g'(t_1)&=\langle y-x, \nabla f(x+t_2 (y-x)) -\nabla f(x+t_1(y-x))\rangle \\ &=\frac1{t_2-t_1}\langle (x+t_2 (y-x)) - (x+t_1(y-x)), \nabla f(x+t_2 (y-x)) -\nabla f(x+t_1(y-x))\rangle \\ &\geq 0, \end{align} by assumption 3.

Hence $$g'$$ is increasing and thus $$g$$ is indeed convex (proof).

So we have $$g(\lambda)\le\lambda g(1)+(1-\lambda) g(0)$$ for every $$\lambda\in[0,1]$$, which, by definition of $$g$$, is exactly $$f((1-\lambda)x+\lambda y)\le(1-\lambda) f(x)+\lambda f(y).$$

$$\square$$