Index-> contents reference index search external Previous Next Up-> ckbs utility ckbs_kuhn_tucker ckbs-> license ckbs_t_general ckbs_nonlinear ckbs_L1_nonlinear ckbs_affine ckbs_affine_singular ckbs_L1_affine utility all_ok.m whatsnew wishlist bib utility-> ckbs_t_obj ckbs_t_grad ckbs_t_hess ckbs_diag_solve ckbs_bidiag_solve ckbs_bidiag_solve_t ckbs_blkbidiag_symm_mul ckbs_blkdiag_mul ckbs_blkdiag_mul_t ckbs_blkbidiag_mul_t ckbs_blkbidiag_mul ckbs_blktridiag_mul ckbs_sumsq_obj ckbs_L2L1_obj ckbs_sumsq_grad ckbs_process_grad ckbs_sumsq_hes ckbs_process_hes ckbs_tridiag_solve ckbs_tridiag_solve_b ckbs_tridiag_solve_pcg ckbs_newton_step ckbs_newton_step_L1 ckbs_kuhn_tucker ckbs_kuhn_tucker_L1 ckbs_kuhn_tucker-> kuhn_tucker_ok.m Headings-> Syntax Purpose Problem Lagrangian Kuhn-Tucker Residual mu s y u b d Bdia B Hdia Hlow H F Example

Compute Residual in Kuhn-Tucker Conditions

Syntax
[F] = ckbs_kuhn_tucker(
mu
syubdBdiaHdiaHlow)

Purpose
This routine computes the residual in the Kuhn-Tucker conditions for the  \mu -relaxed affine constrained Kalman-Bucy smoother problem.

Problem
Given  \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 ).

Lagrangian
We use  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 .

Kuhn-Tucker Residual
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. The Kuhn-Tucker Residual function  F : \B{R}^{r + p + r} \rightarrow \B{R}^{r + p + r} is defined 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  .

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 \B{R}^{m \times n} by  $B_k = Bdia(:, :, k)$

B
The matrix  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)$

Hdia
The argument Hdia is an  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)$

Hlow
The argument Hlow is an  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
The matrix  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)$

F
The result F is a column vector of length  r + p + r containing the value of the Kuhn-Tucker residual ; i.e.,  F(s, y, u) .

Example
The file kuhn_tucker_ok.m contains an example and test of ckbs_kuhn_tucker. It returns true if ckbs_kuhn_tucker passes the test and false otherwise.
Input File: src/ckbs_kuhn_tucker.m