Suppose that f: R --> R is C1.  Prove that f is concave if and only if
f(x*) + (x-x*)f'(x*) is greater than or equal to f(x), for all x and x*

Thank you

Hi, dime365-ga:

It may be a little bit easier to read if we use x and y instead of x
and x* as the arguments to function f and its derivative.  For one
thing, we can then reserve the * symbol solely for denoting
multiplication.

Our approach is to show that for a C^1 function f (ie. continuous
first derivative), the following three conditions are equivalent:

(a) f is concave

(b) f' is nonincreasing

(c) for all x,y in R, f(y) + f'(y)*(x - y) >= f(x)

The proof will be a "round robin" style demonstration, that (a)
implies (c), that (c) implies (b), and that (b) implies (a).

Proof that (a) implies (c):

If x=y, then (c) holds trivially.  So assume x,y distinct.

By the definition of a concave function, for all 0 < t < 1:

t*f(x) + (1-t)*f(y) <= f(tx + (1-t)y)

With a bit of rewriting this becomes:

t*(f(x) - f(y)) + f(y) <= f(t*(x - y) + y)

and thus:

t*(f(x) - f(y)) <= f(t*(x - y) + y) - f(y)

Now t > 0, so the sense of the inequality remains the same if both
sides are divided by t.  Therefore we can conclude:

f(x) - f(y) <= ( f(t*(x - y) + y) - f(y) )/t

             = (x - y) * ( f(t*(x - y) + y) - f(y) )/(t*(x - y))

Note that we have made no assumption about the order of x,y, only that
x - y is nonzero.

Finally, taking the limit as t goes to zero, the difference quotient
on the right hand side tends to the derivative f'(y).  Thus:

f(x) - f(y) <= (x - y) * f'(y)

from which (c) can be immediately obtained.

Proof that (c) implies (b):

Here the proof is quick but depends essentially on the asymmetry of
the roles played by x,y in the hypothesis (c).  To prove (b) we must
argue that if x < y, then f'(x) >= f'(y).

First apply (c) directly, obtaining:

f(y) + f'(y)*(x - y) >= f(x)

Now by the assumption that x < y, division by (x - y) reverses the inequality:

f'(y)*(x - y) >= f(x) - f(y)

f'(y) <= ( f(x) - f(y) )/(x - y)

On the other hand, if the roles of x and y are reversed in (c), the
direction inequality is not reversed when we divide by (y - x):

f'(x)*(y - x) >= f(y) - f(x)

f'(x) >= ( f(y) - f(x) )/(y - x)

Since the two difference quotients on the right hand sides are equal,
we now combine the inequalities to get:

f'(x) >= f'(y)

as was to be shown.

Proof that (b) implies (a):

Up to this point we have not needed the continuity of the first
derivative f', but in this final leg of the proof it comes into play
as we invoke the Mean Value Theorem (twice) on f.

Let's again assume x < y, as this does not materially restrict the
definition of f being concave, i.e. for all 0 < t < 1:

t*f(y) + (1-t)*f(x) <= f(t*y + (1-t)*x)

because swapping x and y simply amounts to replacing t by 1-t above.

Now as t varies from 0 to 1, the expression t*y + (1-t)*x goes from x
to y.  In particular, since x < y, we have for 0 < t < 1:

x < x + t*(y - x)
  = t*y + (1-t)*x
  = y - (1-t)*(y - x)
  < y

Thus we can apply the MVT to each of these difference quotients:

f'(u) = ( f(y) - f(y - (1-t)*(y - x) )/((1-t)*(y - x)

where y - (1-t)*(y - x) < u < y, and:

f'(v) = ( f(x + t*(y - x)) - f(x) )/(t*(y - x))

where x < v < x + t*(y - x).

But as we've already noted above:

x + t*(y - x) = y - (1-t)*(y - x)

Thus v < u, and (b) tells us that f'(u) <= f'(v), or:

( f(y) - f(y - (1-t)*(y - x) )/((1-t)*(y - x)

   <= ( f(x + t*(y - x)) - f(x) )/(t*(y - x))

Multiply both sides by t*(1-t)*(y - x), which is positive:

t*( f(y) - f(y - (1-t)*(y - x) )

   <= (1-t)*( f(x + t*(y - x)) - f(x) )

and "simplify" the arguments of f which are equal to t*y + (1-t)*x:

t*f(y) - t*f(t*y + (1-t)*x)

   <= (1-t)*f(t*y + (1-t)*x) - (1-t)*f(x)

From here we combine terms in the natural way:

t*f(y) + (1-t)*f(x) <= f(t*y + (1-t)*x)

and therefore f is a concave function.

QED


NOTES:

The proof (a) implies (c) is taken from that of Proposition 1 here:

[Concave Functions]
http://www.wilsonc.econ.nyu.edu/UMath/Handouts/ums03h03concaveandquasiconcavefunctionsonthereals.pdf

This PDF, course notes by NYU's C. Wilson in economics, gives proofs
of some additional results in its Appendix, relating
convexity/concavity to increasing or decreasing conditions on the
difference quotient:

g_x(y) = ( f(y) - f(x) )/(y - x)

considered as a function of y (fixing x), y not equal to x.  However
our treatment above is completely self-contained.

regards, mathtalk-ga


Search Strategy

Keywords:  concave derivative decreasing proof

Thanks!!