第十讲 动态最优问题求解：（III....pdf

1›ù Ä •`¯K¦)µ £III¤ Ä 5y •% E ŒÆ²LÆ •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 1 / 20 ù̇SN 1. Ä 5yÄ 1.1 Ä Vg gŽµ48¦) 1.2 ¯K«~ 1.3 -‡Vg 2. (½5Ä 5yµ-‡½n†¦)•{ 2.1 •`z n 2.2 Ø ½n N 2.3 dŠ¼êS“ 3. ‘ÅÄ 3.1 •`z 5yµ-‡½n†¦)•{ nÚdŠ¼êS“ 3.2 dŠ¼êÚüѼê 4. lÑÀJÄ •% (E ŒÆ²LÆ ) 5Ÿ½n 5y£Discrete Choice DP¤ êþ²LÆ£1›ù¤ 2 / 20 1. Ä 5yÄ Vg 1.1 Ä gŽµ48¦) Ä 5y Ä gŽ I ·‚^.‚KF•{Ú•`›› •ŒŠ n£maximum principle¤5©ÛÄ •`¯Kž§Ø%óä´'uS)Cþ ˜ ^‡§ )CþlÑ!¹k )‘ÅCþ§½•3üÑ51• d·‚I‡•˜„z þã•{éJÿÐ E, S Ä •`¯K§Ï ¦)•{" I Rust(2008): Dynamic programming has enabled economists to formulate and solve a huge variety of problems involving sequential decision making under uncertainty, and as a result it is now widely regarded as the single most important tool in economics. I Bellman(1957)JÑ Ä 5y •`z n£the principle of optimality¤ §Ø %gŽ´48Ž{£recursive algorithm¤µAn optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute and optimal policy with regard to the state resulting from the first decision. •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 3 / 20 1. Ä 5yÄ ~1µ•á´» lA E z˜Ú Vg 1.2 ¯K«~ _•¦)£backward induction¤ ´§Xmã ¤«§1 t Ú1i ‡!: ˆE •á´»•Ý©O•µ V4 (E) = 0 V3 (Di ) = min [l (Di , E) + V4 (E)] V2 (Ci ) = min [l (Ci , Dj ) + V3 (Dj )] V1 (Bi ) = min [l (Bi , Cj ) + V2 (Cj )] V0 (A) = min [l (A, Bj ) + V1 (Bj )] = 19 þãL§Œ±L«•_•¦) 48úªµ ã¡5 µzÝz‰/Ä 5y0c^" Vt (i) = min[l (i, j) + Vt+1 (j)] •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 4 / 20 1. Ä 5yÄ Vg 1.2 ¯K«~ ~2µüÏ)·±Ï;O¯K _•¦) max ln c1 + β ln c2 s.t.k1 = w + Rk0 − c1 k2 = w + Rk1 − c2 = 0 I T=2µc2 = w + Rk1 §V2 (k1 ) = max ln (w + Rk1 ) I T=1µ V1 (k0 ) = max [ln c1 + βV2 (k1 )] = max [ln c1 + β ln (w + R (w + Rk0 − c1 ))] 1+R R 1 (k0 ) d˜ ^‡ ∂V∂c = 0 k c1 = φ1 w + φ2 k0 £Ù¥µφ1 = (1+β)R , φ2 = 1+β ¤ § 1 “\Œ µ V1 (k0 ) = (1 + β) ln (φ1 w + φ2 k0 ) + β ln (βR) •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 5 / 20 1. Ä 5yÄ Vg 1.2 ¯K«~ ~3µ(½5•`O•¯K max ∞ P β t ln ct t=0 s.t. kt+1 = zktα − ct k0 = 1, lim β t u0 (ct ) kt = 0 t→∞ r8I¼êP•ÏÐ] ¼ê V (k0 ) = ln c0 + β ln c1 + ... = ln c0 + βV (k1 )§± daí§l?¿ t = 0, 1, 2... m©kµ V (kt ) = max [ln ct + βV (kt+1 )] ßÿ V (kt ) = θ0 + θ1 ln kt §Kµ V (kt+1 ) = θ0 + θ1 ln kt+1 = θ0 + θ1 ln(zktα − ct ) zkα t d˜ ^‡ ∂V∂c(kt t ) = 0 k ct = 1+βθ "“\dŠ¼ê§^–½Xê{Œ 1 µ V (kt ) = θ0 + θ1 ln kt , ct = (1 − αβ)zktα , kt+1 = αβzktα ln(αβ) 1 α Ù¥µθ0 = 1−β [ ln z+αβ + ln(1 − αβ)]!θ1 = 1−αβ " 1−αβ •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 6 / 20 1. Ä 5yÄ Vg 1.2 ¯K«~ ~4µ‘Å5•`O•¯K max E0 [ ∞ P β t ln ct ] t=0 s.t. kt+1 = zt ktα − ct k0 = 1, lim β t u0 (ct ) kt = 0 t→∞ ln zt = ρ ln zt−1 + εt , εt *N (0, σ 2 ) t = 0, 1, 2... ž§aq/½Âµ V (kt , zt ) = max {ln ct + βEt [V (kt+1 , zt+1 )]} ßÿ V (kt , zt ) = θ0 + θ1 ln kt + θ2 ln zt §Ó |^˜ ^‡Ú–½Xê{Œ µ V (kt , zt ) = θ0 + θ1 ln kt + θ2 ln zt ct = (1 − αβ)zt ktα , kt+1 = αβzt ktα ln(αβ) α 1 1 Ù¥µθ0 = 1−β [ αβ1−αβ + ln(1 − αβ)]!θ1 = 1−αβ !θ2 = (1−ρβ)(1−αβ) •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 7 / 20 1. Ä 5yÄ Vg 1.3 -‡Vg -‡Vg I G Cþ£state variable¤st = (xt , zt )§XS) ] •þ! ) Eâ À¶ I ››Cþ£control variable¤ut §XëY ž¤ûü!lÑ ´Äë\ó Š ÀJ ¶ I £=Ϥ£ ¼ê£instantaneous payoff function¤F (st , ut )§Xz˜Ï ^¼ê!|d¼ê ¶ I 8I¼ê£objective function¤½dŠ¼ê£value function¤V (st )§X o ^!o|d ¶ I £•`¤üѼê£policy function¤u∗ t = argmaxV (st )§X•`ž¤û ü!•`Ý]üÑ " •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 8 / 20 1. Ä 5yÄ Vg 1.3 -‡Vg -‡Vg I S)CþS /¤ {¤•þ£history¤µ Ht−1 = (s1 , u1 , s2 , u2 , ...st−1 , ut−1 ) ˜„b½žmS äkê ‰Å5Ÿ§{¤•þ¥ò•kþ˜Ï Cþ (st−1 , ut−1 ) ¬K• ϧl I š˜ I G ¦¯K ©ÛŒŒ{z" Cþ8Ü st ∈ S(Ht−1 )§ ¤^‡•)µ S)G Cþ =£•§£transfer function¤xt = G(st−1 , ut−1 )§ XýŽ 啧 I )G Cþ ^‡VÇ£conditional probability¤ §Xê ‰Åó =£VÇÝ £transition matrix¤P (zt |zt−1 ) I š˜ ûüCþ å8£constraint set¤ut ∈ U(st )§Xž¤ ct ∈ (0, zt ktα )"U ´lG Cþ «m ››Cþ ¢ŠN ½éA8Ü£a set-valued mapping or a correspondence¤ " •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 9 / 20 2. (½5Ä 5yµ-‡½n†¦)•{ •`z 2.1 •`z n n£Principle of optimality¤ ‰½Ð©G x0 §Ä •`z¯KŒ±Lã•S ûü¯K£sequential problem, SP¤µ V ∗ (x0 ) = sup ∞ P {ut }∞ t=0 t=0 β t F (xt , ut ) s.t. xt+1 ∈ X(xt , ut ), ut ∈ U(xt ) •Œ± • ù•§£Bellman equation¤¤£ã •§ûü¯K£functional problem, FP¤£ å^‡ØC§t = 0, 1, ...¤ µ V (xt ) = sup {F (xt , ut ) + βV (xt+1 )} ut b½ V ∗ (s0 ) •3…k•§Kµ ù•§¤½Â I I •3÷v dŠ¼ê£value function¤V (xt ) •3¶ ù•§ •`üѧ=•3üѼê£policy function¤ µ u∗t = argmaxV (xt )¶ I V ∗ (x0 ) = V (x0 )§SP†FP d§::•` •% êþ²LÆ£1›ù¤ (E ŒÆ²LÆ ) yS •`" 10 / 20 2. (½5Ä 5yµ-‡½n†¦)•{ Ä 5y•{ 2.1 •`z n d5µ±•`O•¯K•~ •`O•¯K ù•§•µ V (kt ) = max [ln ct + βV (kt+1 )] ct ŠâýŽ å^‡ kt+1 = zktα − ct §þª duµ V (kt ) = max [ln (zktα − kt+1 ) + βV (kt+1 )] kt+1 dŠ¼êŒ I ˜ žkµ ^‡£FOC¤µ ∂V (kt ) ∂V (kt+1 ) ∂V (kt+1 ) −1 1 = +β =0⇔ =β ∂kt+1 ct ∂kt+1 ct ∂kt+1 I •ä^‡£envelope condition¤µ ∂V (kt ) zαktα−1 = ∂kt ct éá=Œ î.•§µ α−1 ct+1 = βzαkt+1 ct •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 11 / 20 2. (½5Ä 5yµ-‡½n†¦)•{ Ø N 2.2 Ø N ½n ½n£Theorem of Contraction Mapping¤ XJ (M, d) ´˜‡ Ýþ˜m1 §T : M → M ´˜‡ I T 3 M ¥k•˜ ØÄ: V = T (V )¶ •β Ø N 2 §Kµ I é?¿ V (0) ∈ M Ú n = 0, 1...µ d(T n (V (0) ), V ) ≤ β n d(V (0) , V ) ã¡5 µStocky and Lucas(1999)" 1 Ýþ˜m(M, d) ´˜‡½Â Ýþ£ål¼ê¤d 8Ü M§é ∀x, y, z ∈ M kµ £1¤d(x, y) ≥ 0§ x = y ž•"¶£2¤d(x, y) = d(y, x)¶ £3¤d(x, z) ≤ d(x, y) + d(y, z)"XJ S ¥z‡…ÜS ƒ lim xn = x ∈ M§K¡(M, d) • n→∞ Y¼ê V : S → R ¤ ÑÂñ …= M ¥ ˜‡ Ýþ˜m£complete metric space¤"éu·‚'% ¯K§3¤kk.ë 8Ü V þ½Âþ(.‰ê kV k = sup |V (s)|§K (V, k·k) ´˜‡ Ýþ˜m" s∈S 2 ‰½Ýþ˜m (M, d) Ú T : M → M§e•3 β ∈ (0, 1) é ∀x, y ∈ M k d(T x, T y) ≤ βd(x, y)§K¡ T ´ ˜‡ • β •% Ø N " ù•§ m>ҽ ˜‡ • β (E ŒÆ²LÆ ) Ø N " êþ²LÆ£1›ù¤ 12 / 20 2. (½5Ä 5yµ-‡½n†¦)•{ 2.3 dŠ¼êS“ dŠ¼êS“£value function iteration§VFI¤ I Ž{µ Cþ 1. n = 0§3G X (n) ‚: {xi }N (xi )¶ i=1 þédŠ¼ê‰Ð©ßÿ V 2. 3 ‡½Â• x ∈ [xmin , xmax ] þ[ÜÑëY dŠ¼ê V̂ (n) (x)¶ X 3. 3‚: {xi }N i=1 þ¦)µ h i V (n+1) (xi,t ) = max F (xi,t , ut ) + β V̂ (n) (xt+1 ) ut ä´Äk V (n+1) (xi ) − V (n) (xi ) < ε"´µV = V (n+1) ¶Äµ 4. n = n + 1§-EÚ½2*4" I µdµ I `:´ŠâØ N ÿm©§Œ± I ":Ø ½n§•‡¦ V (xt ) k.ëY§ Û•`)¶ Âñ„Ýú£± β • ‡Ý O\ …l?¿Ð©ß Ø N ׄþ,"'XkK‡G Ò‡3 N X = N K ¤± §OŽþò‘G Cþ!z‡G ‡‚:þ|¢ V §ÏdóŠþò‘K Cþ Cþ N‡‚:§ O\¥AÛ?ê O•§Ñy‘ê/J£curse of dimensionality¤" •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 13 / 20 3. ‘ÅÄ 5yµ-‡½n†¦)•{ 3.1 •`z nÚdŠ¼êS“ ¯K£ã ‰½Ð©G s0 = (x0 , z0 ) Úäkê Cþ zt §‘ÅÄ •`¯K£ã•µ ∗ V (s0 ) = ‰Å5Ÿ P (zt |Ht−1 ) = P (zt |zt−1 ) sup E0 {ut }∞ t=0 ∞ P t ‘Å  β F (st , ut ) t=0 s.t. xt+1 = G(st , ut ), ut ∈ U(st ) ò=£•§ xt+1 = G(st , ut ) ÚŒ18 Ä å ut ∈ U(st ) Ü¿• xt+1 ∈ G(st )"‘Å 5y¯K£ã•µ V (st ) = sup {F (st , ut ) + βE[V (st+1 ) |st ]} ut s.t. xt+1 ∈ G(st ), (t = 0, 1, 2...) •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 14 / 20 3. ‘ÅÄ 5yµ-‡½n†¦)•{ •`z éu˜ 3.1 •`z nÚdŠ¼êS“ n ê ‰Åó zt ∈ Z = {Z1 , Z2 ...ZN }§b½µ 1. V ∗ (s0 ) •3…k•¶ 2. £ ¼ê F (st , ut ) ëY¶ 3. S)G Cþ8Ü X • RK ;f8§…¢ŠN £½éA8ܤ G : S → X š˜!;Š…ëY£non-empty compact-valued and continuous¤ éu˜„ ê ‰Å‘ÅL§ zt ∈ Z ⊆ RL §O\b½µ 4. zt äk¤V5Ÿ£Feller property¤§=é?¿k.ëY¼ê V (·, zt )§ E[V (·, zt+1 )|zt ] •´ zt k.ëY¼ê Šâ Acemoglu(2009)§kµ I V (st ) •3!•˜§…k.ëY¶ I u∗t = argmaxV (st ) •3¶ I V ∗ (s0 ) = V (s0 )" •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 15 / 20 3. ‘ÅÄ 5yµ-‡½n†¦)•{ 3.1 •`z nÚdŠ¼êS“ dŠ¼êS“ 1. ò‘ÅL§ zt lÑz• N Z ‡‚:§OŽ=£Ý µ PN Z×N Z = [pij ], pij = Pr (zt+1 = Zj |zt = Zi ) 2. n = 0§3 N S = N X × N Z ‡G Cþ ‚: si = (xi , zi ) þßÿdŠ¼ê Š V (n) (si )¶ 3. ‰½ zi §3 X þ[ÜÑëY dŠ¼ê V̂ (n) (x, zi )§ƒAkµ E[V̂ (n) (xt+1 , zj,t+1 ) |zit ] = V̂ (n) × P T 4. 3‚: si þ¦)µ n o V (n+1) (sit ) = max F (sit , ut ) + βE[V̂ (n) (xt+1 , zj,t+1 ) |zit ] ut ä´Äk V (n+1) (si ) − V (n) (si ) < ε"´µV = V (n+1) ¶Äµn = n + 1§- 5. EÚ½3*5" •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 16 / 20 3. ‘ÅÄ 5yµ-‡½n†¦)•{ 3.2 dŠ¼êÚüѼê 5Ÿ½n dŠ¼êÚüѼê 5Ÿ½n I 3b½1*4 x Ä:þ§O\b½5µF (s, u) ´ u î‚]¼ê§éA G(x, z) ´ à8£convex in x¤§KdŠ¼ê V (s) •î‚]¼ê§üѼê u∗ •˜… é x ëY" I 3b½1*4 Ä:þ§O\b½6µ‰½ z, u§F (x, z, u) ´ x î‚O¼ê§é 0 A G(x, z) é x üN£=éu x ≤ x k G(x, z) ⊆ G(x−, z)¤ § K V (x, z) ´ x î‚O¼ê" I 3b½1*5 Ä:þ§O\b½7µ‰½ z§F (x, z, u) 3 X × U SÜé x Ú u ∗ ëYŒ‡§Kéu x ∈ IntX, u ∈ IntU(s)§kµ Vx (x, z) = Fx (x, z, u∗ (x, z)) •% (E ŒÆ²LÆ ) êþ²LÆ£1›ù¤ 17 / 20 4. lÑÀJÄ 5y£Discrete Choice DP¤ lÑÀJÄ 5yµ±óŠ|¢¯K•~ éuóŠ|¢¯Kµ  V (x) = M ax •3,‡ó] x , β 1−β Z ∞ 0 V (x )dF x  0
0 ©.: x̃£cutting point¤ µ Z ∞

