econometron.utils.projection

• ProjectionSolver Class from econometron.utils.projection

Overview

The ProjectionSolver class is a critical component of the econometron.models.nonlinear_dsge module, designed to solve functional equations in nonlinear Dynamic Stochastic General Equilibrium (DSGE) models using projection methods. It leverages a Chebyshev basis to approximate solutions and supports three numerical methods: collocation, Galerkin, and least squares. Below, I provide a detailed explanation of each method in the ProjectionSolver class, covering their purpose, mechanics, inputs, outputs, and mathematical foundations, ensuring all aspects are thoroughly addressed.

Purpose

The ProjectionSolver class solves functional equations of the form ( R(x, f(x), c) = 0 ), where ( f(x) ) is an unknown function approximated using Chebyshev polynomials, ( x ) is the state vector, and ( c ) represents the coefficients of the approximation. It is tailored for nonlinear DSGE models, which often involve complex, nonlinear equilibrium conditions that lack analytical solutions. The class uses projection methods to approximate the solution ( f(x) ) over a specified domain, leveraging the ChebyshevBasis class for polynomial basis construction and evaluation, and numerical solvers (nr_solve for collocation and Galerkin, minimize_qn for least squares) for optimization.

Key Concepts

• Projection Methods: These methods approximate the solution ( f(x) \approx \sum_{i} c_i \phi_i(x) ), where ( \phi_i(x) ) are basis functions (Chebyshev polynomials), and ( c_i ) are coefficients to be determined. The methods differ in how they enforce the residual ( R(x, f(x), c) = 0 ):
  • Collocation: Enforces zero residuals at specific points (nodes).
  • Galerkin: Minimizes weighted residuals over the domain using integration.
  • Least Squares: Minimizes the sum of squared residuals over a grid.
• Chebyshev Polynomials: Orthogonal polynomials defined on ([-1, 1]), used for their numerical stability and approximation properties.
• Application in DSGE Models: Solves policy functions (e.g., consumption, capital) in DSGE models by approximating them as polynomials and solving the resulting system of equations.

---

Initialization (__init__(self, order_vector, lower_bounds, upper_bounds))

• Purpose: Initializes the solver with a Chebyshev basis and sets up the optimization framework for solving functional equations.

• Parameters:

  Name	Type	Description	Default
  order_vector	array-like	Order of Chebyshev polynomials for each dimension.	None
  lower_bounds	array-like	Lower bounds of the domain for each dimension.	None
  upper_bounds	array-like	Upper bounds of the domain for each dimension.	None

• Attributes:

  • self.cheb_basis (ChebyshevBasis): Instance of ChebyshevBasis for polynomial operations.
  • self.optimizer (callable): Set to minimize_qn for least squares optimization.
  • self.n_dims (int): Number of dimensions (length of order_vector).
  • self.basis_size (int): Total number of basis functions, computed as the product of order_vector + 1.

• Mechanics:

  • Initializes the Chebyshev basis with the specified orders and domain bounds.
  • Computes the total basis size: ( \text{basis_size} = \prod_{i=1}^{\text{n_dims}} (\text{order}_i + 1) ).
  • Assigns minimize_qn as the default optimizer for the least squares method.

• Explanation:

  • The Chebyshev basis is used to represent the solution ( f(x) ) as a linear combination of polynomials.
  • The domain ([lower_bounds, upper_bounds]) defines the state space (e.g., capital, productivity in a DSGE model).
  • The basis size determines the number of coefficients to solve for, balancing accuracy and computational cost.

• Example:

  • For a 2D state space with order_vector=[3, 2], the basis size is ( (3+1) \times (2+1) = 12 ), meaning 12 coefficients are needed.

---

Method: solve_collocation(self, residual_func, initial_guess=None, maxit=5000, stopc=1e-8, verbose=False)

• Purpose: Solves the functional equation ( R(x, f(x), c) = 0 ) using the collocation method, which enforces zero residuals at Chebyshev nodes.

• Parameters:

  Name	Type	Description	Default
  residual_func	callable	Residual function ( R(x, f(x), c) ) returning residuals.	None
  initial_guess	array-like	Initial guess for coefficients (shape: basis_size).	None (zeros)
  maxit	int	Maximum iterations for Newton-Raphson solver.	5000
  stopc	float	Convergence criterion (tolerance).	1e-8
  verbose	bool	Print iteration details if True.	False

• Returns:

  • coeffs (ndarray): Chebyshev coefficients (shape: basis_size).
  • crit (ndarray): Convergence criteria (e.g., residual norms).

• Mechanics:

  • If initial_guess is None, initializes it to zeros (shape: basis_size).
  • Generates Chebyshev nodes using self.cheb_basis.funnode().
  • Creates a grid of nodes using self.cheb_basis.gridmake(nodes).
  • Defines a residual function that:
    • Evaluates the approximated function ( f(x) = \text{funeval}(coeffs, grid) ).
    • Calls residual_func(grid, f_values, coeffs) to compute residuals.
  • Uses nr_solve (Newton-Raphson solver) to find coefficients that minimize residuals.

