![]() |
Previous | Next |
[
ds,
dy,
du] = ckbs_newton_step(
mu,
s,
y,
u,
b,
d,
Bdia,
Hdia,
Hlow)
\mu
-relaxed affine constrained Kalman-Bucy smoother problem.
\mu \in \B{R}_+
,
H \in \B{R}^{p \times p}
,
d \in \B{R}^p
,
b \in \B{R}^r
, and
B \in \B{R}^{r \times p}
,
the
\mu
-relaxed affine constrained Kalman-Bucy smoother problem is:
\[
\begin{array}{rl}
{\rm minimize} & \frac{1}{2} y^\R{T} H y + d^\R{T} y
- \mu \sum_{i=1}^r \log(s_i)
\; {\rm w.r.t} \; y \in \B{R}^p \; , \; s \in \B{R}_+^r
\\
{\rm subject \; to} & s + b + B y = 0
\end{array}
\]
In addition,
H
is symmetric block tri-diagonal with each block of
size
n \times n
and
B
is block diagonal with each block of size
m \times n
(there is an integer
N
such that
p = n * N
and
r = m * N
).
u \in \B{R}^r
to denote the Lagrange multipliers corresponding to the constraint equation.
The corresponding Lagrangian is
\[
L(y, s, u) =
\frac{1}{2} y^\R{T} H y + d^\R{T} y
- \mu \sum_{i=1}^r \log(s_i)
+ u^\R{T} (s + b + B y)
\]
The partial gradients of the Lagrangian are given by
\[
\begin{array}{rcl}
\nabla_y L(y, s, u ) & = & H y + B^\R{T} u + d \\
\nabla_s L(y, s, u ) & = & u - \mu / s \\
\nabla_u L(y, s, u ) & = & s + b + B y \\
\end{array}
\]
where
\mu / s
is the component by component division of
\mu
by the components of the
s
.
Note, from the second equation, that we only need consider
u \geq 0
because
s \geq 0
.
D(s)
to denote the diagonal matrix with
s
along its diagonal and
1_r
to denote the vector, of length
r
with all its components
equal to one.
We define
F : \B{R}^{r + p + r} \rightarrow \B{R}^{r + p + r}
by
\[
F(s, y, u)
=
\left(
\begin{array}{c}
s + b + B y \\
H y + B^\R{T} u + d \\
D(s) D(u) 1_r - \mu 1_r
\end{array}
\right)
\]
The Kuhn-Tucker conditions for a solution of the
\mu
-relaxed constrained affine Kalman-Bucy smoother problem is
F(s, y, u) = 0
.
(s, y, u)
, the Newton step
( \Delta s^\R{T} , \Delta y^\R{T} , \Delta u^\R{T} )^\R{T}
solves the problem:
\[
F^{(1)} (s, y, u)
\left( \begin{array}{c} \Delta s \\ \Delta y \\ \Delta u \end{array} \right)
=
- F(s, y, u)
\]
\mu
.
r
.
All the elements of s are greater than zero.
p
r
.
All the elements of s are greater than zero.
r
.
p
m \times n \times N
array.
For
k = 1 , \ldots , N
we define
B_k \in \B{R}^{m \times n}
by
\[
B_k = Bdia(:, :, k)
\]
B
is defined by
\[
B
=
\left( \begin{array}{cccc}
B_1 & 0 & 0 & \\
0 & B_2 & 0 & 0 \\
0 & 0 & \ddots & 0 \\
& 0 & 0 & B_N
\end{array} \right)
\]
n \times n \times N
array.
For
k = 1 , \ldots , N
we define
H_k \in \B{R}^{n \times n}
by
\[
H_k = Hdia(:, :, k)
\]
n \times n \times N
array.
For
k = 1 , \ldots , N
we define
L_k \in \B{R}^{n \times n}
by
\[
L_k = Hlow(:, :, k)
\]
H
is defined by
\[
H
=
\left( \begin{array}{cccc}
H_1 & L_2^\R{T} & 0 & \\
L_2 & H_2 & L_3^\R{T} & 0 \\
0 & \ddots & \ddots & \ddots \\
& 0 & L_N & H_N
\end{array} \right)
\]
r
equal to the
\Delta s
components of the Newton step.
p
equal to the
\Delta y
components of the Newton step.
r
equal to the
\Delta u
components of the Newton step.
ckbs_newton_step
.
It returns true if ckbs_newton_step
passes the test
and false otherwise.
F
is given by
\[
F^{(1)} (s, y, u) =
\left(
\begin{array}{ccccc}
D( 1_r ) & B & 0 \\
0 & H & B^\R{T} \\
D( u ) & 0 & D(s)
\end{array}
\right)
\]
It follows that
\[
\left( \begin{array}{ccc}
D( 1_r ) & B & 0 \\
0 & H & B^\R{T} \\
D( u ) & 0 & D(s)
\end{array} \right)
\left( \begin{array}{c} \Delta s \\ \Delta y \\ \Delta u \end{array} \right)
=
-
\left( \begin{array}{c}
s + b + B y \\
H y + B^\R{T} u + d \\
D(s) D(u) 1_r - \mu 1_r
\end{array} \right)
\]
Replacing the bottom row by the bottom row minus
D(u)
times the top row,
we obtain the reduced set of equations
\[
\left( \begin{array}{cc}
H & B^\R{T} \\
-D(u) B & D(s)
\end{array} \right)
\left( \begin{array}{c} \Delta y \\ \Delta u \end{array} \right)
=
\left( \begin{array}{c}
- H y - B^\R{T} u - d \\
\mu 1_r + D(u) ( b + B y )
\end{array} \right)
\]
Replacing the top row by
H^{-1}
times the top row we obtain
\[
\left( \begin{array}{cc}
D( 1_p ) & H^{-1} B^\R{T} \\
-D(u) B & D(s)
\end{array} \right)
\left( \begin{array}{c} \Delta y \\ \Delta u \end{array} \right)
=
\left( \begin{array}{c}
- y - H^{-1}( B^\R{T} u + d ) \\
\mu 1_r + D(u) ( b + B y )
\end{array} \right)
\]
Replacing the bottom row by
the
D(u)^{-1}
times the bottom row
plus
B
times the top row,
we obtain the reduced equation
\[
\begin{array}{rcl}
[ B H^{-1} B^\R{T} + D(s / u) ] \Delta u
& = &
\mu ( 1_r / u ) + b - B H^{-1}( B^\R{T} u + d )
\end{array}
\]
Thus we obtain the following solution for the Newton step:
\[
\begin{array}{rcl}
\Delta u & = &
[ B H^{-1} B^\R{T} + D(s / u) ]^{-1}
[ \mu ( 1_r / u ) + b - B H^{-1}( B^\R{T} u + d ) ]
\\
\Delta y & = &
- y - H^{-1} [ d + B^\R{T} ( u + \Delta u ) ] \\
\\
\Delta s & = &
- s - b - B ( y + \Delta y )
\end{array}
\]
It follows from the matrix inversion lemma that
\[
[ B H^{-1} B^\R{T} + D(s / u) ]^{-1}
=
D(s/u)^{-1} - D(s/u)^{-1} B [ H + B^\R{T} D(s/u)^{-1} B ]^{-1} B^\R{T} D(s/u)^{-1}
\]