Optimization.pptx

This is the slide masterClick to edit Master title style,#,Click to edit Master text styles,Second level,Third level,OptimizationLecture 2,Marco Haan,February 21,2005,2,Last week,Optimizing a function of more than 1 variable.,Determining local minima and local maxima.,First and second-order conditions.,Determining global extrema with direct restrictions on variables.,This week,Constrained problems.,The Lagrange Method.,Interpretation of the Lagrange multiplier.,Second-order conditions.,Existence,uniqueness,and characterization of solutions.,3,Suppose that we want to maximize some function f(x,1,x,2,)subject to some constraint g(x,1,x,2,)=0.,Example:A consumer wants to maximize utility,U(x,1,x,2,)=x,1,x,2,subject to budget constraint,2x,1,+3x,2,=10.,In this case:f(x,1,x,2,)=x,1,x,2,and g(x,1,x,2,)=,10,2x,1,3x,2,.,4,Suppose that,from g(x,1,x,2,)=0 we can write x,2,=,(,x,1,).,Take the total differential:dx,2,=,(,x,1,),dx,1,Also:g,1,(x,1,x,2,)dx,1,+g,2,(x,1,x,2,)dx,2,=0,We want to maximize f(x,1,x,2,)subject to g(x,1,x,2,)=0.,Hence:,We can now write the objective function as,:,Weve seen this in Micro 1!,5,Theorem 13.1,If(x,1,*,x,2,*)is a,tangency solution,to the constrained maximization problem,then we have that x,1,*and,x,2,*satisfy,6,Back to the example,f(x,1,x,2,)=x,1,x,2,and g(x,1,x,2,)=,10,2x,1,3x,2,.,We need,So,With,Hence,This yields,Note:this only says that this is a local optimum.,7,Lagrange Method,Again,we want to,Consider the function,The first two equalities imply,Lets maximize this:,Hence,we get exactly the conditions we need!,8,Definition 13.2,The,Lagrange method,of finding a solution(x,1,*,x,2,*)to the problem,consists of deriving the following first-order conditions to find the critical point(s)of the Lagrange function,which are,9,Back to the example,f(x,1,x,2,)=x,1,x,2,and g(x,1,x,2,)=,10,2x,1,3x,2,.,Again,this only says that this is a local optimum.,10,The method,also works for finding minima.,(,Definition 13.2),The,Lagrange method,of finding a solution(x,1,*,x,2,*)to the problem,consists of deriving the following first-order conditions to find the critical point(s)of the Lagrange function,which are,11,The interpretation of*,*is the,shadow price,of the constraint.,It tells you by how much your objective function will increase at the margin as the the constraint is relaxed by 1 unit.,Later,we go into more details as to why this is the case.,In the consumption example,we had income 10 and*=0.204.,This tells us that as income increases by 1 unit,utility increases by 0.204 units.,In this example,this is not very informative,as the“amount of utility”is not a very informative number.,Yet,in the case of e.g.a firm maximizing its profits,this yields information that is much more useful.,12,The,Lagrange method,of finding a solution(x,1,*,.,x,m,*)to the problem,consists of deriving the following first-order conditions to find the critical point(s)of the Lagrange function,which are,It also works with more variables and more constraints.(Definition 13.3),13,Second-Order Conditions,With regular optimization in more dimensions,we needed some conditions on the Hessian.,We now need the same conditions but on the Hessian of the Lagrange function.,This is the,Bordered Hessian.,14,Theorem 13.3,A stationary value of the Lagrange function yields a,maximum if the determinant of the bordered Hessian is positive,minimum if the determinant of the bordered Hessian is negative.,15,Again back to the earlier example,f(x,1,x,2,)=x,1,x,2,and g(x,1,x,2,)=,10,2x,1,3x,2,.,Evaluate in,Thus,we now know that this is a local maximum.,16,With more than two dimensions.(Theorem 13.4),If a Lagrange function has a stationary value,then that stationary value is a maximum if the successive principal minor of|H*|alternate in sign in the following way:,It is a maximum if all the principal minors of|H*|are strictly negative.,Note:Both theorems only give,sufficient conditions.,17,Theorem 13.6,The Lagrange method works(in finding a local extremum)if and only if it is possible to solve the first-order conditions for the Lagrange multipliers.,18,Weierstrasss Theorem:,If f is a continuous function,and X is a nonempty,closed,and bounded set,then f has both a minimum and a maximum on X.,But when can we be sure that a minimum and a maximum really exist!?,19,Weierstrasss Theorem:,If f is a continuous function,and X is a nonempty,closed,and bounded set,then f has both a minimum and a maximum on X.,But when can we be sure that a minimum and a maximum really exist!?,f is continuous if it does not contain any holes,jumps,etc.,You cannot maximize the function f(x)=1/x on the interval-1,1.,But you,can,maximize the function f(x)=1/x on the interval 1,2.,20,Weierstrasss Theorem:,If f is a continuous function,and X is a nonempty,closed,and bounded set,then f has both a minimum and a maximum on X.,But when can we be sure that a minimum and a maximum really exist!?,X is nonempty if it contains at least one element.,Otherwise the problem does not make sense.,If there is no value,there is also no maximum value.,21,Weierstrasss Theorem:,If f is a continuous function,and X is a nonempty,closed,and bounded set,then f has both a minimum and a maximum on X.,But when can we be sure that a minimum and a maximum really exist!?,X is closed if the endpoints of the interval are also included in X.,0 x 1 is an,open set,.It is not a closed set.,0,x,1 is a closed set.,You cannot maximize the function f(x)=x on the interval 0 x 0.,23,But when can we be sure that a local extremum is also a global one!?,Not always.,g(x),f increases,not a global maximum,global maximum,24,To give a formal derivation,we need some more mathematics.,Convex set,Consider some set X.,Take any two points in X.,Draw a line between these points.,If the entire line is within X,and this is true for any two points in the set,then the set is convex.,Convex set,Not a convex set,25,Note,A“convex set”is something entirely different than a“convex function”.,There is no such thing is a“concave set”.,26,To give a formal derivation,we need some more mathematics.,Quasi-concavity,Consider some function f(,x,).,Take some point,x,1,.,Consider the set X,0,consisting of all points,x,0,that have f(,x,0,),f(,x,1,).,If this set is convex,and this is true for all possible,x,1,then the function is quasi-concave.,x,1,This function is quasi-concave,but not concave!,27,To give a formal derivation,we need some more mathematics.,x,1,This function is not quasi-concave.,Quasi-concavity,Consider some function f(,x,).,Take some point,x,1,.,Consider the set X,0,consisting of all points,x,0,that have f(,x,0,),f(,x,1,).,If this set is convex,and this is true for all possible,x,1,then the function is quasi-concave.,28,To give a formal derivation,we need some more mathematics.,Quasi-convexity,Consider some function f(,x,).,Take some point,x,1,.,Consider the set X,0,consisting of all points,x,0,that have f(,x,0,),f(,x,1,).,If this set is convex,and this is true for all possible,x,1,then the function is quasi-convex.,x,1,This function is quasi-convex,but not convex!,29,Quasi-convexity,Consider some function f(,x,).,Take some point,x,1,.,Consider the set X,0,consisting of all points,x,0,that have f(,x,0,),f(,x,1,).,If this set is convex,and this is true for all possible,x,1,then the function is quasi-convex.,x,1,This function is not quasi-convex.,To give a formal derivation,we need some more mathematics.,30,Important to note.,A function that is concave,is also quasi-concave.,A function that is convex,is also quasi-convex.,In almost all of the cases we run into,well have convex and concave functions.,Note also that a utility function that is strict quasi-concave if and only if it yields indifference curves that are strictly convex.,31,Theorem 13.7,In a constrained maximization problem,If,f is quasiconcave,all gs are quasiconvex,then any locally optimal solution to the problem is also globally optimal.,Thus,if these conditions are satisfied,solving the Lagrange yields the global optimum!,32,Theorem 13.8:Uniqueness,In a constrained maximization problem,where f and all the gs are increasing,then if,f is strictly quasiconcave and the gs are convex,or,f is quasiconcave and the gs are strict convex,then a locally optimal solution is unique and also globally optimal.,Example:the consumer problem!,Utility function is increasing and strictly quasi-concave,Budget constraint is increasing and convex.,The theorem says that solving the FOCs yields a unique and global optimum.,33,Another example,A firm produces some output using the following production function,This is a CES production function(constant elasticity of supply).,Its general form is:,34,Another example,A firm produces some output using the following production function,Prices of inputs:,Question:What are the minimal costs of producing 1 unit of output?,35,Of course,second order conditions also have to be checked.,36,Example,A representative student spends 60 hours per week studying.,She takes two subjects.,Her objective:allocate time between the two subjects such that the average grade is maximized.,Subjects differ with respect to their production function.,Objective function:,37,Thus,We have that f is concave and g is convex.So this is a maximum.,Spending one hour more studying leads to an increase in grade average of 1.5.,38,This weeks exercises,pg.615:1,3,5,7.,pg.622:1.,