x < x̃ aø : V (x) = β V x0 dF x0 Z0 ∞

x̃ x = x̃ Ã É : V x0 dF x0 =β 1−β 0 x x > x̃ Øaø : V (x) = 1−β “\dŠ¼ê§²OŽ nŒ µ Z ∞ Z x̃ V (x) dF (x) = 0 •% (E ŒÆ²LÆ ) Z ∞ x̃ x dF (x) + dF (x) 1 − β 1 − β 0 x̃ Z ∞ x̃ x̃ x − x̃ = + dF (x) β (1 − β) 1−β 1−β Z ∞ x̃ β x̃= (x − x̃) dF (x) 1 − β x̃ êþ²LÆ£1›ù¤ 18 / 20 4. lÑÀJÄ 5y£Discrete Choice DP¤ óŠ|¢¯K β x̃ = 1−β Z ∞ I l²L¹Â5w§þª†>´ c \§=aø ó] Ŭ¤ ¶m>K´aø > SÂçü>ƒ ž´Ä†óŠ´Ã Ïd x̃ • 3ó]" ¡• I ‰½ëê β Úó] ~¼ê§ÏdŒ±)Ñ•˜ y 3ó]´ β O¼ê§ ©Ù¼ê§âU (E ŒÆ²LÆ ) É § ©Ù¼ê§dum>´ x̃ AÏ •% (x − x̃) dF (x) x̃ x̃"´ I‡b½˜ x̃ w«)" êþ²LÆ£1›ù¤ 19 / 20 ë•©z I Acemoglu, D. 2013: Introduction to Modern Economic Growth, Princeton University Press I L.L. ¿dA!T.J. ÷êdͧ2013µ 548÷*²LnØ£1 ‡¤6§ R ȧ¥I<¬ŒÆч I N.L. d÷Ä!R.E. ©kd!E.C.ÊXdŽA§1999µ 5²LÄ {6§ •% ²éȧ (E ŒÆ²LÆ ) [÷ §‹ 48• ^Ì"§¥I ¬‰Æч êþ²LÆ£1›ù¤ 20 / 20