Topics in Economic Sciences
Topics in Economic Sciences EconS 521
Popular in Course
Popular in Economic Sciences
This 15 page Class Notes was uploaded by Maurine Kuhic on Thursday September 17, 2015. The Class Notes belongs to EconS 521 at Washington State University taught by Staff in Fall. Since its upload, it has received 58 views. For similar materials see /class/205985/econs-521-washington-state-university in Economic Sciences at Washington State University.
Reviews for Topics in Economic Sciences
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/17/15
KuhnTucker Theory for Constrained Optimization Perhaps the single most fundamental set of mathematical results affecting microeconomic analysis is the theory of maximization and minimization subject to constraint The pur pose of this brief set of notes is to present the theory of Lagrange39s method applied to this class of problems to derive an exhaustive set of firstorder necessary conditions These conditions are popularly known as the K Linn Tucker conditions although it turns out that a master s student in mathematics at the University of Chicago named Karush derived the same conditions as part of his MS thesis in 1937 several years prior to the 1952 work by Kuhn and Tucker at the University of California 7 Berkeley The KuhnTucker condi tions will be presented here in a complete and rigorous manner for the case of two choice variables each required to be nonnegative with one linear inequality constraint The no tation is consistent with the standard theory of consumer choice but the problem and its solution are more general than this The argument given here extends in a straightforward manner to any number of choice variables It also can be extended to several constraints although this will require some additional technical details and analysis Let pxpym gtgt 000 so that the feasible set is compact with open interior The problem of interest is to maximize uxy subject to xyZ00 and pxxpyy S m l Lagrange39s method is simply to define a nonnegative variable A Z 0 called the Lagrange multiplier for the inequality constraint form the Lagrangean L Way MmPxxPyy 2 and nd a relative maximum of L with respect to xy and a relative minimum with re spect to A The nonnegativity of the Lagrange multiplier is purely a sign convention that lets us interpret it as a shadow price or marginal opportunity cost of the constraint The KuhnTucker Theorem gives a complete taxonomy of the rstorder necessary conditions for obtaining a saddle point for L hence a constrained maximum with respect to x y These conditions are given by KT l 6L6x6uxy6x lpxS0x20xgtlt6L6x0 KT 2 6L6y6uxy6y lpyS0yZOygtlt6L6y0 KT 3 6LHMm pxx pyyZOJtZOthoLZM0 These conditions state that the Lagrangean must not be increasing in either x or y at the optimal solution and must not be decreasing in the Lagrange multiplier 1 Furthermore x y and A must each be nonnegative and either the partial derivative of the Lagrangean with respect to each of these variables must be zero or else the variable must be zero at the optimal solution In fact the KuhnTucker theorem states that there exists a nonnegative real number A such that if the pair of real numbers xy is a solution to the constrained maximization problem then the firstorder conditions KT l through KT 3 must be satisfied Let us analyze why this is true Before proceeding it is important to note of an important hypothesis on u R2 gt R In particular we assume that u is twice continuously differentiable in x and y1 That is the partial derivatives 6ux y6x and 6ux y6y are assumed to exist and to be con tinuous functions of x and y throughout the domain of de nition for u For any feasible solution to this problem there are four possibilities for the optimal choice for xy 1 x y 0 2 x gt 0 y 0 3 x0 ygt0or 4 x gt 0 y gt 0 There also are two possibilities for the constraint 1 pxx py y lt m strictly nonbinding or 2 pxxpyy m binding The KuhnTucker theorem is demonstrated by showing that a conditions KT l through KT 3 are satisfied in each case for an appropriate choice of A Z 0 and b that if these conditions are violated then the candidate solution can not be an optimum This means that the KuhnTucker firstorder conditions are necessary for a constrained optimum to have been found However they may not be su cient conditions without additional hy pothesis or conditions on the objective function and feasible set 1 This condition is violated in some examples and practical problems 7 for example the CobbDouglas util ity function ux y xayl39 0 lt 0 lt1 is not differentiable at 00 since it is undefined when x or y is negative Since this case always has to an interior solution this issue generally tends to be ignored How ever the Kuhn Tucker Theorem extends to such cases after considerable attention to technical detail First consider x y 0 Then since pX0py0 0 lt m case 1 for the constraint must be true 7 that is it is nonbinding Let us choose A 0 whenever this is so which is precisely what condition KT 3 states should be the case Under what conditions will 00 be a maximum Intuition suggests that at least locally u must not be increasing in either x or y at the origin Otherwise we could increase one or both choice variables some arbi trarily small amount with the constraint remaining nonbinding and increase the objec tive function More formally suppose that uxy is increasing in x y or both at the point 00 Then because the constraint is a continuous function of x and y linear functions always are continuous 7 in fact they are continuously differentiable a countable infinity of times a sufficiently small number 8 gt 0 exists such that e lt min mpxmpy and at least one of the following is true a ue0 gt u00 b u0e gt u00 or C u gt 00 Why must this be so Because if 6u006x gt 0 then we can add a little bit to x thereby increasing the level of it while not adding too much x to violate the constraint This means a is true Similarly if 6u006y gt 0 then we can add a little bit to y thereby increasing the level of it while again not violating the constraint This means b is true If both 6u0 06x gt 0 and 6u0 06y gt 0 then we can add a little to both x andy to increase it and as long as we do not add too much we will not violate the constraint This implies that c is true although we have yet to de ne formally what too much means In each case by choosing 8to be a small enough positive number we can ensure that the constraint is not Violated Therefore whenever a b or c is true we have a contradiction of the hypothesis that u0 0 Z ux y for all xy in the feasible set 53 xyx20y20pxxpnym 3 In other words if 00 is an optimal choice then u can not be increasing in x y The formal demonstration of these arguments proceeds as follows First suppose that x y 00 maximizes u on the feasible set but that 7 contrary to the KuhnTucker Theorem 7 6u006x gt 0 Then for small enough 8 gt 0 we have au00 u80 u00 6x 8 08 gt u0 0 4 where lim088 0 This identifies the meaning of a little bit for this case 7 we can 7gt0 choose an increase in x that is small enough that the firstorder linear change in u with respect to x dominates all of the second and higherorder terms In addition if 8 lt mpx then we also will have px pyO px lt m This is the meaning of too much 7 we can increase x away from 0 but not so much as would Violate the constraint Second suppose that 6u006y gt 0 Then again for small enough 8 gt 0 we have u80 u008 o8 gt u00 5 y where lin01088 0 Also as long as 8 lt mpy we have px0py8 py8 lt m In this case a little bit means a small enough increase in y away from 0 that the linear rst order change in u dominates second and higherorder effects while not too much means that we don t violate the constraint as a result of this increase in y Finally if both 6u006x gt 0 and 6u006y gt 0 then for small enough 8 gt 0 we have 6u00 6u00 6x 6y oe gt u00 6 u 00 again with lSlLIOIO88 0 and as long as e lt min mpxmpy we also have pxpy lt pxxpyy m 7 Therefore if xy00 maximizes uxy on the feasible feasible set 53 then 6u006x S 0 and 6u006y S 0 must be satisfied at least in the neighborhood of the point 00 If we set A 0 then it follows that each of the KuhnTucker conditions KT l through KT 3 also must be satisfied That is there is a nonnegative real number 1spe cifically l 0 in this case for which the KuhnTucker firstorder conditions are neces sary for 00 to be a local optimum Note that l 0 because the constraint px0 py0 lt m is not binding ie the constraint line lies above and to the right of the point in the xy plane that maximizes the objective function We will see that this is the case in general 7 whenever a constraint is not binding ie it is slack the Lagrange mul tiplier for that constraint vanishes Next consider the case x gt 0 and y 0 We do not need to consider the mirror im age x 0 and y gt 0 separately because the arguments are identical with the roles of x and y 39 39 J Y 39 39 39J ifthe 39 is not binding then we must have an un constrained relative that is a local maximum with respect to x and u must not be in creasing iny at x0 ie 6ux06x 0 and 6ux06y S 0 Formally if these conditions are not met then there is a small number 8 gt 0 such that 8 lt min mpx x x m pxxpy and at least one ofthe following is true a ux80 gt ux0 b ux 80 gt ux0 c ux8 gt ux0 d uxy gt ux0 or e ux ygt ux0 Again we might ask why must this be the case The rst reason is that if u is increasing in x ie 6ux06x gt 0 then we can add a little bit to x thereby increasing the level of u but not so much as to violate the con straint This means a is true That is for small enough 8 gt 0 we have ux 8 0 m ux0 8 gt ux0 8 x where and from this point forward the symbol m means approximately equal to since we can ignore all higherorder terms for small enough 8 gt 0 As long as 8 lt mpx x then we also have px x 8 pyO lt px xmpx x m On the other hand if 6ux06x lt 0 then we can subtract a little bit from x thereby increasing the level of u but not so much as to make x negative This means b is true That is for small enough 8 gt 0 we have 6ux0 ux 80 m ux0 a x 8 gt ux0 9 and as long as 8 lt x we also have x 8 gt 0 Second if 6ux06y gt 0 then we can add a little bit to y thereby increasing the level of u but not adding so much to y that we Violate the constraint This implies that c is true That is for small enough 8 gt 0 we have 6ux0 6y ux8 m ux0 8 gt ux0 10 and as long as 8 lt m pxxpy we also have pxx py8 lt pxx py m pxxpy m Third if both 6ux06x gt 0 and 6ux06y gt 0 then case d is true On the other hand if both6ux06x lt 0 and 6ux06y gt 0 then case e is true The formal argu ments in both of these cases are very similar to those just presented and therefore are omitted here Because the constraint is not binding we set A 0 as before This then implies that the firstorder conditions KT l through KT 3 must be satisfied in the case where 0 lt x lt mpx and y 0 maximize u on the feasible set 53 Continuing with the case where x gt 0 but y 0 we next assume that the constraint is binding so that x mpx In this case we can set A lpx6umpx06x For if to the contrary of the KuhnTucker Theorem 6umpx06x lt 0 then there is an 8 gt 0 such that 8 lt x and umpx g0mumpx0 W8gtumpx0 11 a contradiction of mpx0 being a local maximum Hence 6um px06x Z 0 which implies in turn that A Z 0 We have shown that KT l and KT 3 are satis ed for this choice of l and it remains only to be shown that KT 2 also must be true at such an optimal solution point To see this first suppose that 6um px0 6y gt py px 6um px0 6x gt 0 Then if we move in the direction of the budget line by reducing x some small amount 8 gt 0 and increasing y by the amount p py 8 then the budget constraint will continue to be satis ed since pmp8pypxpy8mp8p8n1 12 However since the utility function increases with y relative to x at a greater rate than the relative price ratio for small enough 8 gt 0 we have that umpx8pyps umpx0 W5Wpyg 13 6y p gt 611mpX 0 because as we assumed a moment ago 6umpx06ygtpypx6umpx06x 14 But this contradicts the condition that x y mp0 is a maximum of uxy on the feasible set 3 Therefore if mpx 0 is a constrained maximum then 6umpx06yspypx6umpx06x 15 S ettin g ilpx6umpx06x20 16 therefore implies that KT 3 also must be satis ed Finally consider the case where xy gtgt 00 Again ifpxxpyy lt m then we will set A 0 Intuitively 6ux y6x 0 and 6ux y6y 0 are necessary conditions for a local unconstrained maximum strictly inside the boundaries of the feasible set We will show that this is precisely what the KuhnTucker conditions mean in this case and that if they are not satis ed then the given candidate point can not be an optimum Suppose that 7 again contrary to the KuhnTucker Theorey 7 6ux y6x 0 6uxy6y 0 or both If 6uxy6x gt 0 then we will add a little bit to x while if 6uxy6x lt 0 then we will subtract a little bit from x Similarly if 6uxy6y gt 0 then we will add a little bit to y while if 6ux y6y lt 0 then we will subtract a little bit from y We will only consider the case where u is increasing in both x and y 7 the other possibilities use very similar reasoning and are omitted from the discussion here Speci cally x 8 gt 0 such that s lt 12 x minm ptx gympt m pix PyyPy 17 and consider the point x 8 y 8 Then we have m Pxx Pyy 2 m P P y pxxepyyeltpxxpxpyypy m 18 y so that the constraint still is not Violated But if uxy is increasing in x and y then for small enough 8 we have ux y8muxy lt19 6x 6y contradicting the point xy being a maximum of u in the feasible set After considering very similar arguments for the cases where u is decreasing in x and y or increasing in one and decreasing in the other 7 all that is required is to change the sign of the change in x y or both 7 we conclude that 6ux y6x 0 and 6uxy6y 0 must hold if xy gtgt 00 such that pxxpyy lt m is an optimal point Setting 1 0 because the constraint is nonbinding implies that KT l through KT 3 must be satis ed once again The only remaining possibility is where xy gtgt 00 and pxxpyy m In this case let A l p 6uxy 6x For this case we will show that we must have A Z 0 and that A lpy 6uxy6y also must be true or else a maximum can not have been found First suppose that 6uxygt amp 6uxy 20 6y p 6x 39 Then we can subtract a little bit from x and add a little bit to y being careful not to Vio late the constraint and increase the level of u Specifically for sufficiently small 8 gt 0 we have 6uxyg 6ux y ux 8ypyp8 e uxy ax 6y i gt uxy 21 Py while px 8PyyPxPygl Pxxpyy M To complete the proof of the KuhnTucker theorem it is only necessary to show that A Z 0 But if 6ux y6x lt 0 then we can simply subtract a little bit 8 gt 0 from x relax ing the constraint and increasing u at the same time contradicting that xy is an optimal solution Therefore 6ux y6x Z 0 is necessary for a constrained maximum and since we have set A l p 6ux y 6x it follows that A Z 0 as well It is a simple matter to see that all three conditions KT l through KT 3 are now satis ed in this last possibility as well Discussion The KuhnTucker conditions stated and proven here are necessary first order conditions for a constrained maximum subject to a linear constraint and nonnegativity of the choice variables The suf cient conditions for the existence of a local unique solution for xyl in a constrained maximization problem is that the matrix of secondorder partial deriva tives the Hessian matrix of the Lagrangean with respect to xyl is nonsingular at the candidate point However because L is linear in A and bilinear in xi and in yJi it is impossible for the Hessian to be either positive de nite or negative de nite it will always be inde nite This is why we adopt the convention that A Z 0 and look for a saddle point 7 it is impossible to obtain a maximum of L jointly with respect to xyl The necessary second order condition for a local constrained maximum in the two variable case is that the Hessian matrix of the Lagrangean has a nonnegative determi nant The su icient second order condition is that the determinant is strictly positive Given the rstorder conditions this latter condition is equivalent to the property that the objective function uxy is strictly quasi concave If u is increasing in xy then quasi concavity means that the level curves are conveX to the origin In general quasiconcavity of uxy implies that the rstorder KuhnTucker condi tions are both necessary and suf cient conditions for a constrained maximum subject to a linear constraint EconS 521 Fall 2008 l Liebnitz Rule for Differentiating an Integral Let the functions f R2 gt R a R gt R and b R gt R be continuously differentiable and define the integral lnction b yfxydx 1 a y Fy I Then the derivative of F with respect to y satisfies the following property My 6 F U J dx f byyb39y f 0yya39y 2 ay Proof Let A at 0 denote an arbitrary change in y We then have byA FyA WW fx yAdx a A b A y y fxyAdx ayA J ayA My fxyAdx jam fxyAdx j b A A 3 y a y j fxyAdx j fxyAdx a y 110 b a bf fx y Adx j M fx y Adx y My A d Jaw9 x I no Therefore subtracting 1 from the last line of 3 and dividing the result by A gives lim Agt0 FyA Fy J M 1imfxyA fxydx A am Agt0 A b A a A j fxyAdx j fxyAdx lim W m 1 4 Agt0 Agt0 A b a j yAfxyAdx j y fxyAdx My m ay I lim Agt0 A Aao A Jim 6may a altygt 6 EconS 521 Fall 2008 2 We can then rewrite the second term in the bottom line of 4 as byA fx y Adx byA limb 1imj hm fxayA fxy dx A90 A Agt0 My A90 A 1im y x ywx 5 Agt0 A JbyA a ydcfbyyb39y My y J50 afoc f byyb39y The first equality follows from the fact that the limit of the limit is the limit The first term in the second equality follows from the de nition of the partial derivative of f with respect to y and the second term in the second equality follows from the fundamental theorem of calculus 7 ie differentiation and integration are inverse functions The bottom line of 5 follows from the fact that there is zero area under a point ie in an integral that has the same upper and lower limit Similarly we can rewrite the integral and limit on the third line of 4 as ayA lim M lim JagM lim dx A90 A Aao am Agt0 A 139 lulll vw ym 53 A 6 11006 J aw mm M y f My ya39y Therefore combining 446 we obtain Liebnitz Rule as stated in 2 above I