Previous Next

Affine Constrained Kalman Bucy Smoother Newton Step

Syntax
[dsdydu] = ckbs_newton_step(musyubdBdiaHdiaHlow)

Purpose
This routine computes one step of Newton's method for solving the non-linear Kuhn-Tucker conditions for the  \mu -relaxed affine constrained Kalman-Bucy smoother problem.

Problem
Given  \mu \in \R_+ ,  H \in \R^{p \times p} ,  d \in \R^p ,  b \in \R^r , and  B \in \R^{r \times p} , the  \mu -relaxed affine constrained Kalman-Bucy smoother problem is:  \[
\begin{array}{rl}
{\rm minimize} & \frac{1}{2} y^\T H y + d^\T y
- \mu \sum_{i=1}^r \log(s_i)
\; {\rm w.r.t} \; y \in \R^p \; , \; s \in \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 ).

Lagrangian
We use  u \in \R^r to denote the Lagrange multipliers corresponding to the constraint equation. The corresponding Lagrangian is  \[
L(y, s, u)  =
\frac{1}{2} y^\T H y + d^\T y
- \mu \sum_{i=1}^r \log(s_i)
+ u^\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^\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 .

Kuhn-Tucker Conditions
We use  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 : \R^{r + p + r} \rightarrow \R^{r + p + r} by  \[
F(s, y, u)
=
\left(
\begin{array}{c}
s + b + B y       \\
H y + B^\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  .

Newton Step
Given a value for  (s, y, u) , the Newton step  ( \Delta s^\T , \Delta y^\T , \Delta u^\T )^\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
The argument mu is a positive scalar specifying the relaxation parameter  \mu .

s
The argument s is a column vector of length  r . All the elements of s are greater than zero.

y
The argument y is a column vector of length  p

u
The argument u is a column vector of length  r . All the elements of s are greater than zero.

b
The argument b is a column vector of length  r .

d
The argument d is a column vector of length  p

Bdia
The argument Bdia is an  m \times n \times N array. For  k = 1 , \ldots , N we define  B_k \in \R^{m \times n} by  \[
     B_k = Bdia(:, :, k)
\] 


B
The matrix  B is defined by  \[

=
\left( \begin{array}{cccc}
B_1 & 0      & 0      &           \\
0   & B_2    & 0      & 0         \\
0   & 0      & \ddots & 0         \\
    & 0      & 0      & B_N 
\end{array} \right)
\] 


Hdia
The argument Hdia is an  n \times n \times N array. For  k = 1 , \ldots , N we define  H_k \in \R^{n \times n} by  \[
     H_k = Hdia(:, :, k)
\] 


Hlow
The argument Hlow is an  n \times n \times N array. For  k = 1 , \ldots , N we define  L_k \in \R^{n \times n} by  \[
     L_k = Hlow(:, :, k)
\] 


H
The matrix  H is defined by  \[

=
\left( \begin{array}{cccc}
H_1 & L_2^\T & 0      &           \\
L_2 & H_2    & L_3^\T & 0         \\
0   & \ddots & \ddots & \ddots    \\
    & 0      & L_N    & H_N 
\end{array} \right)
\] 


ds
The result ds is a column vector of length  r equal to the  \Delta s components of the Newton step.

dy
The result dy is a column vector of length  p equal to the  \Delta y components of the Newton step.

du
The result du is a column vector of length  r equal to the  \Delta u components of the Newton step.

Example
The file newton_step_ok.m contains an example and test of ckbs_newton_step. It returns true if ckbs_newton_step passes the test and false otherwise.

Method
The derivative of  F is given by  \[
F^{(1)} (s, y, u) =
\left(
\begin{array}{ccccc}
D( 1_r ) & B   & 0    \\
0        & H   & B^\T  \\
D( u )   & 0   & D(s)
\end{array}
\right)
\] 
It follows that  \[
\left( \begin{array}{ccc}
D( 1_r ) & B   & 0    \\
0        & H   & B^\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^\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^\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^\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^\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^\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^\T + D(s / u) ] \Delta u 
& = &
\mu ( 1_r / u ) + b - B H^{-1}( B^\T u + d ) 
\end{array}
\] 
Thus we obtain the following solution for the Newton step:  \[
\begin{array}{rcl}
\Delta u & = & 
     [ B H^{-1} B^\T + D(s / u) ]^{-1} 
          [ \mu ( 1_r / u ) + b - B H^{-1}( B^\T u + d ) ]
\\
\Delta y & = &
- y - H^{-1} [ d + B^\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^\T + D(s / u) ]^{-1} 

D(s/u)^{-1} - D(s/u)^{-1} B [ H + B^\T D(s/u)^{-1} B ]^{-1} B^\T D(s/u)^{-1}
\] 

Input File: src/ckbs_newton_step.m