• Mathematical Foundation:

  • The collocation method solves: [ R(x_i, f(x_i), c) = 0, \quad \text{for } x_i \text{ at Chebyshev nodes} ]
  • The solution is approximated as: [ f(x) \approx \sum_{i=1}^{\text{basis_size}} c_i \phi_i(x) ]
  • The number of nodes equals the number of coefficients, forming a square system solved via Newton-Raphson.

• Explanation:

  • The method enforces exact satisfaction of the functional equation at specific points (Chebyshev nodes), which are optimal for polynomial interpolation.
  • Suitable for DSGE models where residuals represent equilibrium conditions (e.g., Euler equations).
  • The Newton-Raphson solver iteratively updates coefficients until residuals are below stopc.

• Example:

  • For a DSGE model, residual_func might compute the Euler equation residual for a policy function ( f(x) ) (e.g., consumption as a function of capital and productivity).
  • The method returns coefficients that define the policy function over the state space.

---

Method: solve_galerkin(self, residual_func, initial_guess=None, maxit=5000, stopc=1e-8, verbose=False)

• Purpose: Solves the functional equation using the Galerkin method, which minimizes weighted residuals over the domain using Gaussian quadrature.

• Parameters:

  Name	Type	Description	Default
  residual_func	callable	Residual function ( R(x, f(x), c) ) returning residuals.	None
  initial_guess	array-like	Initial guess for coefficients (shape: basis_size).	None (zeros)
  maxit	int	Maximum iterations for Newton-Raphson solver.	5000
  stopc	float	Convergence criterion (tolerance).	1e-8
  verbose	bool	Print iteration details if True.	False

• Returns:

  • coeffs (ndarray): Chebyshev coefficients (shape: basis_size).
  • crit (ndarray): Convergence criteria.

• Mechanics:

  • Initializes initial_guess to zeros if None.
  • Uses more nodes for quadrature than the basis order (quad_nodes = order_vector + 5) for accuracy.
  • Generates Gaussian quadrature nodes and weights using self.cheb_basis.gauss_chebyshev_quadrature.
  • Creates a grid and evaluates basis functions at quadrature nodes using self.cheb_basis.funbas.
  • Defines a residual function that:
    • Evaluates ( f(x) = \text{funeval}(coeffs, grid) ).
    • Computes residuals using residual_func.
    • Calculates weighted residuals: [ \text{weighted_residuals}[i] = \sum_{\text{grid}} w \cdot R(x, f(x), c) \cdot \phi_i(x) ] where ( w ) is the Kronecker product of quadrature weights across dimensions.
  • Solves for coefficients using nr_solve.

• Mathematical Foundation:

  • The Galerkin method minimizes the projection of residuals onto the basis functions: [ \int R(x, f(x), c) \phi_i(x) w(x) dx = 0, \quad i = 1, \dots, \text{basis_size} ]
  • Approximates the integral using Gaussian quadrature: [ \sum_{j} w_j R(x_j, f(x_j), c) \phi_i(x_j) = 0 ]
  • Results in a system of basis_size equations solved via Newton-Raphson.

• Explanation:

  • The Galerkin method integrates residuals over the entire domain, weighted by the basis functions, providing a global approximation.
  • More robust than collocation for problems with smooth residuals, as it accounts for the entire domain rather than specific points.
  • The use of extra quadrature nodes ensures accurate integration.

• Example:

  • In a DSGE model, this method might solve for the value function by minimizing the expected residual across the state space, weighted by Chebyshev polynomials.

---

Method: solve_least_squares(self, residual_func, initial_guess=None, maxit=500, gtol=None, ptol=1e-7, verbose=False)

• Purpose: Solves the functional equation using the least squares method, minimizing the sum of squared residuals over a grid of points.

• Parameters:

  Name	Type	Description	Default
  residual_func	callable	Residual function ( R(x, f(x), c) ) returning residuals.	None
  initial_guess	array-like	Initial guess for coefficients (shape: basis_size).	None (zeros)
  maxit	int	Maximum iterations for Quasi-Newton solver.	500
  gtol	float	Gradient tolerance (optional).	None
  ptol	float	Parameter tolerance.	1e-7
  verbose	bool	Print iteration details if True.	False

• Returns:

  • coeffs (ndarray): Chebyshev coefficients (shape: basis_size).
  • crit (ndarray): Convergence criteria.

• Mechanics:

  • Initializes initial_guess to zeros if None.
  • Uses more nodes than the basis order (grid_nodes = order_vector + 5) to create an overdetermined system.
  • Generates Chebyshev nodes and creates a grid using self.cheb_basis.gridmake.
  • Defines an objective function: [ \text{objective}(c) = 0.5 \sum_{\text{grid}} R(x, f(x), c)^2 ] where ( f(x) = \text{funeval}(coeffs, grid) ).
  • Minimizes the objective using minimize_qn (Quasi-Newton solver).

• Mathematical Foundation:

  • The least squares method minimizes: [ \min_c \sum_{i=1}^N R(x_i, f(x_i), c)^2 ]
  • The overdetermined system (more grid points than coefficients) ensures robustness.
  • The Quasi-Newton solver optimizes the nonlinear objective function iteratively.

