39_euler_timeiter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Foundations of Computational Economics #39\n",
    "\n",
    "by Fedor Iskhakov, ANU\n",
    "\n",
    "<img src=\"_static/img/dag3logo.png\" style=\"width:256px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Euler equation and time iterations\n",
    "\n",
    "<img src=\"_static/img/lecture.png\" style=\"width:64px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=\"_static/img/youtube.png\" style=\"width:65px;\">\n",
    "\n",
    "[https://youtu.be/AAv3aO8UJg4](https://youtu.be/AAv3aO8UJg4)\n",
    "\n",
    "Description: First order conditions and Euler equation. Time iterations solution method. Euler residuals for measuring the accuracy of solution for consumption-savings model."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### First order conditions in dynamic models with continuous choice\n",
    "\n",
    "We can write FOCs for the maximization problem in Bellman equation! Is there any use?\n",
    "\n",
    "- must be satisfied with optimal policy $ \\Rightarrow $ solution method ideas\n",
    "  - backwards induction with equation solving instead of optimization\n",
    "  - time iterations in the infinite horizon problems  \n",
    "- must be satisfied even when the problem is solved by some other method $ \\Rightarrow $ ideas of checking accuracy of numerical solutions\n",
    "  - Euler residuals accuracy check\n",
    "  - flat consumption path must be simulated with certain restrictions on parameters (Keane test)\n",
    "  - other known theoretical property of the solution must hold  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### FOCs in the consumption-savings problem (Deaton model)\n",
    "\n",
    "$$\n",
    "V(M)=\\max_{0 \\le c \\le M}\\big\\{u(c)+\\beta \\mathbb{E}_{y} V\\big(\\underset{=M'}{\\underbrace{R(M-c)+\\tilde{y}}}\\big)\\big\\}\n",
    "$$\n",
    "\n",
    "- discrete time, infinite horizon  \n",
    "- one continuous choice of consumption $ 0 \\le c \\le M $  \n",
    "- state space: consumable resources in the beginning of the period $ M $, discretized  \n",
    "- income $ \\tilde{y} $, follows log-normal distribution with $ \\mu = 0 $ and $ \\sigma $  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### First order conditions for Deaton model\n",
    "\n",
    "$$\n",
    "V(M)=\\max_{0 \\le c \\le M}\\big\\{u(c)+\\beta \\mathbb{E}_{y} V\\big(\\underset{=M'}{\\underbrace{R(M-c)+\\tilde{y}}}\\big)\\big\\}\n",
    "$$\n",
    "\n",
    "FOC:\n",
    "\n",
    "$$\n",
    "u'(c^\\star) - \\beta R \\mathbb{E}_{y} V'\\big(R(M-c^\\star)+\\tilde{y}\\big) = 0\n",
    "$$\n",
    "\n",
    "- define implicit function $ c^\\star(M) $ — *policy function*  \n",
    "- but $ V'(\\cdot) $ requires special provisions in the numerical implementation..  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Envelope theorem\n",
    "\n",
    "$$\n",
    "\\text{Let } G(M,c)=u(c)+\\beta \\mathbb{E}_{y} V\\big(\\underset{=M'}{\\underbrace{R(M-c)+\\tilde{y}}}\\big)\n",
    "$$\n",
    "\n",
    "so that the policy function $ c^\\star(M) $ satisfies $ V(M)=G(M,c^\\star(M)) $. Then\n",
    "\n",
    "$$\n",
    "V'(M) = \\tfrac{\\partial G(M,c^\\star)}{\\partial M} + \\underset{=0\\text{ by FOC}}{\\underbrace{\\tfrac{\\partial G(M,c^\\star)}{\\partial c^\\star}}} \\tfrac{\\partial c^\\star(M)}{\\partial M}\n",
    "= \\tfrac{\\partial G(M,c^\\star)}{\\partial M} = \\beta R \\mathbb{E}_{y} V'\\big(R(M-c^\\star)+\\tilde{y}\\big)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Euler equation for Deaton model\n",
    "\n",
    "$$\n",
    "\\text{(FOC)  } u'(c^\\star) = \\beta R \\mathbb{E}_{y} V'\\big(R(M-c^\\star)+\\tilde{y}\\big)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\text{(envelope theorem)  } V'(M) = \\beta R \\mathbb{E}_{y} V'\\big(R(M-c^\\star)+\\tilde{y}\\big)\n",
    "$$\n",
    "\n",
    "Thus, we have $ u'(c^\\star) = V'(M) $ in every period, and thus\n",
    "\n",
    "$$\n",
    "u'\\big(c^\\star(M)\\big) = \\beta R \\mathbb{E}_{y} u'\\big(c^\\star\\big(\\underset{=M'}{\\underbrace{R[M-c^\\star(M)]+\\tilde{y}}}\\big)\\big)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Consumption smoothing\n",
    "\n",
    "In deterministic model where $ \\tilde{y} $ is fixed, if $ \\beta R = 1 $ we have in every two consecutive periods\n",
    "\n",
    "$$\n",
    "u'\\big(c^\\star(M)\\big) = u'\\big(c^\\star(M')\\big) \\Rightarrow\n",
    "c^\\star(M) = c^\\star(M')\n",
    "$$\n",
    "\n",
    "*Perfect consumption smoothing!*\n",
    "\n",
    "This is one of the tests for the correct solution of the consumption-savings model!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Accuracy measure using Euler equation\n",
    "\n",
    "Common in the literature is to use the average squared **Euler residuals** on a dense\n",
    "grid with $ K $ points as a measure of accuracy of the solution for Deaton model\n",
    "\n",
    "$$\n",
    "ER\\big( c(M) \\big) = u'\\big(c(M)\\big) - \\beta R \\mathbb{E}_{y} u'\\big(c\\big(R[M-c(M)]+\\tilde{y}\\big)\\big)\n",
    "$$\n",
    "\n",
    "$$\n",
    "Q \\big( c(M) \\big) = \\frac{1}{K} \\sum_{k=1}^{K} {ER}^2\\big( c(M_k) \\big)\n",
    "$$\n",
    "\n",
    "The closer $ Q\\big( c(M) \\big) $ is to zero, the better the solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Time iterations\n",
    "\n",
    "The idea of this solution method is to solve the Euler equation in the space of\n",
    "policy functions $ c(M) \\in \\mathcal{P} $ as a *functional equation*\n",
    "\n",
    "$$\n",
    "u'\\big(c(M)\\big) = \\beta R \\mathbb{E}_{y} u'\\big(c[R(M-c(M))+\\tilde{y}]\\big)\n",
    "$$\n",
    "\n",
    "The solution is given by the **fixed point** of the *Coleman-Reffett operator* $ K(c)(M) $\n",
    "\n",
    "- takes as input policy function $ c(M) \\in \\mathcal{P} $  \n",
    "- returns the updated policy function $ c'(M) \\in \\mathcal{P} $ that for every $ M $ satisfies  \n",
    "\n",
    "\n",
    "$$\n",
    "u'\\big(c'(M)\\big) = \\beta R \\mathbb{E}_{y} u'\\big(c[R(M-c'(M))+\\tilde{y}]\\big)\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Contraction mapping?\n",
    "\n",
    "Is Coleman-Reffett operator a contraction mapping? **Yes** (in the reasonable metric space with a specially defined norm)\n",
    "\n",
    "📖 Huiyu Li, John Stachurski (2014, *Journal of Economic Dynamics and Control*) “Solving the income fluctuation problem with unbounded rewards”\n",
    "\n",
    "- Existence and uniqueness of the solution!  \n",
    "- Successive approximations solver will deliver the solution  \n",
    "- Globally convergent  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Time iteration algorithm\n",
    "\n",
    "1. Discretize the state space  \n",
    "1. Set the initial policy $ c_0(M) $ at state grid  \n",
    "1. Increment iteration counter $ i $ (initialize to 0)  \n",
    "1. Solve Euler equation in every point of the the grid, i.e. plug $ c_{i-1}(M) $ to the\n",
    "  RHS of the Euler equation, and solve for the $ c $ in the LHS, it becomes new $ c_i(M) $  \n",
    "1. Check for convergence in policy function space:  \n",
    "  - If converged, output $ c_i(M) $  \n",
    "  - Otherwise, return to step 3.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Accuracy and speed\n",
    "\n",
    "How does time iteration solver compares to VFI (with explicit maximization)?\n",
    "\n",
    "- theoretical complexity and convergence rates are the same  \n",
    "- policy functions are easier to interpolate (less curvature), so interpolation errors are smaller  \n",
    "- therefore time iterations usually converge faster  \n",
    "- for the same reasons time iterations deliver more accurate solution  \n",
    "\n",
    "\n",
    "Will do some experiments in the next practical video"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Further learning resources\n",
    "\n",
    "- Derivation of Euler equation in cake eating model [https://python.quantecon.org/cake_eating_problem.html](https://python.quantecon.org/cake_eating_problem.html)  \n",
    "- Time iterations on QuantEcon [https://python.quantecon.org/coleman_policy_iter.html](https://python.quantecon.org/coleman_policy_iter.html)  "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "date": 1612589586.504768,
  "download_nb": false,
  "filename": "39_euler_timeiter.rst",
  "filename_with_path": "39_euler_timeiter",
  "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 #39"
 },
 "nbformat": 4,
 "nbformat_minor": 4
}