Based on Lemma 10, we have the following corollaries, which will be used in
different settings in later derivations.

######  Corollary 2.

Consider two matrices $\bm{\mathcal{A}}$ and
$\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt$ with
$\|{\bm{\mathcal{A}}-\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt}\|\leq\epsilon_{\bm{\mathcal{A}}}$.
Suppose there exists a pair $\\{\rho,\tau\\}$ such that for all
$k\in\mathbb{N}$, $\|{\bm{\mathcal{A}}^{k}}\|\leq\tau\rho^{k}$. Then, we have
$\|{\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}}\|\leq\tau\left(\tau\epsilon_{\bm{\mathcal{A}}}+\rho\right)^{t}$
and
$\|{\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}-\bm{\mathcal{A}}^{t}}\|\leq\tau^{2}t\left(\tau\epsilon_{\bm{\mathcal{A}}}+\rho\right)^{t-1}\epsilon_{\bm{\mathcal{A}}}.$

######  Corollary 3.

Consider two sets of scalars $a_{1},\dots,a_{s}$ and
$\hat{a}_{1},\dots,\hat{a}_{s}$ with $|a_{i}{-}\hat{a}_{i}|{<}\epsilon_{a}$
and $|a_{i}|{<}\bar{a}$ for all $i{\in}[s]$. Then, for all $t$ and any
sequence $\sigma_{1:t}{\in}[s]^{t}$, we have
$|\prod_{h=1}^{t}\hat{a}_{\sigma_{h}}|\leq(\epsilon_{a}+\bar{a})^{t}$ and
$|\prod_{h=1}^{t}\hat{a}_{\sigma_{h}}-\prod_{h=1}^{t}a_{\sigma_{h}}|\leq
t(\epsilon_{a}+\bar{a})^{t-1}\epsilon_{a}.$

The next result considers the evolution of state $\mathbf{x}_{t}$ in the mean-
square sense for autonomous MJSs.

######  Lemma 11 (Lemma 9 in [11]).

Consider MJS$(\mathbf{A}_{1:s},0,\mathbf{T})$ and define matrix
$\bm{\mathcal{A}}{\in}\IfStrEq{sn^{2}}{1}{\mathbb{R}^{sn^{2}}}{\mathbb{R}^{sn^{2}\mathsf{x}\mskip
1.0musn^{2}}}$ with its $ij$-th $n^{2}{\times}n^{2}$ block given by
$[\bm{\mathcal{A}}]_{ij}{:=}\mathbf{T}(j,i){\cdot}\mathbf{A}_{j}{\otimes}\mathbf{A}_{j}$.
Let
${\bm{\Sigma}}_{t}^{(i)}{:=}\mathbb{E}[\mathbf{x}_{t}\mathbf{x}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\mathbf{1}_{\\{\omega_{t}=i\\}}]$
and
$\mathbf{s}_{t}{:=}[\textup{{vec}}({\bm{\Sigma}}_{t}^{(1)})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},\dots,\textup{{vec}}({\bm{\Sigma}}_{t}^{(s)})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$.
Then, $\mathbf{s}_{t}=\bm{\mathcal{A}}^{t}\mathbf{s}_{0}.$

Recall in Section 5, for $\Sigma$, i.e.,
MJS($\mathbf{A}_{1:s},\mathbf{B}_{1:s},\mathbf{T}$), we define the augmented
state matrix
$\bm{\mathcal{A}}\in\IfStrEq{sn^{2}}{1}{\mathbb{R}^{sn^{2}}}{\mathbb{R}^{sn^{2}\mathsf{x}\mskip
1.0musn^{2}}}$ with its $ij$-th $n^{2}\times n^{2}$ block given by
$[\bm{\mathcal{A}}]_{ij}:=\mathbf{T}(j,i)\cdot\mathbf{A}_{j}\otimes\mathbf{A}_{j}$;
and for any $\rho\geq\rho(\bm{\mathcal{A}})$ and all $k\in\mathbb{N}$, we have
$\|{\bm{\mathcal{A}}^{k}}\|\leq\tau\rho^{k}$. The next lemma is regarding the
augmentation of two MJS with the same $\mathbf{A}$ matrix.

######  Lemma 12.

Construct matrix
$\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt\in\IfStrEq{4sn^{2}}{1}{\mathbb{R}^{4sn^{2}}}{\mathbb{R}^{4sn^{2}\mathsf{x}\mskip
1.0mu4sn^{2}}}$ with its $ij$-th $4n^{2}\times 4n^{2}$ block given by
$[\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt]_{ij}:=\mathbf{T}(j,i)\cdot\begin{bmatrix}\mathbf{A}_{j}&\\\
&\mathbf{A}_{j}\end{bmatrix}\otimes\begin{bmatrix}\mathbf{A}_{j}&\\\
&\mathbf{A}_{j}\end{bmatrix}$. Then, for all $k\in\mathbb{N}$,
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{k}}\|\leq\tau\rho^{k}$.

To see this result, first notice that there exists a permutation matrix
$\mathbf{P}$ such that
$\mathbf{P}\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt\mathbf{P}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}=\mathbf{I}_{4}\otimes\bm{\mathcal{A}}$,
where $\mathbf{I}_{4}$ denotes the $4\times 4$ identity matrix. This gives
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{k}}\|=\|{\bm{\mathcal{A}}^{k}}\|$
and shows the claim.

To prove the result in Theorem 3, we first consider the simplified autonomous
case but with potentially different initial states $\mathbf{x}_{0}$ and
$\hat{\mathbf{x}}_{0}$.

######  Proposition 1.

Consider the setup in Theorem 3 except that $\mathbf{u}_{t}=0$ for all $t$,
and $\mathbf{x}_{0}$ and $\hat{\mathbf{x}}_{0}$ can be different such that
$\|{\mathbf{x}_{0}-\hat{\mathbf{x}}_{0}}\|\leq\epsilon_{0}$ for some
$\epsilon_{0}\geq 0$. For perturbation, assume
$\epsilon_{\mathbf{A}}\leq\min\\{\bar{A},\frac{1-\rho}{6\tau\overset{{}}{\bar{A}}\|{\mathbf{T}}\|}\\}$.
Then, $\mathbb{E}[\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|]\leq
4\sqrt{n\sqrt{s}}\tau\rho_{0}^{\frac{t-1}{2}}\big{(}\|{\mathbf{x}_{0}}\|\sqrt{t\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}}+\sqrt{(\|{\mathbf{x}_{0}}\|+\epsilon_{0})\epsilon_{0}}\,\big{)}.$

###### Proof.

First, we construct two autonomous switched systems:

$\check{\Pi}:=\left\\{\begin{matrix}\check{\mathbf{x}}_{t+1}=\check{\mathbf{A}}_{\check{\omega}_{t}}\check{\mathbf{x}}_{t}\\\
\check{\omega}_{t}=\omega_{t},\
\end{matrix}\right.,\quad\bar{\Pi}:=\left\\{\begin{matrix}\bar{\mathbf{x}}_{t+1}=\bar{\mathbf{A}}_{\bar{\omega}_{t}}\bar{\mathbf{x}}_{t}\\\
\bar{\omega}_{t}=\omega_{t},\ \end{matrix}\right.$ (28)

where for $i{\in}[s]$ (suppose $i{\in}\Omega_{k}$),
$\check{\mathbf{A}}_{i}:=\begin{bmatrix}\mathbf{A}_{i}&\\\
&\mathbf{A}_{i}\end{bmatrix},\bar{\mathbf{A}}_{i}:=\begin{bmatrix}\mathbf{A}_{i}&\\\
&\hat{\mathbf{A}}_{k}\end{bmatrix}.$ Since $\omega_{t}$ of $\Sigma$ follows
Markov chain $\mathbf{T}$, systems $\check{\Pi}$ and $\bar{\Pi}$ can be viewed
as MJS$(\check{\mathbf{A}}_{1:s},0,\check{\mathbf{T}})$ and
MJS$(\bar{\mathbf{A}}_{1:s},0,\bar{\mathbf{T}})$ respectively with
$\check{\mathbf{T}}=\bar{\mathbf{T}}=\mathbf{T}$. We then define observations
for $\check{\Pi}$ and $\bar{\Pi}$:
$\check{\mathbf{y}}_{t}=\check{\mathbf{C}}\check{\mathbf{x}}_{t}$ and
$\bar{\mathbf{y}}_{t}=\bar{\mathbf{C}}\bar{\mathbf{x}}_{t}$ where
$\check{\mathbf{C}}=\bar{\mathbf{C}}=[\mathbf{I}_{n},-\mathbf{I}_{n}]$. We set
their initial states as
$\check{\mathbf{x}}_{0}=[\mathbf{x}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},\mathbf{x}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$,
$\bar{\mathbf{x}}_{0}=[\mathbf{x}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},\hat{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$
where $\mathbf{x}_{0}$ and $\hat{\mathbf{x}}_{0}$ are the initial states of
$\Sigma$ and $\hat{\Sigma}$ respectively.

By construction, we have, for all t,
$\check{\mathbf{x}}_{t}{=}[\mathbf{x}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},\mathbf{x}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$
and
$\bar{\mathbf{x}}_{t}{=}[\mathbf{x}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},\hat{\mathbf{x}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$,
thus $\check{\mathbf{y}}_{t}{=}0$ and
$\bar{\mathbf{y}}_{t}{=}\mathbf{x}_{t}{-}\hat{\mathbf{x}}_{t}$. Define
$\check{{\bm{\Sigma}}}_{t}:=\mathbb{E}[\check{\mathbf{x}}_{t}\check{\mathbf{x}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]$
and
$\bar{{\bm{\Sigma}}}_{t}:=\mathbb{E}[\bar{\mathbf{x}}_{t}\bar{\mathbf{x}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]$,
then we have $\mathbb{E}[\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|^{2}]{=}$
$\mathbb{E}[\bar{\mathbf{y}}_{t}\bar{\mathbf{y}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]{=}\mathbb{E}[\bar{\mathbf{y}}_{t}\bar{\mathbf{y}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]{-}\mathbb{E}[\check{\mathbf{y}}_{t}\check{\mathbf{y}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]{=}\textup{{tr}}(\bar{\mathbf{C}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bar{\mathbf{C}}\bar{{\bm{\Sigma}}}_{t}){-}\textup{{tr}}(\check{\mathbf{C}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\check{\mathbf{C}}\check{{\bm{\Sigma}}}_{t}){=}$
$\textup{{tr}}(\bar{\mathbf{C}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bar{\mathbf{C}}(\bar{{\bm{\Sigma}}}_{t}-\check{{\bm{\Sigma}}}_{t})).$
Since
$\bar{\mathbf{C}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bar{\mathbf{C}}\succeq
0$, we further have

$\mathbb{E}[\|{\mathbf{x}_{t}{-}\hat{\mathbf{x}}_{t}}\|^{2}]\leq\textup{{tr}}(\bar{\mathbf{C}}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\bar{\mathbf{C}})\|{\bar{{\bm{\Sigma}}}_{t}{-}\check{{\bm{\Sigma}}}_{t}}\|=2n\|{\bar{{\bm{\Sigma}}}_{t}{-}\check{{\bm{\Sigma}}}_{t}}\|.$
(29)

Let
$\check{{\bm{\Sigma}}}_{t}^{(i)}:=\mathbb{E}[\check{\mathbf{x}}_{t}\check{\mathbf{x}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\mathbf{1}_{\\{\check{\omega}_{t}=i\\}}]$,
$\bar{{\bm{\Sigma}}}_{t}^{(i)}:=\mathbb{E}[\bar{\mathbf{x}}_{t}\bar{\mathbf{x}}_{t}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\mathbf{1}_{\\{\bar{\omega}_{t}=i\\}}]$,
$\check{\mathbf{s}}_{t}:=[\textup{{vec}}(\check{{\bm{\Sigma}}}_{t}^{(1)})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},\dots,\textup{{vec}}(\check{{\bm{\Sigma}}}_{t}^{(s)})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$
and
$\bar{\mathbf{s}}_{t}:=[\textup{{vec}}(\bar{{\bm{\Sigma}}}_{t}^{(1)})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}},\dots$
$,\textup{{vec}}(\bar{{\bm{\Sigma}}}_{t}^{(s)})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$.
Note that
$\textup{{vec}}(\check{{\bm{\Sigma}}}_{t})=[\mathbf{I}_{4n^{2}},\dots,\mathbf{I}_{4n^{2}}]\check{\mathbf{s}}_{t}$
and
$\textup{{vec}}(\bar{{\bm{\Sigma}}}_{t})=[\mathbf{I}_{4n^{2}},\dots,\mathbf{I}_{4n^{2}}]\bar{\mathbf{s}}_{t}$,
thus we have
$\|{\check{{\bm{\Sigma}}}_{t}-\bar{{\bm{\Sigma}}}_{t}}\|\leq\|{\check{{\bm{\Sigma}}}_{t}-\bar{{\bm{\Sigma}}}_{t}}\|_{\textup{F}}=\|{\textup{{vec}}(\check{{\bm{\Sigma}}}_{t}-\bar{{\bm{\Sigma}}}_{t})}\|\leq\sqrt{s}\|{\check{\mathbf{s}}_{t}-\bar{\mathbf{s}}_{t}}\|.$
Plugging this into (29), we have

$\mathbb{E}[\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|^{2}]\leq
2n\sqrt{s}\|{\check{\mathbf{s}}_{t}-\bar{\mathbf{s}}_{t}}\|.$ (30)

By Lemma 11, we have
$\check{\mathbf{s}}_{t}=\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}\check{\mathbf{s}}_{0}$
and
$\bar{\mathbf{s}}_{t}=\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}\bar{\mathbf{s}}_{0}$,
where
$\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt{\in}\IfStrEq{4sn^{2}}{1}{\mathbb{R}^{4sn^{2}}}{\mathbb{R}^{4sn^{2}\mathsf{x}\mskip
1.0mu4sn^{2}}}$ is constructed such that its $ij$-th $4n^{2}\times 4n^{2}$
block given by
$[\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt]_{ij}=\check{\mathbf{T}}(j,i)\check{\mathbf{A}}_{j}\otimes\check{\mathbf{A}}_{j}$,
and $\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt$ is constructed similarly.
By triangle inequality, we further have

$\mathbb{E}[\|{\mathbf{x}_{t}{-}\hat{\mathbf{x}}_{t}}\|^{2}]{\leq}2n\sqrt{s}(\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}{-}\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}}\|\|{\check{\mathbf{s}}_{0}}\|{+}\|{\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}}\|\|{\check{\mathbf{s}}_{0}{-}\bar{\mathbf{s}}_{0}}\|)$
(31)

To bound $\mathbb{E}[\|{\mathbf{x}_{t}{-}\hat{\mathbf{x}}_{t}}\|^{2}]$, we
seek to bound the terms on the RHS individually. Since
$\check{\mathbf{s}}_{0}=[\textup{{vec}}(\check{\mathbf{x}}_{0}\check{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\mathbb{P}(\omega_{t}=1),\dots,\textup{{vec}}(\check{\mathbf{x}}_{0}\check{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}\cdot\mathbb{P}(\omega_{t}=s)]^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}$,
we have
$\|{\check{\mathbf{s}}_{0}}\|=\|{\check{\mathbf{x}}_{0}\check{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}}\|_{\textup{F}}\cdot(\sum_{i\in[s]}\mathbb{P}(\omega_{t}=i)^{2})^{\frac{1}{2}}\leq\|{\check{\mathbf{x}}_{0}\check{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}}\|_{\textup{F}}=2\|{\mathbf{x}_{0}}\|^{2}$.
Similarly, we have
$\|{\check{\mathbf{s}}_{0}-\bar{\mathbf{s}}_{0}}\|\leq\|{\bar{\mathbf{x}}_{0}\bar{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}-\check{\mathbf{x}}_{0}\check{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}}\|_{\textup{F}}\leq\|{\bar{\mathbf{x}}_{0}(\bar{\mathbf{x}}_{0}-\check{\mathbf{x}}_{0})^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}}\|_{\textup{F}}+\|{(\bar{\mathbf{x}}_{0}-\check{\mathbf{x}}_{0})\check{\mathbf{x}}_{0}^{\mathchoice{\raisebox{0.0pt}{$\displaystyle\intercal$}}{\raisebox{0.0pt}{$\textstyle\intercal$}}{\raisebox{0.0pt}{$\scriptstyle\intercal$}}{\raisebox{0.0pt}{$\scriptscriptstyle\intercal$}}}}\|_{\textup{F}}\leq\sqrt{2}(\sqrt{3}\|{\mathbf{x}_{0}}\|+\epsilon_{0})\epsilon_{0}$.

To bound $\|{\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}}\|$ and
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}{-}\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}}\|$,
we first evaluate
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt-\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt}\|$.
Define
${\bm{\Delta}}_{i}:=\check{\mathbf{A}}_{i}\otimes\check{\mathbf{A}}_{i}-\bar{\mathbf{A}}_{i}\otimes\bar{\mathbf{A}}_{i}$
for all $i$, and block diagonal matrix
${\bm{\Delta}}\in\IfStrEq{sn^{2}}{1}{\mathbb{R}^{sn^{2}}}{\mathbb{R}^{sn^{2}\mathsf{x}\mskip
1.0musn^{2}}}$ such that the $i$th $n^{2}{\times}n^{2}$ block is given by
${\bm{\Delta}}_{i}$. Then one can verify that
$\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt-\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt=(\mathbf{T}\otimes\mathbf{I}_{n^{2}}){\bm{\Delta}}$,
which gives
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt-\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt}\|\leq\|{\mathbf{T}}\|\max_{i}\|{{\bm{\Delta}}_{i}}\|$.
For $\|{{\bm{\Delta}}_{i}}\|$, we have
$\|{{\bm{\Delta}}_{i}}\|\leq\|{\check{\mathbf{A}}_{i}}\|\|{\check{\mathbf{A}}_{i}-\bar{\mathbf{A}}_{i}}\|+\|{\check{\mathbf{A}}_{i}-\bar{\mathbf{A}}_{i}}\|\|{\bar{\mathbf{A}}_{i}}\|$.
It is easy to see $\|{\check{\mathbf{A}}_{i}}\|\leq\bar{A}$,
$\|{\check{\mathbf{A}}_{i}-\bar{\mathbf{A}}_{i}}\|\leq\epsilon_{\mathbf{A}}$,
and $\|{\bar{\mathbf{A}}_{i}}\|\leq$ $\bar{A}+\epsilon_{\mathbf{A}}\leq
2\bar{A}$. These give
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt-\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt}\|\leq
3\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}$. From Lemma 12, we know for all
$k\in\mathbb{N}$,
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{k}}\|\leq\tau\rho^{k}$.
Then, according to Corollary 2, we have
$\|{\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}}\|\leq\tau(3\tau\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}+\rho)^{t}\leq\tau\rho_{0}^{t}$
and
$\|{\check{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}-\bar{\bm{\mathcal{A}}\phantom{a}}\kern-5.0pt^{t}}\|\leq
3t(3\tau\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}+\rho)^{t-1}\tau^{2}\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}\leq
3t\rho_{0}^{t-1}\tau^{2}\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}$, where
the premise
$\epsilon_{\mathbf{A}}{\leq}\frac{1-\rho}{6\tau\bar{A}\|{\mathbf{T}}\|}$ and
notation $\rho_{0}{:=}\frac{1+\rho}{2}$ are used.