• Explanation:

  • Minimizes the total squared error across a grid, making it suitable for noisy or complex residuals.
  • Unlike collocation (exact at nodes) or Galerkin (weighted integrals), least squares provides a global fit by balancing errors across many points.
  • The use of minimize_qn makes it suitable for non-differentiable or complex residuals.

• Example:

  • For a DSGE model, this method might approximate the capital policy function by minimizing the squared Euler equation residuals over a dense grid.

---

Method: evaluate_solution(self, coeffs, points)

• Purpose: Evaluates the approximated solution ( f(x) ) at specified points using the computed Chebyshev coefficients.

• Parameters:

  Name	Type	Description
  coeffs	array-like	Chebyshev coefficients (shape: basis_size).
  points	ndarray	Points where to evaluate the solution (shape: (n_points, n_dims)).

• Returns:

  • values (ndarray): Solution values at the specified points (shape: (n_points,)).

• Mechanics:

  • Calls self.cheb_basis.funeval(coeffs, points) to compute: [ f(x) = \sum_{i=1}^{\text{basis_size}} c_i \phi_i(x) ]
  • Returns the evaluated values.

• Explanation:

  • Allows users to compute the solution at arbitrary points in the domain, useful for policy function evaluation or simulation in DSGE models.
  • Leverages the efficiency of the Chebyshev basis for fast evaluation.

• Example:

  • After solving for coefficients, evaluate the consumption policy at specific capital and productivity levels to simulate the DSGE model.

---

Notes

• Integration with DSGE Models:

  • The ProjectionSolver is designed for econometron.models.nonlinear_dsge, where it solves policy or value functions defined by equilibrium conditions (e.g., Euler equations, Bellman equations).
  • The residual_func typically encodes the model’s dynamics, such as utility maximization or market clearing conditions.

• Method Comparison:

  • Collocation: Fast and exact at nodes, but sensitive to node placement.
  • Galerkin: Robust for smooth problems, integrates over the domain, but computationally intensive due to quadrature.
  • Least Squares: Flexible for noisy residuals, but requires more grid points and a robust optimizer.

• Dependencies:

  • econometron.utils.solver.nr_solve: Newton-Raphson solver for collocation and Galerkin.
  • econometron.utils.optimizers.minimize_qn: Quasi-Newton optimizer for least squares.
  • econometron.utils.basis.ChebyshevBasis: Provides Chebyshev polynomial functionality (nodes, basis evaluation, quadrature).

• Numerical Stability:

  • Chebyshev polynomials are orthogonal, reducing numerical instability in high-order approximations.
  • Extra nodes in Galerkin and least squares enhance accuracy.

• Limitations:

  • Curse of Dimensionality: The basis size grows exponentially with n_dims, making high-dimensional problems computationally expensive.
  • Residual Function: The user must provide a well-defined residual_func, which requires careful implementation for DSGE models.
  • Convergence: Newton-Raphson and Quasi-Newton solvers may fail to converge for poorly conditioned problems or bad initial guesses.

---

Example Use Case

import numpy as np
from econometron.utils.projection import ProjectionSolver

# Define a simple residual function (e.g., for a DSGE model)
def residual_func(x, f_values, coeffs):
    # Example: f(x) approximates a policy function, residuals from Euler equation
    return f_values - (x[:, 0] ** 0.5)  # Dummy example: f(x) = sqrt(x_1)

# Initialize solver
order_vector = [3, 2]  # Polynomial orders for 2D state space
lower_bounds = [0.1, 0.5]
upper_bounds = [1.0, 1.5]
solver = ProjectionSolver(order_vector, lower_bounds, upper_bounds)

# Solve using collocation
coeffs, crit = solver.solve_collocation(residual_func, verbose=True)
print("Collocation Coefficients:", coeffs)

# Evaluate solution at points
points = np.array([[0.5, 1.0], [0.7, 1.2]])
values = solver.evaluate_solution(coeffs, points)
print("Solution Values:", values)

# Solve using Galerkin
coeffs_g, crit_g = solver.solve_galerkin(residual_func, verbose=True)
print("Galerkin Coefficients:", coeffs_g)

# Solve using least squares
coeffs_ls, crit_ls = solver.solve_least_squares(residual_func, verbose=True)
print("Least Squares Coefficients:", coeffs_ls)

---

Detailed Explanation of Dependencies

• ChebyshevBasis:

  • Provides methods like funnode (Chebyshev nodes), gridmake (grid construction), funbas (basis evaluation), funeval (function evaluation), and gauss_chebyshev_quadrature (quadrature nodes and weights).
  • Essential for constructing and evaluating Chebyshev polynomials.

• nr_solve:

  • Implements Newton-Raphson iteration to solve nonlinear systems in collocation and Galerkin methods.
  • Takes a residual function, initial guess, and convergence parameters.

• minimize_qn:

  • Implements a Quasi-Newton optimization algorithm for the least squares method.
  • Minimizes the sum of squared residuals, suitable for overdetermined systems.