Chapter 2 Optimization Math Review, ECON 510 See Syds?ter (2005, Chapters 2, 3) and Chiang (1984, Chapters 9, 11, 12 and 21). 1. Positive Definite Matrix Definite matrices are directly related to optimization. A symmetric matrix A is positive semi-definite (A ≥ 0) if x 0 Ax ≥ 0, ? x; positive definite (A>0) if x 0 Ax > 0, ? x null=0; negative semi-definite (A ≤ 0) if x 0 Ax ≤ 0, ? x; negative definite (A<0) if x 0 Ax < 0, ? x null=0. Example 2.1. A = ? ? ? 1 ?1 ?11 ? ? ? ≥ 0.  Example 2.2. Consider A = ? ? ? ab bc ? ? ? .  Example 2.3. For a symmetric matrix A, if A ≥ 0, then a ii ≥ 0 for all i; if A ≤ 0, then a ii ≤ 0 for all i.  2—1 Given a matrix A =(a ij ) n×n , for i 1 ,···,i k ∈ {1,2,···,n} with i 1 <i 2 < ···<i k , define a k ×k minor as d {i 1 ,···i k } ≡ null null null null null null null null null null null null null null null a i 1 i 1 a i 1 i 2 ··· a i 1 i k a i 2 i 1 a i 2 i 2 a i 2 i k . . . . . . . . . a i k i 1 a i k i 1 ··· a i k i k null null null null null null null null null null null null null null null . In particular, denote theprincipal minorsas d 1 ≡ d {1} ,d 2 ≡ d {1,2} ,..., d n ≡ d {1,2,...,n} . Theorem 2.1. For a symmetric matrix A, (a) A>0 ?? d k > 0, for all k. (b) A<0 ?? (?1) k d k > 0, for all k. (c) A ≥ 0 ?? d {i 1 ,···i k } ≥ 0, for all permutations {i 1 ,...,i k } and all k =1,...,n. (d) A ≤ 0 ?? (?1) k d {i 1 ,···i k } ≥ 0, for all permutations {i 1 ,...,i k } and all k =1,...,n.  Example 2.4. (a) Verify ? ? ? 1 ?1 ?11 ? ? ? ≥ 0. (b) Find conditions for A = ? ? ? ab bc ? ? ? ≥ 0.  Proposition 2.1. ? A ≥ 0 i? all its eigenvalues are positive. ? A>0 i? all its eigenvalues are strictly positive. ? If A>0, then A ?1 > 0. ? A ≥ 0 ?? A ≤ 0. 2—2 ? A>0 ?? A<0. ? If A is a tall full-rank matrix, then A 0 A>0 and AA 0 ≥ 0. ? If A>0 and |B| null=0, then B 0 AB > 0.  2. Concavity Given points x k ∈ R n , a convex combination is y ≡ λ 1 x 1 + ···+ λ m x m , λ k ≥ 0, m null k=1 λ k =1. Given any two points x, y, the intervals are [x, y] ≡ null z | z = λx +(1?λ)y, λ ∈ [0, 1] null , (x, y) ≡ null z | z = λx +(1?λ)y, λ ∈ (0, 1) null . A set S ?R n is a convex set if ? x, y ∈ S, [x, y] ? S. Proposition 2.2. (Properties of Convex Sets). 1. Any intersection of convex sets is also convex. 2. The Cartesian product of convex sets is also convex.  f : X → R is concave if X ?R n is convex and f[λx +(1?λ)y] ≥ λf(x)+(1?λ)f(y), ? λ ∈ (0, 1),x,y∈ X. If the inequality holds strictly, f is strictly concave. f is (strictly) convex if ?f is (strictly) concave. Theorem 2.2. (Properties of Concave Functions). X ? R n is convex. 1. f : X → R is concave i? {(x,t) ∈ X ×R | f(x) ≥ t} is convex. 2. Concave functions are continuous in the interior of their domains. 3. A function f : X → R is concave i? f(λ 1 x 1 + ···+ λ k x k ) ≥ λ 1 f(x 1 )+···+ λ k f(x k ), for all k ≥ 1 and all convex combinations λ 1 x 1 + ···+ λ k x k .  2—3 Theorem 2.3. Given convex X ? R n , twice di?erentiable f : X → R, 1. f is convex ?? D 2 f(x) ≥ 0, ? x ∈ X. 2. D 2 f(x) > 0, ? x ∈ X =? f is strictly convex. 3. f is concave ?? D 2 f(x) ≤ 0, ? x ∈ X. 4. D 2 f(x) < 0, ? x ∈ X =? f is strictly concave.  Corollary 2.1. Given convex X ? R n , twice di?erentiable f : X → R, and let d {i 1 ,···,i k } (x) be a k ×k principal minors of D 2 f(x), 1. f is convex ?? d {i 1 ,···,i k } (x) ≥ 0, ? x ∈ X, ? k, ?{i 1 ,···,i k }. 2. f is concave ?? (?1) k d {i 1 ,···,i k } (x) ≥ 0, ? x ∈ X, ? k, ?{i 1 ,···,i k }. 3. d k (x) > 0, ? x ∈ X, ? k. =? f is strictly convex. 4. (?1) k d k (x) > 0, ? x ∈ X, ? k. =? f is strictly concave.  Example 2.5. “f is strictly convex”>“D 2 f>0”. E.g., f(x)=x 4 .  Example 2.6. For f(x,y)=x α + y β , defined on R 2 ++ , where α, β ≥ 0, f is ? ? ? ? ? concave, if 0 ≤ α, β ≤ 1; strictly concave, if 0 < α, β < 1. Example 2.7. For Cobb-Douglas function f(x,y)=x α y β , defined on R 2 ++ , where α, β ≥ 0, f is ? ? ? ? ? concave, if α, β ≥ 0, α + β ≤ 1; strictly concave, if α, β > 0, α + β < 1.  Proposition 2.3. Let f : X → R be di?erentiable. Then, (1) f is concave ?? Df(x) · (y ?x) ≥ f(y)?f(x), for all x, y ∈ X. (2) f is strictly concave ?? Df(x) · (y ?x) >f(y) ?f(x), for all x, y ∈ X, x null= y.  2—4 3. Quasi-Concavity Given a convex set X ? R n ,f: X → R is quasi-concave if, ? x, y ∈ X, z ∈ (x, y), f(y) ≥ f(x) ? f(z) ≥ f(x). f is strictly quasi-concave if, ? x, y ∈ X, z ∈ (x, y), f(y) ≥ f(x) ? f(z) >f(x). f is (strictly) quasi-convex if ?f is (strictly) quasi-concave. Theorem 2.4. Given convex set X ?R n , 1. f : X → R is quasi-concave i? the upper level set {x ∈ X | f(x) ≥ t} is convex, ? t ∈R. 2. f : X → R is quasi-convex i? the lower level set {x ∈ X | f(x) ≤ t} is convex, ? t ∈R.  Set f ?1 (t)={x ∈ X | f(x)=t} is called a level set. Theorem 2.5. (a) Concave functions are quasi-concave; convex functions are quasi-convex. (b) Strictly concave functions are strictly quasi-concave. Strictly convex functions are strictly quasi-convex. (c) Monotonic functions defined on R are both quasi-concave and quasi-convex.  Quasi-concavity doesn’t necessarily imply concavity. strict concavity =? concavity ?? strict quasi-concavity =? quasi-concavity 2—5 Given f : X → R, define the bordered Hessian matrix B f (x): f i ≡ ?f(x) ?x i ,f ij ≡ ? 2 f(x) ?x i ?x j ,B f (x) ≡ ? ? ? ? ? ? ? ? ? ? ? 0 f 1 ··· f n f 1 f 11 ··· f 1n . . . . . . . . . f n f n1 ··· f nn ? ? ? ? ? ? ? ? ? ? ? . Theorem 2.6. Given convex X ?R n , twice di?erentiable f : X → R, and the principal minors b 1 (x),...,b n+1 (x) of B f (x), 1. For X ?R n + ,fis quasi-convex =? b k (x) ≤ 0, ? x ∈ X, ? k. 2. For X ?R n + ,fis quasi-concave =? (?1) k b k (x) ≤ 0, ? x ∈ X, ? k. 3. For X = R n + or R n ,b k (x) < 0, ? x ∈ X, ? k ≥ 2=? f is strictly quasi-convex. 4. For X = R n + or R n , (?1) k b k (x) < 0, ? x ∈ X, ? k ≥ 2=? f is strictly quasi-concave.  Example 2.8. For f(x,y)=x α + y β , defined on R 2 ++ , where α, β ≥ 0, f is ? ? ? ? ? quasi-concave, if 0 ≤ α, β ≤ 1; strictly quasi-concave, if 0 < α, β ≤ 1 and α null=1or β null=1.  Example 2.9. For Cobb-Douglas function f(x,y)=x α y β , defined on R 2 ++ , where α, β ≥ 0, f is ? ? ? ? ? quasi-concave, if α, β ≥ 0; strictly quasi-concave, if α, β > 0.  2—6 4. Unconstrained Optimization See Syds?ter (2005, Chapter 3) and Chiang (1984, Chapter 9). If there is a neighborhood N r (x ? ) of x ? with radius r such that x ? is the maximum point of f on N r (x ? ), then x ? is a local maximum point of f. For f : R n → R, if Df(?x)=0, call ?x or (?x,f(?x)) a stationary point,andf(?x) the stationary value. Given a stationary point ?x, there are three possible situations at ?x : local maximum, local minimum point,andareflection point. Example 2.10. Compare y = x 2 with y = x 3 at x =0.  Theorem 2.7. (Extreme-Value Theorem). For continuous f : R n → R andcompact A ?R n , max x∈A f(x) has at least one solution.  Theorem 2.8. Let A ? R n . (a) If x ? is an interior solution of max x∈A f(x) then (FOC) Df(x ? )=0and (SONC) D 2 f(x ? ) ≤ 0. (b) If Df(x ? )=0and (SOSC) D 2 f(x ? ) < 0, ? N r (x ? ) s.t. x ? is the maximum point of f on N r (x ? ). (c) If f is concave on A, any point x ? ∈ A satisfying Df(x ? )=0is a maximum point. (d) If f is strictly quasi-concave, a local maximum over a convex set A is the unique global maximum.  Note: the FOC and SONC are not necessary for corner solutions; they are also not su?cient for local maximization, even for interior points. Example 2.11. Find a maximum point for f(x 1 ,x 2 )=x 2 ?4x 2 1 +3x 1 x 2 ?x 2 2 .  2—7 5. Constrained Optimization See Syds?ter (2005, Chapter 3) and Chiang (1984, Chapters 12 and 21). Theorem 2.9. (Lagrange). For f : R n → R,G: R n → R m , consider problem max x∈R n f(x) s.t. G(x)=0. Let L(λ,x) ≡ f(x)+λ ·G(x) (Lagrange function). ? If x ? is a solution and if DG(x ? ) has full rank, then ? λ ∈R m (Lagrange multi- plier)s.t. FOC : D x L(λ,x ? )=0, SONC : h 0 D 2 x f(x ? )h ≤ 0, ? h satisfying DG i (x ? )h =0, ? i. ? If the FOC is satisfied, G(x ? )=0,Gis quasi-concave, and SOSC: h 0 D 2 f(x ? )h<0, for h null=0satisfying DG(x ? )h =0, then we have a unique local maximum.  Example 2.12. For a>0 and b>0, consider F(a,b) ≡ max x 1 ,x 2 ?ax 2 1 ?bx 2 2 s.t. x 1 + x 2 =1.  Theorem 2.10. Let A ∈ R n×n be symmetric, C ∈ R m×n has full rank, m<n,and b 1 ,...,b m+n be the principal minors of B ≡ ? ? ? 0 C C T A ? ? ? . Then, 1. x 0 Ax > 0 for x null=0 satisfying Cx=0 ?? (?1) m b k > 0, ? k ≥ 2m +1. 2. x 0 Ax < 0 for x null=0 satisfying Cx=0 ?? (?1) m+k b k > 0, ? k ≥ 2m +1.  2—8 Discussions: (1) What is the intuition for the FOC? (2) What is the intuition for the SOC? (3) How to verify the SOC? (4) Is the SOC related to quasi-concavity? Example 2.13. Verify the SOC for Example 2.12.  Example 2.14. Verify the SOC for Example 2.12.  Theorem 2.11. (Kuhn-Tucker). For di?erentiable f : R n → R and G : R n → R m , consider problem V ≡ max x∈R n f(x) (2.1) s.t. G(x) ≥ 0. Let L(x,λ) ≡ f(x)+λ·G(x). If x ? is a solution and Dg j (x ? ),i=1,...,m, j=1,...,k, corresponding to binding constraints are linearly independent, then there exists λ ∈ R m + such that FOC: D x L(x ? ,λ)=0, Kuhn-Tucker condition: λ ·G(x ? )=0.  Theorem 2.12. Suppose f, g i ,h j : R n → R are C 1 functions, i =1,...,m, j = 1,...,k, and k<n.Let G ≡ (g 1 ,...,g m ) T and H ≡ (h 1 ,...,h k ) T . If x ? is a solution of the following problem V ≡ max x∈R n f(x) (2.2) s.t. G(x) ≥ 0, H(x)=0, and the vectors Dg i (x ? ) and Dh j (x ? ),i=1,...,m, j =1,...,k, corresponding to binding constraints are linearly independent, then there exists a unique λ ∈ R m + and μ ∈R k such that (a) Df(x ? )+λ ·G(x ? )+μ ·H(x ? )=0; (b) λ·G(x ? )=0.  2—9 Theorem 2.13. (global maximum). Let f and g i ,i=1,...,m, be quasi-concave, where G =(g 1 ,...,g m ) T . Let x ? satisfy the Kuhn-Tucker condition and the FOC for (2.1). Then, x ? is a global maximum point if (1) Df(x ? ) null=0, and f is locally twice continuously di?erentiable, or (2) f is concave.  H : R n → R k is linear if H(x)=Ax + B, where A is matrix and B is a vector. Proposition 2.4. Let f : R n → R and G : R n → R k be concave, and H : R n → R m be linear. Also, ? x 0 s.t. G(x 0 ) >> 0. Then, x ? is a solution of max x f(x) s.t. G(x) ≥ 0 H(x)=0 i? G(x ? ) ≥ 0,H(x ? )=0, and there exist λ ∈ R m + and μ ∈ R k such that λ ·G(x ? )=0 and x ? is a solution of max x∈R n L(x,λ,μ) ≡ f(x)+λ ·G(x)+μ·H(x).  Example 2.15. For a ∈ (0, 1), consider v(p 1 ,p 2 ,m) ≡ max x 1 ,x 2 ≥0 Ax a 1 x 1?a 2 s.t. p 1 x 1 + p 2 x 2 ≤ m.  6. Envelope Theorem Theorem 2.14. (Envelope). For di?erentiable f : X × A → R,X? R n ,A? R k , and x ? (a) being an interior maximum point of F(a) ≡ max x∈X f(x,a), we have dF(a) da = ?f(x,a) ?a null null null null x=x ? (a) .  2—10 Theorem 2.15. Suppose f, g i ,h j : R n × R l → R are C 1 functions, i =1,...,m, j =1,...,k. Let G ≡ (g 1 ,...,g m ) T ,H≡ (h 1 ,...,h k ) T , and L(x,a,λ,μ) ≡ f(x,a)+λ ·G(x,a)+μ·H(x,a). If x ? (a) is a solution of the following problem F(a) ≡ max x∈R n f(x,a) s.t. G(x,a) ≥ 0, H(x,a)=0, and λ ? (a) and μ ? (a) are the corresponding Lagrange multipliers, then under some con- ditions 1 we have ?F(a) ?a = ?L(x,a,λ,μ) ?a null null null null x=x ? (a), λ=λ ? (a), μ=μ ? (a) .  (2.3) Example 2.16. Consider F(a,b) in Example 2.12.  Example 2.17. Consider the following economic problem: v(p 1 ,...,p n ,I) ≡ max x≥0 u(x 1 ,...,x n ) s.t. p 1 x 1 + ···+ p n x n ≤ I.  1 See Sydsaeter et al (2005, p.149). 2—11 Chapter 3 Dynamic Optimization Math Review, ECON 510 1. Discrete-Time Stochastic Model Good references: Sydsaeter et al (2005, Chapter 12), Stokey—Lucas (1989, p.239—259), Sargent (1987, Chapter 1). 1.1. Markov Process What is a Markov process? At t, we know x 0 ,...,x t and some knowledge of x t+1 : x t+1 ～ F t (·|x t ,x t?1 ,...,x 0 ). We call {x t } ∞ t=0 a random process. If the distribution function is time-independent, i.e., x t+1 ～ F(·|x t ,x t?1 ,...,x 0 ), for all t, we call {x t } ∞ t=0 a stationary process. If the dependence on past history has a fixed length of time, i.e., there exists an integer n such that x t+1 ～ F(·|x t ,...,x t?n+1 ), for all t, we call {x t } ∞ t=0 an nth-order Markov process. For example, a first-order Markov process {x t } ∞ t=0 is defined by x t+1 ～ F(·|x t ), for all t. 3—1 1.2. Bellman Equation Let x t ∈R n ,u t ∈R k ,f t : R n ×R k → R, and g t : R n ×R k ×R m → R n . Consider V 0 (x 0 ) ≡ max u 0 ,u 1, ... E 0 ∞ null t=0 β t f t (x t ,u t ) s.t. x t+1 = g t (x t ,u t ,ε t+1 ), x 0 is given and known, (3.1) where 0 < β < 1, null t ∈ R m is a random vector unknown until period t, E t is the expectation operator conditional on period t information Φ t . Here u t is the control and x t is the state. Example 3.1. Consider a consumer who, at each time t, consumes c t units of goods and has assets A t , with an endowment of A 0 . The consumer may save at a gross return R t . Theconsumer’sproblemis V 0 (A 0 ) ≡ max c 0 ,c 1, ... E 0 ∞ null t=0 β t u(c t ) s.t. A t+1 = R t+1 (A t ?c t ), given A 0 . Example 3.2. Consider a firm’s problem: max {l t ,s t } E 0 ∞ null t=0 null 1 1+r null t (y t ?w t l t ?s t ) s.t. y t+1 = f(k t ,l t ,ε t+1 ), k t+1 =(1?δ)k t + s t , where s t is saving, l t is labor input, k t is capital stock, w t is wage rate, and r is the interest rate.  Let V t (x t ) ≡ max u t ,u t+1, ... E t ∞ null s=t β s?t f s (x s ,u s ) s.t. x s+1 = g s (x s ,u s ,ε s+1 ), x t is given and known. (3.2) 3—2 The solution of (1.1) is the solution of the Bellman equation: V t (x t ) ≡ max u t f t (x t ,u t )+βE t V t+1 (x t+1 ) (3.3) s.t. x t+1 = g t (x t ,u t ,ε t+1 ). Conversely, the solution {u ? t ,x ? t } of (3.3) is the solution of (1.1) if the transversality condition is satisfied: lim t→∞ β t E t V t+1 (x ? t+1 )=0. (3.4) Problem (3.3) imply two equations: f t,u (x t ,u t )+βE t null V 0 t+1 (x t+1 )g t,u (x t ,u t ,ε t+1 ) null =0, (3.5) V 0 t (x t )=f t,x (x t ,u t )+βE t null V 0 t+1 (x t+1 )g t,x (x t ,u t ,ε t+1 ) null . (3.6) We look for a solution of the form: u ? t = h t (x t ). By (2.15) and (2.2), we can generally find the two functions h t and V t . Theorem 3.1. If f t = f, g t = g and {ε t } is a Markov process, then V t is time invariant.  By Theorem 3.1, a solution (h t ,V t ) from (2.15) and (2.2) will be time invariant: u ? t = h(x t ) and V t (x t )=V (x t ). Example 3.3. Solve the consumer’s problem in Example 3.1. Assuming {R t } to be a first-order Markov process. The Euler equation is: u 0 (c t )=βE t [u 0 (c t+1 )R t+1 ], (3.7) If u(c)=lnc, the optimal consumption has the feedback form: c t =(1?β)A t . Example 3.4. Solve the firm’s problem in Example 3.2. 1.3. Lagrange Method Theorem 3.2. (Kuhn-Tucker). For di?erentiable f : R n → R and G : R n → R m , let L(λ,x) ≡ f(x)+λ ·G(x). If x ? is a solution of max x f(x) s.t. G(x) ≥ 0, then there exists λ ∈R m + such that (Kuhn-Tucker condition) λ ·G(x ? )=0 and FOC: D x L(λ,x ? )=0.  3—3 The Lagrange method can solve more general problems than (1.1). In particular, the Lagrange function for (3.2) is L = E t ∞ null s=t β s?t {f s (x s ,u s )+λ s+1 · [g s (x s ,u s ,null s+1 )?x s+1 ]}. By the Kuhn-Tucker Theorem, we can again derive the two equations (3.5) and (3.6). References [1] Chiang, A.C. (1984): Fundamental Methods of Mathematical Economics,McGraw- Hill. [2] Chiang, A.C. (1992): Elements of Dynamic Optimization, McGraw-Hill. [3] Kamien, M.I. & N.L. Schwartz (1991): Dynamic Optimization, North Holland. [4] Sargent, T.J. (1987): Dynamic Macroeconomic Theory, Harvard University Press. [5] Stokey, N.L. & R.E. Lucas (1989): Recursive Methods in Economic Dynamics, Har- vard University Press. 2. Continuous-Time Deterministic Model See Kamien—Schwartz (1991) and Chiang (1992). Example 3.5. The Shortest Path. What is the shortest path to move from one (x 0 ,y 0 ) to another (x 1 ,y 1 ) in R 2 ?  Theorem 3.3. Suppose H : R×R k ×R k → R is continuous w.r.t. its first argument, continuously di?erentiable w.r.t. its second and third arguments. Let A ≡ {continuously di?erentiable functions u :[t 0 ,T] → R k } be the set of admissible controls. Then, the solution u ? of max u∈A null T t 0 H[t, u(t), ˙u(t)]dt s.t. u(t 0 )=u 0 ,u(T)=u T (3.8) 3—4 must satisfy the Euler equation: d dt H ˙u [t, u ? (t), ˙u ? (t)] = H u [t, u ? (t), ˙u ? (t)],t∈ (0,T). (3.9) If the terminal value u(T) is free, the transversality condition is H ˙u [T, u ? (T), ˙u ? (T)] = 0. (3.10) If the initial value u(t 0 ) is free, the transversality condition is H ˙u [t 0 ,u ? (t 0 ), ˙u ? (t 0 )] = 0. (3.11) If the terminal condition is u(T) ≥ 0, the transversality conditions are u ? (T)H ˙u [T, u ? (T), ˙u ? (T)] = 0,H ˙u [T, u ? (T), ˙u ? (T)] ≤ 0. (3.12) Conversely, if H(t,u, ˙u) is concave in (u, ˙u), then any u ? ∈ A satisfying (3.9) and the initial and terminal conditions is a solution of (3.8).  Here, T can be either finite or infinite. By Kamien—Schwartz (1991, p.43), the Legendre condition is H ˙u ˙u [t, u ? (t), ˙u ? (t)] ≤ 0. It is a second order necessary condition, but not su?cient even locally. Two boundary conditions are needed to pin down the two arbitrary constants in the general solution. When a boundary condition is missing, a transversality condition replaces it. Example 3.6. Solve the following agency model: max a,s(·) null v[y ?s(y)]f(y,a)dy (3.13) s.t. null u[s(y)]f(y,a)dy ≥ c(a)+ˉu.  Example 3.7. Characterize the solution of the following model in asymmetric informa- tion: max x(·) null ˉ θ θ {u[x(θ),θ]+v[x(θ),θ]}dF (θ) s.t. ˙x(θ) ≥ 0.  3—5 Theorem 3.4. Let x ∈ R n ,u∈ R k ,g: R n ×R k ×R→ R n ,f: R n ×R k ×R→ R. For problem J(x 0 ,x T ,t 0 ) ≡ max u null T t 0 f[x(t),u(t),t]dt s.t. ˙x(t)=g[x(t),u(t),t] x(t 0 )=x 0 ,x(T) ≥ 0 define the Hamiltonian as H = f(x, u,t)+λ(t) ·g(x,u,t). Under certain di?erentiability conditions, if u ? is a solution, then there exists λ : [t 0 ,T] → R n such that u ? is a solution of H u =0, (3.14) ˙ λ = ?H x , (3.15) with transversality conditions: lim t→T λx =0, λ(T) ≥ 0.  (3.16) Theorem 3.5. Let x ∈ R n ,u∈ R k ,g: R n ×R k ×R→ R n ,f: R n ×R k ×R→ R. For problem J(x 0 ,x T ,t 0 ) ≡ max u null T t 0 f[x(t),u(t)]e ?θ(t?t 0 ) dt s.t. ˙x(t)=g[x(t),u(t),t] x(t 0 )=x 0 ,x(T) ≥ 0 define the Hamiltonian as H = f(x, u)+λ(t) ·g(x,u,t). Under certain di?erentiability conditions, if u ? is a solution, then there exists λ : [t 0 ,T] → R n such that u ? is a solution of H u =0, ˙ λ = θλ?H x , with transversality condition lim t→T λxe ?θt =0, λ(T) ≥ 0.  3—6 Example 3.8. The corresponding continuous-time version of the consumer’s problem in Example 3.1 is J(A 0 ) ≡ max c null ∞ 0 u(c)e ?ρt dt s.t. ˙ A = rA?c A(0) = A 0 ,A(∞ ) ≥ 0. Characterize the optimal consumption path.  Example 3.9. Many other types of constraints can also be handled similarly. For ex- ample, consider the following problem J(x 0 ,x T ,t 0 ) ≡ max u null T t 0 f[x(t),u(t),t]dt s.t. ˙x(t)=g[x(t),u(t),t], null T t 0 h[x(t),u(t),t]dt = c, x(t 0 )=x 0 ,x(T)=x T .  3. Phase Diagram See Chiang (1984, 1992) and Sydsaeter et al (2005, p.244). 3.1. The Linear System A phase diagram is often used to analyze the solution from a dynamic system. From an optimal control problem, the Euler equation and the motion equation generally lead to two equations of the form: ? ? ? ? ? ˙x = f(x,y,t), ˙y = g(x,y,t). Phase diagrams handle the autonomous case with f = f(x,y) and g = g(x,y). 1. For simple f and g, we may be able to solve this equation system directly. 2. For complicated f and g, we may use a phase diagram to illustrate the solution path. 3—7 Example 3.10. In Example 3.8, c(t) and A(t) are determined by ˙ A = rA?c ˙c =(r ?ρ) c α(c) . The General Solution Consider a linear system ˙x = a(x? ˉx)+b(y ? ˉy), ˙y = α(x? ˉx)+β(y ? ˉy), where a, b, α, β ∈R and (ˉx, ˉy) is the steady state. The equation system can be written in a matrix form: ? ? ? ˙x ˙y ? ? ? = A ? ? ? x? ˉx y ? ˉy ? ? ? , (3.17) where A = ? ? ? d 1 a 1 a 2 d 2 ? ? ? . The eigenvalues of A are λ = 1 2 null d 1 + d 1 ? null (d 1 + d 1 ) 2 ?4|A| null , μ = 1 2 null d 1 + d 1 + null (d 1 + d 1 ) 2 ?4|A| null . We have λ ≤ μ. Let ξ and ζ be eigenvectors of λ and μ, respectively. The general solution of (3.17) is ? ? ? x(t) y(t) ? ? ? = ? ? ? ˉx ˉy ? ? ? + c 1 ξe λt + c 2 ζe μt . (3.18) where c 1 and c 2 are arbitrary constants. Stability Analysis Saddle-Point Stable Path with |A| < 0. If |A| < 0, then λ < 0 and μ > 0, implying that the system is saddle-point stable. Convergent sequences must have c 2 =0. 3—8 Thus, the initial point must be on the convergence line: ? ? ? x y ? ? ? = ? ? ? ˉx ˉy ? ? ? + τξ, for τ ∈R. Given the initial point (x 0 ,y 0 ) on the convergence line, (3.18) implies the adjustment path: ? ? ? x(t) y(t) ? ? ? = ? ? ? ˉx ˉy ? ? ? + ? ? ? x 0 ? ˉx y 0 ? ˉy ? ? ? e λt , which converges to (ˉx, ˉy). The non-convergence line is defined by ? ? ? x y ? ? ? = ? ? ? ˉx ˉy ? ? ? + τζ, for τ ∈R. Theorem 3.6. For the linear system ˙x = A(x? ˉx), where x ∈ R 2 and A ∈ R 2×2 , suppose the system is saddle-point stable with |A| < 0. Then, it has a negative eigenvalue λ < 0 and a positive eigenvalue μ > 0. Let ξ and ζ be eigenvectors of λ and μ, respectively. Then, the convergence line is x =ˉx + τξ, τ ∈R, and the non-convergence line is x =ˉx + τζ, τ ∈R. If the initial point x 0 is on the convergence line, the convergent path is x =ˉx +(x 0 ? ˉx)e λt ; and if the initial point x 0 is on the non-convergence line, the non-convergent path is x =ˉx +(x 0 ? ˉx)e μt .  Example 3.11. Draw the phase diagram for the following system: ˙x = ?(x? ˉx)+10(y ? ˉy), ˙y =20(x? ˉx)+3(y ? ˉy).  3—9 Nonstable Path with |A| > 0. If (d 1 + d 1 ) 2 < 4|A|, thetwoeigenvaluesare λ = d 1 + d 1 2 ?iθ, μ = d 1 + d 1 2 + iθ, where θ ≡ null |A|? null d 1 +d 1 2 null 2 . By (3.18), the adjustment path is ? ? ? x(t) y(t) ? ? ? = ? ? ? ˉx ˉy ? ? ? + null ξe λt , ζe μt null (ξ, ζ) ?1 ? ? ? x 0 ? ˉx y 0 ? ˉy ? ? ? . Since e λt = e d 1 +d 1 2 t [cos(θt)?isin(θt)], e μt = e d 1 +d 1 2 t [cos(θt)+isin(θt)], the convergence is totally determined by d 1 + d 1 . 1. If d 1 + d 1 =0, the adjustment path will be a cycle (a vortex with uniform fluctua- tions). 2. If d 1 + d 1 < 0, the adjustment path is convergent but with cycles (damped fluctua- tions). 3. If d 1 + d 1 > 0, the adjustment path is non-convergent and with cycles (explosive fluctuations). If (d 1 + d 1 ) 2 ≥ 4|A|, since |A| > 0, the signs of λ and μ arethesameasthesign of d 1 + d 1 . 1. If d 1 + d 1 > 0, an adjustment path starting from any point is non-stable. 2. If d 1 + d 1 < 0, an adjustment path starting from any point is convergent. Stable Path with |A| =0. If |A| =0, one of the eigenvalues must be zero and the two demarcation lines defined by A ? ? ? x? ˉx y ? ˉy ? ? ? =0 are merged into one. If d 1 + d 1 > 0, a convergent path must start from the convergence line and it stays at the initial point forever. If d 1 + d 1 < 0, any sequence is convergent, but the limit is generally not (ˉx, ˉy). 3—10 3.2. Linearization For a general nonlinear system ? ? ? ? ? ˙x = f(x,y), ˙y = g(x,y), (3.19) we can convert it into a linear system in (3.17) by linearization. Define the steady state by the state at which ˙x =0and ˙y =0, that is, the steady state (ˉx, ˉy) is the point where f(ˉx, ˉy)=0,g(ˉx, ˉy)=0. By Taylor’s expansion formula, (3.19) can be approximated by ? ? ? ? ? ˙x = f x (ˉx, ˉy)(x? ˉx)+f y (ˉx, ˉy)(y ? ˉy), ˙y = g x (ˉx, ˉy)(x? ˉx)+g y (ˉx, ˉy)(y ? ˉy). This is a linear system, which can then be analyzed using the discussions in previous section. 3.3. Adjustment Path For a system, ? ? ? ? ? ˙x = f(x,y) ˙y = g(x,y) when there is a change in f and/or g, the steady state may change. How does the economy then move towards the new steady state? For a system that is not derived by an optimization problem, two assumptions are needed in order to pin down the adjustment path: Assumption 1. One variable cannot jump, but the other can. Assumption 2. Any adjustment path can only jump at the beginning; it must move continuously afterwards. The general solution of thesystemhas two arbitraryconstants. These twoassumptions pin down these two constants. 3—11 For most dynamic optimization problems, these two assumptions are implied by op- timal behaviors. We now show in an example how to use these two assumptions to pin down the adjustment path. The Model Let A be the aggregate demand, defined by A = C + I + G, where C is aggregate demand, I is aggregate investment, and G is government spending. First, assume investment and consumption are a?ected by the long-term real interest rate r. Then, A =[a + b(Y ?T)] + (α?βr)+G, where T is tax and a, b, α and β are constants. Second, assume that the adjustment of output takes time. Namely, ˙ Y = φ(A?Y)=φ[?(1 ?b)Y ?βr + a + α?bT + G], where φ(·) is a strictly increasing function with φ(0) = 0. Third, assume that there are two types of bonds, 1. short nominal bonds that pay a nominal rate i, and 2. real consols that promise to pay one good per unit of time forever. Let Q be the real price of a consol; then the long-term return from the consol is r = 1 Q . The short-term return from the consol is 1 Q + ˙ Q Q = r? ˙r r . Assume that asset holders equalize rates of return on both assets up to a constant risk premium η, i.e., r ? ˙r r = i?π e + η, where π e is the expected inflation rate. Finally, the money demand function is in the standard form: M d P = L(i,Y ). 3—12