Finally, plugging in the bounds we just derived for each term on the RHS of
(31) back, we have
$\mathbb{E}[\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|]\leq\sqrt{\mathbb{E}[\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|^{2}]}\leq
4\sqrt{n\sqrt{s}}\tau\rho_{0}^{\frac{t-1}{2}}\big{(}\|{\mathbf{x}_{0}}\|\sqrt{t\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}}+\sqrt{(\|{\mathbf{x}_{0}}\|+\epsilon_{0})\epsilon_{0}}\,\big{)}$,
which concludes the proof. ∎

###### Main Proof for Theorem 3.

We first decompose $\mathbf{x}_{t}$ in terms of the contribution from
$\mathbf{x}_{0}$, $\mathbf{u}_{0:t-1}$: define
$\mathbf{x}_{t}^{(0^{\prime})}{:=}\big{(}\prod_{h=0}^{t-1}\mathbf{A}_{\omega_{h}}\big{)}\mathbf{x}_{0}$,
for $l{=}0,\dots,t-2$, define
$\mathbf{x}_{t}^{(l)}{:=}\big{(}\prod_{h=l+1}^{t-1}\mathbf{A}_{\hat{\omega}_{h}}\big{)}\mathbf{B}_{\omega_{l}}\mathbf{u}_{l}$,
and $\mathbf{x}_{t}^{(t-1)}{:=}\mathbf{B}_{\omega_{t-1}}$ $\mathbf{u}_{t-1}$.
Then it is easy to see
$\mathbf{x}_{t}{=}\mathbf{x}_{t}^{(0^{\prime})}{+}\sum_{l=0}^{t-1}\mathbf{x}_{t}^{(l)}$.
Similarly, we define $\hat{\mathbf{x}}_{t}^{(0^{\prime})}$ and
$\hat{\mathbf{x}}_{t}^{(l)}$ for $\hat{\mathbf{x}}_{t}$ such that
$\hat{\mathbf{x}}_{t}=\hat{\mathbf{x}}_{t}^{(0^{\prime})}+\sum_{l=0}^{t-1}\hat{\mathbf{x}}_{t}^{(l)}$.
According to Proposition 1, we have

$\mathbb{E}[\|{\mathbf{x}_{t}^{(0^{\prime})}{-}\hat{\mathbf{x}}_{t}^{(0^{\prime})}}\|]{\leq}4{\textstyle\sqrt{n\sqrt{s}}}\tau\rho_{0}^{\frac{t-1}{2}}{\textstyle\sqrt{t\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}}}\|{\mathbf{x}_{0}}\|.$
(32)

Note that $\mathbf{x}_{t}^{(l)}$ and $\hat{\mathbf{x}}_{t}^{(l)}$ can be
viewed as the states at time $t-l$ with respective initial states
$\mathbf{B}_{\omega_{l}}\mathbf{u}_{l}$ and
$\hat{\mathbf{B}}_{\omega_{l}}\mathbf{u}_{l}$ and zero inputs. Therefore,
applying Proposition 1 again, we have

$\mathbb{E}[\|{\mathbf{x}_{t}^{(l)}-\hat{\mathbf{x}}_{t}^{(l)}}\|]\leq
4{\textstyle\sqrt{n\sqrt{s}}}\tau\rho_{0}^{\frac{t-l-1}{2}}{\textstyle\sqrt{\bar{B}}}\bar{u}\\\
\cdot\big{(}{\textstyle\sqrt{(t-l-1)\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}}}+\sqrt{2\epsilon_{\mathbf{B}}}\big{)},$
(33)

where the premise $\epsilon_{\mathbf{B}}{\leq}\bar{B}$ is applied. With (32)
and (33), we have
$\mathbb{E}[\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|]\leq\mathbb{E}[\|{\mathbf{x}_{t}^{(0^{\prime})}-\hat{\mathbf{x}}_{t}^{(0^{\prime})}}\|]+\sum_{l=0}^{t-1}$
$\mathbb{E}[\|{\mathbf{x}_{t}^{(l)}{-}\hat{\mathbf{x}}_{t}^{(l)}}\|]{\leq}4\sqrt{n\sqrt{s}}\tau\rho_{0}^{\frac{t-1}{2}}\sqrt{t\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}}\|{\mathbf{x}_{0}}\|+4\sqrt{n\sqrt{s}\bar{B}}\tau\bar{u}(\frac{\sqrt{\rho_{0}}}{(1-\sqrt{\rho_{0}})^{2}}\sqrt{\bar{A}\|{\mathbf{T}}\|\epsilon_{\mathbf{A}}}+\frac{\sqrt{2}}{1-\sqrt{\rho_{0}}}\sqrt{\epsilon_{\mathbf{B}}})$,
which concludes the proof. ∎

##  13 Approximation with Unif. Stability — Proof for Theorem 4

###### Proof for Theorem 4 (T1).

$\mathbf{x}_{t}$ and $\hat{\mathbf{x}}_{t}$ can be decomposed as:
$\mathbf{x}_{t}=\big{(}\prod_{h=0}^{t-1}\mathbf{A}_{\omega_{h}}\big{)}\mathbf{x}_{0}+$
$\sum_{t^{\prime}=0}^{t-2}\big{(}\prod_{h=t^{\prime}+1}^{t-1}\mathbf{A}_{\omega_{h}}\big{)}\mathbf{B}_{\omega_{t^{\prime}}}\mathbf{u}_{t^{\prime}}{+}\mathbf{B}_{\omega_{t-1}}\mathbf{u}_{t-1},$
$\hat{\mathbf{x}}_{t}{=}\big{(}\prod_{h=0}^{t-1}$
$\hat{\mathbf{A}}_{\hat{\omega}_{h}}\big{)}\hat{\mathbf{x}}_{0}+\sum_{t^{\prime}=0}^{t-2}\big{(}\prod_{h=t^{\prime}+1}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}}\big{)}\hat{\mathbf{B}}_{\hat{\omega}_{t^{\prime}}}\hat{\mathbf{u}}_{t^{\prime}}+\hat{\mathbf{B}}_{\hat{\omega}_{t-1}}\hat{\mathbf{u}}_{t-1}.$
Since in Algorithm 1 we let
$\hat{\mathbf{A}}_{k}{=}|\hat{\Omega}_{k}|^{\mskip-1.0mu\scalebox{1.5}[0.75]{-}\mskip-1.0mu1}\sum_{i\in\hat{\Omega}_{k}}\mathbf{A}_{i}$,
and the premise gives $\hat{\Omega}_{1:r}{=}\Omega_{1:r}$, we have
$\|{\hat{\mathbf{A}}_{k}-\mathbf{A}_{i}}\|{\leq}$ $\epsilon_{\mathbf{A}}$ for
all $i\in\Omega_{k}$. Based on the mode synchrony Setup S2, i.e.,
$\omega_{t}\in\Omega_{\hat{\omega}_{t}}$, we further have
$\|{\hat{\mathbf{A}}_{\hat{\omega}_{t}}{-}\mathbf{A}_{\omega_{t}}}\|\leq\epsilon_{\mathbf{A}}$.
Similarly, we obtain
$\|{\hat{\mathbf{B}}_{\hat{\omega}_{t}}{-}\mathbf{B}_{\omega_{t}}}\|\leq\epsilon_{\mathbf{B}}$.
Then, by Lemma 10 : (i)
$\|{\prod_{h=t^{\prime}+1}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}}}\|{\leq}\kappa(\kappa\epsilon_{\mathbf{A}}+\xi)^{t-t^{\prime}-1}$
and (ii) $\|\prod_{h=t^{\prime}+1}^{t-1}\mathbf{A}_{\omega_{h}}$
${-}\prod_{h=t^{\prime}+1}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}}\|{\leq}\kappa^{2}(t{-}t^{\prime}{-}1)(\kappa\epsilon_{\mathbf{A}}+\xi)^{t-t^{\prime}-2}\epsilon_{\mathbf{A}}.$

With (i) and (ii), and the fact that
$\prod_{h=t^{\prime}+1}^{t-1}\mathbf{A}_{\omega_{h}}\mathbf{B}_{\omega_{t^{\prime}}}-$
$\prod_{h=t^{\prime}+1}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}}\hat{\mathbf{B}}_{\hat{\omega}_{t^{\prime}}}{=}$
$\big{(}\prod_{h=t^{\prime}+1}^{t-1}\mathbf{A}_{\omega_{h}}{-}\prod_{h=t^{\prime}+1}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}}\big{)}\hat{\mathbf{B}}_{\hat{\omega}_{t^{\prime}}}$
$-\big{(}\prod_{h=t^{\prime}+1}^{t-1}\mathbf{A}_{\omega_{h}}\big{)}$
$(\hat{\mathbf{B}}_{\hat{\omega}_{t^{\prime}}}-\mathbf{B}_{\omega_{t^{\prime}}})$,
we have

${\textstyle\|{\prod_{h=t^{\prime}+1}^{t-1}\mathbf{A}_{\omega_{h}}\mathbf{B}_{\omega_{t^{\prime}}}{-}\prod_{h=t^{\prime}+1}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}}\hat{\mathbf{B}}_{\hat{\omega}_{t^{\prime}}}}\|}\leq\kappa\xi^{t-t^{\prime}-1}\epsilon_{\mathbf{B}}\\\
+\kappa^{2}(t-t^{\prime}-1)(\kappa\epsilon_{\mathbf{A}}+\xi)^{t-t^{\prime}-2}(\bar{B}+\epsilon_{\mathbf{B}})\epsilon_{\mathbf{A}}.$
(34)

According to Setup S1, $\Sigma$ and $\hat{\Sigma}$ have the same initial
states and inputs. Then, applying triangle inequality to the difference
$\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|$, we have

$\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|\leq\kappa^{2}t(\kappa\epsilon_{\mathbf{A}}+\xi)^{t-1}\|{\mathbf{x}_{0}}\|\epsilon_{\mathbf{A}}\\\
+\kappa^{2}\frac{1+t(\kappa\epsilon_{\mathbf{A}}+\xi)^{t}}{1-\kappa\epsilon_{\mathbf{A}}-\xi}(\bar{B}+\epsilon_{\mathbf{B}})\bar{u}\epsilon_{\mathbf{A}}+\frac{\kappa}{1-\xi}\bar{u}\epsilon_{\mathbf{B}},$
(35)

