cross_product_trick.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "a11f7f8b",
   "metadata": {},
   "source": [
    "# Eliminating Cross Products"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "262530af",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "This lecture describes formulas for eliminating\n",
    "\n",
    "- cross products between states and control in linear-quadratic dynamic programming  problems  \n",
    "- covariances between state and measurement noises in  Kalman filtering  problems  \n",
    "\n",
    "\n",
    "For a linear-quadratic dynamic programming problem, the idea involves these steps\n",
    "\n",
    "- transform  states and controls in a way that leads to an equivalent problem with no cross-products between transformed states and controls  \n",
    "- solve the transformed problem using standard formulas for problems with no cross-products between states and controls  presented in this lecture [Linear Control: Foundations](https://python.quantecon.org/lqcontrol.html)  \n",
    "- transform the optimal decision rule for the altered problem into the optimal decision rule for the original problem with cross-products between states and controls  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5bfad5cf",
   "metadata": {},
   "source": [
    "## Undiscounted Dynamic Programming Problem\n",
    "\n",
    "Here is a nonstochastic undiscounted LQ dynamic programming with cross products between\n",
    "states and controls in the objective function.\n",
    "\n",
    "The problem is defined by the 5-tuple of matrices $ (A, B, R, Q, H) $\n",
    "where  $ R $ and $ Q $ are positive definite symmetric matrices and\n",
    "$ A \\sim m \\times m, B \\sim m \\times k,  Q \\sim k \\times k, R \\sim m \\times m $ and $ H \\sim k \\times m $.\n",
    "\n",
    "The problem is to choose $ \\{x_{t+1}, u_t\\}_{t=0}^\\infty $ to maximize\n",
    "\n",
    "$$\n",
    "- \\sum_{t=0}^\\infty (x_t' R x_t + u_t' Q u_t + 2 u_t H x_t)\n",
    "$$\n",
    "\n",
    "subject to the linear constraints\n",
    "\n",
    "$$\n",
    "x_{t+1} = A x_t + B u_t,  \\quad t \\geq 0\n",
    "$$\n",
    "\n",
    "where $ x_0 $ is a given initial condition.\n",
    "\n",
    "The solution to this undiscounted infinite-horizon problem is a time-invariant feedback rule\n",
    "\n",
    "$$\n",
    "u_t  = -F x_t\n",
    "$$\n",
    "\n",
    "where\n",
    "\n",
    "$$\n",
    "F = -(Q + B'PB)^{-1} B'PA\n",
    "$$\n",
    "\n",
    "and  $ P \\sim m \\times m $ is a positive definite solution of the algebraic matrix Riccati equation\n",
    "\n",
    "$$\n",
    "P = R + A'PA - (A'PB + H')(Q + B'PB)^{-1}(B'PA + H).\n",
    "$$\n",
    "\n",
    "It can be verified that an **equivalent** problem without cross-products between states and controls\n",
    "is  defined by  a 4-tuple of matrices : $ (A^*, B, R^*, Q) $.\n",
    "\n",
    "That the omitted matrix $ H=0 $ indicates that there are no cross products between states and controls\n",
    "in the equivalent problem.\n",
    "\n",
    "The matrices $ (A^*, B, R^*, Q) $ defining the  equivalent problem and the value function, policy function matrices $ P, F^* $ that solve it are  related to the matrices $ (A, B, R, Q, H) $ defining the original problem  and the  value function, policy function matrices $ P, F $ that solve the original problem by\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "A^* & = A - B Q^{-1} H, \\\\\n",
    "R^* & = R - H'Q^{-1} H, \\\\\n",
    "P & = R^* + {A^*}' P A - ({A^*}' P B) (Q + B' P B)^{-1} B' P A^*, \\\\\n",
    "F^* & = (Q + B' P B)^{-1} B' P A^*, \\\\\n",
    "F & = F^* + Q^{-1} H.\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74ba9e38",
   "metadata": {},
   "source": [
    "## Kalman Filter\n",
    "\n",
    "The **duality** that prevails  between a linear-quadratic optimal control and a Kalman filtering problem means that there is an analogous transformation that allows us to transform a Kalman filtering problem\n",
    "with non-zero covariance matrix  between between shocks to states and shocks to measurements to an equivalent Kalman filtering problem with zero covariance between shocks to states and measurments.\n",
    "\n",
    "Let’s look at the appropriate transformations.\n",
    "\n",
    "First, let’s recall the Kalman filter with covariance between noises to states and measurements.\n",
    "\n",
    "The hidden Markov model is\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "x_{t+1} & = A x_t + B w_{t+1},  \\\\\n",
    "z_{t+1} & = D x_t + F w_{t+1},  \n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "where $ A \\sim m \\times m, B \\sim m \\times p $ and $ D \\sim k \\times m, F \\sim k \\times p $,\n",
    "and $ w_{t+1} $ is the time $ t+1 $ component of a sequence of i.i.d. $ p \\times 1 $ normally distibuted\n",
    "random vectors with mean vector zero and covariance matrix equal to a $ p \\times p $ identity matrix.\n",
    "\n",
    "Thus, $ x_t $ is $ m \\times 1 $ and $ z_t $ is $ k \\times 1 $.\n",
    "\n",
    "The Kalman  filtering formulas are\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "K(\\Sigma_t) & = (A \\Sigma_t D' + BF')(D \\Sigma_t D' + FF')^{-1}, \\\\\n",
    "\\Sigma_{t+1}&  = A \\Sigma_t A' + BB' - (A \\Sigma_t D' + BF')(D \\Sigma_t D' + FF')^{-1} (D \\Sigma_t A' + FB').\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "Define   tranformed matrices\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "A^* & = A - BF' (FF')^{-1} D, \\\\\n",
    "B^* {B^*}' & = BB' - BF' (FF')^{-1} FB'.\n",
    "\\end{align*}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2f2b27c",
   "metadata": {},
   "source": [
    "### Algorithm\n",
    "\n",
    "A consequence of  formulas {eq}`eq:Kalman102} is that we can use the following algorithm to solve Kalman filtering problems that involve  non zero covariances between state and signal noises.\n",
    "\n",
    "First, compute $ \\Sigma, K^* $ using the ordinary Kalman filtering  formula with $ BF' = 0 $, i.e.,\n",
    "with zero covariance matrix between random shocks to  states and  random shocks to measurements.\n",
    "\n",
    "That is, compute  $ K^* $ and $ \\Sigma $ that  satisfy\n",
    "\n",
    "$$\n",
    "\\begin{align*}\n",
    "K^* & = (A^* \\Sigma D')(D \\Sigma D' + FF')^{-1} \\\\\n",
    "\\Sigma & = A^* \\Sigma {A^*}' + B^* {B^*}' - (A^* \\Sigma D')(D \\Sigma D' + FF')^{-1} (D \\Sigma {A^*}').\n",
    "\\end{align*}\n",
    "$$\n",
    "\n",
    "The Kalman gain for the original problem **with non-zero covariance** between shocks to states and measurements is then\n",
    "\n",
    "$$\n",
    "K = K^* + BF' (FF')^{-1},\n",
    "$$\n",
    "\n",
    "The state reconstruction covariance matrix $ \\Sigma $ for the original problem equals the state reconstrution covariance matrix for the transformed problem."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72d8a132",
   "metadata": {},
   "source": [
    "## Duality table\n",
    "\n",
    "Here is a handy table to remember how the Kalman filter and dynamic program are related.\n",
    "\n",
    "|Dynamic Program|Kalman Filter|\n",
    "|:------------------------------------------------:|:------------------------------------------------:|\n",
    "|$ A $|$ A' $|\n",
    "|$ B $|$ D' $|\n",
    "|$ H $|$ FB' $|\n",
    "|$ Q $|$ FF' $|\n",
    "|$ R $|$ BB' $|\n",
    "|$ F $|$ K' $|\n",
    "|$ P $|$ \\Sigma $|"
   ]
  }
 ],
 "metadata": {
  "date": 1731921898.6835485,
  "filename": "cross_product_trick.md",
  "kernelspec": {
   "display_name": "Python",
   "language": "python3",
   "name": "python3"
  },
  "title": "Eliminating Cross Products"
 },
 "nbformat": 4,
 "nbformat_minor": 5
}