28
$\begingroup$

Given that $$f\left(\frac{x+y}{2}\right)\leqslant \frac{f(x)+f(y)}{2}~,$$ how can I show that $f$ is convex.
Thanks.


Edit: I'm sorry for all the confusion. $f$ is assumed to be continuous on an interval $(a,b)$.

$\endgroup$
  • 3
    $\begingroup$ You can't. At least, not without assuming that $f$ is continuous. $\endgroup$ – Willie Wong Nov 18 '11 at 15:06
  • 4
    $\begingroup$ Lebesgue measurability is enough @WillieWong. This is a theorem by Sierpinski. (If I recall correctly). $\endgroup$ – Jonas Teuwen Nov 18 '11 at 15:11
  • 6
    $\begingroup$ The trick in the continuous case is to set $z = \frac{p}{2^{n + 1}} x + \frac{q}{2^{n + 1}} y$ with $p + q = 2^{n + 1}$ and proceed by induction. $\endgroup$ – Jonas Teuwen Nov 18 '11 at 15:15
  • 1
    $\begingroup$ @Jonas: right. I should have said "... something like '$f$ is continuous' ". The obvious counterexample is, of course, not Lebesgue measurable. Thanks for the correction. $\endgroup$ – Willie Wong Nov 18 '11 at 17:13
  • 1
20
$\begingroup$

Below is the proof of the fact that every midpoint-convex function is rationally convex, which I copied from my older post on a different forum.

If you add the condition that $f$ is continuous, then from rational convexity you will get convexity. (Note that if you are interested only in continuous functions, then it suffices to show the validity of $f(t x + (1-t)y)\le t f(x) + (1-t)f(y)$ for $t=\frac k{2^n}$ as suggested in Jonas' comment. The proof of this fact is a little easier. I've given a little more involved proof, since the relation between midpoint convexity and rational convexity seems to be interesting on its own.)

Maybe I should also mention that midpoint-convex functions are called Jensen convex by some authors.

Note that without some additional conditions on $f$, midpoint convexity does not imply convexity; see this question: Example of a function such that $\varphi\left(\frac{x+y}{2}\right)\leq \frac{\varphi(x)+\varphi(y)}{2}$ but $\varphi$ is not convex


Let $f: \mathbb R\to \mathbb R$ be a midpoint-convex function, i.e. $$f\left(\frac{x+y}2\right) \le \frac{f(x)+f(y)}2$$ for any $x,y \in \mathbb R$.

We will show that then this function fulfills $$f(t x + (1-t)y)\le t f(x) + (1-t)f(y)$$ for any $x,y\in \Bbb R$ and any rational number $t\in\langle0,1\rangle$.

Hint: Cauchy induction: see wikipedia or AoPS or answers to this post.

Proof. It is relatively easy to see that it suffices to show $f([x_1+\dots+x_k]/k)\le [f(x_1)+\dots+f(x_k)]/k$ for any integer $k$ (and any choice of $x_1,\dots,x_k\in \mathbb R$).

The case $k=2^n$ is a straightforward induction.

Now, if $2^{n-1}<k\le 2^n$, then we denote $\overline x=\frac{x_1+\dots+x_k}k$. Now from $$f(\overline x)=f\left(\frac{x_1+\dots+x_k+\overline x+\dots+\overline x}{2^n}\right) \le\frac{f(x_1)+\dots+f(x_k)+(2^n-k)f(\overline x)}{2^n},$$ where $2^n-k$ copies of $\overline x$ are summmed in the middle expression, we get $kf(\overline x) \le f(x_1)+\dots+f(x_k)$ by a simple algebraic manipulation.


The fact that measurability of $f$ is enough for the implication midpoint-convex $\Rightarrow$ convex to hold was mentioned in some of the comments above and in answers to the question I linked. Some references for this fact:

Constantin Niculescu, Lars Erik Persson: Convex functions and their applications, p.60:

H. Blumberg [31] and W. Sierpinski [226] have noted independently that if $f : (a, b) \to \mathbb R$ is measurable and midpoint convex, then $f$ is also continuous (and thus convex). See [212, pp. 220.221] for related results.

[31] H. Blumberg, On convex functions, Trans. Amer. Math. Soc. 20 (1919), 40–44.

[212] A. W. Roberts and D. E. Varberg, Convex Functions, Academic Press, New York and London, 1973.

[226] W. Sierpinski, Sur les fonctions convexes mesurables, Fund. Math. 1 (1920), 125–129.

Marek Kuczma: An introduction to the theory of functional equations and inequalities, p.241. He mentions the book T. Bonnesen and W. Fenchel, Theorie der konvexen Körper, Berlin, 1934 as an additional reference.

