ccer05研究生数理经济学讲义2

Lecture Notes 1 & 2Optimizing TheoryChapter 1 Unconstrained OptimizationTheorem 1.1 Suppose :n f R R → is differentiable and n x R ∈ is a local maximizer or local minimizer of f , then ()0f x ∇=.Theorem 1.2 Suppose :n f R R →is twice continuously differentiable and (')0f x ∇=.1. If 'x is a local maximizer, then matrix 2(')D f x is negative semi-definite.2. If 2(')D f x is negative definite, then x’ is a local maximizer.Theorem 1.3 Suppose function :n f R R → is concave. If (')0f x ∇=, then x’ is a global maximizer of f .Theorem 1.4 (Envelope Theorem) Consider unconstrained optimization problem:n x RMax ∈(,)f x a , where m a R ∈ is the vector of parameters. The function (,)f x a is continuous and differentiable. Suppose the solution point is **()x x a =. Denote ()((),)V a f x a a =. Then we must have*()(,)()j j V a f x a x x a a a ∂∂==∂∂ , 1,,j m =".Chapter 2 Constrained optimization2.1 The general structureThe variables of the problem will be considered to be in the form of a vector in n R . In addition to this vector, x , we have:a. a feasible set K. Only x K ∈ is to be taken into account in the problem.b. A continuous objective function, ()f x , whose value for x K ∈ is to be optimized.Thus we can state a typical maximizing problem in formal terms asFind *x K ∈ such that *()()f x f x ≥, for all x K ∈.If such an *x exists, the problem has a weak global maximum-weak because itsatisfies the weak inequality, global because the inequality is satisfied for all x K ∈. A global optimum should not be confused with an unconstrained optimum. The latter implies that n K R =. We would have a strong maximum if we could find *x such that *()()f x f x >, for all x K ∈.A weak optimum is equivalent to a non-unique optimum point since any x satisfying *()()f x f x = is also an optimum point. A strong global optimum implies a unique optimum.If we reverse the inequalities we obtain a minimum, weak or strong as the case may be. A minimum for ()f x implies a maximum for [-()f x ]. The value *x is often called simply the solution of the optimum problem. To avoid confusion with other claimants for the same name in many economic models, we shall usually call it the optimal solution or optimum point.Most calculus techniques cannot solve the problem as set out above, but can only solve a problem of the following kind:Find *x K ∈ such that *()()f x f x ≥, for all ()x N K ∈∩,where N is a neighborhood of *x .Such a point is a weak local maximum. We can have a weak or strong local maximum, and weak, or strong local minimum.It is obvious that a global optimum must also be a local optimum. Nevertheless, a local optimum is not necessarily global. Our interest is primarily in the global optimum. Thus, we are interested in conditions on the structure of the problem that will guarantee that a local optimum is also global. If such conditions are not satisfied, we need to adopt ad hoc procedures to locate the global optimum.2.2 Constraints and the Feasible SetThe feasible set, over which the variables are permitted to range, may be defined in any suitable way. In the case of discrete variables, the feasible set may even be described by enumeration. Typically, however, the feasible set will be defined by equalities or inequalities involving relationships between the variables.The boundaries of the feasible set are crucial in optimizing problems. In all our discussions of optimizing, it will be assumed that the constraints are such that as to give a closed feasible set. Otherwise the problem is usually without a solution. This is normally guaranteed by ensuring that there are no strict inequalities in any of the constrains and that the constraints are continuous.When there are several constraints, given a feasible point x ’, we say that a particular constraint is effective at x ’ if x ’ gives an equality in the constraint, ineffective at x ’ if it gives an inequality. Note that a constraint may be “effective” in a common sense meaning without being effective this technical sense.2.3 The General Optimizing ProblemThe Standard format:Max ()f x , n x R ∈, s.t. (1) ()0,i g x ≤ 1,...,i m =; (2) 0k x ≥, {1,...,}k S n ∈⊂. Function ()f x is the objective function; x is the variable vector of the problem. The constraints (1) are the functional constraints, the constraints (2) are the direct constraints. The functions are assumed to be continuous.It is convenient to have all the inequalities in the same direction in the same direction in a standard form. Obviously 00f f ≥⇔−≤.The functional constraints can always be put in inequality form by noting that 00&0f f f =⇔≤−≤. For a very important case of the general problem, all the constraints are equalities and it is then easier to drop the inequality form.The direct constraints will always be written in the nonnegative form. The inequalities in both the functional and direct constraints are assumed always to be weak inequalities to ensure that the feasible set is closed.An optimum problem need not have a solution in general. However, we do have a guarantee that the problem is worth pursuing in a large class of cases:Theorem 2.1 (Weierstrass): A continuous function defined over a nonempty closed bounded set attains a maximum and a minimum at least once over the set.Since we usually take the objective function to be continuous and the feasible set to be closed, the boundedness of the feasible set is the only condition that is not ensured. Nevertheless, Weierstrass theorem gives sufficient but not necessary conditions to the existence of a solution of an optimum problem.2.4 The General Solution PrincipleAn optimal point must be in the feasible set but may be either an interior point or a boundary point. If it is an interior point, it has a neighborhood of feasible points and must be an optimum relative to those neighborhood points. Such a point must satisfy the ordinary calculus conditions for an unconstrained optimum. A boundary point has a neighborhood that includes infeasible points as well as feasible ones, and it is not possible to say that such a point must be optimal relative to its neighborhood. A boundary optimal point need not be critical point of f .f x are Proposition 2.2 The solution to the general optimum problem, where ()f x for x over some closed feasible set K will, if it exists, be some differentiable, Max()f x, or (b) a boundary point of K (or both). point x’ which is: (a) a critical point of ()In principle, an optimum problem can be solved by finding the critical points of ()f x along the boundary, finally choosing the f x, then computing the values of ()f x is not differentiablef x. If ()point giving the maximum or minimum of ()everywhere, the points at which it is not differentiable will need to be examined in addition to the critical and boundary points.2.5 Conditions for a Global optimumSince we are usually interested in a global optimum and since many techniques discover only local optima, conditions which guarantee that a local optimum is also a global optimum are of great value. The particular conditions set out below are of special importance because they are satisfied by most typical optimum problems in economicsf x Proposition 2.3 For problem concerned with optimizing a continuous function ()f x over a closed feasible set K, every local optimum is also a global optimum if: (a) () is a concave function for a maximum, or convex function for a minimum; and (b) K is a convex set.f x is strictly concave over a convex feasible set the global Proposition 2.4 If ()optimum is unique.Chapter 3 Classical Calculus Methods3.1 IntroductionClassical calculus methods deal with problem with the following properties:a). The objective and indirect constraint functions possess suitable continuityproperties. Usually they will be taken to be of class 2C.b). The functional constraints are equalities.c). There are no direct (non-negativity) constraints on the variablesThe standard form of the problem will be written asMax ()f x , s.t. ()0,i g x = i =1,…,m (m<n )Since the constraints are all effective at all times, the feasible set K contains only boundary points, so interior optima are ruled out. Unless the constraints are all linear, K will not necessarily be a convex set.If the appropriate Jacobean is nonsingular, we can express n-m of the variables in terms of the remaining m (from the implicit function theorem). Hence, we can reduce the problem to one of the unconstrained optimization of a function of only n-m variables. However, explicit solution of the constraint equations is possible only in a few cases, if these are nonlinear.3.2 The Lagrangean FunctionLet us examine the properties of a function 1(,)()()mi i i L x f x g x λλ==−∑, wherethe λ’s are arbitrary variables. The function (,)L x λ is called the Lagrangean function, and the λ’s are Lagrange multipliers.If we take the derivatives of (,)L x λ with respect to the λ’s, we have (,)/()0i i L x g x λλ∂∂=−= for x K ∈. Hence if (,)L x λhas a critical point at ','x λ, then 'x K ∈. Also for x K ∈, (,)L x λ=()f x . It can be shown that if x ’ maximizes f(x) over K, there is some 'λ such that (','x λ) is a critical point of (',')L x λ. The results hold for a minimum as well as a maximum.To use the Lagrange technique, we set up the Lagrangean and then find its critical point(s). The partial derivatives of (,)L x λ with respect to λ’s are simply the constraint functions and equating them to zero merely ensures that x K ∈. It is the partial derivatives with respect to the x ’s that play the major solution role. If these are equated to zero, we obtain n equations of:1mi j i j i f g λ==∑, (1,...,)j n = We can write it as f G λ∇=, where []ij G g = and []i λλ=3.3 Interpretation of the Lagrange MultipliersConsider a standard classical optimizing problem, solved by the Lagrangean technique to give solution values ','x λ. Let the i th constraint be of the form ()i i g x b =. Initially suppose 0i b =. We wish to examine the result of a small relaxation of thisconstraint.Denote the optimal value of the objective function by V’. Now a small relaxation in the i th constraint will permit small changes in the optimal values of the variables, but we assume the optimum conditions remain satisfied so that the new position reached as a result of this relaxation is also optimal. The effect on the optimal value of the objective function will be given by '(')j j i j i x V f x b x b ∂∂∂=∂∂∂∑ (1)From the constraints we have 0(')1k j j j i x k i g x k i x b ∂≠⎧∂=⎨=∂∂⎩∑ (2)If we multiple the k th equation in (2) by 'k λ, and sum over k , we obtain''(')k j ki k j j i x g x x b λλ∂∂=∂∂∑∑ With (1), we have''(')[i j i j V f x b x λ∂∂=+−∂∂∑(')]k j k kj i x g x x b λ∂∂∂∂∑='i λ Thus 'k λ corresponds to the marginal rate of change of the optimal value of the objective function with respect to a small relaxation of the i th constraint, other constraints being unchanged. In typical economic applications, the constraints might be resource limitations and the objective function is index of some social welfare. The optimal Lagrange multipliers would then correspond to the marginal social valuation of the resources.Proposition 3.1 (Envelope theorem) Let (,)f x r and (,)i g x r for i =1,…,m be continuously differentiable functions of the n+k variables. Consider the following optimizing problem:x Max (,)f x r , s.t. (,)0,i g x r = i =1,…,m (n x R ∈, m<n, k r R ∈)Denote the solution of the problem as *()x r , and **()((),)f r f x r r =. Suppose *()x r and the associated Lagrange multipliers 1,...,m λλ are continuously differentiablefunctions of r and the rank of the *[()]ij g x is m . Then**()(,)h hf r L x r r r ∂∂=∂∂ for h=1,…,k ,where 1(,)(,)(,)mi i i L x r f x r g x r λ==−∑.Example : Consider a utility maximization problem: xMax ()u x , s.t. p x w ⋅= Denote the solution of the problem by *(,)x p w , and *(,)((,))v p w u x p w ≡. Function (,)v p w is known as the indirect utility function . By the envelope theorem, we have**(,)(,)(,)i i v p w p w x p w p λ∂=−⋅∂, and *(,)(,)v p w p w wλ∂=∂. Hence we have*/(,)/i v p x p w v w∂∂=−∂∂. This result is known as Roy’s Identity .Chapter 4 Advanced Optimizing Theory4.1 IntroductionThe classical method, assumes both equality in the functional constraints and the absence of direct constraints on the variables. Although this method is widely employed in economic analysis, the fact is that most economic problems have implicit, if not explicit, properties that do not entirely fit the classical case. Nonnegative constraints on at least some variables are usually implicit, and the functional constraints may be more accurately described by inequalities than equalities. Consider the following problem of a consumer.Max 12(1)(1)u x x =++, s.t. 1241x x +=If we solve the problem, using traditional methods, we obtain the optimal values for x as *(1/4,2)x =−, with the optimal level of utility, *9/4u =. Direct calculation shows, however, that (0,1) is optimal, given the nonnegative condition.4.2 Nonnegative VariablesThe most straightforward extension of the classical calculus method is to the case in which some or all of the variables are subject to direct constraints. Consider thisMax f(x) s.t. ()0i g x =, (1,...,i m =), 0x ≥. (3)We can define the function (,)L x λ in the usual way. Three situations are possible. a). (,)L x λ has a regular local maximum at a critical point **(,)x λ, with *0x >, andthe problem satisfies the strong global optimum conditions.b). (,)L x λ has a regular local maximum at a critical point, with *0x >, but the strong global optimal conditions are not satisfied.c). (,)L x λ does not have a critical point with *0x >, which is also a local maximum.The first case is presumed to occur in traditional economic analysis. In the third case, the global optimum must be at a point at which some non-negativity constraint is operative. In the second case it might be at such a point, and will usually need to check.Still with problem (3), consider the properties of (,)L x λ and ()f x at a point x K ∈ at which 0k x = for at least one k . Since the functional constraints 0i g = are still equalities, the maxima of (,)L x λ and ()f x , x K ∈ still occur at the same point *x . Also we still have /0i L λ∂∂=, but what about the first order conditions /0j L x ∂∂=? In general, they might not all be satisfied.Define (){{1,...,}|0}i S x i n x =∈=. If ()j S x ∉, small variations in j x are possible in both positive and negative directions, so that x cannot be optimal unless /0j L x ∂∂=. If ()j S x ∈, small variations in j x are possible in the positive directiononly, so that x cannot be optimal if /0j L x ∂∂>. But small variations are not possible inthe negative direction, so we cannot rule out /0j L x ∂∂< asnon-optimal.Proposition 4.1 The optimal point *x of the problem (1) satisfies the following conditions: 1) ***1(,)0m i j i j i j L x f g x λλ=∂=−≤∂∑, and ****(,)0j j L x x x λ∂⋅=∂, 1,...,j n =. 2) ***(,)()0i iL x g x λλ∂=−=∂Example Let us return to the earlier example, which shall be stated asMax 12(1)(1)u x x =++, s.t. 1241x x +=; 12,0x x ≥The first order derivatives are 12/14L x x λ∂∂=+−, 21/1L x x λ∂∂=+−, and12/41L x x λ∂∂=+−. We already know that there is no critical point of L with 12,0x x >. Now we try putting 1x , then 2x to zero, given the budget constraints. At (0,1), we have21/110L x x λλ∂∂=+−=−=, whichgives 1λ=. 12/14L x x λ∂∂=+−= -2. U =2At (1/4,0), we have12/14140L x x λλ∂∂=+−=−=, which gives 1/4λ=. 21/11L x x λ∂∂=+−=>0, So (1/4, 0) is not an optimal point.There is no universal rule for determining which variables, when put to zero, are likely to lead to an optimal solution. In principle, we may have to try putting one variable at a time to zero, then two at a time, three at a time, and so on, and then compare the results of all cases that satisfy the optimal conditions.In economic analysis, however, we are usually interested in what happens to the optimal conditions when we do have a solution on the nonnegative boundary, and to this we have the answer. Furthermore, boundary problems of this kind in economic frequently occur as the result of a movement to the boundary from an interior point as some parameter is changed, so that the zero variables are specified for us.4.3 Inequality ConstraintsWe now consider the general optimum problem, with the two restrictions of the classical calculus method removed:Max ()f x s.t. ()0i g x ≤, (1,...,i m =), 0x ≥. (4)The problem can be converted into the case discussed in the preceding section by adding slack variables i z to give the i th constraint as ()0i i g x z +=, 0i z ≥.There are now n+m variables in the problem, an n -vector of x variables and an m -vector of z variables, with non-negativity constraints on all. We form the Lagrangean1(,,)()(())m i i i i L x z f x g x z λλ==−+∑=11()()m mii i i i i f x g x z λλ==−−∑∑ The optimal conditions with respect to j x are as before. The optimal conditionswith respect to i z are ***(,)0i i L x z λλ∂=−≤∂, and 0i i z λ=. These conditions impose no direct constraints on x , Their content is entirely represented by the equivalent statement()0i g x ≤, (1,...,i m =), 0λ≥, and 1()0miii g x λ==∑. Thus if we form the Lagrangean, ignoring the inequalities in the functional constraints, as 1(,)()()mi i i L x f x g x λλ==−∑, adding the non-negativity constraint 0λ≥,all points which are optimal for z in (,,)L x z λ satisfy (,,)L x z λ(,)L x λ=. Consider (,)()i iL x g x λλ∂=−∂. From the constraints we have ()0i g x ≤, and from the optimal conditions with respect to z in (,,)L x z λ, we have 0λ≥ and ()0i i g x λ⋅=. These together imply (,)0iL x λλ∂≥∂ and (,)0i i L x λλλ∂⋅=∂. The above conditions can be recognized as the conditions for a minimum of (,)L x λ with respect to λ, given the non-negativity constraint 0λ≥.How does it come about that, although we are seeking a maximum for ()f x subject to the constraints, and although we were able to treat (,)L x λ as having a maximum with respect to x in the strict classical case, we now seek a minimum with respect to λ of the expression that is analogous to the strict classical Lagrangean?First, we note that, in the strict classical case, if (,)L x λ is neutral with respect to changes in λ over the feasible set, we would have regarded (,)L x λ as having a minimum with respect to λ just as well as having a maximum.Second, we note that at any optimal point of (,)L x λ, whatever a maximum or a minimum with respect to λ, we have (,)L x λ()f x =. Whether a maximum or a minimum is involved, with respect to λ, is related to the constraints but not to the objective function.Third, consider an effect of a small variation in λ from its optimal value *λ. If*λ>0, then **(,)L x λ isunchanged. If *λ=0, we may have *()0i g x <. Because of the nonnegative constraint on λ, the only permissible variation is to some small positive value. In this case, the term ()i i g x λ− in the expression of **(,)L x λ will take on apositive value and we will have *(,')L x λ>**(,)L x λ. Thus, the optimal point gives a minimum of (,)L x λ. The minimum property will only be apparent when at least one constraint is ineffective.Proposition 4.2 (Kuhn-Tucker Conditions) The optimal point *x of the problem (4) satisfies the following conditions: (1) ***1(,)0m i j i j i j L x f g x λλ=∂=−≤∂∑; ****(,)0j jL x x x λ∂⋅=∂, 1,...,j n =. (2) *()0i g x ≤, and *0λ≥; **()0i i g x λ⋅=.If the problem is one of minimizing, the direction of the inequalities in (1) is reversed. If we are not trying to discover whether a certain point is optimal or not, but are merely interested in the properties of a point already known to be optimal, conditions (2) state that we can ignore ineffective constraints at the optimum.We have noted that (,)L x λ, a function of two sets of variables, has a maximum with respect to x and minimum with respect to λ at the optimum. A point which gives a maximum of a function with respect to some variables, and minimum with respect to others, is called a saddle point, a term descriptive of the shape of the function in three dimensions.4.5 Existence of Optimal SolutionsConsider the Lagrangean written in the form 1(,)()()mi i i L x f x g x λλ==−∑, with theconstraints 0,0,x λ≥≥()0i g x ≤. We see that (,)L x λ is a concave function of x if ()f x is concave and each ()i g x is convex. Considering the sets over which ,x λ are confined, since λ is defined on a convex set and the set {|()0}i x g x ≤ is convex when ()i g x is convex, the feasible set is the intersection of convex sets and is convex.We still need the sets to be compact. The nature of the constraint inequalities ensures that they are closed, so it remains to consider boundedness. Since we seek a minimum for λ, and it is bounded below by the non-negativity constraint, we can impose an arbitrary upper bound so large it does not affect the optimal solution. The feasible set for x presents the difficulties. We cannot avoid adding the special assumption that thefeasible set is bounded.Thus if ()f x is concave, every ()i g x is convex and the feasible sets is bounded, the Lagrangean satisfies the conditions of Theorem 4.4, so that is possesses a saddle point and the general optimizing problem possesses a solution. Furthermore, the conditions for a global optimum are satisfied by the same convexity-concavity conditions. Thus we haveTheorem 4.5 The general maximum problem ()Maxf x s.t. ()0i g x ≤, (1,...,i m =), 0x ≥. Always possesses a solution if:a). ()f x is concave and every ()i g x is convex;b). the feasible set {|()0,1,...,;0}i K x g x i n x =≤=≥ is bounded and nonempty.Under these conditions the Lagrangean 1(,)()()mi i i L x f x g x λλ==−∑ possesses asaddle point **,x λ, where *x is optimal in the maximum problem and *0λ≥. Furthermore, the values **,x λ satisfy the Kuhn-Tucker conditions, which are then sufficient for a global optimum. If ()f x is strictly concave, the point *x is unique.Homework:1. If 221122()2f x x bx x x =++, what values of b give: a). a local maximum of f(x), s.t. 121x x += ?b). a local minimum for f(x), s.t. 121x x += ?2. The welfare function for a two-good, two-person economy is 112a a W u u −=. Theindividual utility functions are 111121b b u x x −=, 121222c c u x x −=, where ij x is the amount of thei th good consumed by the j th individual.If the total amounts of the two goods are fixed, what is the optimum allocation between the two individuals? (Assume ,,]0,1[a b c ∈)3. Discuss the nature of the optimum solution for different values of a in the problem:Max 221210(2)(2)x x −−−− s.t. 22121x x +≤, 12x x a +≤, 120,0x x ≥≥.。