Index-> contents reference index search external Previous Next Up-> ckbs utility ckbs_kuhn_tucker_L1 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_L1-> kuhn_tucker_L1_ok.m Headings-> Syntax Purpose Problem Lagrangian Kuhn-Tucker Residual mu s y r b d Bdia B Hdia Hlow H F Example

Compute Residual in Kuhn-Tucker Conditions for Robust L1

Syntax
[F] = ckbs_kuhn_tucker_L1(       mu, s, y, r, b, d, Bdia, Hdia, Hlow,       pPlus, pMinus)

Purpose
This routine computes the residual in the Kuhn-Tucker conditions for the   \mu -relaxed affine L1 robust smoother problem.

Problem
Given   \mu \in \B{R}_+ ,   s \in \B{R}^{m \times N} ,   y \in \B{R}^{n \times N} ,   r \in \B{R}^{m \times N} ,   b \in \B{R}^{m \times N} ,   d \in \B{R}^{n \times N} ,   B \in \B{R}^{m \times n \times N} ,   H \in \B{R}^{n \times n \times N} ,   p^+ \in \B{R}^{m \times N} ,   p^- \in \B{R}^{m \times N} , the   \mu -relaxed affine L1 robust Kalman-Bucy smoother problem is:   $\begin{array}{ll} {\rm minimize} & \frac{1}{2} y^\R{T} H(x) y + d(x)^\R{T} y + \sqrt{\B{2}}^\R{T} (p^+ + p^-) -\mu \sum_{i = 1}^{mN} \log(p_i^+) - \sum_{i=1}^{mN} \mu \log(p_i^-) \;{\rm w.r.t} \; y \in \B{R}^{nN}\; , \; p^+ \in \B{R}_+^{M} \; , \; p^- \in \B{R}_+^{M} \\ {\rm subject \; to} & b(x) + B(x) y - p^+ + p^- = 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

Lagrangian
We use   r, \; s \in \B{R}^{m \times N} to denote   \mu /p^+\;,\; \mu/p^- , respectively, and we denote by   q the lagrange multiplier associated to the equality constraint. We also use   \B{1} to denote the vector of length   mN with all its components equal to one, and   \B{\sqrt{2}} to denote the vector of length   mN with all its components equal to  \sqrt{2} . The corresponding Lagrangian is   $L(p^+, p^-, y, q) = \frac{1}{2} y^\R{T} H y + d^\R{T} y + \B{\sqrt{2}}^T(p^+ + p^-) - \mu \sum_{i=1}^{mN} \log(p_i^+) - \mu\sum_{i=1}^{mN}\log(p_i^-) + q^\R{T} (b + B y - p^+ + p^-)$  The partial gradients of the Lagrangian are given by   $\begin{array}{rcl} \nabla_p^+ L(p^+, p^-, y, q ) & = & \B{\sqrt{2}} - q - r \\ \nabla_p^- L(p^+, p^-, y, q) & = & \B{\sqrt{2}} + q - s \\ \nabla_y L(p^+, p^-, y, q ) & = & H y + c + B^\R{T} q \\ \nabla_q L(p^+, p^-, y, q ) & = & b + B y - p^+ + p^- \\ \end{array}$  From the first two of the above equations, we have   q = (r - s)/2 .

Kuhn-Tucker Residual
We use   D(s) to denote the diagonal matrix with   s along its diagonal. The Kuhn-Tucker Residual function   F : \B{R}^{4mN + nN} \rightarrow \B{R}^{4mN + nN} is defined by   $F(p^+, p^-, r, s, y) = \left( \begin{array}{c} p^+ - p^- - b - B y \\ D(p^-) D(s) \B{1} - \tau \B{1} \\ r + s - 2 \B{\sqrt{2}} \\ D(p^+) D(r ) \B{1} - \tau \B{1} \\ H y + d + B^\R{T} (r - s)/2 \end{array} \right)$  The Kuhn-Tucker conditions for a solution of the   \mu -relaxed constrained affine Kalman-Bucy smoother problem is   F(p^+, p^-, r, s, y) = 0  ; see Equation (13) in Aravkin et al 2009

mu
The argument mu is a positive scalar specifying the relaxation parameter   \mu .

s
The argument s is an array of size   m \times N . All the elements of s are greater than zero.

y
The argument y is an array of size   n \times N

r
The argument r is an array of size   m \times N . All the elements of r are greater than zero.

b
The argument b is an array of size   m \times N .

d
The argument d is an array of size   n \times N .

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   4mN + nN containing the value of the ckbs_kuhn_tucker_L1 ; Kuhn-Tucker L1 residual, i.e.,   F(p^+, p^-, s^+, s^-, y) .

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