where the following facts are implicitly used: (i) $\kappa\geq 1$ by
definition; (ii) $\kappa\epsilon_{\mathbf{A}}+\xi<1$ according to the premise.
Finally, note that we assume perturbation
$\epsilon_{\mathbf{A}}\leq\frac{1-\xi}{2\kappa}$ and
$\epsilon_{\mathbf{B}}\leq\bar{B}$, we have
$\|{\mathbf{x}_{t}-\hat{\mathbf{x}}_{t}}\|\leq
t\xi_{0}^{t-1}\kappa^{2}\|{\mathbf{x}_{0}}\|\epsilon_{\mathbf{A}}+\frac{2(1+t\xi_{0}^{t})\kappa^{2}\bar{B}\bar{u}}{1-\xi_{0}}\epsilon_{\mathbf{A}}+\frac{\kappa\bar{u}}{1-\xi}\epsilon_{\mathbf{B}},$
which concludes the proof. ∎

###  13.1 Proof for Theorem 4 (T2)

To ease the proof exposition, we first define a few notations and concepts.
For the original system $\Sigma$, fixing the initial state $\mathbf{x}_{0}$
and input sequence $\mathbf{u}_{0:t-1}$, there can be at most $s^{t}$ possible
$\mathbf{x}_{t}$, each of which correspond to one possible mode switching
sequence $\omega_{0:t-1}\in[s]^{t}$. We use $g\in[s^{t}]$ to index these
states and mode sequences, i.e., mode sequence $\omega_{0:t-1}^{(g)}$
generates state $\mathbf{x}_{t}^{(g)}$. Then, the reachable set
$\mathcal{X}_{t}$ defined in Section 5 satisfies
$\mathcal{X}_{t}=\bigcup_{g\in[s^{t}]}\\{\mathbf{x}_{t}^{(g)}\\}$. Define
probability measure
$q_{t}(g):=\mathbb{P}(\omega_{0:t-1}=\omega_{0:t-1}^{(g)})$, then we see
$p_{t}(\mathbf{x})$ defined in Section 5 satisfies
$p_{t}(\mathbf{x})=\sum_{g:\mathbf{x}_{t}^{(g)}=\mathbf{x}}q_{t}(g)$. For the
reduced $\hat{\Sigma}$ and for all $\hat{g}\in[r^{t}]$, we similarly define
notations $\hat{\omega}_{0:t-1}^{(\hat{g})}$ for the mode sequence,
$\hat{\mathbf{x}}_{t}^{(\hat{g})}$ for the state, and
$\hat{q}_{t}(\hat{g}):=\mathbb{P}(\hat{\omega}_{0:t-1}=\hat{\omega}_{0:t-1}^{(\hat{g})})$
for the measure. Then, the following holds:
$\hat{\mathcal{X}}_{t}=\bigcup_{\hat{g}\in[r^{t}]}\\{\hat{\mathbf{x}}_{t}^{(\hat{g})}\\}$
and
$\hat{p}_{t}(\hat{\mathbf{x}})=\sum_{\hat{g}:\hat{\mathbf{x}}_{t}^{(\hat{g})}=\hat{\mathbf{x}}}\hat{q}(\hat{g})$.
Next, we introduce the following relation regarding mode sequences between
$\Sigma$ and $\hat{\Sigma}$.

######  Definition 4 (Mode Sequence Synchrony).

For any $g\in[s^{t}],\hat{g}\in[r^{t}]$, we say $\omega_{0:t-1}^{(g)}$ is
synchronous to $\hat{\omega}_{0:t-1}^{(\hat{g})}$ (denoted by
$g\triangleright\hat{g}$) if $\omega_{h}\in\Omega_{h}$ for all
$h=0,1,\dots,t-1$.

Note that the synchrony definition here coincides with the mode synchrony in
Setup S2. With this synchrony relation, we first present a preliminary result.

######  Lemma 13.

For any $\hat{g}\in[r]^{t}$, we have
$\big{|}\hat{q}_{t}(\hat{g})-\sum_{g:g\triangleright\hat{g}}q_{t}(g)\big{|}\leq(t-1)(\bar{\mathcal{T}}+\epsilon_{\mathbf{T}})^{t-2}\epsilon_{\mathbf{T}}.$

###### Proof.

Recall $\zeta_{t}$ indexes the active cluster of $\Sigma$ at time $t$, i.e.,
$\zeta_{t}{=}k$ if and only if $\omega_{t}{\in}\Omega_{k}$. First observe that
$\sum_{g:g\triangleright\hat{g}^{\prime}}q_{t}(g)=$
$\sum_{g:g\triangleright\hat{g}}\mathbb{P}(\omega_{0:t-1}{=}\omega_{0:t-1}^{(g)}){=}\mathbb{P}(\omega_{t-1}{\in}\Omega_{\hat{\omega}_{t-1}^{(\hat{g})}}{,}\dots,\omega_{0}{\in}\Omega_{\hat{\omega}_{0}^{(\hat{g})}}){=}$
$\mathbb{P}(\zeta_{0:t-1}{=}\hat{\omega}_{0:t-1}^{(\hat{g})})$. Also note that
$\hat{q}_{t}(\hat{g}){=}\mathbb{P}(\hat{\omega}_{0:t-1}{=}\hat{\omega}_{0:t-1}^{(\hat{g})})$.
So, to show the claim, it suffices to show for any $\sigma_{0:t}{\in}[r]^{t}$,

$|\mathbb{P}(\hat{\omega}_{0:t}=\sigma_{0:t})-\mathbb{P}(\zeta_{0:t}=\sigma_{0:t})|\leq
t(\bar{\mathcal{T}}+\epsilon_{\mathbf{T}})^{t-1}\epsilon_{\mathbf{T}}.$ (36)

For the LHS of (36), we have

$\displaystyle\mathbb{P}(\hat{\omega}_{0:t}$
$\displaystyle=\sigma_{0:t})=\mathbb{P}(\hat{\omega}_{0}=\sigma_{0})\cdot{\textstyle\prod_{h=1}^{t}}\hat{\mathbf{T}}(\sigma_{h-1},\sigma_{h})$
(37) $\displaystyle\mathbb{P}(\zeta_{0:t}$
$\displaystyle=\sigma_{0:t})=\mathbb{P}(\omega_{0}\in\Omega_{\sigma_{0}})\cdot{\textstyle\prod_{h=1}^{t}}\tilde{T}_{h}$
(38)

where
$\tilde{T}_{h}:=\mathbb{P}(\omega_{h}\in\Omega_{\sigma_{h}}\mid\omega_{h-1}\in\Omega_{\sigma_{h-1}},\dots,\omega_{0}\in\Omega_{\sigma_{0}})$.
Note that $\zeta_{0:t}$ may not be a Markov process when
$\epsilon_{\mathbf{T}}\neq 0$, so we cannot drop the past conditional events
in (38).

Let
$\alpha_{i}:=\mathbb{P}(\omega_{h-1}{=}i\mid\omega_{h-2}{\in}\Omega_{\sigma_{h-2}},\dots,\omega_{0}{\in}\Omega_{\sigma_{0}})$,
then
$\tilde{T}_{h}{=}\sum_{i{\in}\Omega_{\sigma_{h-1}}}\big{[}\mathbb{P}(\omega_{h}{\in}\Omega_{\sigma_{h}}\mid\omega_{h-1}{=}i)\cdot\mathbb{P}(\omega_{h-1}{=}i\mid\omega_{h-2}{\in}$
$\Omega_{\sigma_{h-2}},\dots,\omega_{0}{\in}\Omega_{\sigma_{0}})\big{]}=\sum_{i\in\Omega_{\sigma_{h-1}}}\big{[}\big{(}\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i,j)\big{)}\alpha_{i}\big{]}$.

Let
$\beta_{i}:=|\Omega_{\sigma_{h-1}}|^{\mskip-1.0mu\scalebox{1.5}[0.75]{-}\mskip-1.0mu1}$.
For $\hat{\mathbf{T}}(\sigma_{h-1},\sigma_{h})$, by definition in Algorithm 1
and the assumption $\hat{\Omega}_{1:r}=\Omega_{1:r}$, we know
$\hat{\mathbf{T}}(\sigma_{h-1},\sigma_{h})=|\Omega_{\sigma_{h-1}}|^{\mskip-1.0mu\scalebox{1.5}[0.75]{-}\mskip-1.0mu1}$
$\cdot\sum_{i\in\Omega_{\sigma_{h-1}}}(\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i,j))=$
$\sum_{i\in\Omega_{\sigma_{h-1}}}\big{[}\big{(}\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i,j)\big{)}\beta_{i}\big{]}.$

Then, it follows that the difference
$|\tilde{T}_{h}-\hat{\mathbf{T}}(\sigma_{h-1},\sigma_{h})|$
$=\big{|}\sum_{i,i^{\prime}\in\Omega_{\sigma_{h-1}}}\big{[}\big{(}\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i,j)\big{)}\alpha_{i}\beta_{i^{\prime}}\big{]}-\sum_{i,i^{\prime}\in\Omega_{\sigma_{h-1}}}$
$\big{[}\big{(}\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i^{\prime},j)\big{)}\alpha_{i}\beta_{i^{\prime}}\big{]}\big{|}\leq\sum_{i,i^{\prime}\in\Omega_{\sigma_{h-1}}}\big{[}\big{|}\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i,j)$
$-\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i^{\prime},j)\big{|}\alpha_{i}\beta_{i^{\prime}}\big{]}\leq\epsilon_{\mathbf{T}},$
where the first inequality follows from triangle inequality on the absolute
values; the second inequality holds since the definition of perturbation
$\epsilon_{\mathbf{T}}$ in either Problem P1 or P2 gives
$|\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i,j)-\sum_{j\in\Omega_{\sigma_{h}}}\mathbf{T}(i^{\prime},j)|\leq\epsilon_{\mathbf{T}}$
for any $i,i^{\prime}\in\Omega_{\sigma_{h-1}}$.

We have established upper bounds for the differences between each multiplier
in (37) and (38), by Corollary 3, we obtain
$|\mathbb{P}(\hat{\omega}_{0:t}=\sigma_{0:t})-\mathbb{P}(\zeta_{0:t}=\sigma_{0:t})|\leq
t(\bar{\mathcal{T}}+\epsilon_{\mathbf{T}})^{t-1}\epsilon_{\mathbf{T}}$ which
shows (36) and concludes the proof. ∎

###### Main Proof for Theorem 4 (T2).

To lower bound the Wasserstein distance $W_{\ell}(p_{t},\hat{p}_{t})$ defined
in the mass transportation problem (8), we consider the objective value given
by a constrained mass transportation scheme. Recall with measures $q_{t}$ and
$\hat{q}_{t}$, we have
$p_{t}(\mathbf{x})=\sum_{g:\mathbf{x}_{t}^{(g)}=\mathbf{x}}q_{t}(g)$ and
$\hat{p}_{t}(\hat{\mathbf{x}})=\sum_{\hat{g}:\hat{\mathbf{x}}_{t}^{(\hat{g})}=\hat{\mathbf{x}}}\hat{q}_{t}(\hat{g})$.
With these relations, we consider the following transportation scheme in terms
of $q_{t}$ and $\hat{q}_{t}$: for all the mass $q_{t}(g)$ with mode sequence
$\omega_{t}^{(g)}$ synchronous to mode sequence
$\hat{\omega}_{t}^{(\hat{g})}$, it is prioritized to be moved to location
$\hat{g}$; if there is surplus, i.e.,
$\sum_{g:g\triangleright\hat{g}}q_{t}(g)>\hat{q}_{t}(\hat{g})$, we move the
surplus portion $\sum_{g:g\triangleright\hat{g}}q_{t}(g)-\hat{q}_{t}(\hat{g})$
elsewhere.

Under this moving scheme, let $\bar{W}_{\ell}(q_{t},\hat{q}_{t})$ denote the
optimal objective value of the mass transportation problem (8). Let
$\hat{\mathcal{G}}_{1}{=}\\{\hat{g}:\hat{g}{\in}[r^{t}],\sum_{g:g\triangleright\hat{g}}q_{t}(g){\leq}\hat{q}_{t}(\hat{g})\\}$,
$\hat{\mathcal{G}}_{2}=[r^{t}]\backslash\hat{\mathcal{G}}_{1}$. Then,
$\bar{W}_{\ell}(q_{t},\hat{q}_{t})$ can be viewed as the optimal objective of
the following problem:

$\displaystyle\min_{f\geq 0}\quad$
$\displaystyle\big{(}{\textstyle\sum_{g\in[s^{t}],\hat{g}\in[r^{t}]}}\
f(g,\hat{g})\|{\mathbf{x}_{t}^{(g)}-\hat{\mathbf{x}}_{t}^{(\hat{g})}}\|^{\ell}\big{)}^{1/\ell}$
(39) s.t. $\displaystyle{\textstyle\sum_{g\in[s^{t}]}}\
f(g,\hat{g})=\hat{q}_{t}(\hat{g}),\forall\ \hat{g}$
$\displaystyle{\textstyle\sum_{\hat{g}\in[r^{t}]}}\
f(g,\hat{g})=q_{t}(g),\forall\ g.$ $\displaystyle
f(g,\hat{g})=q_{t}(g),\qquad\quad\;\;\forall\ g\triangleright\hat{g},\forall\
\hat{g}\in\hat{\mathcal{G}}_{1}$ (40)
$\displaystyle{\textstyle\sum_{g\triangleright\hat{g}}}\
f(g,\hat{g})=\hat{q}_{t}(\hat{g}),\;\;\;\forall\
\hat{g}\in\hat{\mathcal{G}}_{2}$ (41)

where constraints (40) and (41) characterize the moving scheme outlined above.
Without them, the problem reduces to (8), thus
$W_{\ell}(p_{t},\hat{p}_{t})\leq\bar{W}_{\ell}(q_{t},\hat{q}_{t})$. To prove
the main claim, it suffices to show

$\bar{W}_{\ell}(q_{t},\hat{q}_{t})\leq
t\xi_{0}^{t-1}\kappa^{2}\|{\mathbf{x}_{0}}\|\epsilon_{\mathbf{A}}\\\
+2r^{2}t\kappa\|{\mathbf{x}_{0}}\|r^{t}(\kappa\epsilon_{\mathbf{A}}+\xi)^{t}(\bar{\mathcal{T}}+\epsilon_{\mathbf{T}})^{\frac{t-2}{\ell}}\epsilon_{\mathbf{T}}^{\frac{1}{\ell}}.$
(42)

For all $\hat{g}{\in}[r^{t}]$, define its synchrony set
$\mathcal{S}(\hat{g}){:=}\\{g:g{\in}[s^{t}],$ $g\triangleright\hat{g}\\}$ and
the asynchrony set
$\mathcal{S}^{c}(\hat{g}){:=}[s^{t}]\backslash\mathcal{S}(\hat{g})$. For the
synchrony flow, define total flow
$F_{s}{:=}\sum_{\hat{g}\in[r^{t}],g\in\mathcal{S}(\hat{g})}f(g,\hat{g})$ and
maximum travel distance
$D_{s}{:=}\max_{\hat{g}\in[r^{t}],g\in\mathcal{S}(\hat{g})}\|\mathbf{x}_{t}^{(g)}$
$-\hat{\mathbf{x}}_{t}^{(\hat{g})}\|$. For the asynchrony flow, similarly
define $F_{a}:=$
$\sum_{\hat{g}\in[r^{t}],g\in\mathcal{S}^{c}(\hat{g})}f(g,\hat{g})$ and
$D_{a}:=\max_{\hat{g}\in[r^{t}],g\in\mathcal{S}^{c}(\hat{g})}$
$\|\mathbf{x}_{t}^{(g)}$ $-\hat{\mathbf{x}}_{t}^{(\hat{g})}\|$. Then, we have
$\bar{W}_{\ell}(q_{t},\hat{q}_{t}){\leq}(F_{s}D_{s}^{\ell}+F_{a}D_{a}^{\ell})^{\frac{1}{\ell}}\leq
F_{s}^{\frac{1}{\ell}}D_{s}+F_{a}^{\frac{1}{\ell}}D_{a}$. We next bound
$F_{s},D_{s},F_{a},D_{a}$ separately.

