Inverse discrete algebraic Riccati equation
Published:
In this blog, I want to talk about the inverse problem of discrete time algebraic Riccati equation (I-DARE), which I encountered during my work on the inverse optimal control (IOC) for LQR. IOC is to identify the objective function based on the optimal state or input trajectories. For a finite horizon discrete-time LQR problem descried as
\[\begin{aligned} & \min J= \sum_{k=0}^{N-1} (x_k^T Q x_k + u_k^T R u_k) + x_N^T H x_N\\ & s.t.~~ x_{k+1} = Ax_k + Bu_k , x_0 = \bar{x}, \end{aligned}\]the solution is the classic linear feedback controller $u_k = K_k x_k$ and the feedback gain matrix $K_k$ (time-variant in finite horizon) is calculated by DARE:
\[\begin{align} & P_{k-1} = A^TP_{k}A - A^T P_{k} B(R+ B^T P_{k}B)^{-1} B^TP_{k}A+Q \\ & K_k = (R + B^T P_{k+1} B)^{-1} B^T P_{k+1} A, \end{align}\]where $P_N = H$. $H,Q,R$ are all positive definite matrices. Riccati equations are applied in various fields like LQR and Kalman filter. There exist some interesting properties of DARE iteration. The sequence $P_{N:0} = P_N, P_{N=1}, …,P_0$ generated by (1) is proved to be monotonous and converges to its fixed point (also the solution of continuos ARE) as $N$ goes to infinity. Now we present the I-DARE problem.
I-DARE Problem: Suppose the system matrices $A,B$ are known. Given the exact sequence $K_{0:N-1}$ as the solution of DARE, can we infer the parameter matrices $H,Q,R$?
\[\hat{H},\hat{Q},\hat{R} = \textit{I-DARE}(K_{0:N-1})\]
There are two points we need to think over.
Uniqueness (scalar ambiguity) Notice that for a DARE iteration, the parameter sets $(H,Q,R)$ and $(\alpha H, \alpha Q, \alpha R)$ with scalar $\alpha \in \mathbb{R}^+$ generate the same solution sequence $K_{0:N-1}$. Thus, does the inverse problem still possess this property? Yes
Identifiability Are $(H,Q,R)$ in I-DARE problem always identifiable? No. Need some conditions
Suppose two gain matrix sequences $K_{0:N-1}, K’_{0:N-1}$ are generated with two sets of parameters ${H},{Q},{R}$ and ${H’},{Q’},{R’}$ respectively through DARE. If we have $K_k=K_k’$ for all $k$, do they satisfy ${H’} = \alpha H, {Q’} = \alpha Q, {R’}=\alpha R$ for some $\alpha \in \mathbb{R}^+$?
The derivation sketch consists of three main steps. (i) Subtract the Riccati equation for $k=i+1$ from the equation for $k=i$ and re-write the difference in the matrix form:
\[R^{-1} \widetilde{\mathcal{BA}}_i \widetilde{QH}_i \widetilde{\mathcal{A}^c}_i = R'^{-1} \widetilde{\mathcal{BA}}_i \widetilde{Q'H'}_i \widetilde{\mathcal{A}^c}_i.\](ii) Take the trace of both sides and we obtain
\[\mathrm{tr}(R^{-1} \widetilde{\mathcal{BA}}_i \widetilde{QH}_i \widetilde{\mathcal{A}^c}_i) = vec(R^{-1})^T \underbrace{(\widetilde{\mathcal{A}^c}_i^T \otimes \widetilde{\mathcal{BA}}_i)}_{\mathcal{E}_i} vec(\widetilde{QH}_i)\]and
\[(\begin{bmatrix} vec(\overline{Q})^T, vec(\overline{H})^T \end{bmatrix} \otimes vec(\overline{R^{-1}})^T) vec(\mathcal{P}_i(\mathcal{E}_i)) = (\begin{bmatrix} vec(\overline{Q'})^T, vec(\overline{H'})^T \end{bmatrix} \otimes vec(\overline{R'^{-1}})^T) vec(\mathcal{P}_i(\mathcal{E}_i)),\]where $\mathcal{P}_i(\mathcal{E}_i)$ is a $\frac{m(m+1)}{2} \times n(n+1)$ matrix.
(iii) If there exist at least $\frac{mn(n+1)(m+1)}{2}$ linearly independent vectors $vec(\mathcal{P}_i(\mathcal{E}_i))$ in the horizon $k=0,\dots, N-1$, then we can combine them as a full row rank matrix and obtain
\[vec(\overline{Q'})=\alpha \cdot vec(\overline{Q}), vec(\overline{H'}) =\alpha \cdot vec(\overline{H}), vec(\overline{R'^{-1}}) =\frac{1}{\alpha} \cdot vec(\overline{R^{-1}}).\]Here we provide the following theorem. $m,n$ are the dimension of input and state vector.
Theorem 1 If the control horizon is set as $N < \frac{mn(n+1)(m+1)}{2}$, the true weight parameters $H,Q,R$ of the control objective will never be identified accurately, which can be utilized in preserving the system’s intention.
If you are interested in IOC-LQR and this I-DARE problem, I also suggest to read H. Zhang (infer R) and C. Yu (infer Q,R).