$\endgroup$
  • $\begingroup$ Not to be too much of a whiner, but that "Spoiler" trick is annoying when the point of asking a question here is to get an answer. It's not like accidentally glancing at your text is going to reveal the answer, so if I want to avoid reading it, I avoid reading it. In addition, there is no way to show your text on displays that do not have "mouse-over" - it stays blank on my iPad no matter what I do, for example. There might be fora and questions where it is appropriate, but this doesn't sem to be one of them. $\endgroup$ – Thomas Andrews Nov 18 '11 at 15:51
  • $\begingroup$ Sorry @Thomas, I've removed it. $\endgroup$ – Martin Sleziak Nov 18 '11 at 16:01
  • $\begingroup$ @Hi, just double check. When I check the midpoint convexity, I have to show the inequality holds for any $x,y$ right? I can not just pick $x,y$ such that $f(x)=f(y)$, which looks like checking for quasi-concavity. $\endgroup$ – Bob Oct 7 '16 at 12:29
  • $\begingroup$ @Bob Yes, by definition midpoint convex means that this inequality is true for any $x$, $y$. $\endgroup$ – Martin Sleziak Oct 7 '16 at 12:49
  • $\begingroup$ @MartinSleziak, I find it is easy for people to make this mistake. Pick $x,y$ such that $f(x)=f(y)$, and once they showed $f(0.5x+0.5y)>f(x)$ they thought they proved concavity, but only got quasi-concavity. We can pick such two points ($x,y$ s.t. $f(x)=f(y)$) wolg for quasi-concavity, but not for concavity. $\endgroup$ – Bob Oct 7 '16 at 13:31
5
$\begingroup$

As was already previously mentioned it is straightforward to see that for a mid point convex function f $$f\left(\frac{x_1+x_2+\ldots+x_{2^n}}{2^n}\right)\leq\frac{1}{2^n}(f(x_1)+f(x_2)+\ldots f(x_{2^n}))$$ By setting $x_i=x$ for $1\leq i\leq m$ and $x_i=y$ for $m+1\leq i\leq 2^n$ where $1\leq m\leq 2^n$ is an integer we now obtain $$f\left(\frac{m}{2^n}x+(1-\frac{m}{2^n})y\right)\leq \frac{m}{2^n}f(x)+(1-\frac{m}{2^n})f(y)$$ Since the set of rational dyadic numbers of the form $\frac{m}{2^n}$ with $m$ and $n$ integers and $1\leq m\leq 2^n$ is dense in $[0,1]$ the proof follows from the continuity of f.

$\endgroup$
3
$\begingroup$

Can you provide any more information about $f$? For example, the property holds for continuous functions $f: I \rightarrow \mathbb{R}$, $I$ being an interval of real numbers. I think this result is due to Jensen [1].

Theorem (Jensen). Let $f: I\rightarrow\mathbb{R}$ be a continuous function. Then $f$ is convex if and only if it is midpoint convex, i.e. for $x,y$ in $I$ we have

$$ f\left(\frac{x+y}{2}\right) \leq \frac{f(x)+f(y)}{2} $$

[1] J. L. W. V. Jensen, Sur les fonctions convexes et les inégalités entre les valeurs moyennes, Acta Math., 30 (1906), 175-193.

$\endgroup$
  • 1
    $\begingroup$ Jensen doesn't prove this, per se, in this paper (his definition of "convex" was the modern-day "midpoint-convex"). It's more correct to say that he proved Jensen's Inequality (with arbitrary real weights) for functions which are midpoint convex and continuous. Of course, Jensen's Inequality with two arguments gives the modern definition of convexity. $\endgroup$ – Robert Wolfe Nov 9 '17 at 20:30
1
$\begingroup$

Given a weight lambda, take its binary expansion. Think of what midpoint convexity implies to the inequalities involving the partial sums of this binary expansion. Then the result follows by the continuity of f.

$\endgroup$
1
$\begingroup$

I would like to properly show by induction that if $ m\in\{0,1,2,\ldots,2^{n}-1\} $ then $$ f\left(\frac{m}{2^n}x+\Big(1-\frac{m}{2^k}\Big)y\right)\le \frac{m}{2^n}f(x) +\Big(1-\frac{m}{2^n}\Big)f(y). $$ and then the result will follows by contuinity since $$ m=\lfloor2^nt\rfloor \in\{0,1,2,\ldots,2^{n}\} ~~~and~~\frac{\lfloor2^nt\rfloor}{2^n}\to t$$


