# Sufficient condition for convexity

Let f:$[a,b] \rightarrow \mathbb{R}$ a continous function

such that $\forall (x,y) \in [a,b]^{2}, \exists t \in ]0,1[, f(tx+(1-t)y) \le tf(x) + (1-t)f(y)$

show that f is convex

• In what way does this differ from the fundamental definition of convexity? – Michael Grant Jan 6 '15 at 22:05
• What definition on convexity are you using? – Tim Raczkowski Jan 6 '15 at 22:07
• @Winther $\forall t \in [0,1]$ or $\forall t \in ]0,1[$ are the same because the cases t=0 or t=1 are obvious – Terminator Jan 6 '15 at 22:15
• @Winther, please read the question and compare it with the definition, this is not an easy question. – Terminator Jan 6 '15 at 22:22
• Sorry about that, I did not see the quantifier $\exists$. I thought it was $\forall$. Then I agree. – Winther Jan 6 '15 at 22:27

The idea is that a convex combination of convex combinations of two numbers $a$ and $b$ is itself a convex combination of $a$ and $b$,

Assume by contradiction that $f$ is not convex. There exist $x_0,x_1\in [a,b],\ t_0\in[0,1]$, ($x_0<x_1$ for simplicity) such that $f(x_{t_0})>(1-t_0)f(x_0)+t_0f(x_1)$, where $x_{t}:=(1-t) x_0+t x_1$, $0\le t\le 1$.

You prove that $0<t_0<1$.

Denote by $g(t):=f(x_{t})-(1-t)f(x_0)-tf(x_1)$. Since $g$ is continuous and positive at $t_0\in(0,1)$ it stays positive on a whole non-degenerate interval $[u,v]\subset(0,1)$.

Let $\alpha:=\inf \{t\in[0,\alpha]\mid g(s)>0.\forall\ s\in[t,v]\}$.

You prove that $g(\alpha)=0$. Also, you need to define similarly $\omega>\alpha$ such that $g(\omega)=0$ and $g$ stays positive on $(\alpha,\omega)$.

Now we use the given assumption for $x=x_\alpha$, $y=x_\omega$ to get a $t\in(0,1)$ such that $f(tx_\alpha+(1-t)x_\omega)\le tf(x_\alpha)+(1-t)f(x_\omega)$ together with the facts that $tx_\alpha+(1-t)x_\omega=x_s$ (for what $s$? -- very easy to guess), $s\in(\alpha,\omega)$, $f(x_\alpha)=(1-\alpha)f(x_0)+\alpha f(x_1)$, and similarly for $f(x_\omega)$. You get a contradiction from the previous inequality. You need to complete all details and/or simplify this proof.

Where is the condition $t\in(0,1)$ essential?

• I think, it should be $\alpha = inf \left\{ t \in [u,t_0] \ | \ g(t)>0 \right\}$ and $\omega = sup \left\{ t \in [t_0, v] \ | \ g(t_0)>0 \right\}$, but your idea is good. Well done. – Terminator Jan 7 '15 at 18:32

A proof might go like this (i.e., this is incomplete):

Suppose that $f$ is not convex. Then there are two points $P=(u, f(u))$ and $Q=(v, f(v))$ such that the line between them is sometimes below $f$; i.e., there is a $t \in (0, 1)$ such that, if $w = tu+(1-t)v$, then $f(w) < tf(u)+(1-t)f(v)$.

Since $f$ is continuous, there is a region around $w$ where the line connecting such points is completely below $f$. This is the part I'm not completely sure of how to prove. I think that we could narrow regions where a point on the line is below $f$ and use the continuity of $f$ to establish an interval where the line is below the curve.

Suppose $f$ is not convex. It means there is an interval $[x,y]\subset[a,b]$ where the line between $x$ and $y$ is above the curve: $$\exists x,y\in[a,b],\forall t\in[0,1]:f(tx+(1-t)y) > tf(x) + (1-t)f(y)$$ which is equivalent to $$\exists x,y\in[a,b],\not\exists t\in[0,1]:f(tx+(1-t)y) \le tf(x) + (1-t)f(y)$$ This contradicts the hypothesis.

By bissection, you can go to $\forall(x,y)\in[a,b]^2,\forall t\in]0,1[, f(tx+(1−t)y)≤tf(x)+(1−t)f(y)$

Let $(x,y) \in [a,b]^2$, let $t^* \in [0,1]$. We want to prove that $$f(t^*x+(1−t^*)y)≤t^*f(x)+(1−t^*)f(y)$$. By property, there exist $t_0$ such as

$$f(t_0x+(1−t_0)y)≤t_0f(x)+(1−t_0)f(y)$$

Let $x_0 = t_0x + (1 -t_0)y$. If $t \in [x, x_0]$, there exist $t_1$ such as

\begin{eqnarray} f(t_1x+(1−t_1)x_0)) & ≤ & t_1f(x)+(1−t_1)f(x_0) \\ & \leq & t_1f(x)+(1−t_1)t_0f(x)+(1−t_0)f(y) \\ & \leq & (t_1 + (1-t_1)t_0) f(x) + (1-t_1)(1-t_0)f(y) \end{eqnarray}

and so forth, you have $t \in [t_{i} , t_{j}]$, with inequality verified by $x_i$ and $x_j$ and both converging to $t$. With continuity of $f$, it's done.

• why did you write if $t \in [x,x_0]$, t, x and $x_0$ are in general in different intervals $0 \le t \le 1$, but, $a \le x, x_0, y \le b$, for example if $a > 1$, please correct if I'm wrong. – Terminator Jan 7 '15 at 17:51