For the synchrony maximum travel distance $D_{s}$, since
$g\triangleright\hat{g}$, by Theorem 4 (T1), we know
$D_{s}{\leq}t\xi_{0}^{t-1}\kappa^{2}\|{\mathbf{x}_{0}}\|\epsilon_{\mathbf{A}}$.
For the synchrony total flow $F_{s}$, we simply bound it with $F_{s}{\leq}1$.

Now we consider the asynchrony maximum travel distance $D_{a}$. First note
that for any $g$ and $\hat{g}$, we have
$\|{\mathbf{x}_{t}^{(g)}{-}\hat{\mathbf{x}}_{t}^{(\hat{g})}}\|{=}$
$\|\prod_{h=0}^{t-1}\mathbf{A}_{\omega_{h}^{(g)}}\mathbf{x}_{0}{-}\prod_{h=0}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}^{(\hat{g})}}\hat{\mathbf{x}}_{0}\|\leq$
$\|{\prod_{h=0}^{t-1}\mathbf{A}_{\omega_{h}^{(g)}}\mathbf{x}_{0}}\|{+}$
$\|{\prod_{h=0}^{t-1}\hat{\mathbf{A}}_{\hat{\omega}_{h}^{(\hat{g})}}\hat{\mathbf{x}}_{0}}\|\leq
2\kappa(\kappa\epsilon_{\mathbf{A}}{+}\xi)^{t}\|{\mathbf{x}_{0}}\|$, where the
second inequality follows from Lemma 10. Then, it follows that
$D_{a}{\leq}2\kappa(\kappa\epsilon_{\mathbf{A}}+\xi)^{t}\|{\mathbf{x}_{0}}\|$.

For the asynchrony total flow $F_{a}$, define
$F_{a,\hat{g}}{:=}\sum_{g\in\mathcal{S}^{c}(\hat{g})}$ $f(g,\hat{g})$, then
$F_{a}=\sum_{\hat{g}\in[r^{t}]}F_{a,\hat{g}}$. By constraints (40) and (41),
$F_{a,\hat{g}}=\sum_{g\in\mathcal{S}^{c}(\hat{g})}f(g,\hat{g})=\hat{q}_{t}(\hat{g}){-}\sum_{g:g\in\mathcal{S}(\hat{g})}f(g,\hat{g})$
$=\hat{q}_{t}(\hat{g}){-}\sum_{g:g\triangleright\hat{g}}f(g,\hat{g}).$ Thus,
if $\hat{g}\in\hat{\mathcal{G}}_{2}$, $F_{a,\hat{g}}=0$; and if
$\hat{g}\in\hat{\mathcal{G}}_{1}$,
$F_{a,\hat{g}}=\hat{q}_{t}(\hat{g})-\sum_{g:g\triangleright\hat{g}}q_{t}(g)>0$.
For the latter case, according to Lemma 13, we have
$F_{a,\hat{g}}=|\hat{q}_{t}(\hat{g})-\sum_{g:g\triangleright\hat{g}}q_{t}(g)|\leq(t-1)(\bar{\mathcal{T}}+\epsilon_{\mathbf{T}})^{t-2}\epsilon_{\mathbf{T}}$,
which further implies that $F_{a}=\sum_{\hat{g}\in[r^{t}]}F_{a,\hat{g}}\leq
r^{2}t(r(\bar{\mathcal{T}}+\epsilon_{\mathbf{T}}))^{t-2}\epsilon_{\mathbf{T}}$.

Finally, (42) can be shown by plugging the upper bounds for
$F_{s},D_{s},F_{a},D_{a}$ into the relation that
$\bar{W}_{\ell}(q_{t},\hat{q}_{t}){\leq}F_{s}^{\frac{1}{\ell}}D_{s}+F_{a}^{\frac{1}{\ell}}D_{a}$,
which concludes the proof. ∎

## References

  * [1] L. Blackmore, S. Funiak, and B. C. Williams, “Combining stochastic and greedy search in hybrid estimation,” in _AAAI_ , 2005, pp. 282–287.
  * [2] D. Cajueiro, “Stochastic optimal control of jumping markov parameter processes with applications to finance,” Ph.D. dissertation, PhD thesis, 2002, Instituto Tecnológico de Aeronáutica-ITA, Brazil, 2002.
  * [3] K. Loparo and F. Abdel-Malek, “A probabilistic approach to dynamic power system security,” _IEEE transactions on circuits and systems_ , vol. 37, no. 6, pp. 787–798, 1990.
  * [4] L. E. Svensson, N. Williams _et al._ , “Optimal monetary policy under uncertainty: a markov jump-linear-quadratic approach,” _Federal Reserve Bank of St. Louis Review_ , vol. 90, no. 4, pp. 275–293, 2008.
  * [5] V. Ugrinovskii and H. R. Pota, “Decentralized control of power systems via robust control of uncertain markov jump parameter systems,” _International Journal of Control_ , vol. 78, no. 9, pp. 662–677, 2005.
  * [6] B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, and S. Sastry, “An lqg optimal linear controller for control systems with packet losses,” in _Proceedings of the 44th IEEE Conference on Decision and Control_. IEEE, 2005, pp. 458–463.
  * [7] T. H. Truong, P. Seiler, and L. E. Linderman, “Analysis of networked structural control with packet loss,” _IEEE Transactions on Control Systems Technology_ , 2021.
  * [8] L. Zhang, B. Huang, and J. Lam, “$\mathcal{H}_{\infty}$ model reduction of markovian jump linear systems,” _Systems & Control Letters_, vol. 50, no. 2, pp. 103–118, 2003.
  * [9] M. Zamani and A. Abate, “Approximately bisimilar symbolic models for randomly switched stochastic systems,” _Systems & Control Letters_, vol. 69, pp. 38–46, 2014.
  * [10] Z. Du, N. Ozay, and L. Balzano, “Clustering-based mode reduction for markov jump systems,” in _Learning for Dynamics and Control Conference_. PMLR, 2022, pp. 689–701.
  * [11] Y. Sattar, Z. Du, D. A. Tarzanagh, L. Balzano, N. Ozay, and S. Oymak, “Identification and adaptive control of markov jump systems: Sample complexity and regret bounds,” _arXiv preprint arXiv:2111.07018_ , 2021.
  * [12] J. Desharnais, V. Gupta, R. Jagadeesan, and P. Panangaden, “Metrics for labelled markov processes,” _Theoretical computer science_ , vol. 318, no. 3, pp. 323–354, 2004.
  * [13] I. Tkachev and A. Abate, “On approximation metrics for linear temporal model-checking of stochastic systems,” in _Proceedings of the 17th international conference on Hybrid systems: computation and control_ , 2014, pp. 193–202.
  * [14] G. Bian and A. Abate, “On the relationship between bisimulation and trace equivalence in an approximate probabilistic context,” in _International Conference on Foundations of Software Science and Computation Structures_. Springer, 2017, pp. 321–337.
  * [15] Y. Z. Lun, J. Wheatley, A. D’Innocenzo, and A. Abate, “Approximate abstractions of markov chains with interval decision processes,” _IFAC-PapersOnLine_ , vol. 51, no. 16, pp. 91–96, 2018.
  * [16] A. Zhang and M. Wang, “Spectral state compression of markov processes,” _IEEE transactions on information theory_ , vol. 66, no. 5, pp. 3202–3231, 2019.
  * [17] Z. Du, N. Ozay, and L. Balzano, “Mode clustering for markov jump systems,” _arXiv preprint arXiv:1910.02193_ , 2019.
  * [18] A. Bittracher and C. Schütte, “A probabilistic algorithm for aggregating vastly undersampled large markov chains,” _Physica D: Nonlinear Phenomena_ , vol. 416, p. 132799, 2021.
  * [19] A. Abate, A. D’Innocenzo, and M. D. Di Benedetto, “Approximate abstractions of stochastic hybrid systems,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 11, pp. 2688–2694, 2011.
  * [20] S. E. Z. Soudjani and A. Abate, “Adaptive gridding for abstraction and verification of stochastic hybrid systems,” in _2011 Eighth International Conference on Quantitative Evaluation of SysTems_. IEEE, 2011, pp. 59–68.
  * [21] A. A. Julius, A. Girard, and G. J. Pappas, “Approximate bisimulation for a class of stochastic hybrid systems,” in _2006 American Control Conference_. IEEE, 2006, pp. 4724–4729.
  * [22] A. A. Julius and G. J. Pappas, “Approximations of stochastic hybrid systems,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 6, pp. 1193–1203, 2009.
  * [23] M. Zamani, M. Rungger, and P. M. Esfahani, “Approximations of stochastic hybrid systems: A compositional approach,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 6, pp. 2838–2853, 2016.
  * [24] Y. Shen, Z.-G. Wu, P. Shi, and C. K. Ahn, “Model reduction of markovian jump systems with uncertain probabilities,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 1, pp. 382–388, 2019.
  * [25] G. Kotsalis and A. Rantzer, “Balanced truncation for discrete time markov jump linear systems,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 11, pp. 2606–2611, 2010.
  * [26] M. Sun and J. Lam, “Model reduction of discrete markovian jump systems with time-weighted $\text{H}_{2}$ performance,” _International Journal of Robust and Nonlinear Control_ , vol. 26, no. 3, pp. 401–425, 2016.
  * [27] K. G. Larsen and A. Skou, “Bisimulation through probabilistic testing,” _Information and computation_ , vol. 94, no. 1, pp. 1–28, 1991.
  * [28] J. Desharnais, A. Edalat, and P. Panangaden, “Bisimulation for labelled markov processes,” _Information and Computation_ , vol. 179, no. 2, pp. 163–193, 2002.
  * [29] A. Abate, “Approximation metrics based on probabilistic bisimulations for general state-space markov processes: a survey,” _Electronic Notes in Theoretical Computer Science_ , vol. 297, pp. 3–25, 2013.
  * [30] A. Girard and G. J. Pappas, “Approximation metrics for discrete and continuous systems,” _IEEE Transactions on Automatic Control_ , vol. 52, no. 5, pp. 782–798, 2007.
  * [31] R. Alur, T. A. Henzinger, G. Lafferriere, and G. J. Pappas, “Discrete abstractions of hybrid systems,” _Proceedings of the IEEE_ , vol. 88, no. 7, pp. 971–984, 2000.
  * [32] E. M. Clarke Jr, O. Grumberg, D. Kroening, D. Peled, and H. Veith, _Model checking_. MIT press, 2018.
  * [33] R. P. Kurshan, _Computer-aided verification of coordinating processes: the automata-theoretic approach_. Princeton university press, 2014, vol. 302.
  * [34] O. Maler, A. Pnueli, and J. Sifakis, “On the synthesis of discrete controllers for timed systems,” in _Annual symposium on theoretical aspects of computer science_. Springer, 1995, pp. 229–242.
  * [35] A. Abate, J.-P. Katoen, J. Lygeros, and M. Prandini, “Approximate model checking of stochastic hybrid systems,” _European Journal of Control_ , vol. 16, no. 6, pp. 624–641, 2010.
  * [36] S. Gugercin and A. C. Antoulas, “A survey of model reduction by balanced truncation and some new results,” _International Journal of Control_ , vol. 77, no. 8, pp. 748–766, 2004.
  * [37] P. Buchholz, “Exact and ordinary lumpability in finite markov chains,” _Journal of applied probability_ , vol. 31, no. 1, pp. 59–75, 1994.
  * [38] K. H. Hoffmann and P. Salamon, “Bounding the lumping error in markov chain dynamics,” _Applied mathematics letters_ , vol. 22, no. 9, pp. 1471–1475, 2009.
  * [39] L. Schulman and B. Gaveau, “Coarse grains: The emergence of space and order,” _Foundations of Physics_ , vol. 31, no. 4, pp. 713–731, 2001.
  * [40] B. Gaveau and L. Schulman, “Dynamical distance: coarse grains, pattern recognition, and network analysis,” _Bulletin des sciences mathematiques_ , vol. 129, no. 8, pp. 631–642, 2005.
  * [41] M. Meilă and J. Shi, “A random walks view of spectral segmentation,” in _International Workshop on Artificial Intelligence and Statistics_. PMLR, 2001, pp. 203–208.
  * [42] L. Bottou and Y. Bengio, “Convergence properties of the k-means algorithms,” _Advances in neural information processing systems_ , vol. 7, 1994.
  * [43] T. F. Gonzalez, “Clustering to minimize the maximum intercluster distance,” _Theoretical computer science_ , vol. 38, pp. 293–306, 1985.
  * [44] A. Kumar, Y. Sabharwal, and S. Sen, “A simple linear time (1+/spl epsiv/)-approximation algorithm for k-means clustering in any dimensions,” in _45th Annual IEEE Symposium on Foundations of Computer Science_. IEEE, 2004, pp. 454–462.
  * [45] M. Song and S. Rajasekaran, “Fast algorithms for constant approximation k-means clustering.” _Trans. Mach. Learn. Data Min._ , vol. 3, no. 2, pp. 67–79, 2010.
  * [46] O. L. V. Costa, M. D. Fragoso, and R. P. Marques, _Discrete-time Markov jump linear systems_. Springer, 2006.
  * [47] D. Kuhn, P. M. Esfahani, V. A. Nguyen, and S. Shafieezadeh-Abadeh, “Wasserstein distributionally robust optimization: Theory and applications in machine learning,” in _Operations research & management science in the age of analytics_. Informs, 2019, pp. 130–166.
  * [48] Y. Chen, T. T. Georgiou, and M. Pavon, “Optimal steering of a linear stochastic system to a final probability distribution, part i,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 5, pp. 1158–1169, 2015.
  * [49] M. Goldshtein and P. Tsiotras, “Finite-horizon covariance control of linear time-varying systems,” in _2017 IEEE 56th Annual Conference on Decision and Control (CDC)_. IEEE, 2017, pp. 3606–3611.
  * [50] K. Okamoto, M. Goldshtein, and P. Tsiotras, “Optimal covariance control for stochastic systems under chance constraints,” _IEEE Control Systems Letters_ , vol. 2, no. 2, pp. 266–271, 2018.
  * [51] J.-S. Li and J. Qi, “Ensemble control of time-invariant linear systems with linear parameter variation,” _IEEE Transactions on Automatic Control_ , vol. 61, no. 10, pp. 2808–2820, 2015.
  * [52] R. Jungers, _The joint spectral radius: theory and applications_. Springer Science & Business Media, 2009, vol. 385.
  * [53] P. A. Parrilo and A. Jadbabaie, “Approximation of the joint spectral radius using sum of squares,” _Linear Algebra and its Applications_ , vol. 428, no. 10, pp. 2385–2402, 2008.
  * [54] Y. Sattar, Z. Du, D. A. Tarzanagh, S. Oymak, L. Balzano, and N. Ozay, “Certainty equivalent quadratic control for markov jump systems,” in _2022 American Control Conference (ACC)_ , 2022, pp. 2871–2878.
  * [55] J. Lei, A. Rinaldo _et al._ , “Consistency of spectral clustering in stochastic block models,” _The Annals of Statistics_ , vol. 43, no. 1, pp. 215–237, 2015.
  * [56] G. E. Cho and C. D. Meyer, “Comparison of perturbation bounds for the stationary distribution of a markov chain,” _Linear Algebra and its Applications_ , vol. 335, no. 1-3, pp. 137–150, 2001.


