\section{Stability Analysis}
\label{sec: stability}
In this section, we analyze the stability properties of the proposed pMHE iteration scheme (Algorithm \ref{alg: eta changes}). 
More specifically, we derive sufficient conditions on the Bregman distance~$D_\psi$ and on the step sizes $\eta_k^i$  for the global exponential stability (GES) of the estimation error 
\begin{align}
\label{EstimError}
 e_{k-N} \coloneqq x_{k-N} - \hat{x}_{k-N}^{j}  
\end{align}
for any $j \in \{0,...,\mathrm{it}(k)\}.$
 The following key result establishes the stability properties of the pMHE iteration scheme.
 \begin{theorem}
\label{prop: Stabadap}
 Consider  Algorithm \ref{alg: eta changes}    and suppose that Assumptions~\ref{ass: S closed}-\ref{ass: Bregman} hold. If we choose the Bregman distance $D_\psi$ such that
 \begin{align}
 \label{DiffDBoundadap}
D_\psi\left(\Phi_k(\mathbf{z}), \Phi_k(\mathbf{\hat{z}})\right) - D_\psi(\mathbf{z},\mathbf{\hat{z}})  \leq  - c \, \Vert \mathbf{z} - \mathbf{\hat{z}}   \Vert^2,
\end{align}
is satisfied for all $ \mathbf{z},\mathbf{\hat{z}} \in \mathbb{R}^{(N+1)n}$, where $ \Phi_k(\cdot) $ is defined in~\eqref{Adap: warm}, and if the step size at the $i$-th iteration and time instant $k$ satisfies 
\begin{align}
\label{stepSizeadap}
\eta_k^i \leq \frac{ \sigma }{L_f},
\end{align}
then  the estimation error \eqref{EstimError} is GES.
\end{theorem}

To prove this theorem, we require the following result.
  \begin{lem}
  \label{lem: Stabadap}
   Consider  Algorithm \ref{alg: eta changes}  and suppose Assumptions  \ref{ass: S closed}-\ref{ass: Bregman} hold true.   Then, for two consecutive iterates  $\mathbf{\hat{z}}_{k}^{i}$ and $\mathbf{\hat{z}}_{k}^{i+1}$
   at any time instant $k>0$, we obtain  
           \begin{align}
        \label{result: Stabadap}
D_\psi \big(\mathbf{z}_k, \mathbf{\hat{z}}_{k}^{i+1}  \big) & \leq D_\psi \big(\mathbf{z}_k,\mathbf{\hat{z}}_{k}^i\big) +      \frac{1}{2}  \big(\eta_k^i\, L_f -  \sigma \big) \left\Vert \mathbf{\hat{z}}_{k}^{i+1}   - \mathbf{\hat{z}}_{k}^i \right\Vert^2,
   \end{align} 
  where $i\in \{0,...,\mathrm{it}(k)\}$ and $\mathbf{z}_k $ is defined in \eqref{notation}. Moreover,  we have that for any $j\in\{0,...,\mathrm{it}(k)\}$
  \begin{align}
  \label{result: StabadapiT}  
D_\psi\big(\mathbf{z}_k, \mathbf{\hat{z}}_{k}^{j}\big) &\leq D_\psi\big(\mathbf{z}_k,  \mathbf{\bar{z}}_k \big)   \\& + \frac{1 }{2}  \sum_{i=0}^{j-1} \big(\eta_k^{i} \,L_f - \sigma  \big)\left\Vert  \mathbf{\hat{z}}_{k}^{i+1} -\mathbf{\hat{z}}_{k}^{i}   \right\Vert^2. \nonumber 
\end{align}
    \end{lem}
 The proof of Lemma~\ref{lem: Stabadap} can be found in  Appendix \ref{app:stabilityLemma}. We are now in a position to prove the stability result for the proposed pMHE scheme.


\begin{proof}[Proof of Theorem~\ref{prop: Stabadap}]
We first prove GES of the estimation error (\ref{EstimError}) with $j=\mathrm{j}(k)$. Let $V$ be a candidate Lyapunov function chosen as the Bregman distance  in (\ref{optAdap}), i.e.,
\begin{align}
 V\big(  \mathbf{z}_{k}, \mathbf{\hat{z}}^{\mathrm{j}(k)}_{k}\big)  = D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{\mathrm{j}(k)}_{k}\big).
