9 Quasiconvexity and Quasiconcavity

1 , Math for EconomistsFall 2004 Lecture Notes, 10/7/2004 These notes are primarily based on those written by Andrei Bremzen in 2002/3, and by Marek Pycia for the MIT Math Camp in 2003/4. Ihave made only minor changes to the order of presentation, and added a fewshort examples. The usual disclaimerapplies; questions and comments Quasiconvexity and QuasiconcavityOne problem with concavity and convexity (which we ll encounter again whenwe look at homogeneity) is that they arecardinalproperties. That is, whetheror not a function is concave depends on the numbers which the function assignsto its level curves, not just to their shape.

2 The problem with this is that amonotonic transformation of a concave (or convex) function need not be concave(or convex). For example,f(x)= x22is concave, andg(x)=exis a monotonictransformation, butg(f(x)) =e x22is not concave. This is problematic whenwe want to analyze things like utility which we consider to be ordinal weaker condition to describe a function is Quasiconvexity (or quasiconcav-ity). Functions which are quasiconvex maintain this quality under monotonictransformations; moreover, every monotonic transformation of a concave func-tion is quasiconcave (although it is not true that every quasiconcave functioncan be written as a monotonic transformation of a concave function).

3 Definition 166 Afunctionfdefined on a convex subsetUofRnisquasicon-caveif for every real numbera,C+a {x U:f(x) a}is a convex set. Similarly,fisquasiconvexif for every reala,C a {x U:f(x) a}is a convex following theorem gives some equivalent definitions for Quasiconcavity :Theorem 167 Letfbe a function defined on a convex following statements are equivalent:(a)fis a quasiconcave function (b)For allx, y Uand allt [0,1],f(x) f(y)impliesf(tx+(1 t)y) f(y)(c)For allx, y Uand allt [0,1],f(tx+(1 t)y) min{f(x),f(y)}Exercise 168 For a functionfdefined on a convex subsetUinRn,showthatfconcave previous exercise shows what we mean when we say that quasiconcavityis weaker than concavity.

4 Moreover, as noted previously, monotone transforma-tions of quasiconcave functions remain quasiconcave, allowing us to use them torepresent ordinal concepts such as utility. From our point of view, looking atoptimization, the important point is that a critical point of many quasiconcavefunctions will be a maximum, just as is the case with a concave function. Butsuch critical points need not exist - and even if they do, they are not necessar-ily maximizers of the function - considerf(x)=x3. Any strictly increasingfunction is quasiconcaveandquasiconvex (check this); this function is bothover the compact interval[ 1,1], but the critical pointx=0is clearly neithera maximum nor a minimum over that interval.

5 What we usually use theseconcepts for is to check that upper contour sets (which can represent demandcorrespondences, or sets of optimal strategies in game theory, etc.) are Static Unconstrained have already stated thefirst optimization result, the Bolzano-Weierstra theorem. Remember, the only property that we assumed8off:Rn Rwascontinuity and that the theorem, although asserting that a maximum exists(over a compact set), gave no clue as to how tofind it. Differentiability is astronger property than continuity; and yes, as it is very often the case in math,stronger assumptions allow us to come to stronger conclusions.

6 We may indeedlocate optima offby looking at its derivative (or gradient).The very definition of differentiability states that locally a differentiablefunction is well approximated by a linear function. But optimizing a linearfunction is easy: it never reaches an interior maximum or a minimum except ifall its coefficients are zero. That immediately gives us the following necessarycondition:Theorem 169(First Order Conditions) Iff:Z Rn Rreaches its (local)maximum at some interior pointx intZ(by interior we mean thatx belongs8We do not study oprtimization of more general functionsRn Rmsimply because theremaximum or minimum value is not defined: remember, there is no natural way to with a small enough open ballBr(x ),for somer>0)andfisdifferentiable atx thenDx f=0(points at whichDf=0are called criticalpoints off).

7 Corollary 170 The same result holds ifx is instead a local theorem is the theoretical ground behind the mechanical differentiationusedbymanycollegestudents . , this theorem gives you anecessarycondition which is by no meanssufficient. If a function has a zero gradient at some particular interior point,than it does not have to be (even a local) maximum or minimum (think aboutf(x)=x3at point 0).Second, the theorem gives you a necessary condition only for aninterioroptimum. If a local optimum is reached byfat a point on the boundary ofD,its gradient does not have to equal zero at this point (think aboutf(x)=xonD=[0,1]). You have to consider boundary points , the theorem tells you nothing aboutglobaloptima.

8 You have toemploy other (notfirst order) considerations tofigure out at which of the sus-picious points (which include all critical points offand all boundary points ofD) the function actually attains a global maximum. Good news is, though, thattypically there will not be too many of is all there is to say aboutfirst order condition and unconstrainedoptimization. Again, assuming more structure (in our case, existence of thesecond derivative) allows one to come to more definite 171(Second Order Conditions) Supposefis aC2function onZ Rn,andx is an interior point a local maximum (respectively, min-imum) atx ,thenDx (f)is zero andHf(x )is negative (respectively, positive)semidefinite.

9 Conversely, ifDx (f)is zero andHf(x )is negative (respectively,positive) definite, thenfhas a strict local maximum (respectively, minimum) atx .The above theorem gives almost necessary and sufficient conditions for aninterior optimum. Almost because no conclusions can be drawn if the Hessianis semidefinite but not the one-dimentional case, the Hessian offis simply one , second order conditions do not give a definite answer for points atwhichboththefirst and second derivatives are zero. A natural next move isthen to consider the third derivative whetherf000(x )6=0. If so, then locallythe function looks likex3around zero, , it is not an optimum.

10 Iff000(x )=0,then consider the fourth derivative. Iff0000(x0)<0,then locallyflooks likex4, ,x is a local minimum. Iff0000(x )>0,thenx is a local maximum. Iff0000(x )=0,you have to consider further derivatives. Unfortunately, as the lastexample shows, this process may never come to the end: you may be evaluatinghigher and higher order derivatives and they all may turn out to be zero even61though the function itself is nonzero aroundx ,and you will neverfind outwhetherx is a local maximum, a local minimum, or working out quadratic forms, there is another simple algorithm fortesting the definiteness of a symmetric matrix like the Hessian.