# On AKKT optimality conditions for cone-constrained vector optimization
problems

Nguyen Van Tuyen  School of Mathematical Sciences, University of Electronic
Science and Technology of China, Chengdu, P.R. China; Department of
Mathematics, Hanoi Pedagogical University 2, Xuan Hoa, Phuc Yen, Vinh Phuc,
Vietnam<EMAIL_ADDRESS><EMAIL_ADDRESS>,  Yi-Bin Xiao
School of Mathematical Sciences, University of Electronic Science and
Technology of China, Chengdu, P.R. China<EMAIL_ADDRESS>and  Ta Quang
Son∗ Faculty of Applied Mathematics and Applications, Saigon University,
Hochiminh City, Vietnam<EMAIL_ADDRESS>
###### Abstract.

In this paper, we introduce a kind of approximate Karush–Kuhn–Tucker condition
(AKKT) for a smooth cone-constrained vector optimization problem. We show
that, without any constraint qualification, the AKKT condition is a necessary
for a local weak efficient solution of the considered problem. For convex
problems, we prove that the AKKT condition is a necessary and sufficient
optimality condition for a global weak efficient solution. We also introduce
some strict constraint qualifications associated with the AKKT condition.

###### Key words and phrases:

AKKT conditions, strict constraint qualifications, cone-constrained vector
optimization

###### 2010 Mathematics Subject Classification:

90C29, 90C46, 90C34

∗Corresponding.

The research of Nguyen Van Tuyen was supported by the Ministry of Education
and Training of Vietnam [grant number B2018-SP2-14] as well as the grant from
School of Mathematical Sciences, University of Electronic Science and
Technology of China, Chengdu, P.R. China. The research of Yi-bin Xiao was
supported by the National Natural Science Foundation of China (11771067). The
research of Ta Quang Son was supported by Vietnam National Foundation for
Science and Technology Development (NAFOSTED) under grant number
101.01-2017.08.

##  1\. Introduction

In this paper, we are concerned with the following cone-constrained vector
optimization problem:

$\text{\rm
Min}_{\,\mathbb{R}^{m}_{+}}\,\big{\\{}f(x)\,:\,x\in\mathbb{R}^{n},\;g(x)\in-\Theta\big{\\}},$
(CCVP)

where $f$ is a mapping from $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$, $g$ is a
mapping from $\mathbb{R}^{n}$ to a Banach space $Y$, and $\Theta\subset Y$ is
a closed convex cone. When $m=1$, then (CCVP) is called a cone-constrained
optimization problem. Since $\Theta$ is in an arbitrary Banach space $Y$, the
problems of the form (CCVP) contain a wide class of problems in mathematical
programming such as semi-infinite optimization problems, semidefinite
optimization problems, second-order cone programs, and so on.

It is well known that Karush–Kuhn–Tucker (KKT) optimality conditions play an
important role in both the theory and practice of constrained optimization and
are very relative to the class of important problems in mechanics and
engineering, i.e., variational inequality problems, see, e.g., [19, 27, 24,
31, 39, 40, 42]. In order to obtain optimality conditions of KKT-type,
constraint qualifications are indispensable; see, e.g., [3, 8, 21, 37, 41]. A
constraint qualification (CQ) of (CCVP) is a condition that ensures that every
optimal solution of (CCVP) satisfies the KKT condition. In other words, usual
necessary optimality conditions are of the form KKT or not-CQ. In the case of
without CQ, sequential optimality conditions (or approximate KKT optimality
conditions) are considered. Recently, sequential optimality conditions have
been recognized to be useful in designing algorithms for finding approximate
optimal solutions of nonlinear programming problems; see, e.g., [1, 2, 4, 5,
6, 9, 14, 16, 17, 20, 22, 23, 29, 30, 32].

For convex cone-constrained optimization problems, there have been some papers
in the literature dealing with sequential optimality conditions; see, e.g.,
[7, 11, 12, 18, 25, 26, 28]. However, to the best of our knowledge, there has
been only one work [35] concerning sequential optimality conditions for
nonconvex cone-constrained optimization problems. Based on advanced
constructions and techniques of variational analysis and generalized
differentiation, Mordukhovich et al. [35] derived new necessary optimality
conditions in fuzzy form for nonsmooth and nonconvex cone-constrained
optimization problems. As a consequence of these fuzzy optimality conditions,
the authors obtained optimality conditions of approximate KKT-type without any
constraint qualifications.

In this paper, motivated and inspired by the work of Mordukhovich et al. [35],
we introduce an approximate KKT condition for cone-constrained vector
optimization (CCVP). We show that the approximate KKT condition is a necessary
one for local weak efficient solutions. Under convexity assumptions, we prove
that this condition is also a sufficient optimality condition. We also
introduce some strict constraint qualifications under which the approximate
KKT condition implies the KKT condition.

The paper is organized as follows. In Section 2, we recall some basic
definitions and preliminaries from variational analysis and generalized
differentiation. Section 3 is devoted to presenting the main results.

##  2\. Preliminaries

We use the following notation and terminology. Fix
$n\in{\mathbb{N}}:=\\{1,2,\ldots\\}$. The space $\mathbb{R}^{n}$ is equipped
with the usual scalar product and Euclidean norm.

For a Banach space $X$, the bracket $\langle\cdot\,,\cdot\rangle$ stands for
the canonical pairing between space $X$ and its dual $X^{*}$. The weak∗
convergence in $X^{\ast}$ is denoted by $\stackrel{{\scriptstyle
w^{\ast}}}{{\longrightarrow}}$. The topological closure, the topological
interior and the conic hull of a subset $\Omega$ of $X$ are denoted,
respectively, by $\mathrm{cl}\,{\Omega}$, $\mathrm{int}\,{\Omega}$ and
$\mathrm{cone}\,\Omega$. The closed ball with center $x$ and radius $\delta$
is denoted by $B(x,\delta)$.

Here, we recall the notions of the normal cones to nonempty sets and the
subdifferential of real-valued functions used in this paper. The reader is
referred to [33, 34] for more details.

######  Definition 2.1 (see [33]).

Let $\Omega\subset\mathbb{R}^{n}$ and $\bar{x}\in\mbox{cl}\,\Omega$. The set

$N(\bar{x};\Omega):=\\{z^{*}\in\mathbb{R}^{n}\;:\;\exists
x^{k}\stackrel{{\scriptstyle\Omega}}{{\longrightarrow}}\bar{x},z^{*}_{k}\to
z^{*},z^{*}_{k}\in{\widehat{N}}(x^{k};\Omega),\ \ \forall k\in\mathbb{N}\\},$

is called the Mordukhovich/limiting normal cone of $\Omega$ at $\bar{x}$,
where

$\widehat{N}(x;\Omega):=\bigg{\\{}{z^{*}\in{\mathbb{R}^{n}}\;:\;\limsup_{u\overset{\Omega}{\rightarrow}x}\frac{{\langle
z^{*},u-x\rangle}}{{\parallel u-x\parallel}}\leq 0}\bigg{\\}}$

is the set of regular/Fréchet normals of $\Omega$ at $x$ and
$u\xrightarrow{{\Omega}}x$ means that $u\rightarrow x$ and $u\in\Omega$.

######  Definition 2.2 (see [33]).

Consider a function $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ and a point
$\bar{x}\in\mathbb{R}^{n}$. The Mordukhovich/limiting subdifferential of
$\varphi$ at $\bar{x}$ is defined by

$\displaystyle\partial\varphi(\bar{x}):=\\{x^{*}\in\mathbb{R}^{n}\,:\,(x^{*},-1)\in
N((\bar{x},\varphi(\bar{x}));\mbox{epi}\varphi)\\},$

where $\mbox{epi}\varphi$ is the epigraph of $\varphi$ and is given by

$\mbox{epi}\varphi:=\\{(x,\alpha)\in\mathbb{R}^{n}\times\mathbb{R}\;:\;\varphi(x)\leq\alpha\\}.$

The following lemma will be used in the next section.

######  Lemma 2.3 (see [33, Theorem 3.46]).

