Proving Increasing Nature of Concave Function f

[statsmichael]

Homework Statement

My question is similar to this one (https://www.physicsforums.com/threads/metric-function-composed-with-concave-function.566338/), I think. I have a concave function $f: [0, \infty) \rightarrow [0, \infty)$ where $f(0) = 0, f(x) > 0, x \neq 0$ and I need to show that this function is always increasing, or at least non-decreasing.

Homework Equations

The Attempt at a Solution

I'm trying a proof by contradiction. If the function isn't increasing, then $f(a) > f(b)$ for some $a < b$. That gives me $f(a) - f(b) > 0$, but I don't see how to proceed. I know that $f(a + b) \leq f(a) + f(b)$, i.e. the function is subadditive, but once again, I'm stuck.

 

[DEvens]

Are you in fact required to use proof by contradiction?

Can you show something about the derivative based on the inequalities you have?

 

[RUber]

By definition of a concave function, the line connecting any two points (x, f(x)) and (y,f(y)) will lie above the graph of the function.
You have a<b and f(a)>f(b).
Since your function is only looking at [0,infty] there must be a minimum value on [0,a], given that f(0)=0, that is a good start.
Connecting (0,0) to (b,f(b)) should contradict the definition of concavity.

 

[statsmichael]

By definition of a concave function, the line connecting any two points (x, f(x)) and (y,f(y)) will lie above the graph of the function.
You have a<b and f(a)>f(b).
Since your function is only looking at [0,infty] there must be a minimum value on [0,a], given that f(0)=0, that is a good start.
Connecting (0,0) to (b,f(b)) should contradict the definition of concavity.

I thought the definition of a concave function was that any line connecting two points (x, f(x)) and (y, f(y)) will lie BELOW the graph. Isn't that the correct interpretation of the definition (see Wikipedia, for example: https://en.wikipedia.org/wiki/Concave_function)

If I look at the line between (0, f(0)) = (0, 0) and (b, f(b)), I can get that $f(0t + (1-t)b) \geq tf(0)+(1-t)f(b) = (1-t)f(b)$, but I don't see where that gets me. Since f(a) must lie above that line, I have that $f(a) > f(b)$, but that's already given in the assumption that I'm trying to contradict.

 

[statsmichael]

Are you in fact required to use proof by contradiction?

Can you show something about the derivative based on the inequalities you have?

This is in an analysis textbook that I'm working through, and it mentions that since we haven't encountered differentiation in the course yet (it's in the section on basic metric spaces), I should be able to prove it without using anything besides proof by contradiction.

 

[DEvens]

I thought the definition of a concave function was that any line connecting two points (x, f(x)) and (y, f(y)) will lie BELOW the graph. Isn't that the correct interpretation of the definition (see Wikipedia, for example: https://en.wikipedia.org/wiki/Concave_function)

That would be concave downwards. But clearly such a function cannot be always increasing. Your description seems to indicate concave upwards.

 

[statsmichael]

That would be concave downwards. But clearly such a function cannot be always increasing. Your description seems to indicate concave upwards.

The book just says this function is concave, i.e. $f(tx + (1-t)y) \geq tf(x) + (1-t)f(y)$ when $t \in [0, 1], \forall x, y \in [0, \infty)$. That's concave downwards, right? Concave upwards is the same as convex, right?

If the function can't be increasing, it can at least be non-decreasing, I think.

 

[Ray Vickson]

That would be concave downwards. But clearly such a function cannot be always increasing. Your description seems to indicate concave upwards.

In many modern textbooks, papers, monographs, etc. (especially in the area of optimization theory and practice) the terminologies "concave up" and "concave down" have been abandoned. They have been replaced by "convex" and "concave". Typical convex functions would be $x^2$, $e^x$ or $e^{-x}$, while typical concave functions would be $-x^2$, $-e^x$ or $-e^{-x}$. More generally, $f$ concave implies that the interpolating line-segment from $(x_1,f(x_1))$ to $(x_2,f(x_2))$ lies on or below the graph $y = f(x)$ between $x_1$ and $x_2$. For a convex function, it lies above instead of below.

 

[Ray Vickson]

This is in an analysis textbook that I'm working through, and it mentions that since we haven't encountered differentiation in the course yet (it's in the section on basic metric spaces), I should be able to prove it without using anything besides proof by contradiction.

Without assuming differentiability, see if you can establish the following (true) statements. If $f$ is concave on a convex subset $I \subset \mathbb{R}$, then for any $x_1 < x_2 < x_3$ in $I$ we have
$$\frac{f(x_2)-f(x_1)}{x_2 - x_1} \geq \frac{f(x_3) - f(x_1)}{x_3 - x_1} \geq \frac{f(x_3) - f(x_2)}{x_3 - x_2}$$
with strict inequalities if $f$ is strictly concave on $I$. (I suggest you draw a picture to see what these are saying.) Basically, these follow by looking at $x_2$ as a appropriate convex combination of $x_1$ and $x_3$.

So, if we have $x_1 < x_2$ but $f(x_1) > f(x_2)$, what would the inequalities above tell you about the behavior of $f(x)$ for $x > x_2$?

 

[RUber]

Okay, so I was flipped upside down in my earlier post. If you have a concave function and it starts decreasing, it will continue decreasing, eventually driving f(x) < 0 for some large x.
In your description of the function, f: [0, infty) --> [0, infty). This is the part that will be contradicted, since an infinitely large x will have to generate a negative f(x) if f is decreasing at any point. Examples of this sort of function are $f(x) = \sqrt{x}; f(x) = \ln x$.

 

[Ray Vickson]

Okay, so I was flipped upside down in my earlier post. If you have a concave function and it starts decreasing, it will continue decreasing, eventually driving f(x) < 0 for some large x.
In your description of the function, f: [0, infty) --> [0, infty). This is the part that will be contradicted, since an infinitely large x will have to generate a negative f(x) if f is decreasing at any point. Examples of this sort of function are $f(x) = \sqrt{x}; f(x) = \ln x$.

It is your statement "... it starts decreasing, it will continue decreasing..." which needs proof. It is obvious for (piecewise) continuously-differentiable $f$, but needs more work for general concave $f$. An argument as in #9 will go a long way towards a solution.