View Question
 Question
 Subject: Concavity Proof Category: Science > Math Asked by: dime365-ga List Price: \$10.00 Posted: 06 Nov 2003 14:04 PST Expires: 06 Dec 2003 14:04 PST Question ID: 273307
 ```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```
 dime365-ga rated this answer: `Thanks!!`