Let
$\varphi_{1},\ldots,\varphi_{m}\colon{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$
be continuously differentiable functions and $\bar{x}\in\mathbb{R}^{n}$. For
each $x\in\mathbb{R}^{n}$, put

$\varphi(x):=\max_{1\leq i\leq m}\varphi_{i}(x).$

Then, we have

$\displaystyle\partial\varphi(\bar{x})$ $\displaystyle\subset$
$\displaystyle\left\\{\displaystyle\sum_{i\in
I(\bar{x})}\alpha_{i}\nabla\varphi_{i}(\bar{x})\;:\;\alpha_{i}\geq
0\quad\textrm{ and }\quad\displaystyle\sum_{i\in
I(\bar{x})}\alpha_{i}=1\right\\},$

where
$I(\bar{x}):=\\{i\in\\{1,\ldots,m\\}\,:\,\varphi_{i}(\bar{x})=\varphi(\bar{x})\\}$.

##  3\. Main results

Hereafter we assume that $f\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ and
$g\colon\mathbb{R}^{n}\to Y$ are continuously Fréchet differentiable on
$\mathbb{R}^{n}$. The derivatives of $f$ and $g$ at $x\in\mathbb{R}^{n}$ are
denoted by $\nabla f(x)$ and $\nabla g(x)$, respectively. The adjoint operator
of $\nabla g(x)$ is denoted by $\nabla g(x)^{\ast}$. The polar cone of
$\Theta$ is denoted by

$\Theta_{+}:=\\{\mu\in Y^{*}\;:\;\langle\mu,\theta\rangle\geq 0,\ \
\forall\theta\in\Theta\\}.$

Clearly, $\Theta_{+}$ is a weak∗ closed subset of $Y^{*}$. For convenience,
let $\mathcal{F}$ denote the feasible set of (CCVP), i.e.,

$\mathcal{F}:=\\{x\in\mathbb{R}^{n}\;:\;g(x)\in-\Theta\\}.$

A point $\bar{x}\in\mathcal{F}$ is called a local weak efficient solution of
(CCVP) if and only if there exists a neighborhood $U$ of $\bar{x}$ such that
there is no $x\in U\cap\mathcal{F}$ satisfying

$f_{i}(x)<f_{i}(\bar{x}),\ \ \forall i=1,\ldots,m.$

If $U=\mathbb{R}^{n}$, then we say that $\bar{x}$ is a (global) weak efficient
solution of (CCVP).

######  Definition 3.1.

We say that $\bar{x}\in\mathcal{F}$ satisfies the KKT condition if and only if
there exists a multiplier $(\lambda,\mu)\in\mathbb{R}^{m}_{+}\times\Theta_{+}$
such that

  1. (i)

$\sum_{i=1}^{m}\lambda_{i}=1$,

  2. (ii)

$\nabla g(\bar{x})^{*}\mu+\sum_{i=1}^{m}\lambda_{i}\nabla f_{i}(\bar{x})=0$,

  3. (iii)

$\langle\mu,g(\bar{x})\rangle=0$.

We now introduce the concept of approximate Karush–Kuhn–Tucker condition for
(CCVP) inspired by the work of Mordukhovich et al. [35].

######  Definition 3.2.

We say that $\bar{x}\in\mathcal{F}$ satisfies the approximate
Karush–Kuhn–Tucker condition (AKKT) if and only if there exist a vector
$\lambda\in\mathbb{R}^{m}_{+}$ with $\sum_{i=1}^{m}\lambda_{i}=1$ and
sequences $\\{x^{k}\\}\subset\mathbb{R}^{n}$ and
$\\{\mu^{k}\\}\subset\Theta_{+}$ such that

  1. (A0)

$x^{k}\to\bar{x}$,

  2. (A1)

$\nabla g(x^{k})^{*}\mu^{k}+\sum_{i=1}^{m}\lambda_{i}\nabla f_{i}(\bar{x})\to
0$,

  3. (A2)

$\langle\mu^{k},g(x^{k})\rangle\to 0$.

A sequence $\\{x^{k}\\}$ satisfying the above definition will be called an
AKKT sequence. We note here that the sequence of points $\\{x^{k}\\}$ is not
required to be feasible.

The following result shows that the AKKT condition is necessary for a feasible
point to be a local weak efficient solution of (CCVP) without any constraint
qualification.

######  Theorem 3.3.

If $\bar{x}$ is a local weak efficient solution of (CCVP), then $\bar{x}$
satisfies the AKKT condition.

###### Proof.

By assumption, there exists $\delta>0$ such that, for all $x\in\mathcal{F}\cap
B(\bar{x},\delta)$, there exists $i\in\\{1,\ldots,m\\}$ satisfying
$f_{i}(x)\geq f_{i}(\bar{x}).$ This implies that

$\psi(x):=\max\\{f_{i}(x)-f_{i}(\bar{x})\;:\;i=1,\ldots,m\\}\geq 0,\ \ \
\forall x\in\mathcal{F}\cap B(\bar{x},\delta).$

Consequently, $\bar{x}$ is a local minimum of the function $\psi$ on
$\mathcal{F}$. Clearly, $\psi$ is Lipschitz continuous around $\bar{x}$.
Hence, by [35, Corollary 5.1], there exist a subgradient
$x^{*}\in\partial\psi(\bar{x})$ and sequences
$\\{x^{k}\\}\subset\mathbb{R}^{n}$ and $\\{\mu^{k}\\}\subset\Theta_{+}$ such
that

$x^{k}\to\bar{x},\nabla g(x^{k})^{*}\mu^{k}+x^{*}\to 0,\ \ \text{and}\ \
\langle\mu^{k},g(x^{k})\rangle\to 0\ \ \text{as}\ \ k\to\infty.$

By Lemma 2.3, we have

$\partial\psi(\bar{x})\subset\left\\{\displaystyle\sum_{i=1}^{m}\lambda_{i}\nabla
f_{i}(\bar{x})\;:\;\lambda_{i}\geq 0\ \ \textrm{ and }\ \
\displaystyle\sum_{i=1}^{m}\lambda_{i}=1\right\\}.$

Hence there exists $\lambda\in\mathbb{R}^{m}_{+}$ with
$\sum_{i=1}^{m}\lambda_{i}=1$ such that

$x^{*}=\sum_{i=1}^{m}\lambda_{i}\nabla f_{i}(\bar{x}),$

as required. ∎

In the following example, we consider a local weak efficient solution that
does not satisfy the KKT condition. Let us then construct an AKKT sequence
guaranteed to exist by Theorem 3.3.

######  Example 3.4.

Consider the following problem:

$\displaystyle\text{min}\,f(x):=(f_{1}(x),f_{2}(x))$
$\displaystyle\text{s.t.}\ \
x\in\mathcal{F}:=\\{x\in\mathbb{R}^{2}\,:\,g(x)\in-\Theta\\},$

where $\Theta:=\mathbb{R}^{3}_{+}$ and

$\displaystyle f_{1}(x_{1},x_{2})$
$\displaystyle:=-3x_{1}-2x_{2}+3,f_{2}(x_{1},x_{2}):=-x_{1}-3x_{2}+1,$
$\displaystyle g(x_{1},x_{2})$
$\displaystyle:=(g_{1}(x_{1},x_{2}),g_{2}(x_{1},x_{2}),g_{3}(x_{1},x_{2})),$
$\displaystyle g_{1}(x_{1},x_{2})$
$\displaystyle:=-x_{1},g_{2}(x_{1},x_{2}):=-x_{2},g_{3}(x_{1},x_{2}):=(x_{1}-1)^{3}+x_{2}.$

Let $\bar{x}=(1,0)$. It is easy to check that $\bar{x}$ is a weak efficient
solution, $\Theta_{+}=\Theta$ and

$\displaystyle\nabla f_{1}(\bar{x})$ $\displaystyle=(-3,-2),\nabla
f_{2}(\bar{x})=(-1,-3),$ $\displaystyle\nabla g_{1}(\bar{x})$
$\displaystyle=(-1,0),\nabla g_{2}(\bar{x})=(0,-1),\nabla
g_{3}(\bar{x})=(0,1).$

Since

$\begin{cases}\lambda_{1}\nabla f_{1}(\bar{x})+\lambda_{2}\nabla
f_{2}(\bar{x})+\mu_{2}\nabla g_{2}(\bar{x})+\mu_{3}\nabla g_{3}(\bar{x})=0\\\
\mu_{1}g_{1}(\bar{x})+\mu_{2}g_{2}(\bar{x})+\mu_{3}g_{3}(\bar{x})=0\\\
\lambda_{1},\lambda_{2},\mu_{2},\mu_{3}\geq
0\end{cases}\Leftrightarrow\begin{cases}\lambda_{1}=\lambda_{2}=0\\\
\mu_{1}=0,\mu_{2}=\mu_{3}\\\ \mu_{2},\mu_{3}\geq 0,\end{cases}$

it follows that there is no multiplier
$(\lambda,\mu)\in\mathbb{R}_{+}^{2}\times\Theta_{+}$ satisfying conditions
(i)–(iii) of Definition 3.1. This means that the KKT condition does not hold
at $\bar{x}$.

We now check that the AKKT condition holds at $\bar{x}$. Let
$\lambda=(\frac{1}{2},\frac{1}{2})$. We claim that there exist sequences
$\\{x^{k}\\}\subset\mathbb{R}^{2}$ and
$\\{\mu^{k}\\}\subset\mathbb{R}^{3}_{+}$ satisfying conditions (A0)–(A2) with
respect to $\lambda$. Indeed, let $x^{k}=(1+\frac{1}{k},0)$ and
$\mu^{k}_{1}=0$ for all $k\in\mathbb{N}$. Then condition (A0) is satisfied and
conditions (A1) and (A2) are equivalent to

$\begin{cases}\mu^{k}_{2}(0,-1)+\mu^{k}_{3}\left(\frac{3}{k^{2}},1\right)+\left(-2,-\frac{5}{2}\right)\to(0,0),\\\
\frac{1}{k^{3}}\mu^{k}_{3}\to 0,\end{cases}$ (3.1)

as $k\to\infty$. Thus, by letting $\mu^{k}_{2}=\frac{2k^{2}}{3}-\frac{5}{2}$
and $\mu^{k}_{3}=\frac{2k^{2}}{3}$ for all $k\geq 2$, we can check that
condition (3.1) holds. This means that sequences $\\{x^{k}\\}$ and
$\\{\mu^{k}\\}$ satisfy conditions (A0)–(A2), as required.

The next result shows that, for convex problems of the form (CCVP), the AKKT
condition is not only a necessary optimality condition but also a sufficient
one. Recall that problem (CCVP) is called convex if and only if the functions
$f_{i},i=1,\ldots,m,$ are convex and the mapping $g$ is $\Theta$-convex, i.e.,

$g(tx+(1-t)y)-tg(x)-(1-t)g(y)\in-\Theta,$

for all $x,y\in\mathbb{R}^{n}$ and $t\in[0,1]$.

######  Theorem 3.5.

Assume that problem (CCVP) is convex and $\bar{x}\in\mathcal{F}$. Then,
$\bar{x}$ is a weak efficient solution of (CCVP) if and only if $\bar{x}$
satisfies the AKKT condition.

###### Proof.

Thanks to Theorem 3.3, we only need to prove the “if” part. Arguing by
contradiction, assume that $\bar{x}$ satisfies the AKKT condition but
$\bar{x}$ is not a weak efficient solution of (CCVP). Hence there exists
$\hat{x}\in\mathcal{F}$ such that

$f_{i}(\hat{x})<f_{i}(\bar{x}),\ \ \forall i=1,\ldots,m.$ (3.2)

By the AKKT condition, there exist $\lambda\in\mathbb{R}^{m}_{+}$ with
$\sum_{i=1}^{m}\lambda_{i}=1$, $\\{x^{k}\\}\subset\mathbb{R}^{n}$ and
$\\{\mu^{k}\\}\subset\Theta_{+}$ satisfying conditions (A0)–(A2). Since
$f_{i}$, $i=1,\ldots,m$, are convex functions, we have

$f_{i}(\hat{x})\geq f_{i}(\bar{x})+\langle\nabla
f(\bar{x}),\hat{x}-\bar{x}\rangle.$ (3.3)

By the $\Theta$-convexity of $g$, it is easily seen that
$\langle\mu^{k},g(\cdot)\rangle$ is a convex function. Hence

$\langle\mu^{k},g(\hat{x})\rangle\geq\langle\mu^{k},g(x^{k})\rangle+\langle\nabla
g(x^{k})^{\ast}\mu^{k},\hat{x}-x^{k}\rangle,\ \ \forall k\in\mathbb{N}.$ (3.4)

Multiplying (3.3) by $\lambda_{i}$ and adding up then gives, from (3.4) and
the facts that $\hat{x}\in\mathcal{F}$ and $\mu^{k}\in\Theta_{+}$, that

$\displaystyle\sum_{i=1}^{m}\lambda_{i}f_{i}(\hat{x})$
$\displaystyle\geq\sum_{i=1}^{m}\lambda_{i}f_{i}(\hat{x})+\langle\mu^{k},g(\hat{x})\rangle$
$\displaystyle\geq\sum_{i=1}^{m}\lambda_{i}(f_{i}(\bar{x})+\langle\nabla
f(\bar{x}),\hat{x}-\bar{x}\rangle)+\langle\mu^{k},g(x^{k})\rangle+\langle\nabla
g(x^{k})^{\ast}\mu^{k},\hat{x}-x^{k}\rangle$
$\displaystyle=\sum_{i=1}^{m}\lambda_{i}f_{i}(\bar{x})+\sigma_{k}$ (3.5)

for all $k\in\mathbb{N}$, where

$\sigma_{k}:=\langle\mu^{k},g(x^{k})\rangle+\sum_{i=1}^{m}\lambda_{i}\langle\nabla
f(\bar{x}),\hat{x}-\bar{x}\rangle+\langle\nabla
g(x^{k})^{\ast}\mu^{k},\hat{x}-x^{k}\rangle.$

We claim that $\sigma_{k}\to 0$ as $k$ tends to infinity. Indeed, for each
$k\in\mathbb{N}$, we have

$\sigma_{k}=\langle\mu^{k},g(x^{k})\rangle+\left\langle\nabla
g(x^{k})^{\ast}\mu^{k}+\sum_{i=1}^{m}\lambda_{i}\nabla
f_{i}(\bar{x}),\hat{x}-\bar{x}\right\rangle-\langle\nabla
g(x^{k})^{\ast}\mu^{k},x^{k}-\bar{x}\rangle.$

By conditions (A1) and (A2), the two first terms of $\sigma_{k}$ converge to
$0$ as $k\to\infty$. Moreover, from condition (A1) it follows that the
sequence $\\{\nabla g(x^{k})^{\ast}\mu^{k}\\}$ is bounded. This and condition
(A0) imply that the last term of $\sigma_{k}$ also tends to $0$. Hence
$\sigma_{k}\to 0$ as $k$ tends to infinity, as required.

Now, taking $k\to\infty$ in (3.5) yields

$\sum_{i=1}^{m}\lambda_{i}f_{i}(\hat{x})\geq\sum_{i=1}^{m}\lambda_{i}f_{i}(\bar{x}).$
(3.6)

From $\sum_{i=1}^{m}\lambda_{i}=1$ and (3.2) it follows that

$\sum_{i=1}^{m}\lambda_{i}f_{i}(\hat{x})<\sum_{i=1}^{m}\lambda_{i}f_{i}(\bar{x}),$

contrary to (3.6). The proof is complete. ∎

We now introduce some strict constraint qualifications of (CCVP). Recall that
a property P is called a strict constraint qualification (SCQ) of (CCVP) if
and only if the implication

$\mathrm{AKKT+P}\ \ \Rightarrow\ \ \mathrm{KKT}$ (3.7)

is true; see [9, Definition 3.3]. SCQs are important because they are
sufficient conditions to guarantee that limits of AKKT sequences are KKT
points. Furthermore, since every local weak efficient solution satisfies the
AKKT condition, the property (3.7) shows that every SCQ is also a constraint
qualification of (CCVP).

The first SCQ of (CCVP) is as follows.

######  Definition 3.6.

We say that $\bar{x}\in\mathcal{F}$ satisfies the bounded approximate
Karush–Kuhn–Tucker condition (BAKKT) if and only if there exist a vector
$\lambda\in\mathbb{R}^{m}_{+}$ with $\sum_{i=1}^{m}\lambda_{i}=1$ and
sequences $\\{x^{k}\\}\subset\mathbb{R}^{n}$ and
$\\{\mu^{k}\\}\subset\Theta_{+}$ such that conditions (A0)–(A2) hold and the
sequence $\\{\mu^{k}\\}$ is bounded.

######  Theorem 3.7.

If $\bar{x}\in\mathcal{F}$ satisfies the BAKKT condition, then so does the KKT
condition. (That is, the BAKKT condition is an SCQ.)

###### Proof.

By assumption, there exist $\lambda\in\mathbb{R}^{m}_{+}$ with
$\sum_{i=1}^{m}\lambda_{i}=1$, $\\{x^{k}\\}\subset\mathbb{R}^{n}$ and
$\\{\mu^{k}\\}\subset\Theta_{+}$ such that $x^{k}\to\bar{x}$ and

$\displaystyle\nabla g(x^{k})^{*}\mu^{k}+\sum_{i=1}^{m}\lambda_{i}\nabla
f_{i}(\bar{x})\to 0,$ (3.8) $\displaystyle\langle\mu^{k},g(x^{k})\rangle\to
0,$ (3.9)

and the sequence $\\{\mu^{k}\\}$ is bounded. Thanks to [13, Theorem 3.16],
without loss of generality, we may assume that $\mu^{k}\stackrel{{\scriptstyle
w^{\ast}}}{{\longrightarrow}}\mu$ as $k\to\infty$. Since $\Theta_{+}$ is weak∗
closed, one has $\mu\in\Theta_{+}$. Taking the limit in (3.8) and (3.9) as
$k\to\infty$, we obtain

$\nabla g(\bar{x})^{*}\mu+\sum_{i=1}^{m}\lambda_{i}\nabla f_{i}(\bar{x})=0\ \
\text{and}\ \ \langle\mu,g(\bar{x})\rangle=0.$

This means that $\bar{x}$ satisfies the KKT condition. The proof is complete.
∎

We next show that if the cone $\Theta$ is dually compact, then the Robinson
constraint qualification is a sufficient condition for the BAKKT condition.

######  Definition 3.8 (see [38]).

We say that $\bar{x}\in\mathcal{F}$ satisfies the Robinson constraint
qualification (RCQ) if and only if

$0\in\mathrm{int}\left[g(\bar{x})+\nabla
g(\bar{x})(\mathbb{R}^{n})+\Theta\right].$

######  Remark 3.9.

Thanks to [10, Proposition 2.95], the RCQ is equivalent to the following
condition

$\nabla g(\bar{x})(\mathbb{R}^{n})+\mathrm{cone}\,(\Theta+g(\bar{x}))=Y.$
(3.10)

Moreover, if $\Theta$ has a nonempty interior, then by [10, Lemma 2.99] the
RCQ is equivalent to the Mangasarian–Fromovitz constraint qualification:

$\exists d\in\mathbb{R}^{n}\;:\;g(\bar{x})+\nabla
g(\bar{x})d\in-\mathrm{int}\,\Theta.$

######  Definition 3.10 (see [36, Definition 3.1]).

We say that a closed convex cone $\Theta\subset Y$ is dually compact if and
only if there exists a compact subset $K$ of $Y$ such that

$\Theta_{+}\subset\mathcal{W}(K),$

where

$\mathcal{W}(K):=\left\\{y^{\ast}\in
Y^{\ast}\;:\;\|y^{\ast}\|\leq\sup\\{\langle y^{\ast},y\rangle\;:\;y\in
K\\}\right\\}.$

The following remark summarizes some important facts of the dually
compactness. For more information, the readers are referred to [36, 15] and
the references therein.

######  Remark 3.11.

  1. (i)

The cone $\Theta$ is dually compact if and only if there exists a finite
subset $P:=\\{y_{1},y_{2},\ldots,y_{p}\\}\subset Y$ such that

$\Theta_{+}\subset\left\\{y^{\ast}\in
Y^{\ast}\;:\;\|y^{\ast}\|\leq\max\\{\langle y^{\ast},y_{i}\rangle\;:\;y_{i}\in
P\\}\right\\}.$

  2. (ii)

The cone $\Theta$ is dually compact if and only if $\Theta_{+}$ is weak∗
locally compact.

  3. (iii)

If $\mathrm{dim}\,Y<\infty$ or $\mathrm{int}\,\Theta\not=\emptyset$, then
$\Theta$ is dually compact. The converse does not hold in general. For
example, the cone

$\Theta:=\left\\{(0,\theta_{1},\theta_{2},\ldots)\in
l_{2}\;:\;\sum_{k=2}^{\infty}\theta_{k}^{2}\leq+\infty\right\\}$

has an empty interior, but it is dually compact.

  4. (iv)

If $\Theta$ is dually compact, then

$\mu^{k}\stackrel{{\scriptstyle
w^{\ast}}}{{\longrightarrow}}0\Leftrightarrow\mu^{k}\to 0\ \ \text{for any
(generalized) sequence}\ \ \\{\mu^{k}\\}\subset\Theta_{+}.$

######  Theorem 3.12.

Assume that $\Theta$ is dually compact. Let $\bar{x}\in\mathcal{F}$ be such
that the AKKT condition and the RCQ are satisfied. Then the BKKT condition
holds and so does the KKT condition.

###### Proof.

Since $\bar{x}$ satisfies the AKKT condition, there exist
$\lambda\in\mathbb{R}^{m}_{+}$ with $\sum_{i=1}^{m}\lambda_{i}=1$,
$\\{x^{k}\\}\subset\mathbb{R}^{n}$ and $\\{\mu^{k}\\}\subset\Theta_{+}$ such
that $x^{k}\to\bar{x}$ and

$\displaystyle\nabla g(x^{k})^{*}\mu^{k}+\sum_{i=1}^{m}\lambda_{i}\nabla
f_{i}(\bar{x})\to 0,$ (3.11) $\displaystyle\langle\mu^{k},g(x^{k})\rangle\to
0.$ (3.12)

We claim that the sequence $\\{\mu^{k}\\}$ is bounded. Indeed, if otherwise,
then we may assume without loss of generality that $\|\mu^{k}\|\to\infty$ as
$k\to\infty$. For each $k\in\mathbb{N}$, put
$\tilde{\mu}^{k}:=\frac{\mu^{k}}{\|\mu^{k}\|}$. Then, $\|\tilde{\mu}^{k}\|=1$
for all $k\in\mathbb{N}$. Selecting a subsequence if necessary we may assume
that $\\{\tilde{\mu}^{k}\\}$ converges weakly∗ to some
$\tilde{\mu}\in\Theta_{+}$. By the dually compactness, we see that
$\tilde{\mu}$ is not null. Indeed, if otherwise, then $\mu^{k}\to 0$ in norm
due to Remark 3.11(iv) and this is not possible since $\|\mu^{k}\|=1$ for all
$k\in\mathbb{N}$. From (3.11) and (3.12), we have

$\displaystyle\nabla
g(\bar{x})^{\ast}\tilde{\mu}=\lim\limits_{k\to\infty}\left[\nabla
g(x^{k})^{*}\tilde{\mu}^{k}+\frac{1}{\|\mu^{k}\|}\sum_{i=1}^{m}\lambda_{i}\nabla
f_{i}(\bar{x})\right]=0,$
$\displaystyle\langle\tilde{\mu},g(\bar{x})\rangle=\lim\limits_{k\to\infty}\langle\tilde{\mu}^{k},g(x^{k})\rangle=0.$

Therefore

$\displaystyle\langle\tilde{\mu},\nabla
g(\bar{x})d+t(\theta+g(\bar{x}))\rangle$ $\displaystyle=\langle\nabla
g(\bar{x})^{*}\tilde{\mu},d\rangle+t\langle\tilde{\mu},g(\bar{x})\rangle+t\langle\tilde{\mu},\theta\rangle$
$\displaystyle=t\langle\tilde{\mu},\theta\rangle\geq 0,$

for all $d\in\mathbb{R}^{n}$, $\theta\in\Theta$ and $t\geq 0$. This means that

$\langle\tilde{\mu},\nabla g(\bar{x})d+v\rangle\geq 0,\ \ \forall
d\in\mathbb{R}^{n},v\in\mathrm{cone}\,(\Theta+g(\bar{x})).$

Thanks to (3.10), we obtain

$\langle\tilde{\mu},y\rangle\geq 0,\ \ \forall y\in Y.$

This implies that $\tilde{\mu}=0$, a contradiction. Hence the sequence
$\\{\mu^{k}\\}$ is bounded. The poof is complete. ∎

The following example shows that the BAKKT condition does not imply the RCQ
condition.

######  Example 3.13.

Consider the following problem:

$\displaystyle\text{min}\,f(x)$ $\displaystyle\text{s.t.}\ \
x\in\mathcal{F}:=\\{x\in\mathbb{R}^{2}\,:\,g(x)\in-\Theta\\},$

where $\Theta=\mathbb{R}^{3}_{+}$ and

$f(x)=x_{1},g(x)=(g_{1}(x),g_{2}(x),g_{3}(x)),g_{1}(x)=-x_{1},g_{2}(x)=-x_{2},g_{3}(x)=x_{2},$

for all $x=(x_{1},x_{2})\in\mathbb{R}^{2}$. Then we have that the feasible set
is $\mathcal{F}=\mathbb{R}_{+}\times\\{0\\}$ and $\bar{x}=(0,0)$ is a minimum
point of $f$ on $\mathcal{F}$. Since

$\nabla f(\bar{x})=(1,0),\nabla g_{1}(\bar{x})=(-1,0),\nabla
g_{2}(\bar{x})=(0,-1),\nabla g_{3}(\bar{x})=(0,1),$

it is easy to check that $\bar{x}$ satisfies the KKT (BAKKT) but not the RCQ
condition.

We are now introducing the weakest SCQ associated with the AKKT condition
called the AKKT-regularity. Let
$K(\cdot,\cdot)\colon\mathbb{R}^{n}\times\mathbb{R}_{+}\rightrightarrows\mathbb{R}^{n}$
be a set-valued mapping defined by

$K(x,r):=\bigg{\\{}\nabla
g(x)^{*}\mu\;:\;\mu\in\Theta_{+},|\langle\mu,g(x)\rangle|\leq r\bigg{\\}},\ \
\ \forall x\in\mathbb{R}^{n},r\in\mathbb{R}_{+}.$

The set $K(x,r)$ is as a perturbation of $K(\bar{x},0)$ around a given point
$(\bar{x},0)$. This set is always nonempty and convex. Moreover, we have
$K(x,\alpha r)=\alpha K(x,r)$ for all $\alpha>0$.

######  Definition 3.14.

We say that the AKKT-regularity holds at $\bar{x}\in\mathcal{F}$ if and only
if the set-valued mapping $K(\cdot,\cdot)$ is outer semicontinuous at
$(\bar{x},0)$, that is,

$\mathop{{\rm Lim}\,{\rm sup}}_{(x,r)\to(\bar{x},0)}K(x,r)\subset
K(\bar{x},0),$ (3.13)

where

$\mathop{{\rm Lim}\,{\rm
sup}}_{(x,r)\to(\bar{x},0)}K(x,r):=\\{\bar{w}:\exists\,(x^{k},r_{k},w^{k})\to(\bar{x},0,\bar{w})\
\ \text{with}\ \ w^{k}\in K(x^{k},r_{k}),\,\forall k\in\mathbb{N}\\}.$

The following theorem shows that the AKKT-regularity is the weakest SCQ.

######  Theorem 3.15.

A feasible point $\bar{x}$ is the AKKT-regularity if and only if for every
continuously differentiable objective function $f$ in (CCVP) such that the
AKKT condition holds at $\bar{x}$, we have that the KKT condition also holds
at $\bar{x}$.

###### Proof.

$(\Rightarrow):$ Assume that the AKKT-regularity holds at
$\bar{x}\in\mathcal{F}$ and $f$ is an arbitrary continuously differentiable
objective function such that the AKKT holds at $\bar{x}$. Then, there exist
$\lambda\in\mathbb{R}^{m}_{+}$ with $\sum_{i=1}^{m}\lambda_{i}=1$,
$\\{x^{k}\\}\subset\mathbb{R}^{n}$ and $\\{\mu^{k}\\}\subset\Theta_{+}$ such
that $x^{k}\to\bar{x}$ and

$\displaystyle\nabla g(x^{k})^{*}\mu^{k}\to-\sum_{i=1}^{m}\lambda_{i}\nabla
f_{i}(\bar{x}),$ (3.14) $\displaystyle\langle\mu^{k},g(x^{k})\rangle\to 0.$
(3.15)

For each $k\in\mathbb{N}$, put $r_{k}:=|\langle\mu^{k},g(x^{k})\rangle|\ \
\text{and}\ \ w^{k}:=\nabla g(x^{k})^{*}\mu^{k}.$ Then, we have $w^{k}\in
K(x^{k},r_{k})$ for all $k\in\mathbb{N}$. From (3.14), (3.15) and the AKKT-
regularity it follows that

$-\sum_{i=1}^{m}\lambda_{i}\nabla f_{i}(\bar{x})\in K(\bar{x},0).$

Hence $\bar{x}$ satisfies the KKT condition.

$(\Leftarrow):$ Let $\bar{x}\in\mathcal{F}$. Assume that for any continuously
differentiable objective function $f$ in (CCVP) such that if the AKKT
condition holds at $\bar{x}$, then the KKT condition also holds at this point.
We claim that $\bar{x}$ satisfies the AKKT-regularity, i.e., the inclusion
(3.13) holds. Indeed, let $\bar{w}$ be an arbitrary element in the left-hand
side of (3.13). Then, there exists a sequence $\\{(x^{k},r_{k},w^{k})\\}$
converging to $(\bar{x},0,\bar{w})$ such that $w^{k}\in K(x^{k},r_{k})$ for
all $k\in\mathbb{N}$. Hence, for each $k\in\mathbb{N}$, there exists
$\mu^{k}\in\Theta_{+}$ such that

$w^{k}=\nabla g(x^{k})^{*}\mu^{k}\ \ \text{and}\ \
|\langle\mu^{k},g(x^{k})\rangle|\leq r_{k}.$

Let $f$ be the linear function defined by $f(x)=-\langle\bar{w},x\rangle$ for
all $x\in\mathbb{R}^{n}$. Since $w^{k}\to\bar{w}$ and $\nabla
f(\bar{x})=-\bar{w}$, one has

$\nabla g(x^{k})^{*}\mu^{k}+\nabla f(\bar{x})\to 0.$

Moreover, since $r_{k}\to 0$, we have $\langle\mu^{k},g(x^{k})\rangle\to 0.$
By assumption, the KKT condition holds at $\bar{x}$, i.e., there exists
$\mu\in\Theta_{+}$ such that

$\nabla g(\bar{x})^{*}\mu+\nabla f(\bar{x})=0\ \ \text{and}\ \
\langle\mu,g(x)\rangle=0.$

Hence

$\bar{w}=-\nabla f(\bar{x})\in K(\bar{x},0),$

as required. ∎

We finish this section by presenting an example to show that although the
AKKT-regularity is the weakest constraint qualification associated with the
AKKT condition, this condition alone does not imply the RCQ one.

######  Example 3.16.

Let the feasible set $\mathcal{F}$ of (CCVP) be defined by

$\mathcal{F}:=\\{x\in\mathbb{R}^{2}\;:\;g(x)\in-\Theta\\},$

where

$g(x)=(g_{1}(x),g_{2}(x)),g_{1}(x)=x_{1},g_{2}(x)=x_{1}^{2},\ \ \forall
x=(x_{1},x_{2})\in\mathbb{R}^{2},$

and $\Theta=\\{0\\}\times\mathbb{R}_{+}$. Clearly,
$\bar{x}=(0,0)\in\mathcal{F}$. By direct calculations, we get

$\nabla g_{1}(x)=(1,0),\nabla g_{2}(x)=(2x_{1},0),\ \ \forall
x=(x_{1},x_{2})\in\mathbb{R}^{2},$ (3.16)

and $\Theta_{+}=\mathbb{R}\times\mathbb{R}_{+}$. Hence

$\displaystyle g(\bar{x})+\nabla
g(\bar{x})(\mathbb{R}^{n})+\Theta=\mathbb{R}\times\mathbb{R}_{+}.$

This implies that $(0,0)$ is not an interior point of $g(\bar{x})+\nabla
g(\bar{x})(\mathbb{R}^{n})+\Theta$, i.e., the RCQ does not hold at $\bar{x}$.

Now let us prove that the AKKT-regularity holds at $\bar{x}$. Since (3.16), we
have

$\displaystyle K(x,r)$
$\displaystyle=\\{(\mu_{1}+2x_{1}\mu_{2},0)\,:\,\mu_{1}\in\mathbb{R},\mu_{2}\in\mathbb{R}_{+},|\mu_{1}x_{1}+\mu_{2}x_{1}^{3}|\leq
r\\},\;\forall x\in\mathbb{R}^{2},r\in\mathbb{R}_{+},$ $\displaystyle
K(\bar{x},0)$
$\displaystyle=\\{(\mu_{1},0)\,:\,\mu_{1}\in\mathbb{R}\\}=\mathbb{R}\times\\{0\\}.$

Clearly, $K(x,r)\subset K(\bar{x},0)$ for all $x\in\mathbb{R}^{2}$ and
$r\in\mathbb{R}_{+}$. Thus the AKKT-regularity holds at $\bar{x}$.

## References

  * [1] R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim. 18 (2007), 1286–1309.
  * [2] R. Andreani, J. M. Martínez and B. F. Svaiter, A new sequential optimality condition for constrained optimization and algorithmic consequences, SIAM J. Optim. 20 (2010), 3533–3554.
  * [3] R. Andreani, G. Haeser and J. M. Martínez, On sequential optimality conditions for smooth constrained optimization, Optimization 60 (2011), 627–641.
  * [4] R. Andreani, J. M. Martínez, A. Ramos and P. J. S. Silva, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim. 26 (2016), 96–110.
  * [5] R. Andreani, J. M. Martínez, A. Ramos and P. J. S. Silva, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res. 43 (2018), 693–717.
  * [6] R. Andreani, G. Haeser and D. S. Viana, Optimality conditions and global convergence for nonlinear semidefinite programming, Math. Program. (2018). DOI:10.1007/s10107-018-1354-5
  * [7] F. Bai, Z. Wu and D. Zhu, Sequential Lagrange multiplier condition for $\epsilon$-optimal solution in convex programming, Optimization 57 (2008), 669–680.
  * [8] D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, 1999.
  * [9] E. G. Birgin and J. M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, SIAM Publications, Philadelphia, 2014.
  * [10] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 2000.
  * [11] R. I. Boţ, E. R. Csetnek and G. Wanka, Sequential optimality conditions for composed convex optimization problems, J. Math. Anal. Appl. 342 (2008), 1015–1025.
  * [12] R. I. Boţ, E. R. Csetnek and G. Wanka, Sequential characterization of solutions in convex composite programming and applications to vector optimization, J. Ind. Manag. Optim. 4 (2008), 767–782.
  * [13] H. Brezis, Functional Analysis, Sobolev spaces and Partial Differential Equations, Springer, 2010.
  * [14] T. D. Chuong and D. S. Kim, Approximate solutions of multiobjective optimization problems, Positivity 20 (2016), 187–207.
  * [15] M. Durea, J. Dutta and C. Tammer, Bounded sets of Lagrange multipliers for vector optimization problems in infinite dimension, J. Math. Anal. Appl. 348 (2008), 589–606.
  * [16] J. Dutta, S. R. Pattanaik and M. Théra, A note on an approximate Lagrange multiplier rule, Math. Program. 123 (2010), 161–171.
  * [17] J. Dutta, K. Deb, R. Tulshyan and R. Arora, Approximate KKT points and a proximity measure for termination, J. Glob. Optim. 56 (2013), 1463–1499.
  * [18] N. Dinh, M. A. Goberna, M. A. López and M. Volle, Convex inequalities without constraint qualification nor closedness condition, and their applications in optimization, Set-Valued Var. Anal. 18 (2010), 423–445.
  * [19] F. Facchinei and J. S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, vols. I and II, Springer, New York, 2003.
  * [20] M. Feng and S. J. Li, An approximate strong KKT condition for multiobjective optimization, TOP (2018). DOI: 10.1007/s11750-018-0491-6
  * [21] G. Giorgi, B. Jiménez and V. Novo, Approximate Karush–Kuhn–Tucker condition in multiobjective optimization, J. Optim. Theory Appl. 171 (2016), 70–89.
  * [22] G. Haeser and M. L. Schuverdt, On approximate KKT condition and its extension to continuous variational inequalities, J. Optim. Theory Appl. 149 (2011), 528–539.
  * [23] G. Haeser and V. V. Melo, Convergence detection for optimization algorithms: approximate-KKT stopping criterion when Lagrange multipliers are not available, Oper. Res. Lett. 43 (2015), 484–488.
  * [24] R. Hu, Y. -B. Xiao, N. -J. Huang and X. Wang, Equivalence results of well-posedness for split variational-hemivariational inequalities, J. Nonlinear Convex Anal., to appear.
  * [25] V. Jeyakumar, G. M. Lee and N. Dinh, New sequential Lagrange multiplier conditions characterizing optimality without constraint qualification for convex programs, SIAM J. Optim. 14 (2003), 534–547.
  * [26] V. Jeyakumar, The strong conical hull intersection property for convex programming, Math. Program. 106 (2006), 81–92.
  * [27] D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, SIAM, 2000.
  * [28] G. M. Lee and K. B. Lee, On optimality conditions for abstract convex vector optimization problems, J. Korean Math. Soc. 44 (2007), 971–985.
  * [29] R. Li, J. -C. Yao and X. Y. Zheng, Approximate KKT points for smooth vector optimization problems in infinite dimensional spaces, J. Nonlinear Convex Anal. 16 (2015), 1385–1396.
  * [30] X. -J. Long, Y. -B. Xiao and N. -J. Huang, Optimality conditions of approximate solutions for nonsmooth semi-infinite programming problems, J. Oper. Res. Soc. China 6 (2018), 289–299.
  * [31] J. Lu, Y. -B. Xiao and N. -J. Huang, A Stackelberg quasi-equilibrium problem via quasi-variational inequalities, Carpathian J. Math. 34 (2018), 355-362.
  * [32] J. M. Martínez and B. F. Svaiter, A practical optimality condition without constraint qualifications for nonlinear programming, J. Optim. Theory Appl. 118 (2003), 117–133.
  * [33] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, I: Basic Theory; II: Applications, Springer, Berlin, 2006.
  * [34] B. S. Mordukhovich, Variational Analysis and Applications, Springer, New York, 2018.
  * [35] B. S. Mordukhovich and T. T. A. Nghia, Nonsmooth cone-constrained optimization with applications to semi-infinite programming, Math. Oper. Res. 39 (2014), 301–324.
  * [36] K. F. Ng and X. Y. Zheng, The Fermat rule for multifunctions on Banach spaces, Math. Program. 104 (2005), 69–90.
  * [37] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, New York, 1999.
  * [38] S. M. Robinson, Stability theory for systems of inequalities. II. Differentiable nonlinear systems, SIAM J. Numer. Anal. 13 (1976), 497–513.
  * [39] Q. -Y. Shu, R. Hu and Y. -B. Xiao, Metric characterizations for well-posedness of split hemivariational inequalities, J. Ineq. Appl. 2018:190 (2018). DOI:10.1186/s13660-018-1761-4.
  * [40] M. Sofonea, Y. -B. Xiao and M. Couderc, Optimization problems for elastic contact models with unilateral constraints, Z. Angew. Math. Phys. (2019). DOI:10.1007/s00033-018-1046-2
  * [41] N. V. Tuyen, J. -C. Yao and C. -F. Wen, A note on approximate Karush–Kuhn–Tucker conditions in locally Lipschitz multiobjective optimization, Optim. Lett. 13 (2019), 163–174.
  * [42] Y. -B. Xiao and M. Sofonea, On the optimal control of variational-hemivariational inequalities, J. Math. Anal. Appl. (2019). DOI:10.1016/j.jmaa.2019.02.046


Eigenvalues and Diagonal Elements

1Rajendra Bhatia and 2Rajesh Sharma

1Ashoka University, Sonepat, Haryana, 131029, India

2Department of Mathematics & Statistics, H.P. University Shimla-5, India

Abstract. A basic theorem in linear algebra says that if the eigenvalues and
the diagonal entries of a Hermitian matrix are ordered as
$\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n}$ and $a_{1}\leq
a_{2}\leq\cdots\leq a_{n},$ respectively, then $\lambda_{1}\leq a_{1}.$ We
show that for some special classes of Hermitian matrices this can be extended
to inequalities of the form $\lambda_{k}\leq a_{2k-1},$
$k=1,2,...,\lceil\frac{n}{2}\rceil.$

