{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Foundations of Computational Economics #37\n", "\n", "by Fedor Iskhakov, ANU\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## Dynamic programming theory and overview of solution methods\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\n", "\n", "[https://youtu.be/7Ta-zq2aXjc](https://youtu.be/7Ta-zq2aXjc)\n", "\n", "Description: Overview of dynamic programming problem formulations and solution methods. Theoretical foundations of dynamic programming in infinite horizon. Contraction mappings and fixed points." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Plan\n", "\n", "1. Classification of dynamic models \n", "1. The list of solution methods and their domains \n", "1. Contraction mappings and fixed points " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### General form of Bellman equation\n", "\n", "$$\n", "V(\\text{state}) = \\max_{\\text{decisions}} \\big[ U(\\text{state},\\text{decision}) + \\beta \\mathbb{E}\\big\\{ V(\\text{next state}) \\big| \\text{state},\\text{decision} \\big\\} \\big]\n", "$$\n", "\n", "- $ V(\\text{state}) $ is **value function** = maximum attainable (discounted) expected reward/utility/payoff \n", "- $ U(\\text{state},\\text{decision}) $ is per-period/flow/instantaneous reward/utility/payoff \n", "- (*next state*) is the *stochastic* next period state resulting from current state and decision \n", "- expectation $ \\mathbb{E}\\{\\cdot\\} $ is taken over the distribution of the next period state conditional on current state and decision \n", "- $ \\beta $ is a discount factor to measure future rewards in terms of current ones \n", "\n", "\n", "The optimal choices are revealed along the solution of the Bellman equation as decisions which solve the maximization problem in the right hand side!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Variety of problems: existence of choice\n", "\n", "Problems with no optimal choice (solved by dynamic programming)\n", "\n", "- tiling problems (video 27) \n", "- in computer science rather than economics \n", "\n", "\n", "Dynamic (or sequential) discrete/discretized choice\n", "\n", "- deal or no deal problem (video 27) \n", "- inventory management model (video 27) \n", "- Rust model of bus engine replacement (video 28, 29) \n", "- cake eating problem (video 30, 32) \n", "- consumption-savings problem (video 35) " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Variety of problems: nature of choice\n", "\n", "Problems with discrete choice\n", "\n", "- deal or no deal problem, inventory management model (video 27) \n", "- Rust model of bus engine replacement (video 28, 29) \n", "\n", "\n", "Problems with continuous choice\n", "\n", "- discretized: cake eating problem (video 30), consumption-savings models (video 35) \n", "- treated as continuous: coming up next \n", "- require interpolating of value function in Bellman equation \n", "\n", "\n", "Problems with discrete and continuous choice\n", "\n", "- much more complicated: kinks in value functions, discontinuous policy function \n", "- problems go away if choices are discretized " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### What about state space?\n", "\n", "- When choice is discrete, typically state space is also finite \n", "- Even when state variables are continuous, by discretization it is *converted* to discrete \n", "\n", "\n", "This is true in general when using numerical solvers: state space is discretized within some reasonable bounds\n", "\n", "- choice of upper bounds, number and placement of grid points influence the (accuracy of the) solution \n", "\n", "\n", "Another approach is to approximate the value function, for example, using orthogonal polynomials\n", "\n", "- only works well when value function is sufficiently smooth " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Variety of problems: continuity of time\n", "\n", "Discrete time\n", "\n", "- time periods $ t $, $ t+1 $ \n", "- dynamics given by difference equations \n", "\n", "\n", "Continuous time\n", "\n", "- all entities in the model are functions of time \n", "- dynamics given by differential equation \n", "- so, math is very different \n", "- continuous time for cleaner theoretical models, sometimes also solved numerically \n", "- *not part of this course* " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Variety of problems: horizon\n", "\n", "Finite horizon\n", "\n", "- there is terminal period $ T $ \n", "- special form of Bellman equation in period $ T $ \n", "- value function and policy function are time dependent \n", "- solved by backwards induction with $ T $ number of steps \n", "\n", "\n", "Infinite horizon\n", "\n", "- time subscripts are dropped, primes for next period values instead \n", "- solution is given by fixed point of the Bellman operator \n", "- have to actually solve a functional equation \n", "\n", "\n", "*Most problems can be specified in finite or infinite horizon*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Variety of problems: stochasticity\n", "\n", "Deterministic models\n", "\n", "- No random elements, all motion rules deterministic \n", "- No need for expectation operator in Bellman equation \n", "\n", "\n", "Stochastic models with idiosyncratic shocks (Rust model, stochastic inventory dynamics)\n", "\n", "- expectation does not have to be conditioned on current period shocks \n", "- solving the fixed point in expected value function space is beneficial \n", "\n", "\n", "General form stochastic models\n", "\n", "- expectation in Bellman equation has to be computed with quadrature or Monte Carlo integration " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Classification of dynamic models\n", "\n", "- Discrete or continuous time? \n", "- Finite or infinite horizon? \n", "- Choice space (discrete, continuous, mixed)? \n", "- State space (finite, discretized)? \n", "- Stochastic or deterministic evolution of states? " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Solving (discrete time) dynamic models\n", "\n", "Various types of dynamic models require different implementations and admit various solution methods:\n", "\n", "- Choice space (discrete, continuous, mixed)? \n", "- State space (finite, discretized)? \n", "- Stochastic or deterministic evolution of states? \n", "\n", "\n", "$ \\Rightarrow $ influence how Bellman operator is formulated and implemented numerically\n", "\n", "- Choice space (discrete, continuous, mixed)? \n", "- Finite or infinite horizon? \n", "\n", "\n", "$ \\Rightarrow $ decides which overall solution method can be applied" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solving finite horizon dynamic models\n", "\n", "1. Standard backwards induction: solving Bellman equation sequentially (video 27) \n", "1. Backwards induction using F.O.C. of Bellman maximization problem (for problems with continuous choice) \n", "1. Finite horizon version of endogenous gridpoint method (for a particular class of problems) " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solving infinite horizon dynamic models\n", "\n", "1. Value function iterations (successive approximations to solve for the fixed point of Bellman operator) (video 28-35) \n", "1. Time iterations (successive approximations to solve for the fixed point of Coleman-Reffett operator in policy function space) \n", "1. Policy iteration method (Howard’s policy improvement algorithm, iterative solution for the fixed point of Bellman operator) \n", "1. Newton-Kantorovich method (Newton solver for the fixed point of Bellman operator) \n", "1. Endogenous gridpoint method (for a particular class of problems) " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Convergence of infinite horizon solution methods\n", "\n", "- In infinite horizon all solution methods continue until convergence. \n", "- How can we be sure that the algorithm would terminate? \n", "\n", "\n", "The answer is given by the theory of contraction mappings:\n", "\n", "- Bellman operator is generally a contraction mapping \n", "- Banach theorem guarantees uniqueness of the fixed point, and \n", "- successive approximation solver is globally convergent (works with any starting point) " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Definition of contraction mapping\n", "\n", "Let\n", "- $ (S,\\rho) $ be a complete metric space\n", "- $ T: S \\rightarrow S $ denote an operator mapping $ S $ to itself\n", "\n", "$ T $ is called a *contraction* on $ S $ with modulus $ \\lambda $ if $ 0 \\le \\lambda < 1 $ and\n", "\n", "$$\n", "\\rho(Tx,Ty) \\le \\lambda \\rho(x,y) \\; \\forall x,y \\in S\n", "$$\n", "\n", "*Contraction mapping brings points in its domain “closer” to each other!*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Simple example of contraction mapping\n", "\n", "$$\n", "\\stackrel{\\nearrow}{V} \\quad\n", "\\stackrel{\\searrow}{c} \\quad\n", "\\stackrel{\\searrow}{c} \\quad\n", "\\stackrel{\\searrow}{c} \\quad\n", "\\dots\n", "$$\n", "\n", "- interest rate $ r $ \n", "- What is the value of the annuity $ V $? " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Value of annuity\n", "\n", "$$\n", "\\stackrel{\\nearrow}{V} \\quad\n", "\\stackrel{\\searrow}{c} \\quad\n", "\\stackrel{\\searrow}{c} \\quad\n", "\\stackrel{\\searrow}{c} \\quad\n", "\\dots\n", "$$\n", "\n", "$$\n", "V=\\quad\n", "\\frac{c}{(1+r)^0} + \\quad\n", "\\frac{c}{(1+r)^1} + \\quad\n", "\\frac{c}{(1+r)^2} + \\quad\n", "\\frac{c}{(1+r)^3} + \\quad\n", "\\dots\n", "$$\n", "\n", "$$\n", "\\beta = \\frac{1}{1+r}\n", "$$\n", "\n", "$$\n", "V=\\quad\n", "c + \\quad\n", "c \\beta + \\quad\n", "c \\beta^2 + \\quad\n", "c \\beta^3 + \\quad\n", "\\dots\n", "=\n", "\\sum_{t=0}^{\\infty} \\beta^t c\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Answer by the geometric series formula\n", "\n", "Assuming $ \\beta<1 $\n", "\n", "$$\n", "V = \\sum_{t=0}^{\\infty} \\beta^t c = \\frac{c}{1-\\beta}\n", "$$\n", "\n", "Can reformulate recursively (as “Bellman equation” without choice)\n", "\n", "$$\n", "V = c + \\beta ( c + \\beta c + \\beta^2 c + \\dots ) = c + \\beta V\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Contraction!\n", "\n", "$$\n", "T(V) = c + \\beta V\n", "$$\n", "\n", "$$\n", "|T(V_1) - T(V_2)| = |(c + \\beta V_1) - (c + \\beta V_2)| = \\beta | V_1 - V_2 |\n", "$$\n", "\n", "- contraction mapping under Euclidean norm \n", "- modulus $ \\beta $ " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Successive approximations\n", "\n", "1. Start with a guess $ V_0 $ \n", "1. Insert into the “Bellman equation” \n", "\n", "\n", "$$\n", "V_{i+1} = c + \\beta V_i\n", "$$\n", "\n", "1. Repeat until convergence \n", "\n", "\n", "$$\n", "||V_{i}-V_{i-1}|| \\le \\varepsilon \\text{ (small number)}\n", "$$" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "%matplotlib inline\n", "\n", "class annuity():\n", "\n", " def __init__(self,c=1,beta=.9):\n", " self.c = c # Annual payment\n", " self.beta = beta # Discount factor\n", " self.analytic = c/(1-beta) # compute analytic solution right away\n", "\n", " def bellman(self,V):\n", " '''Bellman equation'''\n", " return self.c + self.beta*V\n", "\n", " def solve(self, maxiter = 1000, tol=1e-4, verbose=False):\n", " '''Solves the model using successive approximations'''\n", " if verbose: print('{:<4} {:>15} {:>15}'.format('Iter','Value','Error'))\n", " V0=0\n", " for i in range(maxiter):\n", " V1=self.bellman(V0)\n", " if verbose: print('{:<4d} {:>15.8f} {:>15.8f}'.format(i,V1,V1-self.analytic))\n", " if abs(V1-V0) < tol:\n", " break\n", " V0=V1\n", " else: # when i went up to maxiter\n", " print('No convergence: maximum number of iterations achieved!')\n", " return V1" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Analytic solution is 217.3913043478259\n", "Numeric solution is 217.38928066546833\n" ] } ], "source": [ "a = annuity(c=10,beta=0.954)\n", "print('Analytic solution is',a.analytic)\n", "print('Numeric solution is ',a.solve())" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "hide-output": false, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iter Value Error\n", "0 10.00000000 -207.39130435\n", "1 19.54000000 -197.85130435\n", "2 28.64116000 -188.75014435\n", "3 37.32366664 -180.06763771\n", "4 45.60677797 -171.78452637\n", "5 53.50886619 -163.88243816\n", "6 61.04745834 -156.34384600\n", "7 68.23927526 -149.15202909\n", "8 75.10026860 -142.29103575\n", "9 81.64565624 -135.74564811\n", "10 87.88995605 -129.50134829\n", "11 93.84701808 -123.54428627\n", "12 99.53005524 -117.86124910\n", "13 104.95167270 -112.43963164\n", "14 110.12389576 -107.26740859\n", "15 115.05819655 -102.33310779\n", "16 119.76551951 -97.62578484\n", "17 124.25630562 -93.13499873\n", "18 128.54051556 -88.85078879\n", "19 132.62765184 -84.76365251\n", "20 136.52677986 -80.86452449\n", "21 140.24654798 -77.14475636\n", "22 143.79520678 -73.59609757\n", "23 147.18062726 -70.21067708\n", "24 150.41031841 -66.98098594\n", "25 153.49144376 -63.89986058\n", "26 156.43083735 -60.96046700\n", "27 159.23501883 -58.15628552\n", "28 161.91020797 -55.48109638\n", "29 164.46233840 -52.92896595\n", "30 166.89707083 -50.49423351\n", "31 169.21980557 -48.17149877\n", "32 171.43569452 -45.95560983\n", "33 173.54965257 -43.84165178\n", "34 175.56636855 -41.82493580\n", "35 177.49031560 -39.90098875\n", "36 179.32576108 -38.06554327\n", "37 181.07677607 -36.31452828\n", "38 182.74724437 -34.64405998\n", "39 184.34087113 -33.05043322\n", "40 185.86119106 -31.53011329\n", "41 187.31157627 -30.07972808\n", "42 188.69524376 -28.69606059\n", "43 190.01526255 -27.37604180\n", "44 191.27456047 -26.11674388\n", "45 192.47593069 -24.91537366\n", "46 193.62203788 -23.76926647\n", "47 194.71542414 -22.67588021\n", "48 195.75851463 -21.63278972\n", "49 196.75362295 -20.63768140\n", "50 197.70295630 -19.68834805\n", "51 198.60862031 -18.78268404\n", "52 199.47262377 -17.91868057\n", "53 200.29688308 -17.09442127\n", "54 201.08322646 -16.30807789\n", "55 201.83339804 -15.55790631\n", "56 202.54906173 -14.84224262\n", "57 203.23180489 -14.15949946\n", "58 203.88314187 -13.50816248\n", "59 204.50451734 -12.88678701\n", "60 205.09730954 -12.29399481\n", "61 205.66283330 -11.72847104\n", "62 206.20234297 -11.18896138\n", "63 206.71703520 -10.67426915\n", "64 207.20805158 -10.18325277\n", "65 207.67648120 -9.71482314\n", "66 208.12336307 -9.26794128\n", "67 208.54968837 -8.84161598\n", "68 208.95640270 -8.43490165\n", "69 209.34440818 -8.04689617\n", "70 209.71456540 -7.67673895\n", "71 210.06769539 -7.32360895\n", "72 210.40458141 -6.98672294\n", "73 210.72597066 -6.66533369\n", "74 211.03257601 -6.35872834\n", "75 211.32507751 -6.06622683\n", "76 211.60412395 -5.78718040\n", "77 211.87033425 -5.52097010\n", "78 212.12429887 -5.26700548\n", "79 212.36658112 -5.02472322\n", "80 212.59771839 -4.79358596\n", "81 212.81822335 -4.57308100\n", "82 213.02858507 -4.36271928\n", "83 213.22927016 -4.16203419\n", "84 213.42072373 -3.97058062\n", "85 213.60337044 -3.78793391\n", "86 213.77761540 -3.61368895\n", "87 213.94384509 -3.44745926\n", "88 214.10242822 -3.28887613\n", "89 214.25371652 -3.13758783\n", "90 214.39804556 -2.99325879\n", "91 214.53573546 -2.85556888\n", "92 214.66709163 -2.72421272\n", "93 214.79240542 -2.59889893\n", "94 214.91195477 -2.47934958\n", "95 215.02600485 -2.36529950\n", "96 215.13480863 -2.25649572\n", "97 215.23860743 -2.15269692\n", "98 215.33763149 -2.05367286\n", "99 215.43210044 -1.95920391\n", "100 215.52222382 -1.86908053\n", "101 215.60820152 -1.78310283\n", "102 215.69022425 -1.70108010\n", "103 215.76847394 -1.62283041\n", "104 215.84312414 -1.54818021\n", "105 215.91434043 -1.47696392\n", "106 215.98228077 -1.40902358\n", "107 216.04709585 -1.34420850\n", "108 216.10892944 -1.28237491\n", "109 216.16791869 -1.22338566\n", "110 216.22419443 -1.16710992\n", "111 216.27788148 -1.11342286\n", "112 216.32909894 -1.06220541\n", "113 216.37796038 -1.01334396\n", "114 216.42457421 -0.96673014\n", "115 216.46904379 -0.92226055\n", "116 216.51146778 -0.87983657\n", "117 216.55194026 -0.83936409\n", "118 216.59055101 -0.80075334\n", "119 216.62738566 -0.76391869\n", "120 216.66252592 -0.72877843\n", "121 216.69604973 -0.69525462\n", "122 216.72803144 -0.66327291\n", "123 216.75854200 -0.63276235\n", "124 216.78764906 -0.60365528\n", "125 216.81541721 -0.57588714\n", "126 216.84190802 -0.54939633\n", "127 216.86718025 -0.52412410\n", "128 216.89128996 -0.50001439\n", "129 216.91429062 -0.47701373\n", "130 216.93623325 -0.45507110\n", "131 216.95716652 -0.43413783\n", "132 216.97713686 -0.41416749\n", "133 216.99618856 -0.39511578\n", "134 217.01436389 -0.37694046\n", "135 217.03170315 -0.35960120\n", "136 217.04824481 -0.34305954\n", "137 217.06402555 -0.32727880\n", "138 217.07908037 -0.31222398\n", "139 217.09344267 -0.29786167\n", "140 217.10714431 -0.28416004\n", "141 217.12021567 -0.27108868\n", "142 217.13268575 -0.25861860\n", "143 217.14458221 -0.24672214\n", "144 217.15593142 -0.23537292\n", "145 217.16675858 -0.22454577\n", "146 217.17708768 -0.21421666\n", "147 217.18694165 -0.20436270\n", "148 217.19634234 -0.19496201\n", "149 217.20531059 -0.18599376\n", "150 217.21386630 -0.17743805\n", "151 217.22202845 -0.16927590\n", "152 217.22981514 -0.16148921\n", "153 217.23724365 -0.15406070\n", "154 217.24433044 -0.14697391\n", "155 217.25109124 -0.14021311\n", "156 217.25754104 -0.13376331\n", "157 217.26369415 -0.12761019\n", "158 217.26956422 -0.12174013\n", "159 217.27516427 -0.11614008\n", "160 217.28050671 -0.11079764\n", "161 217.28560340 -0.10570095\n", "162 217.29046565 -0.10083870\n", "163 217.29510423 -0.09620012\n", "164 217.29952943 -0.09177492\n", "165 217.30375108 -0.08755327\n", "166 217.30777853 -0.08352582\n", "167 217.31162072 -0.07968363\n", "168 217.31528616 -0.07601818\n", "169 217.31878300 -0.07252135\n", "170 217.32211898 -0.06918537\n", "171 217.32530151 -0.06600284\n", "172 217.32833764 -0.06296671\n", "173 217.33123411 -0.06007024\n", "174 217.33399734 -0.05730701\n", "175 217.33663346 -0.05467089\n", "176 217.33914832 -0.05215603\n", "177 217.34154750 -0.04975685\n", "178 217.34383631 -0.04746803\n", "179 217.34601984 -0.04528450\n", "180 217.34810293 -0.04320142\n", "181 217.35009020 -0.04121415\n", "182 217.35198605 -0.03931830\n", "183 217.35379469 -0.03750966\n", "184 217.35552013 -0.03578421\n", "185 217.35716621 -0.03413814\n", "186 217.35873656 -0.03256779\n", "187 217.36023468 -0.03106967\n", "188 217.36166388 -0.02964046\n", "189 217.36302735 -0.02827700\n", "190 217.36432809 -0.02697626\n", "191 217.36556900 -0.02573535\n", "192 217.36675282 -0.02455153\n", "193 217.36788219 -0.02342216\n", "194 217.36895961 -0.02234474\n", "195 217.36998747 -0.02131688\n", "196 217.37096805 -0.02033630\n", "197 217.37190352 -0.01940083\n", "198 217.37279595 -0.01850839\n", "199 217.37364734 -0.01765701\n", "200 217.37445956 -0.01684479\n", "201 217.37523442 -0.01606993\n", "202 217.37597364 -0.01533071\n", "203 217.37667885 -0.01462550\n", "204 217.37735162 -0.01395272\n", "205 217.37799345 -0.01331090\n", "206 217.37860575 -0.01269860\n", "207 217.37918989 -0.01211446\n", "208 217.37974715 -0.01155720\n", "209 217.38027878 -0.01102557\n", "210 217.38078596 -0.01051839\n", "211 217.38126980 -0.01003454\n", "212 217.38173139 -0.00957295\n", "213 217.38217175 -0.00913260\n", "214 217.38259185 -0.00871250\n", "215 217.38299262 -0.00831172\n", "216 217.38337496 -0.00792938\n", "217 217.38373971 -0.00756463\n", "218 217.38408769 -0.00721666\n", "219 217.38441965 -0.00688469\n", "220 217.38473635 -0.00656800\n", "221 217.38503848 -0.00626587\n", "222 217.38532671 -0.00597764\n", "223 217.38560168 -0.00570267\n", "224 217.38586400 -0.00544035\n", "225 217.38611426 -0.00519009\n", "226 217.38635300 -0.00495135\n", "227 217.38658076 -0.00472358\n", "228 217.38679805 -0.00450630\n", "229 217.38700534 -0.00429901\n", "230 217.38720309 -0.00410125\n", "231 217.38739175 -0.00391260\n", "232 217.38757173 -0.00373262\n", "233 217.38774343 -0.00356092\n", "234 217.38790723 -0.00339711\n", "235 217.38806350 -0.00324085\n", "236 217.38821258 -0.00309177\n", "237 217.38835480 -0.00294955\n", "238 217.38849048 -0.00281387\n", "239 217.38861992 -0.00268443\n", "240 217.38874340 -0.00256095\n", "241 217.38886121 -0.00244314\n", "242 217.38897359 -0.00233076\n", "243 217.38908080 -0.00222354\n", "244 217.38918309 -0.00212126\n", "245 217.38928067 -0.00202368\n" ] }, { "data": { "text/plain": [ "217.38928066546833" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a.solve(verbose=True)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Banach contraction mapping theorem (fixed point theorem)\n", "\n", "Let $ (S,\\rho) $ be a complete metric space with a contraction mapping $ T: S \\rightarrow S $.\n", "Then\n", "\n", "1. $ T $ admits a unique fixed-point $ V^{\\star} \\in S $, i.e. $ T(V^{\\star}) = V^{\\star} $. \n", "1. $ V^{\\star} $ can be found by repeated application of the operator $ T $, i.e. $ T^n(V) \\rightarrow V^{\\star} $ as $ n\\rightarrow \\infty $. \n", "\n", "\n", "*In other words, the fixed point can be found by successive approximations from any starting point* $ \\rightarrow $ *VFI method follows*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### What about Bellman operator?\n", "\n", "$$\n", "T(V)(\\text{state}) = \\max_{\\text{decisions}} \\big[ U(\\text{state},\\text{decision}) + \\beta \\mathbb{E}\\big\\{ V(\\text{next state}) \\big| \\text{state},\\text{decision} \\big\\} \\big]\n", "$$\n", "\n", "- Bellman operator $ T: U \\rightarrow U $ from functional space $ U $ to itself \n", "- metric space $ (U,d_{\\infty}) $ with uniform/infinity/sup norm (max abs distance between functions over their domain) " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Blackwell sufficient conditions for contraction\n", "\n", "Let $ X \\subseteq \\mathbb{R}^n $ and $ B(x) $ be the space of bounded functions $ f: X \\rightarrow \\mathbb{R} $ defined on $ X $.\n", "Suppose that $ T: B(X) \\rightarrow B(X) $ is an operator satisfying the following conditions:\n", "\n", "1. (monotonicity) For any $ f,g \\in B(X) $ and $ f(x) \\le g(x) $ for all $ x\\in X $ implies $ T(f)(x) \\le T(g)(x) $ for all $ x\\in X $, \n", "1. (discounting) There exists $ \\beta \\in (0,1) $ such that \n", "\n", "\n", "$$\n", "T(f+a)(x) \\le T(f)(x) + \\beta a, \\text{ for all } f\\in B(X), a \\ge 0, x\\in X,\n", "$$\n", "\n", "Then $ T $ is a contraction mapping with modulus $ \\beta $." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Bellman operator is contraction mapping by Blackwell condition\n", "\n", "- Monotonicity of Bellman equation follows trivially due to maximization in $ T(V)(x) $ \n", "- Discounting: satisfied by elementary argument when $ \\beta<1 $ \n", "\n", "\n", "Under additional boundedness conditions, **Bellman operator is a contraction mapping** by Blackwell sufficient conditions\n", "\n", "$ \\Rightarrow $\n", "\n", "- unique solution \n", "- VFI algorithm is globally convergent \n", "- does not depend on the numerical implementation of the Bellman operator " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Examples of other contraction mappings\n", "\n", "- All successive approximation examples (video 22) \n", "- Markov chain stationary distributions \n", "- Platform market equilibrium model \n", "- Bellman operators in all infinite horizon models we have considered " ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Why do we need other solution algorithms?\n", "\n", "Although VFI is guaranteed to find the solution, it may be very inefficient when modulus of contraction (discount factor $ \\beta $) is close to one.\n", "\n", "- Time iterations algorithm (sequentially solving F.O.C.) have the same linear convergence \n", "- Newton-based method converge quadratically, but are not globally convergent, have to be initialized at their domain of attraction \n", "\n", "\n", "Polyalgorithm would be a good idea!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "#### Further learning resources\n", "\n", "- Banach spaces crash course [https://www.youtube.com/watch?v=yDdxFBcvSGw&list=PLBh2i93oe2qsGKDOsuVVw-OCAfprrnGfr&ab_channel=TheBrightSideOfMathematics](https://www.youtube.com/watch?v=yDdxFBcvSGw&list=PLBh2i93oe2qsGKDOsuVVw-OCAfprrnGfr&ab_channel=TheBrightSideOfMathematics) \n", "- Fixed points around us [https://www.youtube.com/watch?v=csInNn6pfT4&ab_channel=Vsauce](https://www.youtube.com/watch?v=csInNn6pfT4&ab_channel=Vsauce) " ] } ], "metadata": { "celltoolbar": "Slideshow", "date": 1612589586.4162061, "download_nb": false, "filename": "37_dp_theory.rst", "filename_with_path": "37_dp_theory", "kernelspec": { "display_name": "Python", "language": "python3", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.6" }, "title": "Foundations of Computational Economics #37" }, "nbformat": 4, "nbformat_minor": 4 }