3

I got the following definition of a convex functions on $\mathbb R$:

Let $I \subseteq \mathbb R$ be an interval and $f \to \mathbb R$. Then $f$ is called convex, if for all $x_1,x_2 \in I$ and all $\lambda \in [0,1]$ holds that $f((1-\lambda)x_1 + \lambda x_2) \le (1 - \lambda)f(x_1) + \lambda f(x_2)$.

I wonder why this is equivalent to the following: For all $x_0 \in I$ there exists some number $c(x_0)$ such that $f(x) \ge f(x_0) + c(x - x_0), $ $ x \in I$.

A proof and or a geometrical interpretation would be helpful.

Pazu
  • 1,077
  • Convex means that the super-graph is a convex set. The first condition means that the graph between two points is always below the chord. The second condition means that there is a line at every point, a support line, like a tangent, such that the whole graph is above it. If you intersect all those half planes you get the super-graph. An intersection of convex sets is convex. Showing that the first condition is equivalent to the super-graph being convex is also easy. – Bettybel Jul 05 '17 at 18:35

3 Answers3

4
  1. $S=\{(x,y):\ x\in I, y\geq f(x)\}$ is convex.
  2. Let $I \subseteq \mathbb R$ be an interval and $f \to \mathbb R$. Then $f$ is called convex, if for all $x_1,x_2 \in I$ and all $\lambda \in [0,1]$ holds that $f((1-\lambda)x_1 + \lambda x_2) \le (1 - \lambda)f(x_1) + \lambda f(x_2)$.
  3. For all $x_0 \in I$ there exists some number $c(x_0)$ such that $f(x) \ge f(x_0) + c(x - x_0), $ $ x \in I$.

If (1) then $(1-\lambda)(x_1,f(x_1))+\lambda(x_2,f(x_2)) = ((1-\lambda)x_1+\lambda x_2,(1 - \lambda)f(x_1) + \lambda f(x_2)) \in S$. This means (2).

If (2), $(x_1,y_1),(x_2,y_2)\in S$ and $\lambda\in[0,1]$. Then $(1-\lambda)y_1+\lambda y_2\geq (1-\lambda)f(x_1)+\lambda f(x_2)\geq f((1-\lambda)x_1+\lambda x_2)$. This means that $((1-\lambda)x_1+\lambda x_2, (1-\lambda)y_1+\lambda y_2)\in S$. This means that (1).

If (3) then (1). Because $S$ turns out to be equal to the intersection of all the half-planes $\{y\geq f(x_0)+c_{x_0}(x-x_0)\}$, which are convex and the rectangle $I\times\mathbb{R}$, which is also convex.

If (1) then proving (3) is this kind of standard business.

Bettybel
  • 377
4

The claim is WRONG.

Take $I = [-1,1]$, and $f(x) = - \sqrt{1-x^2}$, then clearly $f$ is convex.But for $x_0 = 1 $ there exist No $c \in R$ such that $$f(x) \ge f(x_0) + c(x - x_0)$$ for all $x \in I.$

The claim is true provided that $x_0$ is chosen in interior point of $I$, i.e., $ x_0 \in \text{int }I = (a,b)$. Then one possible argument (but not best) to prove the claim can be an argument like in @cooper.hat 's answer by following correction

$$ R(a,x_0) \leq c_- = \limsup_{h \uparrow 0}R(x_0,x_0+h) \le \liminf_{h \downarrow 0}R(x_0,x_0+h) = c_+ \leq R(x_0, b ) $$

Red shoes
  • 6,948
  • Instead of indicating that the argument is not the best, why not add the best argument? The first line of the question suggests that the functions are defined on $\mathbb{R}$. – copper.hat Jul 08 '17 at 03:09
  • Here, my point was toward OP, which could directly show

    $$ c:=\inf_{x > x_0} \frac{f(x) - f(x_0) }{ x - x_0 } <+ \infty $$

    provided $ x_0 \in \text{int} I $. And I didn't say your argument is not good !

    @copper.hat

     – Red shoes Jul 08 '17 at 08:17
  • @Ashkan You made a good point here. This equivalent definition was actually used in the proof of Jensen's inequality : $ \phi $ $ convex \implies \mathbb E( \phi (X)) \ge \phi ( \mathbb E (X)) $ (stochastics). In the proof it was distinguished whether $\mathbb E(X)$ is an interior point or a boundary point. – Pazu Jul 08 '17 at 09:16
3

Here is another approach:

Suppose $f$ is convex, $x \neq y$, and $R(x,y) = {f(x)-f(y) \over x-y }$ (see https://en.wikipedia.org/wiki/Convex_function#Properties) .

It is straightforward to show that if $ x<y<z$, then $R(x,y) \le R(y,z)$. This can be seen graphically by noticing that the slopes of the secants joining points on the graph of $f$ at $x,y,z$ are non decreasing.

Pick $x_0$, then the above shows that $c_- = \limsup_{h \uparrow 0}R(x_0,x_0+h) \le \liminf_{h \downarrow 0}R(x_0,x_0+h) = c_+$. Choose $c_0 \in [c_-,c_+]$, then if $x>x_0$ we have $R(x,x_0) \ge c_0$ and if $x<x_0$ we have $R(x,x_0) \le c_0$. Combining shows that $f(x) \ge f(x_0) + c(x-x_0)$ for all $x$.

For the other direction, suppose $\lambda \in (0,1)$ and $x_0 = (1-\lambda) x_1 + \lambda x_2$. Let $c_0$ be the constant $c(x_0)$, then we have $f(x_1)-f(x_0) \ge c_0(x_1-x_0)$ and $f(x_2)-f(x_0) \ge c_0(x_2-x_0)$.

Hence $(1-\lambda) (f(x_1)-f(x_0)) + \lambda (f(x_2)-f(x_0)) \ge (1-\lambda )c_0(x_1-x_0) + \lambda c_0(x_2-x_0)$ which reduces to $(1-\lambda) f(x_1) + \lambda f(x_2) \ge f(x_0)$.

copper.hat
  • 172,524
  • How do you know $c_-$ and $c_+$ are finite ? – Red shoes Jul 08 '17 at 00:13
  • $c_+ \le R(x_0,x_0+1)$, and similarly for $c_-$. The function is defined on $\mathbb{R}$ so there are no boundary situations to deal with. – copper.hat Jul 08 '17 at 03:06
  • I don't see in question that $f$ is defined on whole $\Bbb{R}$. Even $f$ is defined on whole space, $f$ is only convex on interval $I$ (as question states). First line is not part of question, and OP clearly defines convexity on $I$.

    even if you have taken $f: \Bbb{R} \to \Bbb{R} $ is convex. Don't you think you should have used this assumption ( clearly ) in your argument ? since otherwise there is counter example !

     – Red shoes Jul 08 '17 at 08:02
  • @Ashkan: I read the first line as indicating that $f$ was a convex function on $\mathbb{R}$. Depending on how pedantic one wishes to be, there is no requirement that $c(x_0)$ be finite valued (it is not stated in the question). Choosing $c(-1) = -\infty, c(1) = +\infty$ in your example would work (cf. asymptotic generalised gradient). – copper.hat Jul 08 '17 at 16:28