2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ In what way does this differ from the fundamental definition of convexity? $\endgroup$ – Michael Grant Jan 6 '15 at 22:05
  • 2
    $\begingroup$ What definition on convexity are you using? $\endgroup$ – Tim Raczkowski Jan 6 '15 at 22:07
  • $\begingroup$ @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 $\endgroup$ – Terminator Jan 6 '15 at 22:15
  • $\begingroup$ @Winther, please read the question and compare it with the definition, this is not an easy question. $\endgroup$ – Terminator Jan 6 '15 at 22:22
  • $\begingroup$ Sorry about that, I did not see the quantifier $\exists$. I thought it was $\forall$. Then I agree. $\endgroup$ – Winther Jan 6 '15 at 22:27
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Terminator Jan 7 '15 at 18:32
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Terminator Jan 7 '15 at 17:51

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.