Solution Algorithms
Value iteration
Value function algorithms require a Bellman representation of the model:
\[s_t = {\color{red} g} \left( m_{t-1}, s_{t-1}, x_{t-1}, m_t \right)\]\[V(m_t, s_t) = \max_{\underline{x}(m_t,s_t) \leq x_t \leq \overline{x}(m_t,s_t)} {\color{red} u}\left(m_t, s_t, x_t\right) + {\color{blue} \beta} E_{m_t} V\left(m_{t+1}, s_{t+1}\right)\]
where $g$ is the transition function, $u$ the instantaneous felicity function and $\beta$ the time-discount parameter.
The solution of this problem produces naturally two functions, $x=\varphi(m,s)$ and $V=\varphi(m,s)$, for the controls and the value function respectively.
Given an initial value function $V^n(m,s)$ applying the maximum operator produces a new and improved value function $\tilde{V}^n(m,s)$ and a corresponding policy rule $x=\varphi^n(m,s)$. This is an improvement step.
Note that at this stage, $\tilde{V}^n$ is not the value of following $\varphi^n$ forever. An evaluation step performs the recursion (note the absence of a $\max$):
\[x_t=\varphi^n(m_s, s_t)\]\[s_t = {\color{red} g} \left( m_{t-1}, s_{t-1}, x_{t-1}, m_t \right)\]\[V^{n+1}_{k+1}(m_t, s_t) = {\color{red} u}\left(m_t, s_t, x_t\right) + {\color{blue} \beta} E_{m_t} V^{n+1}_{k}\left(m_{t+1}, s_{t+1}\right)\]
Starting from the initial guess, $\tilde{V}^{n+1}$, this recursion converges to the value $V^{n+1}()$ associated to $\varphi^{n+1}()$. If high accuracy is not required, it is common to restrict the number of steps to perform a partial evaluation.
The value function algorithm implemented in Dolo follows the following scheme:
Given an initial guess for the policy rule $\varphi^0()$, evaluate the corresponding value function $V^0()$.
Then given $\varphi_n$:
perform one improvement step to get $\varphi^{n+1}()$, $\tilde{V}^{n+1}()$
perform a partial evaluation of $\varphi^{n+1}()$
starting from $\tilde{V}^{n+1}()$ to get $V^{n+1}()$ using at most $K$ steps.
Compute $\eta_{n+1}=|\varphi^n-\varphi^{n+1}|$ and $\epsilon_{n+1}=|V^n-V^{n+1}|$
if $\eta_{n+1}<\tau_{\eta}$ and $\epsilon_{n+1}<\tau_{\epsilon}$, return
else return to step 2.
This algorithm is controlled by the precision parameters $\tau_{\eta}$, $\tau_{\epsilon}$ and the evaluation length $K$. Note that setting $K=0$ corresponds to the naive (but robust ?) VFI algorithm while $K$ high corresponds to Howard improvements which converge faster: convergence of the outer loop $\varphi^n$ is quadratic instead of geometric.
Dolo.value_iteration — Function.Solve for the value function and associated decision rule using value function iteration.
Arguments
model::NumericModel: Model object that describes the current model environment.pdr: Initial guess for the decision rule.
Returns
dr: Solved decision rule object.drv: Solved value function object.
Time iteration
We consider a model with the form:
\[s_t = g\left(m_{t-1}, s_{t-1}, x_{t-1}, m_t \right)\]\[0 = E_t \left[ f\left(m_t, s_{t}, x_{t}, m_{t+1}, s_{t+1}, x_{t+1} \right) \right]\]
where $g$ is the state transition function, and $f$ is the arbitrage equation.
The time iteration algorithm consists in approximating the optimal controls as a function of exogenous and endogenous controls $x_t = \varphi(m_t,s_t)$. At step $n$, the current guess for the control, $x(s_t) = \varphi^n(m_t, s_t)$, serves as the control being used next period.
Here is an outline of the algorithm:
Start with initial guess $\varphi^0$
Given current guess, find the current period's $\varphi^{n+1}(m_t,s_t)$ controls for any $(m_t,s_t)$ by solving (numerically) the arbitrage equation :
\[0 = E_t \left[ f\left(m_t, s_{t}, \varphi^{n+1}(m_t, s_t), g(s_t, \varphi^{n+1}(m_t, s_t)), \varphi^{n}(m_{t+1},g(s_t, \varphi^{n+1}(s_t))) \right) \right]\]
Compute successive approximation errors $\eta_n=|\varphi^{n+1}-\varphi^{n}|$.
if $\eta_n$ smaller thatn criterion $\epsilon_{\eta}$, return
otherwise return to step 2
Dolo.time_iteration — Function.Computes a global solution for a model via backward time iteration. The time iteration is applied to the residuals of the arbitrage equations.
If the initial guess for the decision rule is not explicitly provided, the initial guess is provided by ConstantDecisionRule. If the stochastic process for the model is not explicitly provided, the process is taken from the default provided by the model object, model.exogenous
Arguments
model::NumericModel: Model object that describes the current model environment.process: The stochastic process associated with the exogenous variables in the model.init_dr: Initial guess for the decision rule.
Returns
dr: Solved decision rule.
In some cases, the solution of the Euler equation, can be obtained faster if a direct solution for optimal controls is known as a function expectation as in the following specification:
\[s_t = g\left(m_{t-1}, s_{t-1}, x_{t-1}, m_t \right)\]\[z_t = E_t \left[ h\left(m_{t+1}, s_{t+1}, x_{t+1} \right) \right]\]\[x_t = d(m_t, s_t, z_t)\]
This information can be used by passing the solver=Dict(:type=>:direct) option to the time_iteration function, or by using the devoted function:
Dolo.time_iteration_direct — Function.Computes a global solution for a model via backward time iteration. The time iteration is applied directly to the decision rule of the model.
If the initial guess for the decision rule is not explicitly provided, the initial guess is provided by ConstantDecisionRule. If the stochastic process for the model is not explicitly provided, the process is taken from the default provided by the model object, model.exogenous.
Arguments
model::NumericModel: Model object that describes the current model environment.process: The stochastic process associated with the exogenous variables in the model.init_dr: Initial guess for the decision rule.
Returns
dr: Solved decision rule.
Improved Time iteration
Dolo.improved_time_iteration — Function.Computes a global solution for a model via backward Improved Time Iteration. The algorithm is applied to the residuals of the arbitrage equations. The idea is to solve the system G(x) = 0 as a big nonlinear system in x, where the inverted Jacobian matrix is approximated by an infinite sum (Neumann series).
If the initial guess for the decision rule is not explicitly provided, the initial guess is provided by ConstantDecisionRule. If the stochastic process for the model is not explicitly provided, the process is taken from the default provided by the model object, model.exogenous
Arguments
model::NumericModel: Model object that describes the current model environment.dprocess: The stochastic process associated with the exogenous variables in the model.init_dr: Initial guess for the decision rule.maxbstepsMaximum number of backsteps.verboseSet "true" if you would like to see the details of the infinite sum convergence.smaxitMaximum number of iterations to compute the Neumann series.complementaritiescompute_radiustraceRecord Iteration informations
Returns
sol: Improved Time Iteration results
Perfect Foresight
Consider a series for the exogenous process $(m_t)_{0 \leq t \leq T}$. The perfect foresight problem consists in finding the path of optimal controls $(x_t)_{0 \leq t \leq T}$ and corresponding states $(s_t)_{0 \leq t \leq T}$ such that:
\[s_t = g\left(m_{t-1}, s_{t-1}, x_{t-1}, m_t \right)\]\[0 = E_t \left( f\left(m_{t}, s_{t}, x_{t}, m_{t+1}, s_{t+1}, x_{t+1}\right) \right) \ \perp \ \underline{u} <= x_t <= \overline{u}\]
Special conditions apply for the initial state and controls. Initial state $s_0$ is given exogenously, or determined so that it corresponds for a steady-state corresponding to $m_0$. Final states and controls are determined by assuming the exogenous process satisfies $m_t=m_T$ for all $t\leq T$ and optimality conditions are satisfied in the last period:
.
We assume that $\underline{u}$ and $\overline{u}$ are constants. This is not a big restriction since the model can always be reformulated in order to meet that constraint, by adding more equations.
The stacked system of equations satisfied by the solution is:
Transition Arbitrage $s_0 = \overline{s_0}$ $f(m_0, s_0, x_0, m_1, s_1, x_1) \perp \underline{u} <= x_0 <= \overline{u}$ $s_1 = g(m_0, s_0, x_0, m_1)$ $f(m_1, s_1, x_1, m_2, s_2, x_2) \perp \underline{u} <= x_1 <= \overline{u}$ ... ... $s_T = g(m_{T-1}, s_{T-1}, x_{T-1}, m_T)$ $f(m_T, s_T, x_T, m_T, s_T, x_T) \perp \underline{u} <= x_T <= \overline{u}$
The system is solved using a nonlinear solver.
Dolo.perfect_foresight — Function.Document pf.
Local Analysis
Dolo.residuals — Function.residuals(model::AModel, [calib::ModelCalibration])::DictCompute the steady state residuals for the aribtrage and transition equations of model, when these functions are evaluated at the data in calib. If no calib is provided, model.calibration will be used.
See the docstring for find_deterministic_equilibrium for more information
Dolo.find_deterministic_equilibrium — Function.find_deterministic_equilibrium(model::AModel, [calib::ModelCalibration])Solve for the steady state equilibrium of model, data in cailb to fill in parameter values and provide an initial guess for the states and controls. When no calibration is passed model.calibration is used
The exogenous variables at time t-1 (m) and t (M) are set to calib[:exogenous].
The deterministic equilibrium is found by solving for vectors s and x, such that
s = transition(m, s, x, m, p)0 = arbitrage(m, s, x, m, s, x, p)
Dolo.perturb — Function.TBD