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$.

Solution 1:

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$, \begin{equation}\label1\tag1f(y)\geq f(x)+\langle y-x,\nabla f(x)\rangle\end{equation} but also \begin{equation}\label2\tag2f(x)\geq f(y)+\langle x-y,\nabla f(y)\rangle.\end{equation}

\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]$, \begin{equation} 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, \end{equation} 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$