---
abstract: 'In this paper, we consider the inverse optimal control problem for the discrete-time linear quadratic regulator, over finite-time horizons. Given observations of the optimal trajectories, and optimal control inputs, to a linear time-invariant system, the goal is to infer the parameters that define the quadratic cost function. The well-posedness of the inverse optimal control problem is first justified. In the noiseless case, when these observations are exact, we analyze the identifiability of the problem and provide sufficient conditions for uniqueness of the solution. In the noisy case, when the observations are corrupted by additive zero-mean noise, we formulate the problem as an optimization problem and prove the statistical consistency of the problem later. The performance of the proposed method is illustrated through numerical examples.'
address:
- 'Department of Mathematics, KTH Royal Institute of Technology, SE-100 44, Stockholm, Sweden'
- 'Department of Information Technology, Uppsala University, Uppsala, Sweden'
author:
- Han Zhang
- Jack Umenberger
- Xiaoming Hu
bibliography:
- 'ref.bib'
title: 'Inverse Quadratic Optimal Control for Discrete-Time Linear Systems'
---

,

,

,

Inverse optimal control, Linear Quadratic Regulator

Introduction
============

Problem Formulation and Well-Posedness {#sec:well-poseness}
======================================

The “forward" optimal LQ problem reads $$\begin{aligned}
&\min_{x_{1:N},u_{1:N-1}} J = x_N^TSx_N+{\sum}_{t=1}^{N-1} \left(u_t^TRu_t+x_t^T Qx_t\right)\label{eq:opt_ctrl_pro_fin_t}\\
&\mbox{s.t. }x_{t+1} = Ax_t+Bu_t,\quad x_1=\bar{x},\label{eq:lti}\end{aligned}$$ where $S,Q$ are $n$-dimensional positive semidefinite matrices, $R$ is $m$-dimensional positive definite matrix, $x_t\in\mathbb{R}^n$ and $u_t\in\mathbb{R}^m$. The inverse optimal control problem aims to find $(S,Q,R)$ given $(A,B)$, the initial value $x_1=\bar{x}$ and (possibly noisy) observations of the optimal trajectory $x_{2:N}^*$ or control input $u_{1:N-1}^*$. For simplicity, in this paper, we consider the case of $R=I$ and $S=0$. In addition, it is assumed that $(A,B)$ is controllable and $B$ has full column rank. Moreover, we assume that $A$ is invertible. To see that the assumption is reasonable, consider a discrete-time system sampled from a continuous linear system $\dot{x}=\hat{A}x+\hat{B}u$, where the sample period $\Delta t$ is small. Hence for the discretized linear system, we have $A=e^{\hat{A}\Delta t}$, $B=\int_0^{\Delta t}e^{\hat{A}\tau}\hat{B}d\tau$. It is clear that $A=e^{\hat{A}\Delta t}$ is invertible.

Before moving on considering how to solve the inverse optimal control problem, we would like to justify the well-posedness of it. The fundamental question for well-posedness that remains to be anwered is that: does there exist two different $Q$’s such that they can generate the same closed-loop LQR system? If there exists two different $Q$’s that can generate the same closed-loop system matrix, then the problem is obviously ill-posed. Before continuing, we would like to present the following lemma first.

\[lem:A\_cl\_invertible\] If $A\in\mathbb{R}^{n\times n}$ is invertible and $\mathscr{S}\in\mathbb{S}^n_+$, then the matrix $A-B(B^T\mathscr{S}B+I)^{-1}B^T\mathscr{S}A$ is invertible, for all $B\in\mathbb{R}^{n\times m}$.

Consider the matrix $$\begin{aligned}
    H=
    \begin{bmatrix}
        I &B\\B^T\mathscr{S} &B^T\mathscr{S}B+I
    \end{bmatrix}.\end{aligned}$$ Note that $H$ is invertible since $\det(H)=\det(I)\det(H\backslash I)=\det(B^T\mathscr{S}B+I-B^T\mathscr{S}B)=1$. Moreover, note that $\det(H)=1=\det(B^T\mathscr{S}B+I)\det\left(H\backslash (B^T\mathscr{S}B+I)\right)$ and $B^T\mathscr{S}B+I$ is invertible since $\mathscr{S}\in\mathbb{S}^n_+$. This implies that $\det(H\backslash (B^T\mathscr{S}B+I))=I-B(B^T\mathscr{S}B+I)^{-1}B^T\mathscr{S}\neq 0$, which means that $H\backslash (B^T\mathscr{S}B+I)$ is invertible. Since $A-B(B^T\mathscr{S}B+I)^{-1}B^T\mathscr{S}A=\left(H\backslash (B^T\mathscr{S}B+I)\right)A$ and $A$ is invertible, the statement follows.

Now we are ready to justify the well-posedness of the inverse LQR optimal control problem.

\[thm:well\_poseness\] Given the closed-loop system matrices $A_{cl}(1:N-1)$ and $N\geq n+2$, the $Q$ that is used to generate the closed-loop system matrices is unique.

We know that $$\begin{aligned}
K_t=-(B^TP_{t+1}B+I)^{-1}B^TP_{t+1}A,
\label{eq:K_t}\end{aligned}$$ where $P_{2:N}\succeq 0$ is the solution to the discrete-time Riccati Equation (DRE) $$\begin{aligned}
&P_t=A^TP_{t+1}A+Q-\\
&\quad A^TP_{t+1}B(B^TP_{t+1}B+I)^{-1}B^TP_{t+1}A,t=1:N-1\\
&P_N=0.
\end{aligned}
\label{eq:discrete_riccati_eq}$$ Now assume both $Q,Q^\prime\succeq 0$ generates the closed-loop system matrices $A_{cl}(1:N-1)$. Then there are $P_{2:N}^\prime$ together with $Q^\prime$ that satisfy the DRE . Denote $Q^\prime=Q+\Delta Q$, $P_t^\prime=P_t+\Delta P_t,t=2:N$, where $\Delta Q,\Delta P_{2:N}\in\mathbb{S}^n$.

First, it is worth noticing that note that if the closed-loop systems are the same, then the control gain matrix must be the same. This is because $A+BK_t=A+BK_t^\prime\Leftrightarrow BK_t=BK_t^\prime\Rightarrow (B^TB)K_t=(B^TB)K_t^\prime$ and since $B$ has full column rank, $B^TB$ is invertible and hence $K_t=K_t^\prime$. It follows from that $$\begin{aligned}
&(B^TP_{t+1}B+I)K_t=-B^TP_{t+1}A\\
\Leftrightarrow&B^TP_{t+1}(A+BK_t)=-K_t,\quad t=1:N-1.\end{aligned}$$ Recall $A_{cl}(t)=A+BK_t=A-B(B^TP_{t+1}B+I)^{-1}B^TP_{t+1}A$ and $P_{t+1}\in\mathbb{S}^n_+$ for all $t=1:N-1$. Note that $A_{cl}(t)=A+BK_t$ is invertible for all $t=1:N-1$. To see that, consider the determinant of $A_{cl}(t)$: $$\begin{aligned}
&\det\left(A_{cl}(t)\right)=\det(A-B(B^TP_{t+1}B+I)^{-1}B^TP_{t+1}A)\\
&=\det(I-B(B^TP_{t+1}B+I)^{-1}B^TP_{t+1})\det(A)\end{aligned}$$ By Sylvester’s determinant theorem, it follows that $$\begin{aligned}
&\det\left(A_{cl}(t)\right)\\
&=\det(I-B^TP_{t+1}B(B^TP_{t+1}B+I)^{-1})\det(A)\\
&=\det\left((B^TP_{t+1}B+I)-B^TP_{t+1}B\right)\\
&\times\det\left[(B^TP_{t+1}B+I)^{-1}\right]\det(A)\\
&=\det(A)/\det(B^TP_{t+1}B+I)\neq 0,\quad t=1:N-1,\end{aligned}$$ since $A$ is invertible. Therefore $B^TP_{t+1}=-K_tA_{cl}^{-1}(t),t=1:N-1$. Since $Q^\prime$ generate the same $A_{cl}(1:N-1)$, it also holds that $B^TP_{t+1}^\prime=-K_tA_{cl}^{-1}(t),t=1:N-1$ and hence $$\begin{aligned}
B^T\Delta P_t=0,t=2:N.\label{eq:B^T_delta_P_t}\end{aligned}$$

Moreover, recall that $P_{2:N}^\prime$ and $Q^\prime$ satisfy the DRE and $Q^\prime=Q+\Delta Q$, $P_t^\prime=P_t+\Delta P_t$. The DRE for $Q^\prime$ and $P_{2:N}^\prime$ reads $$\begin{aligned}
&P_{t}+\Delta P_t=A^T(P_{t+1}+\Delta P_{t+1})A+(Q+\Delta Q)\\
&-A^T(P_{t+1}+\Delta P_{t+1})B\left[B^T(P_{t+1}+\Delta P_{t+1})B+I\right]^{-1}\\
&\times B^T(P_{t+1}+\Delta P_{t+1})A=0,\quad P_N+\Delta P_N=0.\end{aligned}$$ By , it follows from the above equation that $$\begin{aligned}
&A^T\Delta P_{t+1}A-\Delta P_t+\Delta Q=0,\quad t=2:N-1,\\
&\Delta P_N=0.
\end{aligned}
\label{eq:necessary_cond_for_uniqueness}$$ By examining the recursion , utilizing the fact $A$ is invertible and , we know that $$\begin{aligned}
&\Delta P_{N-1}=\Delta Q, \quad B^T\Delta P_{N-1}=B^T\Delta Q=0,\label{eq:delta_Q=0(1)}\\
&\Delta P_{N-2}=A^T\Delta P_{N-1}A+\Delta Q, \nonumber\\
& B^T\Delta P_{N-2}=B^TA^T\Delta QA+B^T\Delta Q=B^TA^T\Delta QA=0,\nonumber\\
& \implies B^TA^T\Delta Q=0,\end{aligned}$$ $$\begin{aligned}
&\Delta P_{N-3}=A^T\Delta P_{N-2}A+\Delta Q\nonumber\\
&=(A^T)^2\Delta QA^2+A^T\Delta QA+\Delta Q,\nonumber\\
&B^T\Delta P_{N-3}=B^T(A^T)^2\Delta QA^2+\underbrace{B^TA^T\Delta QA+B^T\Delta Q}_{=0}\nonumber\\
&=B^T(A^T)^2\Delta Q A^2=0\implies B^T(A^T)^2\Delta Q=0\label{eq:delta_Q=0(2)}\\
&\qquad\qquad\qquad\qquad \vdots\nonumber\\
&\Delta P_2=A^T\Delta P_3A+\Delta Q\nonumber\\
&=(A^T)^{N-3}\Delta QA^{N-3}+\cdots A^T\Delta QA+\Delta Q,\nonumber\end{aligned}$$ $$\begin{aligned}
&B^TP_2=B^T(A^T)^{N-3}\Delta QA^{N-3}\nonumber\\
&+\underbrace{B^T\left((A^T)^{N-4}\Delta QA^{N-4}+\cdots A^T\Delta QA+\Delta Q\right)}_{=0}\nonumber\\
&=B^T(A^T)^{N-3}\Delta QA^{N-3}=0\implies B^T(A^T)^{N-3}\Delta Q=0.\label{eq:delta_Q=0(3)}\end{aligned}$$ Stacking - together, we get $$\begin{aligned}
\underbrace{\begin{bmatrix}
B^T\\B^TA^T\\\vdots\\B^T(A^T)^{N-3}
\end{bmatrix}}_{\tilde{\Gamma}}\Delta Q=0\end{aligned}$$ Since $(A,B)$ is controllable and $N\ge n+2$, $\tilde{\Gamma}$ has full column rank and hence $\Delta Q=0$. Thus the statement follows.

Inverse Optimal Control in the Noiseless Case {#sec:noiseless}
=============================================

After justifying the well-posedness of the inverse optimal control problem, in this section, we consider inverse optimal control for the LQR problem in the noiseless case. It is assumed that we have knowledge of $M$ sets of optimal trajectories $\lbrace x_{1:N}^{(i)*},u_{1:N-1}^{(i)*}\rbrace_{i=1}^M$, i.e., $u_t^{(i)*}=K_tx_t^{(i)*}$, where $K_t$ is the optimal feedback gain. We omit the superscript “star" in the remainder of this section to shorten the notation.

By PMP, if $u_{1:N-1}$ and $x_{1:N}$ are the optimal control and corresponding trajectory, then there exists adjoint variables $\lambda_{2:N}$ such that $$\begin{aligned}
&\lambda_t=A^T\lambda_{t+1}+Qx_t,\:t=2:N-1,\\
&\lambda_N=0,\\
&u_t=-B^T\lambda_{t+1},\:t=1:N-1.
\label{eq:PMP_original}
\end{aligned}$$ Note that in general, PMP only provides necessary optimality conditions for optimal control problems, nevertheless, since the optimal solution to the LQ optimal control problem is unique, PMP becomes also sufficient conditions for optimality.

Note that in this case, knowing $u_{1:N-1}^{(1:M)}$ and $x_1^{(1:M)}=\bar{x}^{(1:M)}$ is equivalent to knowing $x_{1:N}^{(1:M)}$. This is because when given an optimal trajectory $x_{1:N}^{(i)}$, its corresponding optimal control $u_{1:N-1}^{(i)}$ can be determined by $u_t^{(i)}=(B^TB)^{-1}B^T(x_{t+1}^{(i)}-Ax_t^{(i)})$ since $B$ has full column rank by assumption. On the other hand, when given the initial value $\bar{x}^{(1:M)}$ and $u_{1:N-1}^{(1:M)}$, we can use to compute the optimal trajectory $x_{1:N}^{(1:M)}$. Hence we do not distiguish these two cases in the remainder of this section.

Based on , it is straight forward to solve the inverse optimal control problem, i.e., get the matrix $Q$ by solving the following feasibility SDP problem $$\begin{aligned}
& \underset{\lambda_{2:N}^{(1:M)},Q\in\mathbb{S}^n_+}{\text{minimize}}
    & & 0
    & \text{subject to}
    & &\eqref{eq:PMP_original},\:i=1:M,
\end{aligned}$$ with a slightly abuse of notation that “subject to " actually means with a superscript $(i)$ on every $x_t$, $\lambda_t$ and $u_t$’s. The objective function of the above problem can be any constant, without losing generality, here we let it be 0.

Though the problem is easy in the noiseless case, however, we would like to have a closer look at the identifiability of $Q$. Namely, given a set of noiseless optimal trajectories $x_{1:N}^{(1:M)}$, is there a unique positive semidefinite matrix that corresponds to the given optimal trajectories? Now we give two sufficient conditions on the given trajectories $x_{1:N}^{(1:M)}$ that can be used to determine the uniqueness of $Q$.

\[prop:AD\_full\_rank\] Define matrix $$\begin{aligned}
&\mathscr{A}(x)=
\begin{bmatrix}
x_2^{(1)T}\\ \vdots\\x_2^{(M)T}
\end{bmatrix}
\otimes
\begin{bmatrix}
B^T\\0\\ \vdots\\0
\end{bmatrix}+
\begin{bmatrix}
x_3^{(1)T}\\ \vdots\\x_3^{(M)T}
\end{bmatrix}
\otimes
\begin{bmatrix}
B^TA^T\\B^T\\ \vdots\\0
\end{bmatrix}\\
&+\cdots+
\begin{bmatrix}
x_{N-1}^{(1)T}\\ \vdots\\x_{N-1}^{(M)T}
\end{bmatrix}
\otimes
\begin{bmatrix}
B^T(A^T)^{N-3}\\B^T(A^T)^{N-4}\\\vdots\\B^T
\end{bmatrix}.
\end{aligned}
\label{eq:A_mat_eq}$$ If $M(N-2)m\geq n(n+1)/2$ and $\mathscr{A}(x)\mathscr{D}$ has full column rank, then the $Q\in\mathbb{S}^n_+$ that corresponds to the given optimal trajectories $x_{1:N}^{(1:M)}$ is unique, where $\mathscr{D}$ is the duplication matrix for $\mathbb{S}^n$.

By PMP , it follows that $$\begin{aligned}
&\begin{bmatrix}
I &-A^T \\
  &I &\ddots\\
  &  &\ddots&-A^T\\
  &  &      &I
\end{bmatrix}
\begin{bmatrix}
\lambda_2^{(i)}\\\vdots\\\lambda_N^{(i)}
\end{bmatrix}
=
\begin{bmatrix}
Qx_2^{(i)}\\\vdots\\Qx_{N-1}^{(i)}\\0
\end{bmatrix},\\
\Leftrightarrow 
&\begin{bmatrix}
\lambda_2^{(i)}\\\vdots\\\lambda_N^{(i)}
\end{bmatrix}
=
\begin{bmatrix}
I &A^T &(A^T)^2 &\cdots &(A^T)^{N-2}\\
  &I &A^T&\cdots &(A^T)^{N-3}\\
  &  &\ddots &\ddots &\vdots\\
  &  &      &I&A^T\\
  &  &      & &I
\end{bmatrix}
\begin{bmatrix}
Qx_2^{(i)}\\\vdots\\Qx_{N-1}^{(i)}\\0
\end{bmatrix},\\
\Rightarrow &-\operatorname{vec}(u_{1:N-1}^{(i)})
=(I\otimes B^T)\operatorname{vec}(\lambda_{2:N}^{(i)})
\\
&=
\begin{bmatrix}
B^TQx_2^{(i)}+B^TA^TQx_3^{(i)}+\cdots +B^T(A^T)^{N-3}Qx_{N-1}^{(i)}\\
             B^TQx_3^{(i)}    +\cdots +B^T(A^T)^{N-4}Qx_{N-1}^{(i)}\\
             \vdots\\
             B^TQx_{N-1}^{(i)}\\
             0
\end{bmatrix}\end{aligned}$$ Using the property of vectorization and Kronecker product, we can rewrite the above equation as $$\begin{aligned}
-\operatorname{vec}(u_{1:N-1}^{(i)})&=(x_2^{(i)T}\otimes
\begin{bmatrix}
B^T\\0\\\vdots\\0
\end{bmatrix}
+x_3^{(i)T}\otimes
\begin{bmatrix}
B^TA\\B^T\\0\\\vdots\\0
\end{bmatrix}
+\cdots\\
&x_{N-1}^{(i)T}\otimes
\begin{bmatrix}
B^T(A^T)^{N-3}\\B^T(A^T)^{N-4}\\\vdots\\B^T\\0
\end{bmatrix})\operatorname{vec}(Q)\end{aligned}$$ Stacking all $u_{1:N-2}^{(i)}$ for $i=1:M$ and by $\operatorname{vec}(Q)=\mathscr{D}\operatorname{vech}(Q)$, we get $$\begin{aligned}
-\operatorname{vec}(u_{1:N-2}^{(1:M)})=\mathscr{A}(x)\mathscr{D}\operatorname{vech}(Q).
\label{eq:vech_Q_equation}\end{aligned}$$ Since $\mathscr{A}(x)\mathscr{D}$ has dimension $M(N-1)m\times n(n+1)/2$ and $M(N-1)m\geq n(n+1)/2$, $\operatorname{vech}(Q)$ must be unique provided that $\mathscr{A}(x)\mathscr{D}$ has full column rank.

Sometimes, $\mathscr{A}(x)\mathscr{D}$ does not necessarily have full column rank, but we can still get a unique $Q$ by the optimal trajectories $x_{1:N}^{(1:M)}$ available. We give the following sufficient condition:

\[prop:uniqueness\_dual\] Suppose $\mathscr{A}(x)\mathscr{D}$ does not have full column rank, $\operatorname{vech}(Q^\prime)$ is a solution to and $\operatorname{span}\{\operatorname{vech}(\Delta Q_k)\}=\operatorname{ker}(\mathscr{A}(x)\mathscr{D})$, where $\operatorname{vech}(\Delta Q_k)$ are linearly independent. In addition, suppose $\Phi^*\in\mathbb{S}^n_+$ is an optimal solution to $$\begin{aligned}
& \underset{\Phi\in\mathbb{S}^n_+}{\text{minimize}}
    & & tr(Q^\prime\Phi)\\
    & \text{subject to}
    & &tr(\Delta Q_k\Phi)=0,k=1:\dim\left(\operatorname{ker}\left(\mathscr{A}(x)\mathscr{D}\right)\right),
\end{aligned}
\label{eq:vech_Q_dual}$$ where $rank(\Phi^*)=r$, $\Phi^*=G\:diag(\sigma_1,\cdots\sigma_r,0,\cdots,0)G^T$ and $GG^T=I$. Define $$\begin{aligned}
\mathscr{N}_\Phi=\left\{G
\begin{bmatrix}
0&0\\0 &W
\end{bmatrix}G^T\:|\:W\in\mathbb{S}^{n-r}
\right\}.\end{aligned}$$ If $\mathscr{N}_\Phi\cap \operatorname{span}\{\Delta Q_k\}=\{0\}$, then the $Q\in\mathbb{S}^n_+$ that corresponds to the given optimal trajectories $x_{1:N}^{(1:M)}$ is unique.

Denote $\eta=\dim(\operatorname{ker}(\mathscr{A}(x)\mathscr{D}))$. Since $\mathscr{A}(x)\mathscr{D}$ does not have full column rank, $\operatorname{vech}(Q^\prime)$ is a solution to and $\operatorname{vech}(\Delta Q_k)$ are linearly independent and spans $\operatorname{ker}(\mathscr{A}(x)\mathscr{D})$, it holds that $$\begin{aligned}
\mathscr{A}(x)\mathscr{D}\left(\operatorname{vech}(Q^\prime)+\sum_{k=1}^{\eta}\alpha_k\operatorname{vech}(\Delta Q_k)\right)=0,\forall \alpha_k.\end{aligned}$$ What remains to show is that there exists a unique $\{\alpha_k\}_{k=1}^\eta$, such that $Q=Q^\prime+\sum_{k=1}^\eta\alpha_k\Delta Q_k\in\mathbb{S}^n_+$. Consider the following SDP $$\begin{aligned}
& \underset{\{\alpha_k\}}{\text{minimize}}
    & & 0\\
    & \text{subject to}
    & &Q^\prime+\sum_{k=1}^\eta\alpha_k\Delta Q_k\succeq 0,
\end{aligned}
\label{eq:vech_Q_feasible}$$ whose dual problem is . If $\Phi^*$ is an optimal solution to and $\mathscr{N}_\Phi\cap \operatorname{span}\{\Delta Q_k\}=\{0\}$, then the optimal solution is non-degenerate. Hence the primal problem has a unique solution.[@alizadeh1997complementarity]

If the “real" $Q$ is strictly positive definite, then “the matrix $\mathscr{A}(x)\mathscr{D}$ has full column rank" also becomes a necessary condition for the identifiability of $Q$. If $\mathscr{A}(x)$ does not have full rank, then there always exists some $\Delta Q\in \operatorname{ker}(\mathscr{A}(x)\mathscr{D})$ and small enough $\varepsilon$ such that $\mathscr{A}(x)\mathscr{D}(\operatorname{vech}(Q)+\varepsilon \operatorname{vech}(\Delta Q))=-\operatorname{vec}(u_{1:N-2}^{(1:M)})$ and $\operatorname{vech}(Q)+\varepsilon \operatorname{vech}(\Delta Q)\in\mathbb{S}^n_+$ since $Q$ is an interior point in $\mathbb{S}^n_+$.

Here is an example that illustrates Proposition \[prop:uniqueness\_dual\]. Suppose $M=1$, $N=15$, the system matrices, the initial value and the “real" $Q$ matrix (we denote it as $\bar{Q}$) are as follows $$\begin{aligned}
&A=
\begin{bmatrix}
-0.1922   &-0.2490    &1.2347\\
-0.2741   &-1.0642    &-0.2296\\
1.5301    &1.6035     &-1.5062
\end{bmatrix},
B=
\begin{bmatrix}
-0.4446\\-0.1559\\0.2761
\end{bmatrix},\\
&\bar{Q}=
\begin{bmatrix}
0.0068   &-0.0116   &-0.0102\\
-0.0116  &0.0197    &0.0174\\
-0.0102  &0.0174    &0.0154
\end{bmatrix},
x_0=
\begin{bmatrix}
-25.0136 \\ -18.9592 \\ -14.8221
\end{bmatrix}.\end{aligned}$$ In this case, $dim(\operatorname{ker}(\mathscr{A}(x)\mathscr{D}))=1$ and $$\begin{aligned}
&\Delta Q=
\begin{bmatrix}
0.0723   &-0.6085   &-0.1447\\
-0.6085  &-0.0422   &-0.6661\\
-0.1447  &-0.6661   &-0.3976
\end{bmatrix},\\
&\Phi^*=
\begin{bmatrix}
7.5572    &1.6696    &3.1474\\
1.6696    &4.4056    &-3.8723\\
3.1474    &-3.8723   &6.4792
\end{bmatrix},\end{aligned}$$ $rank(\Phi^*)=2$. If we solve the following problem $$\begin{aligned}
& \underset{\beta,W\in\mathbb{R}}{\text{minimize}}
    & & 0\\
    & \text{subject to}
    & &G\begin{bmatrix}
0&0\\0 &W
\end{bmatrix}G^T=\beta \Delta Q,\end{aligned}$$ we will find that the only feasible solution is $\beta=W=0$. And if one solves the inverse optimal control problem, she will get an unique solution $Q^*=\bar{Q}$.

Note that $\mathscr{A}(x)\mathscr{D}$ depends on the data. Though it has been stated in Proposition \[prop:AD\_full\_rank\] that we would have a unique $Q$ that corresponds to the given optimal trajectories $x_{1:N}^{(1:M)}$ if $\mathscr{A}(x)\mathscr{D}$ has full column rank, we would like to say a bit more about the data set $x_{1:N}^{(1:M)}$, more precisely, under what conditions of the data set $x_{1:N}^{(1:M)}$ will let $\mathscr{A}(x)\mathscr{D}$ have full column rank. Since $\mathscr{D}$ has full column rank, $\mathscr{A}(x)\mathscr{D}$ would have full column rank if $\mathscr{A}(x)$ has full column rank. In the following we will focus on discussing what kind of data set $x_{1:N}^{(1:M)}$ would let $\mathscr{A}(x)$ have full column rank. Before we give a sufficient condition for that, we would like to present the following lemma:

\[lem:struct\_mat\_linear\_indep\] If the vectors $$\begin{aligned}
\begin{bmatrix}
a^{(1)}_1\\a^{(1)}_2\\\vdots\\a^{(1)}_n
\end{bmatrix},
\begin{bmatrix}
a^{(2)}_1\\a^{(2)}_2\\\vdots\\a^{(2)}_n
\end{bmatrix},
\cdots,
\begin{bmatrix}
a^{(n)}_1\\a^{(1)}_2\\\vdots\\a^{(n)}_n
\end{bmatrix}\end{aligned}$$ are linearly independent, then matrix $$\begin{aligned}
\bar{\chi}=
\begin{bmatrix}
\bar{\chi}_1^{(1)} &\bar{\chi}_2^{(1)} &\cdots &\bar{\chi}_n^{(1)}\\
\bar{\chi}_1^{(2)} &\bar{\chi}_2^{(2)} &\cdots &\bar{\chi}_n^{(2)}\\
\vdots&\vdots&\vdots\\
\bar{\chi}_1^{(n)} &\bar{\chi}_2^{(1)} &\cdots &\bar{\chi}_n^{(n)}
\end{bmatrix}\end{aligned}$$ is nonsingular $\forall \xi_{j,l}^{(i)}$, where $$\begin{aligned}
\bar{\chi}_j^{(i)}=
\begin{bmatrix}
a_j^{(i)} &\xi_{j,1}^{(i)} &\cdots &\xi_{j,n-1}^{(i)}\\
          &a_j^{(i)}       &\ddots &\vdots\\
          &                &\ddots &\xi_{j,1}^{(i)}\\
          &                &       &a_j^{(i)}
\end{bmatrix}.\end{aligned}$$

Suppose there exists constants $\eta_{1:n}^{(1:n)}$ such that $\sum_{i=1}^n\sum_{j=1}^n\eta_j^{(i)}\left[\bar{\chi}\right]_{(i-1)n+j}=0$. Recall the structure of $\bar{\chi}$, it must hold for the first row of every row block $\left[\bar{\chi}_1^{(i)} \bar{\chi}_2^{(i)}\cdots\bar{\chi}_n^{(i)}\right]$ in $\bar{\chi}$ that $\sum_{i=1}^n\eta_1^{(i)}\left[\bar{\chi}_1^{(i)} \bar{\chi}_2^{(i)}\cdots\bar{\chi}_n^{(i)}\right]_1=0$, which reads precisely as $$\begin{aligned}
&a_1^{(1)}\eta_1^{(1)}+a_1^{(2)}\eta_1^{(2)}+\cdots a_1^{(n)}\eta_1^{(n)}=0\\
&\vdots\\
&a_n^{(1)}\eta_1^{(1)}+a_n^{(2)}\eta_1^{(2)}+\cdots a_n^{(n)}\eta_1^{(n)}=0\\
\Leftrightarrow 
&\begin{bmatrix}
a_1^{(1)} &a_1^{(2)} &\cdots &a_1^{(n)}\\
a_2^{(1)} &a_2^{(2)} &\cdots &a_2^{(n)}\\
\vdots & & &\vdots\\
a_n^{(1)} &a_n^{(2)} &\cdots &a_n^{(n)}
\end{bmatrix}
\begin{bmatrix}
\eta_1^{(1)}\\\eta_1^{(2)}\\\vdots\\\eta_1^{(n)}
\end{bmatrix}=0.\end{aligned}$$ Since by assumption $\left[a^{(1)T}_1,a^{(1)T}_2,\cdots,a^{(1)T}_n\right]^T$, $\cdots$ $\left[a^{(n)T}_1,a^{(1)T}_2,\cdots\\a^{(n)T}_n\right]^T$ are linearly independent, the above matrix only have unique zero solution, i.e., $\eta_1^{(i)}=0,\:\forall i$. This implies that $\sum_{i=2}^n\sum_{j=1}^n\eta_j^{(i)}\left[\bar{\chi}\right]_{(i-1)n+j}=0$. Similar to the argument above, we can iteratively show $\eta_j^{(i)}=0,\:\forall i,j$ and hence all of the rows in $\bar{\chi}$ are linearly independent. Therefore, $\bar{\chi}$ is nonsingular.

\[thm:end\_pt\_indep\] Suppose $N\ge n+2$ and $M\geq n$. If there exists $n$ linearly independent $x_{N-1}^{(1:n)}$ among all $M$ sets of data, then there exists a unique $Q$ that corresponds to the given optimal trajectories $x_{1:N}^{(1:M)}$.

Recall the definition of $\mathscr{A}(x)$ in , it can be rewritten as: $$\begin{aligned}
\mathscr{A}(x)=\sum_{t=2}^{N-1}X_t\otimes(\mathcal{S}_t \Gamma)=\underbrace{\left[\sum_{t=2}^{N-1}X_t\otimes \mathcal{S}_t\right]}_\chi(I_n\otimes\Gamma),\end{aligned}$$ where $$\begin{aligned}
&\Gamma=
\begin{bmatrix}
B^T(A^T)^{N-3}\\B^T(A^T)^{N-4}\\\vdots\\B^T
\end{bmatrix},
\mathcal{S}_2=
\begin{bmatrix}
0_m &\cdots &0_m &I_m\\
0_m &\cdots & &0_m\\
\vdots &\vdots& &\vdots\\
0_m &\cdots & &0_m
\end{bmatrix}\end{aligned}$$ $$\begin{aligned}
&\mathcal{S}_3=
\begin{bmatrix}
0_m &\cdots &I_m &0_m\\
0_m &\cdots &0_m &I_m\\
\vdots & &\vdots &\vdots\\
0_m &\cdots &0_m &0_m
\end{bmatrix},\cdots,
\mathcal{S}_{N-2}=
\begin{bmatrix}
0_m &I_m &0_m &\cdots &0_m\\
0_m &0_m &I_m &\cdots &0_m\\
\vdots &\vdots& &\ddots &I_m\\
0_m &0_m &\cdots & &0_m
\end{bmatrix},\end{aligned}$$ $$\begin{aligned}
&\mathcal{S}_{N-1}=I_{m(N-2)},\: X_t=
\begin{bmatrix}
x_t^{(1)T}\\ \vdots\\x_t^{(M)T}
\end{bmatrix}.\end{aligned}$$

Note due to the structure of $\mathcal{S}_t$’s, $\chi$ has the following form $$\begin{aligned}
\chi=
\begin{bmatrix}
\chi_1^{(1)} &\cdots &\chi_n^{(1)}\\
\vdots & &\vdots\\
\chi_1^{(M)} &\cdots &\chi_n^{(M)}
\end{bmatrix},\end{aligned}$$ where $$\begin{aligned}
\chi_j^{(i)}=
\begin{bmatrix}
x_{N-1,j}^{(i)}I_m &x_{N-2,j}^{(i)}I_m &\cdots &x_{1,j}^{(i)}I_m\\
                   &x_{N-1,j}^{(i)}I_m &\ddots &\vdots\\
                   &       &\ddots &x_{N-2,j}^{(i)}I_m\\
                   &       &       &x_{N-1,j}^{(i)}I_m
\end{bmatrix}.\end{aligned}$$ Note that the first $n$ row blocks in $\chi$ has exactly the same structure as $\bar{\chi}$ in Lemma \[lem:struct\_mat\_linear\_indep\]. Since $x_{N-1}^{(1:n)}$ are linearly independent, that is, $\left[x_{N-1,1}^{(1)},\cdots,x_{N-1,n}^{(1)}\right]^T$ $\cdots$ $\left[x_{N-1,1}^{(n)},\cdots,x_{N-1,n}^{(n)}\right]^T$ are linearly independent, we can apply Lemma \[lem:struct\_mat\_linear\_indep\] and conclude that the matrix formed by the first $n$ row blocks of $\chi$ is nonsingular. Thus $\chi$ has full column rank.

On the other hand, since $(A,B)$ is controllable, $\Gamma$ has full column rank and $rank(\Gamma)=n$. By the property of Kronecker product, it holds that $rank(I_n\otimes\Gamma)=rank(I_n)\times rank(\Gamma)=n^2$. Therefore, due to the fact that $\chi$ has full column rank, $rank(\mathscr{A}(x))=rank\left(\chi(I_n\otimes\Gamma)\right)=rank(I_n\otimes\Gamma)=n^2$, i.e., $\mathscr{A}(x)$ has full column rank. Hence the solution $\operatorname{vech}(Q)$ to the equation is unique.

Theorem \[thm:end\_pt\_indep\] indicates that if among $M$ trajectories, there exists $n$ trajectories such that the second last states of each, i.e., $x_{N-1}^{(1)},\cdots,x_{N-1}^{(n)}$ are linearly independent, then $Q$ is identifiable. The theorem provides a convenient way of checking the identifiability of $Q$.

Inverse Optimal Control in the Noisy Case {#sec:noisy}
=========================================

Now we turn our attention to the noisy case. Inspired by [@aswani2015inverse], we first pose the inverse optimal control problem in the noisy case. Suppose the probability space $(\Omega,\mathcal{F},\mathbb{P})$ carries independent random vectors $\bar{x}\in\mathbb{R}^n$, $\{v_t\in\mathbb{R}^n\}_{t=2}^N$ and $\{w_t\in\mathbb{R}^n\}_{t=1}^{N-1}$ distributed according to some unknown distributions. The following assumptions are made in the remainder of the paper:

\[ass:zero\_mean\_fin\_var\] $\mathbb{E}(\|\bar{x}\|^2)<+\infty$, $\mathbb{E}(v_t)=\mathbb{E}(w_{t-1})=0$ and $\mathbb{E}(\|v_t\|^2)<+\infty$, $\mathbb{E}(\|w_{t-1}\|^2)<+\infty,t=2:N$.

\[ass:neighbourhood\_not\_measure\_zero\] $\forall \eta\in\mathbb{R}^n$, $\exists r(\eta)\in\mathbb{R}\backslash\{0\}$ such that $\mathbb{P}\left(\bar{x}\in\mathscr{B}_\varepsilon(r\eta)\right)>0,\forall \varepsilon>0$, where $\mathscr{B}_\varepsilon(r\eta)$ is the open $\varepsilon$-ball centered at $r\eta$.

Equipped with the stochastic set-up above and given that the initial value $x_1$ is actually a realization of the random vector $\bar{x}$, i.e., $x_1=\bar{x}(\omega)$, the LQR problem can actually be seen as $$\min \{J(u_{1:N-1}(\omega),x_{2:N}(\omega);Q;\bar{x}(\omega))|\eqref{eq:lti},\mbox{given }\omega\in\Omega\},
\label{eq:aswani_formulation}$$ Note that the optimal control input and trajectory $\{u_t^*\},\{x_t^*\}$ are now random vectors implicitly determined by the random variable $\bar{x}$ and the parameter $Q$. With the formulation of the “forward problem" , we now can pose the formulation of the inverse optimal control problem.

Suppose $\{u_t^*\}$ and $\{x_t^*\}$ are corrupted by some zero mean noise, namely, $y_t=x_t^*+v_t,t=2:N$, $\mu_t=u_t^*+w_t,t=1:N-1$. To abbreviate the notation, we denote $Y=(y_2^T,\cdots,y_N^T)^T$, $\Upsilon=(\mu_1^T,\cdots,\mu_{N-1}^T)^T$, $\xi_{x}=(\bar{x}^T,Y^T)^T$ and $\xi_u=(\bar{x}^T,\Upsilon^T)^T$. In addition, we assume that the “real" $Q$ belongs to a compact set $\bar{\mathbb{S}}^n_+(\varphi)=\{Q|Q\in\mathbb{S}^n_+,\|Q\|^2_F\leq \varphi\}$. We aim to find the $Q\in\bar{\mathbb{S}}^n_+(\varphi)$ that corresponds to the optimal trajectory $\{x_t^*\}$ and control input $\{u_t^*\}$ by using the initial value $\bar{x}$ and the noisy observations $\xi_x$ or $\xi_u$.

Given $Q$ and an initial value $\bar{x}$, the solution to is unique. We define the risk functions $\mathscr{R}_x:\bar{\mathbb{S}}^n_+(\varphi)\mapsto\mathbb{R}$ and $\mathscr{R}_u:\bar{\mathbb{S}}^n_+(\varphi)\mapsto\mathbb{R}$ as $$\mathscr{R}^x(Q)=\mathbb{E}_{\xi_x}\left[f_x(Q;\xi_x)\right],
\label{eq:risk_function}$$ $$\mathscr{R}^u(Q)=\mathbb{E}_{\xi_u}\left[f_u(Q;\xi_u)\right],
\label{eq:risk_function_u}$$ where $f_x:\bar{\mathbb{S}}^n_+(\varphi)\times \mathbb{R}^{Nn}\mapsto\mathbb{R}$ and $f_u:\bar{\mathbb{S}}^n_+(\varphi)\times \mathbb{R}^{n+m(N-1)}\mapsto\mathbb{R}$ $$\begin{aligned}
f_x(Q;\xi_x)=\sum_{t=2}^{N}\|y_t-x_t^*(Q;\bar{x})\|^2,\label{eq:risk_function1}\\
f_u(Q;\xi_x)=\sum_{t=1}^{N-1}\|\mu_t-u_t^*(Q;\bar{x})\|^2,\label{eq:risk_function1_u}\end{aligned}$$ and $x_{2:N}^*(Q;\bar{x})$ and $u_{1:N-1}^*(Q;\bar{x})$ are the optimal solution to . In order to solve the inverse optimal control problem, we would like to minimize the risk functions, namely, $$\min_{Q\in\bar{\mathbb{S}}^n_+(\varphi)}\mathscr{R}^x(Q)
\label{eq:risk_minimization}$$ or $$\min_{Q\in\bar{\mathbb{S}}^n_+(\varphi)}\mathscr{R}^u(Q),
\label{eq:risk_minimization_u}$$ depending on which observations are available. Nevertheless, since the distributions of $\bar{x}$, $v_t$ and $w_t$ are unknown, the distributions of $\xi_x$ and $\xi_u$ are also unknown. We can not solve and directly. and in principle, however, can be approximated by $$\begin{aligned}
\mathscr{R}_M^x(Q)=\frac{1}{M}\sum_{i=1}^M f_x(Q;\xi_x^{(i)}),\label{eq:risk_function_approx}\\
\mathscr{R}_M^u(Q)=\frac{1}{M}\sum_{i=1}^M f_u(Q;\xi_u^{(i)}),\label{eq:risk_function_approx_u}\end{aligned}$$

where $\xi_x^{(i)}$ and $\xi_u^{(i)}$ are i.i.d. random samples. We will show the statistical consistency for the approximation later.

Recall that for discrete-time LQR’s in finite-time horizon, PMP provides sufficient and necessary conditions for optimality, hence we can express $u_{1:N-1}^*$, $x_{2:N}^*$ using and the approximated risk-minimizing problem reads $$\begin{aligned}
\underset{Q\in\bar{\mathbb{S}}^n_+(\varphi),x_{2:N}^{(i)},\lambda_{2:N}^{(i)}}{\text{min}\qquad}
    &  \mathscr{R}_M^x(Q)=\frac{1}{M}\sum_{i=1}^M f_x(Q;\xi^{(i)})\\
         \text{s.t.\qquad}
    & x_{t+1}^{(i)}=Ax_t^{(i)}-BB^T\lambda_{t+1}^{(i)},\quad t=2:N-1,\\
    & \lambda_t^{(i)}=A^T\lambda_{t+1}^{(i)}+Qx_t^{(i)},\:t=2:N-1,\\
    & x_2^{(i)}=A\bar{x}^{(i)}-BB^T\lambda_2^{(i)},\\
    &\lambda_N^{(i)}=0,\quad i=1:M,
\end{aligned}
\label{eq:risk_minimizing_pro_approx}$$ We omit the “star" in the notation to avoid the confusion with the optimizer of . The risk-minimization problem for $\mathscr{R}_M^u(Q)$ is omitted here for the sake of brevity. The optimizer $\left(Q_M^*(\omega),x_{2:N}^{(i)*}(\omega),\lambda_{2:N}^{(i)*}(\omega)\right)$ is defined in the sense that it optimizes (or ) for every $\omega\in\Omega$.

\[thm:statistical\_consistency\] Suppose $Q_M^*\in\bar{\mathbb{S}}^n_+(\varphi)$, $N\geq n+2$, $\{x_{2:N}^{(i)*}\}$ and $\{\lambda_{2:N}^{(i)*}\}$ solves , then $Q_M^*\overset{p}{\rightarrow}\bar{Q}$ as $M\rightarrow \infty$, where $\bar{Q}$ is the true value used in the “forward" problem .

Before moving on, we would like to take a close look at and the system dynamics . Denote $z_t=\left(x_t^T,\lambda_t^T\right)^T,t=2:N$, then the first two constraints can be written as the following implicit dynamics $$\underbrace{\begin{bmatrix}
I &BB^T\\0 &A^T
\end{bmatrix}}_{E}
z_{t+1}=
\underbrace{\begin{bmatrix}
A &0\\-Q &I
\end{bmatrix}}_F z_t,\quad t=2:N-1.$$ Hence we can write together with as the following compact form $$\underbrace{\begin{bmatrix}
\tilde{E} & & &\tilde{F}\\
-F &E\\
   &\ddots &\ddots\\
   &  &-F& E
\end{bmatrix}}_{\mathscr{F}(Q)}
\underbrace{\begin{bmatrix}
z_2\\\vdots\\z_N
\end{bmatrix}}_{Z}
=
\underbrace{\begin{bmatrix}
A\bar{x}^{(i)}\\0\\\vdots\\0
\end{bmatrix}}_{b(\bar{x})},
\label{eq:PMP_matrix_equation}$$ where $$\begin{aligned}
\tilde{E}=
\begin{bmatrix}
I &BB^T\\0 &0
\end{bmatrix},
\tilde{F}=
\begin{bmatrix}
0 &0\\0 &I
\end{bmatrix}.\end{aligned}$$ We claim that $\mathscr{F}(Q)$ is invertible for all $Q\in\mathbb{S}^n_+$. Though this fact can be proven by “brute force", i.e., by considering its determinant using Laplace expansion, perhaps the easiest way to see this is that for an arbitrary $Q\in\mathbb{S}^n_+$, is a sufficient and necessary condition for the corresponding “forward" LQR problem. Since the “forward" LQR problem has a unique solution, it must hold that $\mathscr{F}(Q)$ is invertible for all $Q\in\mathbb{S}^n_+$. Thus, it follows that $Z=\mathscr{F}(Q)^{-1}b(\bar{x})=\mathscr{F}(Q)^{-1}\tilde{A}\bar{x}$, where $\tilde{A}=[A^T,0,\cdots,0]^T$. Hence $f_x(Q;\xi_x)$ can be rewritten as $$\begin{aligned}
f_x(Q;\xi_x)=\|Y-G_xZ\|^2=\|Y-G_x\mathscr{F}(Q)^{-1}\tilde{A}\bar{x}\|^2,\end{aligned}$$ where $G_x=I_{N-1}\otimes \left[I_n, 0_n\right]$.

It is clear that $f_x(Q;\xi_x)$ is continuous with respect to $\xi_x$, hence it is a measurable function of $\xi_x$ at each $Q$. Further, $\mathscr{F}(Q)$ is continuous and hence $\mathscr{F}(Q)^{-1}$ is continuous. Then $f_x(Q;\xi_x)$ is also continuous with respect to $Q$.

On the other hand, since $\mathscr{F}(Q)^{-1}$ is continuous and $Q$ lives in a compact set, then $\|\mathscr{F}(Q)^{-1}\|_F$ is bounded, i.e., $\|\mathscr{F}(Q)^{-1}\|_F\leq \bar{\varphi}$ for some finite positive $\bar{\varphi}$. It follows that $\mathbb{E}(\|Z^*\|^2)=\mathbb{E}(\|\mathscr{F}(\bar{Q})^{-1}\tilde{A}\bar{x}\|^2)\leq \|\mathscr{F}(\bar{Q})^{-1}\|_F^2\|\tilde{A}\|_F^2\mathbb{E}(\|\bar{x}\|^2)<+\infty$, where $Z^*$ corresponds to the “true" $\bar{Q}$.

Recall that $y_t=x_t^*+v_t$ and this implies that $Y=G_xZ^*+\zeta$, where $\zeta=[v_2^T\cdots,v_N^T]^T$. By Assumption \[ass:zero\_mean\_fin\_var\], $\mathbb{E}(\|v_t\|^2)<\infty$, which implies $\mathbb{E}(\|\zeta\|^2)<+\infty$. Therefore, $\mathbb{E}(\|Y\|^2)=\mathbb{E}(\|G_xZ^*+\zeta\|^2)\leq 2\left(\mathbb{E}(\|G_xZ^*\|^2)+\mathbb{E}(\|\zeta\|^2)\right)\leq 2\big(\|G_x\|_F^2\mathbb{E}(\|Z^*\|^2)$ $+\mathbb{E}(\|\zeta\|^2)\big)$ $<+\infty$. Hence it holds that $$\begin{aligned}
f_x(Q,\xi_x)&=\|Y-G_x\mathscr{F}(Q)^{-1}\tilde{A}\bar{x}\|^2\\
&\leq 2\left(\|Y\|^2+\|G_x\mathscr{F}(Q)^{-1}\tilde{A}\bar{x}\|^2\right)\\
&\leq 2\left(\|Y\|^2+\|G_x\|_F^2\|\mathscr{F}(Q)^{-1}\|_F^2\|\tilde{A}\|_F^2\|\bar{x}\|^2\right)\\
&\leq 2\left(\|Y\|^2+\bar{\varphi}^2\|G_x\|_F^2\|\tilde{A}\|_F^2\|\bar{x}\|^2\right):=d(\xi_x),\end{aligned}$$ and it is clear that $\mathbb{E}(d(\xi_x))<+\infty$ since $\mathbb{E}(\|Y\|^2)<+\infty$ and $\mathbb{E}(\|\bar{x}\|^2)<+\infty$. By the analysis above, we conclude that the uniform law of large numbers [@jennrich1969asymptotic] applies, namely, $$\sup_{Q\in\bar{\mathbb{S}}^n_+(\varphi)}\|\frac{1}{M}\sum_{i=1}^M f_x(Q,\xi_x^{(i)})-\mathbb{E}_{\xi_x}\left(f_x(Q;\xi_x)\right)\|\overset{p}{\rightarrow} 0.
\label{eq:uniform_law_of_large_numbers}$$ Besides , if we are able to show $\bar{Q}$ is the unique optimizer to , then $Q_M^*\overset{p}{\rightarrow}\bar{Q}$ follows directly from Theorem 5.7 in [@van2000asymptotic].

Note that by assumption, $\bar{x}$, $\{v_t\}$ are independent, hence $x_t^*(Q;\bar{x})$ are independent of the noises $\{v_t\}$. Since $y_t=x^*_t(\bar{Q},\bar{x})+v_t$, $\mathbb{E}(v_t)=0,t=2:N$, can be simplified as $\mathscr{R}^x(Q)=L(Q)+\sum_{t=2}^N\mathbb{E}(\|v_t\|^2)$, where $L(Q)=\mathbb{E}\left(\sum_{t=2}^N\|x_t^*(\bar{Q},\bar{x})-x_t^*(Q,\bar{x})\|^2\right)$. It is clear that $Q=\bar{Q}$ minimizes the risk function $\mathscr{R}^x(Q)$. What remains to show is the uniqueness. By Theorem \[thm:well\_poseness\], if $Q\neq\bar{Q}$, then $A_{cl}(1,Q)\neq A_{cl}(1,\bar{Q})$. Hence there exists $\eta\in\mathbb{R}^n$, such that $A_{cl}(1,Q)\eta\neq A_{cl}(1,\bar{Q})\eta$. On the other hand, by Assumption \[ass:neighbourhood\_not\_measure\_zero\], $\exists r(\eta)\neq 0$, such that $\mathbb{P}(\bar{x}\in \mathscr{B}_\varepsilon(r\eta))>0,\forall \varepsilon$. Since $r\neq 0$, $A_{cl}(1,Q)(r\eta)\neq A_{cl}(1,\bar{Q})(r\eta)$. Further, since $A_{cl}(1,Q)\eta$ is continuous with respect to $\eta,\forall Q\in\mathbb{S}^n_+$, this implies $\exists \varepsilon_1$, such that $A_{cl}(1,Q)\bar{x}\neq A_{cl}(1,\bar{Q})\bar{x},\forall \bar{x}\in\mathscr{B}_{\varepsilon_1}(r\eta)$ and $\mathbb{P}\left(\bar{x}\in\mathbb{B}_{\varepsilon_1}(r\eta)\right)>0$. Thus $L(Q)\geq \int_{\mathscr{B}_{\varepsilon_1}(r\eta)}\|\left(A_{cl}(1,Q)-A_{cl}(1,\bar{Q})\right)\bar{x}(\omega)\|^2\mathbb{P}(d\omega)>0$. Hence $\bar{Q}$ is the unique minimizer to and the statement follows.

Suppose $Q_M^*\in\bar{\mathbb{S}}^n_+(\varphi)$, $\{x_{2:N}^{(i)*}\}$ and $\{\lambda_{2:N}^{(i)*}\}$ solves the problem of minimizing $\mathscr{R}^u(Q)$, then $Q_M^*\overset{p}{\rightarrow}\bar{Q}$ as $M\rightarrow \infty$, where $\bar{Q}$ is the true value used in the “forward" problem .

Similar to the proof of Theorem \[thm:statistical\_consistency\], we can rewrite $f_u(Q;\xi_u)$ as $$\begin{aligned}
f_u(Q;\xi_u)=\|\Upsilon-G_uZ\|^2=\|\Upsilon-G_u\mathscr{F}(Q)^{-1}\tilde{A}\bar{x}\|^2,\end{aligned}$$ The first part of proof that involves uniform law of large numbers can be shown analogously to the proof of Theorem \[thm:statistical\_consistency\]. What remains to show is that $\bar{Q}$ is the unique minimizer.

Analogously, since $\bar{x}$ and $\{w_t\}$ are independent by assumption, $u_t^*(Q;\bar{x})$ are independent of the noises $w_t$. Since $\mu_t=u_t^*(\bar{Q};\bar{x})+w_t$, $\mathbb{E}(w_t)=0,t=1:N-1$, the risk function can be written as $\mathscr{R}^u(Q)=L^\prime(Q)+\sum_{t=1}^{N-1}\mathbb{E}(\|w_t\|^2)$, where $L^\prime(Q)=\mathbb{E}\left(\sum_{t=1}^{N-1}\|u_t^*(\bar{Q};\bar{x})-u_t^*(Q;\bar{x})\|^2\right)$. By Theorem \[thm:well\_poseness\], if $Q\neq \bar{Q}$, then $A_{cl}(1,Q)\neq A_{cl}(1,\bar{Q})$. Since $B$ has full column rank and recall that $A_{cl}(1,Q)=A+BK_1(Q)$, it follows that $K_1(Q)\neq K_1(\bar{Q})$. Similar to the proof of Theorem \[thm:statistical\_consistency\] and using the fact that $u_1(Q,\bar{x})=K_1(Q)\bar{x}$, we can show that $L^\prime(Q)>0$. Therefore, $\bar{Q}$ is the unique minimizer to the risk-minimizing problem and the statement follows.

Now we have shown that the solutions $Q_M^*$ to the risk-minimizing problems are statistically consistent, we start to consider how to solve the problem. When actually solving the problem, $Y^{(i)}$, $\Upsilon^{(i)}$ and $\bar{x}$ are substituted with the actual measurement of the samples. From the analysis above, we know can be rewritten in the compact form of $\min_{Q\in\bar{\mathbb{S}}^n_+(\varphi)} \frac{1}{M}\sum_{i=1}^M\|Y^{(i)}-G_x\mathscr{F}(Q)^{-1}\tilde{A}\bar{x}\|^2$ (the risk-minimizing problem for control-input observations follows analogously). To solve the problems, we introduce the following convex matrix function $\hat{f}_\varepsilon:\mathbb{S}^n\mapsto\mathbb{R}$, $\hat{f}_\varepsilon(Q)=\varepsilon\ln tr(e^{Q/\varepsilon})=\varepsilon \ln[\sum_{i=1}^Ne^{\sigma_i(Q)/\varepsilon}]$ [@nesterov2007smoothing], where $\sigma_i(Q)$ is the $i$’th largest eigenvalue of $Q$. It holds that $\sigma_1(Q)\leq \hat{f}_\varepsilon(Q)\leq \sigma_1(Q)+\varepsilon\ln n$. Hence when $\varepsilon$ is small, the function $\hat{f}(Q)$ approximates the largest eigenvalue of $Q$ well. On the other hand, the gradient of $\hat{f}_\varepsilon(Q)$ reads $\nabla_Q\hat{f}_\varepsilon(Q)=[\sum_{i=1}^Ne^{\sigma_i(Q)/\varepsilon}]^{-1}[\sum_{i=1}^Ne^{\sigma_i(Q)/\varepsilon}\nu_i\nu_i^T],$ where $(\sigma_i(Q),\nu_i)$ are eigen-pairs of $Q$ with $\|\nu_i\|=1,\forall i$. Note that for $\varepsilon$ small enough, the gradient only numerically depends on the eigenvectors that correspond to the largest eigenvalues [@nesterov2007smoothing], which makes the gradient easy to compute. With the set-up above, we approximate the semi-positive definite constraint $Q\in\mathbb{S}^n_+$ with $\hat{f}_\varepsilon(-Q)\leq 0$ and we can solve the optimization problems with standard nonlinear optimization solvers.

Numerical Examples {#sec:examples}
==================

To illustrate the performance of the estimation statistically, we consider a series of discrete-time systems sampled from continuous systems $\dot{x}=\hat{A}x+\hat{B}u$ with the sampling period $\Delta t=0.1$, where $$\begin{aligned}
\hat{A}=
\begin{bmatrix}
0 &1\\a_1 &a_2
\end{bmatrix},
B=
\begin{bmatrix}
0\\1
\end{bmatrix};\end{aligned}$$ and $a_1,a_2$ are sampled from uniform distributions on $[-3,3]$. The aim for us to generate systems like this is to unsure the controllability of the systems. We take the time horizon $N=50$. The “real " $\bar{Q}$ is generated by letting $\bar{Q}=Q_1Q_1^T$ where each elements of $Q_1$ are sampled from the uniform distribution on $[-1,1]$. We set the feasible compact set for $Q$ as $\mathbb{S}^n_+(5)$ (we discard those randomly generated $\bar{Q}$ that does not belong to $\mathbb{S}^n_+(5)$). Each element of the initial conditions $\bar{x}^{(1:M)}$ are generated by sampling from a uniform distribution supported on $[-5,5]$. We generate 200 different sets of $(\hat{A},\hat{B},\bar{Q})$ and for each fixed $(\hat{A},\hat{B},\bar{Q})$, 200 trajectories are generated, i.e., $M=200$. 15dB and 20dB of white Gaussian noises are added to $x_{2:N}^{(1:M)}$ and $u_{1:N-1}^{(1:M)}$ respectively to get $y_{2:N}^{(1:M)}$ and $\mu_{1:N-1}^{(1:M)}$. MATLAB function `fmincon` is used to solve the risk-minimizing problem. When solving the optimization problem, we use $Q=I$ as the initial iteration values for all cases.

As illustrated in Fig. \[fig:statistical\_consistency1\] and Fig. \[fig:statistical\_consistency2\], the relative error $\|Q_{est}-\bar{Q}\|_F/\|\bar{Q}\|_F$ roughly decreases as $M$ increases.

![The relative errors of minimizing $\mathscr{R}^x_M(Q)$.[]{data-label="fig:statistical_consistency1"}](observation_x_20_200_rel-eps-converted-to.pdf){width="50.00000%"}

![The relative errors of minimizing $\mathscr{R}^u_M(Q)$.[]{data-label="fig:statistical_consistency2"}](observation_u_20_200_rel-eps-converted-to.pdf){width="50.00000%"}

The result is also compared with the “residual minimization" method proposed in [@keshavarz2011imputing]. In [@keshavarz2011imputing], it is assumed that the observations of the solutions to the “forward" problems are completely available, namely in this scenario, both $y_{1:N}^{(1:M)}$ and $\mu_{1:N-1}^{(1:M)}$ are available. In order to make the comparison fair, in this numerical example, observations on both of the optimal trajectories and control input are used. This will not change the statistical consistency of the method. The result is shown in Fig. \[fig:statistical\_error1\].

![Our method vs. residual minimization[]{data-label="fig:statistical_error1"}](consistency_15_20.pdf){width="40.00000%"}

We denote the estimation of $Q$ by our method as $Q_{est}$ and the estimation by “residual minimization" [@keshavarz2011imputing] as $Q_{RM}$. In Fig. \[fig:statistical\_error1\], the blue line illustrates $\|Q_{est}-\bar{Q}\|_F=\|Q_{RM}-\bar{Q}\|_F$. As we can see from Fig. \[fig:statistical\_error1\], our method out-performs the residual-minimization method statistically.

Conclusion {#sec:conclusion}
==========

In this paper, we analyse the inverse optimal control problem for discrete-time LQR in finite-time horizons. We consider both the noiseless case (in which observations of the optimal trajectories are exact) and the noisy case (in which such observations are corrupted by additive noise). The well-posedness of the problem is first justified. In the noiseless case, we discuss identifiability of the problem, and provide sufficient conditions on the uniqueness of the solution. In the noisy case, we formulate the search for $Q$ as an optimization problem, and prove that such formulation is statistically consistent. Numerical examples shows our method has a better performance than that proposed in [@keshavarz2011imputing].
