# quant-econ Solutions: Finite Markov Chains

Solutions for 

* http://quant-econ.net/py/linear_algebra.html

* http://quant-econ.net/jl/linear_algebra.html

Thanks to Willem Hekman and Guanlong Ren for providing this solution.

## Solution to Exercise 1

We have an optimization problem:

$$ v(x) = \max_{y,u} \{ -y'Py - u'Qu \} $$

s.t.

$$ y = Ax + Bu $$

with primitives

- $P$ be a symmetric and positive semidefinite $n \times n$ matrix.

- $Q$ be a symmetric and positive semidefinite $m \times m$ matrix.

- $A$ an $n \times n$ matrix.

- $B$ an $n \times m$ matrix.


The associated Lagrangian is :

$$L = -y'Py - u'Qu + \lambda' \lbrack Ax + Bu - y \rbrack$$

### 1.

Differentiating Lagrangian equation w.r.t y and setting its derivative equal to zero yields

$$ \frac{ \partial L}{\partial y} = - (P + P') y - \lambda = - 2 P y - \lambda = 0 \:,$$
since P is symmetric.

Accordingly, the first-oder condition for maximizing L w.r.t. y implies

$$ \lambda = -2 Py \:.$$



### 2.

Differentiating Lagrangian equation w.r.t. u and setting its derivative equal to zero yields

$$ \frac{ \partial L}{\partial u} = - (Q + Q') u - B'\lambda = - 2Qu + B'\lambda = 0 \:.$$

Substituting $\lambda = -2 P y$ gives

$$ Qu + B'Py = 0 \:.$$


Substituting the linear constraint $y = Ax + Bu$ into above equation gives

$$ Qu + B'P(Ax + Bu) = 0  $$

$$ (Q + B'PB)u + B'PAx = 0 $$
which is the first-oder condition for maximizing L w.r.t. u.

Thus, the optimial choice of u must satisfy

$$ u = -(Q + B'PB)^{-1}B'PAx \:,$$

which follows from the definition of the first-oder conditions for Lagrangian equation. 


### 3.

Rewriting our problem by substituting the constraint into the objective function, we get

$$ v(x) = \max_{u} \{ -(Ax+ Bu)'P(Ax+Bu) - u'Qu \} \:.$$

Since we know the optimial choice of u satisfies $ u = -(Q + B'PB)^{-1}B'PAx $, then 

$$ v(x) =  -(Ax+ B u)'P(Ax+B u) - u'Q u  \,\,\,\, with \,\,\,\, u = -(Q + B'PB)^{-1}B'PAx $$

To evaluate the function

\begin{align}
v(x) &=  -(Ax+ B u)'P(Ax+Bu) - u'Q u \\
&= -(x'A' + u'B')P(Ax+Bu) - u'Q u \\
&= - x'A'PAx - u'B'PAx - x'A'PBu - u'B'PBu - u'Qu \\
&= - x'A'PAx - 2u'B'PAx - u'(Q + B'PB) u
\end{align}

For simplicity, denote by $S := (Q + B'PB)^{-1} B'PA$,
then $ u = -Sx$.

Regarding the second term $- 2u'B'PAx$, 

\begin{align}
- 2u'B'PAx &= -2 x'S'B'PAx  \\
& = 2 x'A'PB( Q + B'PB)^{-1} B'PAx
\end{align}
Notice that the term $(Q + B'PB)^{-1}$ is symmetic as both P and Q are symmetric.


Regarding the third term $- u'(Q + B'PB) u$,

\begin{align}
- u'(Q + B'PB) u &= - x'S' (Q + B'PB)Sx \\
&= -x'A'PB(Q + B'PB)^{-1}B'PAx
\end{align}

Hence, the summation of second and third terms is $x'A'PB(Q + B'PB)^{-1}B'PAx$.

This implies that 

\begin{align}
 v(x) &= - x'A'PAx - 2u'B'PAx - u'(Q + B'PB) u\\
 &= - x'A'PAx + x'A'PB(Q + B'PB)^{-1}B'PAx \\
 &= -x'[A'PA - A'PB(Q + B'PB)^{-1}B'PA] x
\end{align}

Therefore, the solution to the optimization problem $v(x) = -x' \tilde{P}x$ follows the above result by denoting $\tilde{P} := A'PA - A'PB(Q + B'PB)^{-1}B'PA$.



```python

```

25ac40a73becbe2bad60c6a99257d2383a8866d9
ipynb
Jupyter Notebook
linear_algebra/linear_algebra_solutions.ipynb
joelmcmurry/QuantEcon.applications
fb961d045627f4819f8a3d23674679039e93956a
BSD-3-Clause
linear_algebra/linear_algebra_solutions.ipynb
joelmcmurry/QuantEcon.applications
fb961d045627f4819f8a3d23674679039e93956a
BSD-3-Clause
linear_algebra/linear_algebra_solutions.ipynb
joelmcmurry/QuantEcon.applications
fb961d045627f4819f8a3d23674679039e93956a
BSD-3-Clause
2020-06-09T21:30:49.000Z
2020-06-09T21:30:49.000Z
Qwen/Qwen-72B
1. YES
2. YES