An Introduction To Dynamic Programming
An Introduction to Dynamic ProgrammingJin CaoMacroeconomics (Research, WS10/11)November, 2010
OutlineMotivationWhy Dynamic ProgrammingBasic IdeaOptimality ConditionsThe First Order ConditionThe Envelope ConditionAn Example: Brock-Mirman ModelValue Function and Policy FunctionGuess and VerifyValue Function IterationNumerical Simulation2 of 21
Why dynamic programming? Lagrangian and optimal control are able to deal with most of thedynamic optimization problems, even for the cases where dynamicprogramming fails.However, dynamic programming has become widely used becauseof its appealing characteristics: Recursive feature: flexible, and significantly reducing the complexity ofthe problems;Convergence in the value function: quantitative analysis, especiallynumerical simulation;Although based on profound theories, numerical computation is rathersimple as well as full-fledged. — At least one can get numericalresults.In this presentation: How to USE dynamic programming methods.3 of 21
The prototype problem Consider a general discrete-time optimization problemmax {ct ,kt 1 }t 0s.t. Xβ t u(ct )t 0kt 1 f (ct , kt ).Now define a function (mostly, bounded in value)V (kt ) s.t.4 of 21maxct ,kt 1 X(β i u(ct i ) maxi 0ct ,kt 1max {u(ct ) βV (kt 1 )}ct ,kt 1kt 1 f (ct , kt ).u(ct ) β Xi 0)β i u(ct i 1 )
Basic idea: recursive structure Recursive nature of the problem — same problem for all t!Bellman equationV (kt ) max {u(ct ) βV (kt 1 )}ct ,kt 1 More jargons, similar as before: State variable kt , control variablect , transition equation (law of motion), value function V (kt ),policy function ct h(kt ). Now the problem turns out to be a one-shot optimization problem,given the transition equation!5 of 21
The first order condition The next step: finding the optimality conditions! Trivial to see: FOC of the maximization problem.V (kt ) max {u(ct ) βV (kt 1 )} ct ,kt 1 u(ct ) V (kt 1 ) β 0. kt 1 kt 1 Reason: Decision problem at period t is to allocate resourcesbetween ct and kt 1 . V (kt ) is an optimized value for each periodt — FOC with respect to kt 1 should hold. To get Euler equation, still need a second equation to eliminateV (·) term.6 of 21
The envelope condition The Envelope TheoremTheoremSuppose that value function m(a) is defined as following:m(a) max f (x(a), a).xThen the total derivative of m(a) with respect to a equals the partialderivative of f (x(a), a) with respect to a, if f (x(a), a) is evaluated atx x(a) that maximizes f (x(a), a), i.e.dm(a) f (x(a), a) da a7 of 21.x x(a)
The envelope condition Then the envelope condition of the maximization problem.V (kt ) max {u(ct ) βV (kt 1 )} ct ,kt 1 V (kt ) u(ct ) . kt ktCombine with the FOC: update and eliminate V (·) u(ct ) V (kt 1 ) β 0. kt 1 kt 1 To see how it works? An example.8 of 21
Example: deterministic Brock-Mirman model Consider the following social planner’s problem: Xmax{ct ,kt } t 0t 0kt 1 ktα ct .s.t. β t ln ctBellman equation: V (k) maxln c βV (k 0 )0ks.t.9 of 21c k 0 k α.
Example: optimality conditions Use the transition equation to replace c V (k) maxln(k α k 0 ) βV (k 0 ) .0k The first order condition and the envelope conditionV 0 (k) c1 βV 0 (k 0 ) 1α 1 V 0 (k 0 )c αk0 10α 1c 0 αkEuler equation, same as one can get from Hamiltonian:c00α 1 .c αβk10 of 21
What’s new: making more senses If dynamic programming simply arrives at the same outcome asHamiltonian, then one doesn’t have to bother with it. However, the marginal return from dynamic programming becomeshigher if one explores deeper. Take a closer look: Value function? Tells you how different paths may affect your valueon the entire time horizon. Policy evaluation!Policy function? Tells you explicitly how you make optimal choice ineach period, given the state!Strategy: Determine V (k), and optimize to get ct h(kt ). Noteasy. 11 of 21Analytical — not always tractable, orNumerical — in principle, always works.
Mickey Mouse models: guess and verify Brock-Mirman model: V (k) maxln c βV (k 0 )0ks.t. c k 0 k α.Guess: V (k) A B ln k. Verify with the first order condition1βB1 0 0. βV 0 (k 0 ) α0ck kk βBSolve to get k 0 1 βBk α , as well as c these equations back to Bellman.12 of 211α1 βB k .Then apply
Mickey Mouse models: guess and verify Compare with our conjecture V (k) A B ln kV (k) ln βB βA (1 βB) ln(1 βB) α(1 βB) ln k. Solve to get the value of the parameters and the policy functionB α,1 αβ 1αβA ln αβ ,ln(1 αβ) 1 β1 αβct 13 of 211k α (1 αβ)ktα .1 βB t
Value function at the end of the world More general approach: To find the value function in the limit.Suppose that the world ends after some finite peroid T . Thensurely V (kT 1 ) 0 as well as cT kTα , and kT 1 0. Apply these in the Bellman equationV (kT ) ln kTα βV (kT 1 ) ln kTα . Then take one period backward, the agent has to solveV (kT 1 ) max {ln(cT 1 ) βV (kT )} .cT 1 ,kT14 of 21
Value function before the end of the world Insert V (kT ) and solve for V (kT 1 ) in terms of kT 1V (kT 1 ) αβ ln(αβ) (1 αβ) ln(1 αβ) (1 αβ) ln kTα 1 . In the limit T one can show that the value functionconverges to 1αβV (kt ) max ln ct βln(1 αβ) ln αβct ,kt 11 β1 αβ α ln kt 1 .1 αβ Then solve this static maximization problem to get the policyfunctionct (1 αβ)ktα .15 of 21
Numerical simulation How if the problem gets more complicated? Consider V (k) max0 u(c) βV (k 0 )c,ks.t. c k 0 Ak α δk.No open form solution! But. let the computer do the valuefunction iteration. 16 of 21Discretize the state space, and determine its range;Start from the end of the world, and do the backward inductionUntil the change in value function meets the convergence criterion.
Numerical simulation: value function Take β 0.6, A 20, α 0.3, δ 0.5 and run MATLABValue Function98.5Utility87.576.5617 of 210246Capital81012
Numerical simulation: convergence . and see how it converges .Value Function987Utility65432118 of 210246Capital81012
Numerical simulation: steady state . and find the steady state.Policy Function12Capital Tomorrow108642019 of 210246Capital Today81012
Summary If one only needs the Euler equation and qualitative reasoning,dynamic programming is no better than Hamiltonian. To use dynamic programming, more issues to worry: Recursive?Existence of equilibrium (Blackwell sufficient conditions forcontraction mapping, and fixed point theorem)? Stochastic? .But rewarding if one wants to know more Flexibility in modelling;Well developed numerical methods.Especially, some interesting new research 20 of 21Dynamic contract theory, e.g. Marcet & Marimon (1998), Werning(2008), Doepke (2008);Computating dynamic equilibrium, e.g. Heer & Maussner (2005), anddynamic equilibrium econometrics, e.g. Canova (2007);Stochastic models, e.g. Stachurski (2009), Dixit & Pindyck (1994).
For further reading.Klaus Wälde.Applied Intertemporal Optimization.Mimeo, University of Mainz, 2010.Nancy L. Stokey, Robert E. Lucas with Edward C. PrescottRecursive Methods in Economic Dynamics.Cambridge: Harvard University Press, 1989.21 of 21
Why dynamic programming? Lagrangian and optimal control are able to deal with most of the dynamic optimization problems, even for the cases where dynamic programming fails. However, dynamic programming has become widely used because of its appealing characteristics: Recursive feature: ex
Dec 06, 2018 · Dynamic Strategy, Dynamic Structure A Systematic Approach to Business Architecture “Dynamic Strategy, . Michael Porter dynamic capabilities vs. static capabilities David Teece “Dynamic Strategy, Dynamic Structure .
A nonlinear programming formulation is introduced to solve infinite horizon dynamic programming problems. This extends the linear approach to dynamic programming by using ideas from approximation theory to avoid inefficient discretization. Our numerical results show that this nonlinear programmin
Stochastic Programming Stochastic Dynamic Programming Conclusion : which approach should I use ? Objective and constraints Evaluating a solution Presentation Outline 1 Dealing with Uncertainty Objective and constraints Evaluating a solution 2 Stochastic Programming Stochastic Programming Approach Information Framework Toward multistage program
work/products (Beading, Candles, Carving, Food Products, Soap, Weaving, etc.) ⃝I understand that if my work contains Indigenous visual representation that it is a reflection of the Indigenous culture of my native region. ⃝To the best of my knowledge, my work/products fall within Craft Council standards and expectations with respect to
There are many dynamic probe devices in the world, such as Dynamic Cone Penetrometer (DCP), Mackin-tosh probe, Dynamic Probing Light (DPL), Dynamic Probing Medium (DPM), Dynamic Probing High (DPH), Dynamic Probing Super High (DPSH), Perth Sand Penetrometer (PSP), etc. Table 1 shows some of the dynamic probing devices and their specifications.
Hands-on Introduction to Dynamic Blocks 2 What is a Dynamic Block? A dynamic block has flexibility and intelligence. A dynamic block reference can easily be changed in a drawing while you work. You can manipulate the geometry in a dynamic b
Dynamic Programming and Optimal Control 3rd Edition, Volume II by Dimitri P. Bertsekas Massachusetts Institute of Technology Chapter 6 Approximate Dynamic Programming This is an updated version of the research-oriented Chapter 6 on Approximate Dynamic
AAT Advanced Diploma in Accounting Synoptic Assessment – SAMS – Assessment book 2 Notes for students and training providers This is a sample assessment and mark scheme which is reflective of the question types, depth of content coverage, the level of demand, duration and mark allocation of tasks that will be in the live assessment It is not designed to be used on its own to determine .
