# $f \text{ convex }\Rightarrow \forall (x_0,f(x_0))\in \Gamma(f) \exists a : \forall x\in \mathbb{R}, f(x) \ge a(x-x_0)+f(x_0)$

$f:I \to \mathbb R$ is a convex function on an open interval $I$. I know that if $f$ is differentiable on $I$, then $\forall x_0,x \in I , f(x_0)+f'(x_0)(x-x_0) \le f(x)$

I read somewhere that something similar true even if $f$ is not differentiable, i.e. $\exists a \in \mathbb R: \forall x_0, x \in I, f(x) \ge a(x-x_0)+f(x_0)$.

Does anybody know a proof for that? It would e.g. help to show that $\forall x_0 \in I$ there is a convex differentiable function $g:I \to \mathbb R, g(x_0)=f(x_0)$ and $\forall x \in I, g(x) \le f(x)$

• Look up the concept of a "subgradient" – Brian Borchers Feb 5 '17 at 17:09
• You seem to have your quantifiers in the wrong order. For example, if $f(x)=x^2$ for all $x$, then consideration of $x_0=0$ shows that $a=0$; this $a$ is incompatible with $x_0=1$. Most likely you want to show: If $f$ is convex then for all $x_0$ there exists $a$ such that $f(x)\ge a(x-x_0)+f(x_0)$ for all $x$. – John Dawkins Feb 5 '17 at 17:16
• John Dawkins is right. In the differentiable case you have $a = f'(x_0)$ which depends explicitly on $x_0$. – Paul Frost Aug 7 '18 at 19:05
• A convex function is left-differentiable and right-differentiable at every point. Any $a$ between these left- and right-derivatives at that point will satisfy your inequality. – Robert Wolfe Aug 7 '18 at 22:33

It is well-known that a convex function $f : I \to \mathbb{R}$ defined on an open interval is continuous and has a left derivative $f'_-(x_0) = \lim_{x \to x_0^-} \frac{f(x) - f(x_0)}{x-x_0}$ and a right derivative $f'_+(x_0) = \lim_{x \to x_0^+} \frac{f(x) - f(x_0)}{x-x_0}$ at each $x_0 \in I$ such that for $x_- < x_0 < x_+$

$$\frac{f(x_-) - f(x_0)}{x_- - x_0} \le f'_-(x_0) \le f'_+(x_0) \le \frac{f(x_+) - f(x_0)}{x_+ - x_0} .$$

Then for any $a \in [f'_-(x_0),f'_+(x_0)]$ and $x \ne x_0$ we get

$$a(x - x_0) \le f(x) - f(x_0) .$$

If $f$ is differentiable at $x_0$, this yields

$$f'(x_0)(x - x_0) \le f(x) - f(x_0) .$$

A function $f : I \to \mathbb{R}$ is convex if for all $x_1, x_2 \in I$ and all $t \in [0,1]$ one has $f(tx_1 + (1-t)x_2) \le tf(x_1) + (1-t)f(x_2)$. Here is an alternative characterization of convex functions:

Lemma. For a function $f : I \to \mathbb{R}$ the following are equivalent:

(1) $f$ is convex.

(2) For all $a,b,x \in I$ such that $a \le x \le b$, $f(x) \le f(a) + \frac{f(b) - f(a)}{b-a}(x - a)$.

(3) The function $\Delta_f : I \backslash \{ x_0 \} \to \mathbb{R}, \Delta_f(x) = \frac{f(x) - f(x_0)}{x - x_0}$ is monotonically increasing for all $x_0 \in I$.

Proof. (1) $\Rightarrow$ (2) : Define $t = \frac{b-x}{b-a} \in [0,1]$. Then $x = ta + (1-t)b$ and $1-t = \frac{x-a}{b-a}$ so that $f(x) \le tf(a) + (1-t)f(b) = f(a) + (1-t)(f(b) - f(a)) = f(a) + \frac{f(b) - f(a)}{b-a}(x - a)$.

(2) $\Rightarrow$ (1) : It suffices to consider the case $x_1 < x_2$. Apply (2) for $a = x_1, b = x_2, x = tx_1 + (1-t)x_2$ and use $x - x_1 = (1-t)(x_2-x_1)$.

(2) $\Rightarrow$ (3) : Let $x_1, x_2 \in I \backslash \{ x_0 \}$ such that $x_1 < x_2$. Case 1: $x_0 < x_1$. Let $a = x_0, b = x_2, x = x_1$. Then $f(x_1) \le f(x_0) + \frac{f(x_2) - f(x_0)}{x_2 - x_0}(x_1 -x_0)$, hence $\frac{f(x_1) - f(x_0)}{x_1 - x_0} \le \frac{f(x_2) - f(x_0)}{x_2 - x_0}$. Case 2: $x_2 < x_0$. $a = x_1, b = x_0, x = x_2$. Case 3: $x_1 < x_0 < x_2$. $a = x_1, b = x_2, x = x_0$.

(3) $\Rightarrow$ (2) : $x_1 = a,x_2 =b, x_0 = x$.

The lemma shows that $f'_-(x_0) = \lim_{x \to x_0^-}\Delta_f(x)$ exists because $\Delta_f(x)$ is bounded from above for $x < x_0$. Similarly $f'_+(x_0) = \lim_{x \to x_0^+}\Delta_f(x)$ exists because $\Delta_f(x)$ is bounded from below for $x > x_0$ (by $f'_-(x_0)$ which proves the second inequality).

• Hi! Could you give more details between first and second inequalities? – Lev Bahn Aug 8 '18 at 0:23
• @LevBan I shall edit my answer. – Paul Frost Aug 8 '18 at 7:49
• Thank you so much! – Lev Bahn Aug 8 '18 at 10:46