Key words: Hermitian matrix, Majorization, Nonnegative matrix, Laplacian
matrix of graph.

Let $A$ be an $n\times n$ complex Hermitian matrix. The eigenvalues and the
diagonal entries of $A$ are real numbers, and we enumerate them in increasing
order as

$\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{n},$

and

$a_{1}\leq a_{2}\leq\cdots\leq a_{n},$

respectively. Various inequalities relating these two $n$-tuples are known and
are much used in matrix analysis. For example, we have

$\lambda_{1}\leq a_{1}\text{ \ \ and\ \ }\lambda_{n}\geq a_{n}.$ (1)

These are subsumed in the majorization relations due to I. Schur: for $1\leq
k\leq n$

$\underset{j=1}{\overset{k}{\sum}}\lambda_{j}\leq\underset{j=1}{\overset{k}{\sum}}a_{j},$
(2)

with equality when $k=n$. This is a complete characterization of two
$n$-tuples that could be the eigenvalues and diagonal entries of a Hermitian
matrix. In general, there are no further relations between individual
$\lambda_{j}$ and $a_{k}.$ However, for large and interesting subsets of
Hermitian matrices, it might be possible to find such extra relations. In [1]
the authors consider eigenvalues of matrices associated with graphs. Let $G$
be a simple weighted graph on $n$ vertices and let $A$ be the signless
Laplacian matrix associated with $G.$ Then, it is shown in [1] that
$\lambda_{2}\leq a_{3}.$ This result is extended to other classes in [3]. One
of these is the class $\mathcal{P}$ of Hermitian matrices whose off-diagonal
entries are nonnegative. (In particular, this includes symmetric entrywise
nonnegative matrices.) It is shown in [3] that if $A\in\mathcal{P},$ then
$\lambda_{2}\leq a_{3}.$

