Casting Kalman filter recursion as an SDP

Question

In finding the optimal Kalman gain one has to solve the following optimization problem.

$$\min_{K\in\mathbb{R}^{n\times m}} \mathbf{trace}\left(\left(I - KH\right)P\left(I - KH\right)^{\top} + KRK^{\top}\right)$$

where $P \in \mathbb{R}^{n\times n}, R \in \mathbb{R}^{m\times m}$ are positive definite, $I \in \mathbb{R}^{n\times n}$ is the identity matrix and $H \in \mathbb{R}^{m\times n}$ is some matrix. One can simply cast this as a quadratic program by vectorizing all the matrices involved. This can subsequently be cast as a semidefinite program (SDP). What I would like to do is to cast it as an SDP directly. I have

$$\mathbf{trace}\left(\left(I - KH\right)P\left(I - KH\right)^{\top} + KRK^{\top}\right) = \left<HPH^{\top}+R,KK^{\top}\right> - \left<2PH^{\top},K\right>$$

This does not seem to fit in the framework of SDP but I believe there is a trick to make it fit. Furthermore, I also have a constraint $KA + b \geq 0$ where $A \in \mathbb{R}^{m\times n}$ and $b \in \mathbb{R}^n$. I don't know if this makes things more complicated. I would appreciate any tips/help.

Answer 1

It is possible to cast the problem of finding the optimal Kalman gain directly as an SDP as follows. First, note that the following problem is equivalent to the original problem.

$$\min_{K \in \mathbb{R}^{n\times m},Q\in \mathbb{R}^{n\times n}} \mathbf{trace}(Q) \quad \text{s.t.}\quad Q \succcurlyeq \left(\left(I - KH\right)P\left(I - KH\right)^{\top} + KRK^{\top}\right)$$

To see why this is equivalent to the original problem suppose that $K^*,Q^*$ are a solution to the equivalent problem such that $$Q^* \neq \left(\left(I - K^*H\right)P\left(I - K^*H\right)^{\top} + K^*R(K^*)^{\top}\right)$$ But then $$\mathbf{trace}(Q^*) > \mathbf{trace}\left(\left(I - K^*H\right)P\left(I - K^*H\right)^{\top} + K^*R(K^*)^{\top}\right)$$

So now the next step is to cast this equivalent problem as an SDP. We only need Schur complement for this. Recall that $P$ and $R$ are positive definite. We can write $$Q - KRK^{\top} -\left(I - KH\right)P\left(I - KH\right)^{\top} \succcurlyeq 0 \iff \begin{bmatrix}P^{-1} & \left(I - KH\right)^{\top} \\ I - KH & Q - KRK^{\top}\end{bmatrix} \succcurlyeq 0 $$ Applying Schur complement once more we get

$$\begin{bmatrix}P^{-1} & \left(I - KH\right)^{\top} \\ I - KH & Q - KRK^{\top}\end{bmatrix} \succcurlyeq 0 \iff \begin{bmatrix}P^{-1} & \left(I - KH\right)^{\top} & 0\\ I - KH & Q &K \\ 0 & K^{\top} &R^{-1}\end{bmatrix} \succcurlyeq 0$$

Answer 2

Aposteriori Covariance = (I−KH)P(I−KH)^t+KRK^t

In the past I've seen the optimal gain derived by minimizing the whole Posteriori Covariance matrix w.r.t. K. It seems that if the whole matrix is minimized the trace will be minimized. Tip: minimize w.r.t. K treating K^t as a separate set of variables.