\end{align}
Here, $\mathbf{z}_k$ denotes the true state with zero model residual as defined in (\ref{notation}) and $\mathbf{\hat{z}}^{\mathrm{j}(k)}_{k}$ the  selected  pMHE iterate   at time instant $k$. In the following, we show that $V $ satisfies the following conditions
\begin{subequations}
\begin{align}
\label{firstV}
\alpha_1 \big\Vert \mathbf{z}_{k}-\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k} \big\Vert^2 \leq  V\big(\mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big) \leq \alpha_2 \big\Vert \mathbf{z}_{k}-\mathbf{\hat{z}}^{\mathrm{j}(k)}_{k} \big\Vert^2 
\end{align}
and 
\begin{align}
\label{secondV}
\Delta V &\coloneqq V\big( \mathbf{z}_{k+1},\mathbf{\hat{z}}^{ \mathrm{j}(k+1)}_{k+1}\big) - V\big(  \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)   \\& \leq -\alpha_3 \big\Vert  \mathbf{z}_{k}-\mathbf{\hat{z}}^{\mathrm{j}(k)}_{k} \big\Vert^2  \nonumber
\end{align}
\end{subequations}
for some positive constants $\alpha_1$, $\alpha_2$ and $\alpha_3$. Note that, in view of (\ref{notation}), the error generated by the pMHE iteration scheme at time $k$ is given by 
\begin{align}
\mathbf{z}_{k}-\mathbf{\hat{z}}^{\mathrm{j}(k)}_{k}= \begin{bmatrix}
\vspace{0.1cm} x_{k-N}  \\[0.24em] \mathbf{0}_{[Nn]}  
\end{bmatrix} -  \begin{bmatrix}
 \hat{x}_{k-N}^{\mathrm{j}(k)}   \\[0.2em]  \mathbf{\hat{w}}^{ \mathrm{j}(k)}_{k}  
\end{bmatrix} =  \begin{bmatrix} e_{k-N}  \\[0.2em] -\mathbf{\hat{w}}^{ \mathrm{j}(k)}_{k} \end{bmatrix},
\end{align}
where $ \mathbf{\hat{w}}^{ \mathrm{j}(k)}_{k} \coloneqq \begin{bmatrix} \big(\hat{w}_{k-N}^{\mathrm{j}(k)}\big)^\top & \cdots & \big(\hat{w}_{k-1}^{\mathrm{j}(k)}\big)^\top   \end{bmatrix}^\top$.
By Assumption \ref{ass: Bregman},  (\ref{firstV}) follows with $\alpha_1 = \frac{\sigma}{2}$ and  $\alpha_2 = \frac{\gamma}{2}$. Furthermore, by (\ref{result: StabadapiT}) in Lemma \ref{lem: Stabadap}, we have
 \begin{align}
 \label{Vdiff1}
 \Delta V &=  D_\psi\big( \mathbf{z}_{k+1},\mathbf{\hat{z}}^{ \mathrm{j}(k+1)}_{k+1}\big)  - D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)  \\ 
& \leq D_\psi(\mathbf{z}_{k+1},  \mathbf{\bar{z}}_{k+1} )   - D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big) \nonumber\\& \quad+ \frac{1 }{2}  \sum_{i=0}^{\mathrm{j}(k+1)-1} \big(\eta_{k+1}^{i} \,L_f - \sigma  \big)\left\Vert  \mathbf{\hat{z}}_{k+1}^{i+1} -\mathbf{\hat{z}}_{k+1}^{i}   \right\Vert^2. \nonumber    
\end{align}
The condition on the step sizes given in (\ref{stepSizeadap}) implies that $
\eta_{k+1}^{i} \,L_f - \sigma \leq 0$ and hence,
\begin{align}
\label{VdiffsumNeg}
\frac{1 }{2}  \sum_{i=0}^{\mathrm{j}(k+1)-1} \big(\eta_{k+1}^{i} \,L_f - \sigma  \big)\left\Vert   \mathbf{\hat{z}}_{k+1}^{i+1} -\mathbf{\hat{z}}_{k+1}^{i} \right\Vert^2 \leq 0.
\end{align}
Moreover, since $ \mathbf{\bar{z}}_{k+1} = \Phi_k\big( \mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)$ and  
	\begin{align}
\Phi_k \left(\mathbf{z}_{k} \right) \! &=  \!  \begin{bmatrix}
   \! A\,  x_{k-N} +\!B\, u_{k-N}+\!L \left(y_{k-N} - C  x_{k-N}  \right)     \\\mathbf{0}_{[Nn]}  
     \end{bmatrix}\nonumber \\ 
     &=  \!  \begin{bmatrix}
   \! A\,  x_{k-N} +\!B\, u_{k-N}     \\\mathbf{0}_{[Nn]}  
     \end{bmatrix} = \mathbf{z}_{k+1} 
       \end{align}
in view of (\ref{Adap: warm}), we have 
 \begin{align}
 \label{diff21}