In this note we consider, in addition the class $\mathcal{P}$, another class
$\mathcal{I}$ consisting of Hermitian matrices all whose off-diagonal entries
are purely imaginary. We show that the inequality $\lambda_{2}\leq a_{3}$ is
valid for $A\in\mathcal{I}$ as well. The proof we give works for both the
classes $\mathcal{P}$ and $\mathcal{I}$. Then we show that much more is true
for the class $\mathcal{I}.$ We show that in this case the inequality
$\lambda_{n-1}\geq a_{n-2}$ also holds. Further, for all $1\leq
k\leq\lceil\frac{n}{2}\rceil$ we have $\lambda_{k}\leq a_{2k-1}.$ We construct
examples to show that neither of these results is true for the class
$\mathcal{P}.$

Theorem 1. Let $A$ be an $n\times n$ Hermitian matrix whose off-diagonal
entries are either all nonnegative real numbers or all purely imaginary
numbers. Then

$\lambda_{2}\leq a_{3}.$ (3)

In case the off-diagonal entries are all purely imaginary, we also have

$\lambda_{n-1}\geq a_{n-2}.$ (4)

For the second class of matrices in Theorem 1, we can go further:

Theorem 2. Let $A$ be an $n\times n$ Hermitian matrix whose off-diagonal
entries are all purely imaginary. Then, for $1\leq
k\leq\lceil\frac{n}{2}\rceil,$

$\lambda_{k}\leq a_{2k-1}\text{ \ \ and \ \ }\lambda_{n-k+1}\geq a_{n-2k+2}.$
(5)

We remark that in both (1) and (5) the second inequality follows from the
first by considering $-A$ in place of $A$. Similarly (4) follows from (3). The
argument cannot be used for the class $\mathcal{P}$.

Our proofs rely upon two basic theorems of matrix analysis. Let
$\lambda_{j}\left(A\right)$, $1\leq j\leq n$, denote the eigenvalues of a
Hermitian matrix enumerated in the increasing order. Weyl’s inequality says
that if $A$ and $B$ are two $n\times n$ Hermitian matrices, then

$\lambda_{j}\left(A+B\right)\leq\lambda_{j}\left(A\right)+\lambda_{n}\left(B\right),\text{
\ \ \ }1\leq j\leq n.$ (6)

Cauchy’s interlacing principle says that if $A_{r}$ is an $r\times r$
principal submatrix of $A$, then

$\lambda_{j}\left(A\right)\leq\lambda_{j}\left(A_{r}\right),\text{ \ \ \
}1\leq j\leq r.$ (7)

See Chapter III of [2] for this and other facts used here.

Proof of Theorem 1. If $P$ is a permutation matrix, then the increasingly
ordered eigenvalues and diagonal entries of $PAP^{T}$ are the same as those of
$A$. So, for simplicity, we may assume that the diagonal entries of $A$ are in
increasing order. Let

$A_{3}=\left[\begin{array}[]{ccc}a_{11}&a_{12}&a_{12}\\\
\overline{a_{12}}&a_{22}&a_{23}\\\
\overline{a_{13}}&\overline{a_{23}}&a_{33}\end{array}\right]$

be the top-left $3\times 3$ submatrix of $A$. (Note $a_{jj}=a_{j}$ is our
notation.) Decompose

$A_{3}=D_{3}+M_{3}$ (8)

where $D_{3}$ is the diagonal part and $M_{3}$ the off-diagonal part of
$A_{3}$. By Weyl’s inequality

$\lambda_{2}\left(A_{3}\right)\leq\lambda_{2}\left(M_{3}\right)+\lambda_{3}\left(D_{3}\right)=\lambda_{2}\left(M_{3}\right)+a_{3}.$
(9)

Note that $\det M_{3}=2\mathop{\mathrm{R}e}a_{12}a_{23}\overline{a_{13}}$. So,
under the hypothesis of Theorem 1, $\det M_{3}\geq 0.$ We also have
tr$M_{3}=0$. These two conditions imply that we must have
$\lambda_{2}\left(M_{3}\right)\leq 0$. For, if
$\lambda_{3}\left(M_{3}\right)\geq\lambda_{2}\left(M_{3}\right)>0$, then the
condition tr$M_{3}=0$ forces $\lambda_{1}\left(M_{3}\right)$ to be negative.
But this is impossible if $\det M_{3}\geq 0.$ So, from (9) we see that
$\lambda_{2}\left(A_{3}\right)\leq a_{3}.$ Then, by the interlacing principle
(7), we have $\lambda_{2}\left(A\right)\leq a_{3}.$ $\blacksquare$

Here we should observe that the only property of $M_{3}$ we used was that
$\det M_{3}\geq 0$. Thus the conclusion of Theorem 1 is valid for some other
matrices not included in the classes $\mathcal{P}$ or $\mathcal{I}$.

Proof of Theorem 2. Let $A_{r}$ be the top $r\times r$ principal submatrix of
$A$. Decompose $A_{r}$ as

$A_{r}=D_{r}+M_{r}$

where $D_{r}$ is diagonal and $M_{r}$ off-diagonal. The matrix $iM_{r}$ is a
real skew-symmetric matrix. So, the nonzero eigenvalues of $iM_{r}$ are purely
imaginary and occur in conjugate pairs. Thus the nonzero eigenvalues of
$M_{r}$ occur in $\pm$ pairs. This shows that

$\lambda_{k}\left(M_{r}\right)\leq 0\text{ \ \ for \ }1\leq
k\leq\lceil\frac{r}{2}\rceil.$ (10)

Now let $1\leq k\leq\lceil\frac{n}{2}\rceil.$ Using, successively, the
interlacing principle, Weyl’s inequality and (10), we get

$\lambda_{k}\left(A\right)\leq\lambda_{k}\left(A_{2k-1}\right)\leq\lambda_{k}\left(M_{2k-1}\right)+a_{2k-1}\leq
a_{2k-1}.$

$\blacksquare$

We now give two examples to show why for the case of matrices with nonnegative
off-diagonal entries we have to be content just with inequality (3). Let $A$
be the $4\times 4$ matrix

$A=\left[\begin{array}[]{cccc}0&1&1&1\\\ 1&0&1&1\\\ 1&1&0&1\\\
1&1&1&0\end{array}\right].$

The $4\times 4$ matrix $E$ all whose entries are equal to one has eigenvalues
$(4,0,0,0)$. So the matrix $A=E-I$ has eigenvalues $(3,-1,-1,-1)$. Thus
$\lambda_{3}=-1$, and the inequality (4) does not hold in this case.

Let $B$ be the $5\times 5$ matrix

$B=\left[\begin{array}[]{ccccc}0&0&1&1&0\\\ 0&0&0&1&1\\\ 1&0&0&0&1\\\
1&1&0&0&0\\\ 0&1&1&0&0\end{array}\right].$

Then $B=S^{2}+S^{3}$, where $S$ is the shift matrix

$S=\left[\begin{array}[]{ccccc}0&1&0&0&0\\\ 0&0&1&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\\\ 1&0&0&0&0\end{array}\right].$

The eigenvalues of $S$ are the fifth roots of 1. Using this one readily sees
that the eigenvalues of $B$ are $2$, $2\cos\frac{2\pi}{5}$ and
$2\cos\frac{4\pi}{5}$, the first of these with multiplicity one and the latter
two with multiplicities two each. In particular, $\lambda_{3}>0$ and the
assertion $\lambda_{3}\leq a_{5}$ in the first inequality (5) does not hold in
this case.

Acknowledgements. The second author thanks Ashoka University for arranging his
visit during Dec 2021- Jan 2022.

## References

  * [1] A. Berman and M. Farber, A lower bound for the second Laplacian eigenvalues of weighted graphs, Electron. J. Linear Algebra, 22 (2011), 1179-1184.
  * [2] R. Bhatia, Matrix Analysis, Springer Verlag New York, (1997).
  * [3] Z. Charles, M. Farber, C. R. Johnson, L.K. Shaffer, The relation between the diagonal entries and eigenvalues of a symmetric matrix, based upon the sign patterns of its off-diagonal entries, Linear Algebra Appl; 438 (2013), 1427-1445.