The initial state $n = 1$ is trivial by hypothesis.

Now we assume that for every $k<n$, whenever $m\in\{0,1,2,\ldots,2^{k-1}-1\}$,we have $$ f\left(\frac{m}{2^k}x+\Big(1-\frac{m}{2^k}\Big)y\right)\le \frac{m}{2^k}f(x) +\Big(1-\frac{m}{2^k}\Big)f(y). \tag{I}\label{I} $$

we want to prove \eqref{I} for $k=n$.

Let $m \in\{0,1,2,\ldots,2^{n}-1\}$ then the division by 2 yields $m =2p +r$ with $r\in \{0,1\}$ \begin{align}X&:=\left(\frac{m}{2^n}x+\Big(1-\frac{m}{2^n}\Big)y\right)= \left(\frac{2p +r}{2^n}x+\Big(1-\frac{2p +r}{2^n}\Big)y\right) \\&= \left(\frac{p }{2^n}x+\frac{p +r}{2^n}x+\Big(1-\frac{p }{2^n}y-\frac{p +r}{2^n}y\Big)y\right) \\&= \frac12 \left(\frac{p }{2^{n-1}}x+\frac{p +r}{2^{n-1}}x+\Big(2-\frac{p }{2^{n-1}}y-\frac{p +r}{2^{n-1}}y\Big)y\right) \\&=\frac12\left(\frac{p }{2^{n-1}}x+ \Big(1-\frac{p }{2^{n-1}}y\Big)\right)+\frac12\left(\frac{p+r }{2^{n-1}}x+ \Big(1-\frac{p +r}{2^{n-1}}y\Big)\right) \\&:= \color{red}{\frac{1}{2}\left(X_1+X_2\right)}\end{align}

On the other hand, since $r\in \{0,1\}$ and $m\in\{0,1,2,\ldots,2^{n}-1\}$ it is easy to check using parity that $p,p+1 \in \{0,1,2,\ldots,2^{n-1}-1\}$ that is $p+r \in \{0,1,2,\ldots,2^{n-1}-1\}$

By hypothesis of induction we obtain \begin{align}f(X) &= f\left(\frac{1}{2}\left(X_1+X_2\right)\right)\le \frac12f(X_1) +\frac12f(X_2) \\&= \frac12f\left(\frac{p }{2^{n-1}}x+ \Big(1-\frac{p }{2^{n-1}}y\Big)\right)+\frac12f\left(\frac{p+r }{2^{n-1}}x+ \Big(1-\frac{p +r}{2^{n-1}}y\Big)\right) \\&\le\frac12\left(\frac{p }{2^{n-1}}f(x)+ \Big(1-\frac{p }{2^{n-1}}f(y)\Big)\right)+\frac12\left(\frac{p+r }{2^{n-1}}f(x)+ \Big(1-\frac{p +r}{2^{n-1}}f(y)\Big)\right) \\&= \frac{2p+r}{2^n}f(x) +\Big(1-\frac{2p+r}{2^n}\Big)f(y)\\&= \frac{m}{2^n}f(x) +\Big(1-\frac{m}{2^n}\Big)f(y).\end{align}

$\endgroup$
1
$\begingroup$

Here is a sketch of the standard proof by contradiction:

if $f$ is not convex, then continuity implies that there is an interval $[a',b']\subset (a,b)$ such that, if $g:[a',b']\to \mathbb R$ is defined by $$g(x)=f(x)-\frac{f(b')-f(a')}{b'-a'}(x-a')-f(a'),$$

then the following is true:

$\tag 1 s:=\sup_{x\in [a',b']}\{g(x)\}>0$

$\tag 2 g(a')=g(b')=0$

$\tag 3 g \ \text{is midpoint convex}$

The motivation for this is that if $f$ is not convex then, by continuity, the graph of $f$ must rise above a segment connecting the endpoints $(a',f(a'))$ and $(b',f(b'))$

Note that since $g$ is continuous and $[a',b']$ is compact, $s$ is actually attained by at least one $x\in [a',b'].$

Now, put $c=\inf \{x\in [a',b']: g(x)=s\}.$ Continuity of $g$ implies that $g(c)=s$ and $(2)$ implies that $a'<c<b'.$ Now choose $\delta>0$ small enough so that $c+\delta$ and $c-\delta$ are contained in $(a',b').$ Then, the definition of $c$ together with $(1)$ implies that $g(c-h)<g(c)$ and $g(c+h)\le g(c)$, and therefore that $g(c)>\frac{g(c-h)+g(c+h)}{2}$, which contradicts $(3).$

$\endgroup$

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.