\Delta V 
&\leq    D_\psi(\mathbf{z}_{k+1},  \mathbf{\bar{z}}_{k+1} )   - D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)  \\
&= D_\psi\big(  \Phi_k\big(\mathbf{z}_{k} \big), \Phi_k\big( \mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)\big)-D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)   \nonumber.
\end{align}

 Given that the Bregman distance satisfies  (\ref{DiffDBoundadap}), we obtain \begin{align}
 \label{Vdiff2}
\Delta V 
&\leq - c \,\big\Vert \mathbf{z}_{k} -  \mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k} \big\Vert^2  \\
& =  - c \, \big\Vert  e_{k-N} \big\Vert^2  -c\, \big\Vert  \mathbf{\hat{w}}^{ \mathrm{j}(k)}_{k} \big\Vert^2\nonumber.
\end{align}
Hence, the candidate Lyapunov function satisfies (\ref{secondV}) with $\alpha_3 = c$ and the estimation error (\ref{EstimError}) with $j=\mathrm{j}(k)$ is GES. In the following, we show that GES holds also for any $j~\in~\{0,...,\mathrm{it}(k)\}$. Based on the previous Lyapunov analysis, we have that 
 \begin{align}
 & D_\psi \big( \mathbf{z}_{k} ,\mathbf{\hat{z}}^{\mathrm{j}(k )}_{k} \big)  - D_\psi\big( \mathbf{z}_{k-1},\mathbf{\hat{z}}^{ \mathrm{j}(k-1)}_{k-1} \big) \\
&\quad\leq   -  c \Vert \mathbf{z}_{k-1} - \mathbf{\hat{z}}^{ \mathrm{j}(k-1)}_{k-1} \Vert^2  \leq  -\frac{2c}{\gamma} D_\psi\big( \mathbf{z}_{k-1},\mathbf{\hat{z}}^{ \mathrm{j}(k-1)}_{k-1}\big) , \nonumber
\end{align} 
where the last inequality holds by the strong smoothness of the Bregman distance.
By defining $\beta_e \coloneqq 1 - \frac{2c}{\gamma}$, 
\begin{align}
0 \leq  D_\psi \big( \mathbf{z}_{k} ,\mathbf{\hat{z}}^{\mathrm{j}(k )}_{k} \big)  \leq \beta_e \, D_\psi\big( \mathbf{z}_{k-1},\mathbf{\hat{z}}^{ \mathrm{j}(k-1)}_{k-1}\big),
\end{align}
 where $\beta_e \in [0,1)$ since $D_\psi$ is nonnegative and $\frac{2c}{\gamma}>0$. Hence
\begin{align}
\label{toreplace}
 D_\psi\big(    \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}  \big) \leq \beta_e^{k} \, D_\psi\big( \mathbf{z}_{0},\mathbf{\bar{z}}_0\big).
\end{align}
We consider the difference 
$   D_\psi\big( \mathbf{z}_{k+1},\mathbf{\hat{z}}^{ j}_{k+1}\big)  - D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)
$
for any $j\in\{0,...,\mathrm{it}(k+1)\}$. By (\ref{result: StabadapiT}), we have  
  \begin{align}
 &D_\psi\big( \mathbf{z}_{k+1},\mathbf{\hat{z}}^{ j}_{k+1}\big)  - D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big) \\ &\quad\leq  D_\psi\big( \mathbf{z}_{k+1},\mathbf{\bar{z}}_{k+1}\big)  - D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big)\nonumber \\
 &\quad\leq - c \,\big\Vert \mathbf{z}_{k} -  \mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k} \big\Vert^2 \nonumber,
\end{align}
where the last inequality holds in view of (\ref{diff21}) and (\ref{Vdiff2}). Hence, by using $\beta_e$ again, we have for any $j\in\{0,...,\mathrm{it}(k+1)\}$
\begin{align}
  D_\psi \big( \mathbf{z}_{k+1} ,\mathbf{\hat{z}}^{j}_{k+1} \big)  \leq \beta_e \, D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big).
\end{align} 
By (\ref{toreplace}), we obtain  $\forall k>0$
\begin{align}
  D_\psi \big( \mathbf{z}_{k+1} ,\mathbf{\hat{z}}^{j}_{k+1} \big)  \leq \beta_e^{k+1} \, D_\psi\big( \mathbf{z}_{0},\mathbf{\bar{z}}_0\big).
\end{align}
By the strong smoothness and convexity of $D_\psi$, we therefore get the following GES property of the estimation error 
\begin{align}
\label{GESproperty1}
  \big\Vert \mathbf{z}_k - \mathbf{\hat{z}}_{k}^{j} \big\Vert^2   &\leq    \frac{\gamma}{\sigma}\beta_e^{k} \,  \big\Vert \mathbf{z}_{0}-\mathbf{\bar{z}}_0\big\Vert^2.
