2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Look up the concept of a "subgradient" $\endgroup$ – Brian Borchers Feb 5 '17 at 17:09
  • 2
    $\begingroup$ 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$. $\endgroup$ – John Dawkins Feb 5 '17 at 17:16
  • $\begingroup$ John Dawkins is right. In the differentiable case you have $a = f'(x_0)$ which depends explicitly on $x_0$. $\endgroup$ – Paul Frost Aug 7 '18 at 19:05
  • $\begingroup$ 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. $\endgroup$ – Robert Wolfe Aug 7 '18 at 22:33
2
$\begingroup$

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

Added on request:

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.