\end{align}
\end{proof}
The theorem implies that stability of the estimation error is guaranteed 
for any iterate and is
independent  of which iterate $\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}$ is picked from the sequence  $\big\lbrace  \mathbf{\hat{z}}^{0}_{k}, \cdots,\mathbf{\hat{z}}^{\mathrm{it}(k)}_{k} \big\rbrace $
in Step 7 in Algorithm \ref{alg: eta changes}, as well as of the number of iterations $\mathrm{it}(k)$. Hence, the algorithm generates convergent estimates after each optimizer update step and can be therefore considered as an  anytime  MHE algorithm.   Moreover, selecting $\eta_k^i = \frac{\sigma}{L_f}$, for all $i$ and $k$, is sufficient for ensuring GES. \rev{In addition, this guarantee holds independently of the choice of the horizon length $N\in \mathbb{N}_+$ and for any convex stage cost satisfying Assumptions \ref{ass: f convex} and \ref{ass: f strngSmooth}. This includes for instance quadratic functions and the Huber penalty function,  which allows to handle the important case of measurement outliers.} 

 It is worth pointing out that detectability of the pair $(A,C)$ implies that we can find  suitable choices of the Bregman distance $D_\psi$  that fulfill condition (\ref{DiffDBoundadap}). In particular, let
\begin{align}
\label{quadBregm}
D_\psi(\mathbf{z}_1,\mathbf{z}_2)  = \frac{1}{2}  \Vert x_1 -x_2 \Vert^2_P + \frac{1}{2}  \Vert \mathbf{w}_1 -\mathbf{w}_2 \Vert^2_W
\end{align}
with $\mathbf{z}_1= \begin{bmatrix}
 x_1^\top & \mathbf{w}_1^\top  \end{bmatrix}^\top$,  $\mathbf{z}_2=\begin{bmatrix}
 x_2^\top & \mathbf{w}_2^\top  \end{bmatrix}^\top$, $x_1, x_2 \in \mathbb{R}^n$, $\mathbf{w}_1, \mathbf{w}_2 \in \mathbb{R}^{Nn}$, and $P \in \mathbb{S}_{+\!\!+}^n$, $W \in \mathbb{S}_{+\!\!+}^{Nn}$. Using (\ref{Adap: warm}) and a simple algebraic manipulation, we have that
 \begin{align}
 \label{Bregman difference }
 &D_\psi(\Phi_k(\mathbf{z}_1), \Phi_k(\mathbf{z}_2)) - D_\psi(\mathbf{z}_1,\mathbf{z}_2) \\ & \qquad=     \frac{1}{2} \left\Vert (A-LC) (x_1 - x_2)  \right\Vert^2_P - \frac{1}{2} \left\Vert x_1 - x_2   \right\Vert^2_P \nonumber \\ &\qquad \qquad+ \frac{1}{2} \left\Vert \mathbf{0} \right\Vert^2_W - \frac{1}{2} \left\Vert \mathbf{w}_1 - \mathbf{w}_2 \right\Vert^2_W \nonumber.
 \end{align}
 Hence, satisfying (\ref{DiffDBoundadap}) amounts to designing  the weight matrix $P \in \mathbb{S}_{+\!\!+}^n$ such that the linear matrix inequality  (LMI) 
\begin{align}
\label{LMIBregman}
(A-LC )^ \top P \, (A-LC) -P \prec - Q  
\end{align} 
holds for some $Q \in \mathbb{S}_{+\!\!+}^n$. This is because when (\ref{LMIBregman}) holds,~(\ref{Bregman difference }) yields 
 \begin{align}
 &D_\psi(\Phi_k(\mathbf{z}_1), \Phi_k(\mathbf{z}_2)) - D_\psi(\mathbf{z}_1,\mathbf{z}_2) \\ & \qquad\leq  - \frac{\lambda_{\min}(Q)}{2} \left\Vert x_1 - x_2   \right\Vert^2 - \frac{\lambda_{\min}(W)}{2} \left\Vert \mathbf{w}_1 - \mathbf{w}_2 \right\Vert^2 \nonumber \\
 & \qquad \leq -c \, \Vert \mathbf{z}_1 - \mathbf{z}_2 \Vert^2  \nonumber
 \end{align}
 where $c = \frac{1}{2} \min\lbrace \lambda_{\min}(Q), \lambda_{\min}(W) \rbrace $.
{"config": "arxiv", "file": "2006.14303/stability.tex"}