Controllability and Observability Imply Exponential Decay of Sensitivity in Dynamic Optimization

Sungho Shin and Victor M. Zavala Department of Chemical and Biological Engineering,
University of Wisconsin-Madison, Madison, WI 53706 USA
(e-mail: {sungho.shin,victor.zavala}@wisc.edu).

Abstract

We study a property of dynamic optimization (DO) problems (as those encountered in model predictive control and moving horizon estimation) that is known as exponential decay of sensitivity (EDS). This property indicates that the sensitivity of the solution at stage $i$ against a data perturbation at stage $j$ decays exponentially with $|i-j|$ . Building upon our previous results, we show that EDS holds under uniform boundedness of the Lagrangian Hessian, a uniform second order sufficiency condition (uSOSC), and a uniform linear independence constraint qualification (uLICQ). Furthermore, we prove that uSOSC and uLICQ can be obtained under uniform controllability and observability. Hence, we have that uniform controllability and observability imply EDS. These results provide insights into how perturbations propagate along the horizon and enable the development of approximation and solution schemes. We illustrate the developments with numerical examples.

keywords:

sensitivity analysis, nonlinear, model predictive control, moving horizon estimation

^†^†thanks: We acknowledge support from the Grainger Wisconsin Distinguished Graduate Fellowship.

1 Introduction

This work studies the discrete-time, dynamic optimization (DO) formulation:


$\displaystyle\min_{\begin{subarray}{c}x_{0:N}\\ u_{0:N-1}\end{subarray}}\;$	$\displaystyle\sum_{i=0}^{N-1}\ell_{i}(x_{i},u_{i};d_{i})+\ell_{N}(x_{N};d_{N})$	(1a)
$\displaystyle\mathop{\text{s.t.}}\;$	$\displaystyle Tx_{0}=d_{-1}\quad\|\quad\lambda_{-1}$	(1b)
	$\displaystyle x_{i+1}=f_{i}(x_{i},u_{i};d_{i}),\;i\in\mathbb{I}_{[0,N-1]}\quad\|\quad\lambda_{i}.$	(1c)

Here, $N\in\mathbb{I}_{>0}$ is the horizon length; for each stage (time) $i$ , $x_{i}\in\mathbb{R}^{n_{x}}$ are the states, $u_{i}\in\mathbb{R}^{n_{u}}$ are the controls, $d_{i}\in\mathbb{R}^{n_{d}}$ are the data (parameters), $\lambda_{i}\in\mathbb{R}^{n_{x}}$ are the dual variables, $\ell_{i}:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\times\mathbb{R}^{n_{d}}\rightarrow\mathbb{R}$ are the stage cost functions, $f_{i}:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{u}}\times\mathbb{R}^{n_{d}}\rightarrow\mathbb{R}^{n_{x}}$ are the dynamic mapping functions, $\ell_{N}:\mathbb{R}^{n_{x}}\times\mathbb{R}^{n_{d}}\rightarrow\mathbb{R}$ is the final cost function, and the symbol $|$ is used to denote the associated dual variables. The initial state constraint is enforced with the initial state mapping $T\in\mathbb{R}^{n_{0}\times n_{x}}$ and parameter $d_{-1}\in\mathbb{R}^{n_{0}}$ . We let $x_{-1},u_{-1},u_{N},\lambda_{N}$ be empty vectors (for convenience), and define $z_{i}:=[x_{i},u_{i}]$ , $w_{i}:=[z_{i};\lambda_{i}]$ , and $\xi_{i}:=[w_{i};d_{i}]$ for $i\in\mathbb{I}_{[-1,N]}$ , and we use the syntax $v_{a:b}:=[v_{a};v_{a+1};\cdots;v_{b}]$ for $v=x,u,\lambda,d,z,w,\xi$ . The DO problem (1) is a parametric nonlinear program that we denote as $P_{0:N}(d_{-1:N})$ . We assume that all functions are twice continuously differentiable and potentially nonconvex. Typical MPC problems are formulated with $T=I$ and typical MHE problems are formulated with an empty matrix $T\in\mathbb{R}^{0\times n_{x}}$ (i.e., the initial constraint is not enforced). State-output mappings encountered in MHE problems are assumed to be embedded within the stage cost functions.

In this paper we study a property of DO problems that is known as exponential decay of sensitivity (EDS) (Na and Anitescu, 2020a; Shin et al., 2021). The property indicates that the sensitivity of the solution at stage $i$ against a data perturbation at stage $j$ decays exponentially with $|i-j|$ . This property helps understand how different data perturbations (e.g., disturbances or changes in set-points, initial conditions, and terminal penalties) propagate along with the time horizon. Moreover, EDS has been shown to be essential in constructing efficient discretization schemes for continuous-time DO formulations (Shin and Zavala, 2020; Grüne et al., 2020b) and in establishing convergence of algorithms (Na et al., 2020; Na and Anitescu, 2020b).

Building upon our previous results (Shin et al., 2021) we show that, under uniform boundedness of the Lagrangian Hessian (uBLH), a uniform second order sufficiency condition (uSOSC), and a uniform linear independence constraint qualification (uLICQ), the primal-dual solution of the DO problem at a given stage decays exponentially with the distance to the stage at which a data perturbation is introduced. In particular, given base data $d_{-1:N}^{\star}$ and associated primal-dual solution trajectory $w^{\star}_{-1:N}$ (at which uBLH, uSOSC, and uLICQ are satisfied), there exist uniform constants $\Upsilon>0$ and $\rho\in(0,1)$ and a neighborhood $\mathbb{D}^{\star}_{-1:N}$ of $d_{-1:N}^{\star}$ such that the following holds for any $d_{-1:N},d^{\prime}_{-1:N}\in\mathbb{D}^{\star}_{-1:N}$ :

\displaystyle\|w^{\dagger}_{i}(d_{-1:N})-w^{\dagger}_{i}(d^{\prime}_{-1:N})\|\leq{\sum_{j=-1}^{N}}\Upsilon\rho^{|i-j|}\|d_{j}-d^{\prime}_{j}\|,

(2)

where $w^{\dagger}_{i}(\cdot)$ is the primal-dual solution mapping at stage $i$ . That is, the sensitivity $\Upsilon\rho^{|i-j|}$ of the solution at stage $i$ against a data perturbation at stage $j$ decays exponentially with respect to the distance $|i-j|$ . Here, it is important that $(\Upsilon,\rho)$ are uniform constants (independent of horizon length $N$ ); this allows us to maintain $(\Upsilon,\rho)$ unchanged even if the horizon length becomes indefinitely long (e.g., when approaching an infinite horizon). Our key finding is that uBLH, uLICQ, and uSOSC can be obtained under uniform controllability/observability and under uniformly bounded system matrices (standard assumption). This result thus allows to establish EDS directly from fundamental system-theoretic properties.

In summary, our main contribution is showing that controllability and observability provide sufficient conditions for EDS. This result sheds light on how system-theoretic properties influence the propagation of perturbations along the solution trajectory. EDS for continuous-time, linear-quadratic MPC has been established under stablizability and detectability in Grüne et al. (2019, 2020b, 2020a). EDS has been established for discrete-time, nonlinear MPC under uniform SOSC and controllability in (Na and Anitescu, 2020a); the proof of this result uses a Riccati recursion representation of the optimality conditions of the DO problem. The proof that we present here is more compact and general; specifically, our approach is based on a graph-theoretic analysis of the optimality conditions. This general setting allows us to establish EDS for discrete-time, nonlinear MPC and MHE problems.

Basic Notation: The set of real numbers and the set of integers are denoted by $\mathbb{R}$ and $\mathbb{I}$ , respectively, and we define $\mathbb{I}_{A}:=\mathbb{I}\cap A$ , where $A$ is a set; $\mathbb{I}_{>0}:=\mathbb{I}\cap(0,\infty)$ ; $\mathbb{I}_{\geq 0}:=\mathbb{I}\cap[0,\infty)$ . We consider vectors always as column vectors. We use the syntax: $\{M_{i}\}_{i=1}^{N}:=[M_{1};\cdots;M_{N}]:=[M_{1}^{\top}\,\cdots\,M_{n}^{\top}]^{\top}$ . Furthermore, $v[i]$ denotes the $i$ -th component of $v$ . For a function $\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and variable vectors $y\in\mathbb{R}^{p}$ , $z\in\mathbb{R}^{q}$ , $\nabla^{2}_{yz}\phi(x):=\{(\{\frac{\partial^{2}}{\partial y[i]\partial z[j]}\phi(x)\}_{j=1}^{q})^{\top}\}_{i=1}^{p}$ . For a vector function $\varphi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ and a variable vector $w\in\mathbb{R}^{s}$ , $\nabla_{w}\varphi(x):=\{(\{\frac{\partial}{\partial w[j]}\varphi(x)[i]\}_{j=1}^{s})^{\top}\}_{i=1}^{m}$ . Vector 2-norms and induced 2-norms of matrices are denoted by $\|\cdot\|$ . For matrices $A$ and $B$ with the same dimensions, $A\succ(\succeq)B$ indicates that $A-B$ is positive (semi) definite. We use the convention: if $m$ or $n$ is zero, $\mathbb{R}^{m\times n}$ is a singleton only containing the $m\times n$ null matrix.

2 Main Results

2.1 Exponential Decay of Sensitivity

In this section, we establish EDS (2) for $P_{0:N}(\cdot)$ . We first formally define sufficient conditions for EDS to hold (uBLH, uSOSC, and uLICQ). We begin by defining the notion of uniformly bounded quantities.

Definition 1 (Uniform Bounds).

A set $\{A_{i}\}_{i\in\mathcal{A}}$ is called $L$ -uniformly bounded above (below) if there exists a uniform constant $L\in\mathbb{R}$ (independent of $N$ ) such that $\|A_{i}\|\leq(\geq)L$ holds for any $i\in\mathcal{A}$ .

We say that a set of a quantity is uniformly bounded above (below) if there exists a uniform constant $L$ such that the set is $L$ -uniformly bounded above (below). Also, we will write that some quantity $a$ is uniformly bounded above (below) if $\{a\}$ is uniformly bounded above (below).

The Lagrangian function of $P_{0:N}(d_{-1:N})$ is defined as

\displaystyle\mathcal{L}_{0:N}(w_{-1:N};d_{-1:N}):=\sum_{i=0}^{N}\mathcal{L}_{i}(z_{i},\lambda_{i-1:i};d_{i}),

where:

	$\displaystyle\mathcal{L}_{i}(z_{i},\lambda_{i-1:i};d_{i})$	$\displaystyle:=\ell_{i}(z_{i};d_{i})-\lambda_{i-1}^{\top}x_{i}+\lambda_{i}^{\top}f_{i}(z_{i};d_{i})$
	$\displaystyle\mathcal{L}_{N}(x_{N},\lambda_{N-1};d_{N})$	$\displaystyle:=\ell_{N}(x_{N};d_{N})-\lambda^{\top}_{N-1}x_{N}.$

Definition 2 (uBLH).

Given $d_{-1:N}^{\star}$ and the solution $w_{-1:N}^{\star}$ of $P_{0:N}(d_{-1:N}^{\star})$ , $L$ -uBLH holds if:

\displaystyle\|\nabla^{2}_{w_{-1:N}\xi_{-1:N}}\mathcal{L}_{0:N}(w_{-1:N}^{\star};d_{-1:N}^{\star})\|\leq L,

(3)

with uniform constant $L<\infty$ .

The primal Hessian $\boldsymbol{H}_{0:N}$ of the Lagrangian and the constraint Jacobian $\boldsymbol{J}_{0:N}$ are:


$\displaystyle\boldsymbol{H}_{0:N}$	$\displaystyle:=\nabla^{2}_{z_{0:N},z_{0:N}}\mathcal{L}_{0:N}(w_{-1:N}^{\star};d_{-1:N}^{\star})$	(4a)
$\displaystyle\boldsymbol{J}_{0:N}$	$\displaystyle:=\nabla_{z_{0:N}}c_{-1:N-1}(z^{\star}_{0:N};d_{-1:N}^{\star}),$	(4b)

where $c_{-1:N-1}(\cdot)$ is the constraint function for $P_{0:N}(\cdot)$ ; that is,

c_{-1:N-1}(z_{0:N};d_{-1:N}):=\begin{bmatrix}Tx_{0}-d_{-1}\\ x_{1}-f_{1}(z_{0};d_{0})\\ \cdots\\ x_{N}-f_{N-1}(z_{N-1};d_{N-1})\end{bmatrix}.

Definition 3 (uSOSC).

Given $d_{-1:N}^{\star}$ and the solution $w_{-1:N}^{\star}$ of $P_{0:N}(d_{-1:N}^{\star})$ , $\gamma$ -uSOSC holds if:

\displaystyle ReH(\boldsymbol{H}_{0:N},\boldsymbol{J}_{0:N})\succeq\gamma I,

(5)

with uniform constant $\gamma>0$ .

Here, $ReH(\boldsymbol{H}_{0:N},\boldsymbol{J}_{0:N}):=Z^{\top}\boldsymbol{H}_{0:N}Z$ is the reduced Hessian and $Z$ is a null-space matrix of $\boldsymbol{J}_{0:N}$ .

Definition 4 (uLICQ).

Given $d_{-1:N}^{\star}$ and the primal-dual solution $w_{-1:N}^{\star}$ of $P_{0:N}(d_{-1:N}^{\star})$ , $\beta$ -uLICQ holds if:

\displaystyle\boldsymbol{J}_{0:N}\boldsymbol{J}_{0:N}^{\top}\succeq\beta I

(6)

with uniform constant $\beta>0$ .

Note that uSOSC assumes that the smallest eigenvalue of the reduced Hessian is uniformly bounded below by $\gamma$ , while uLICQ assumes that the smallest non-trivial singular value of the Jacobian is uniformly bounded below by ${\beta}^{1/2}$ . Thus, these are strengthened versions of SOSC and LICQ. We require uSOSC and uLICQ because, under SOSC and LICQ, the smallest eigenvalue of reduced Hessian or the smallest non-trivial singular value of the Jacobian may become arbitrarily close to $0$ as the horizon length $N$ is extended (e.g., see Shin et al. (2021, Example 4.18)). Under uSOSC and uLICQ, on the other hand, the lower bounds are independent of $N$ .

Assumption 5.

Given twice continuously differentiable functions $\{\ell_{i}(\cdot)\}_{i=0}^{N}$ , $\{f_{i}(\cdot)\}_{i=0}^{N-1}$ and base data $d^{\star}_{-1:N}$ , there exists a primal-dual solution $w_{-1:N}^{\star}$ of $P_{0:N}(d_{-1:N}^{\star})$ at which $L$ -uBLH, $\gamma$ -uSOSC, and $\beta$ -uLICQ are satisfied.

The following lemma is a well-known characterization of solution mappings of parametric nonlinear programs (NLPs) (Robinson, 1980; Dontchev and Rockafellar, 2009).

Lemma 6.

Under Assumption 5, there exist neighborhoods $\mathbb{D}^{\star}_{-1:N}$ of $d^{\star}_{-1:N}$ and $\mathbb{W}^{\star}_{-1:N}$ of $w^{\star}_{-1:N}$ and continuous $w^{\dagger}_{-1:N}:\mathbb{D}^{\star}_{-1:N}\rightarrow\mathbb{W}^{\star}_{-1:N}$ such that for any $d_{-1:N}\in\mathbb{D}^{\star}_{-1:N}$ , $w^{\dagger}_{-1:N}(d_{-1:N})$ is a local solution of $P_{0:N}(d_{-1:N})$ .

{pf}

From Shin et al. (2021, Lemma 3.3). ∎ We can thus see that there exists a well-defined solution mapping $w^{\dagger}_{-1:N}(\cdot)$ around the neighborhood of $d_{-1:N}^{\star}$ . We now study stage-wise solution sensitivity by characterizing the dependence of $w^{\dagger}_{i}(\cdot)$ on the data $d_{-1:N}$ .

Theorem 7.

Under Assumption 5, there exist uniform constants $\Upsilon>0$ and $\rho\in(0,1)$ (functions of $L,\gamma,\beta$ ) and neighborhoods $\mathbb{D}^{\star}_{-1:N}$ of $d_{-1:N}^{\star}$ and $\mathbb{W}^{\star}_{-1:N}$ of $w_{-1:N}^{\star}$ such that (2) holds for any $d_{-1:N},d^{\prime}_{-1:N}\in\mathbb{D}^{\star}_{-1:N}$ and $i\in\mathbb{I}_{[-1,N]}$ .

{pf}

We observe that $P_{0:N}(\cdot)$ is graph-structured (induced by $\mathcal{G}_{N}=(\mathcal{V}_{N},\mathcal{E}_{N})$ , where $\mathcal{V}_{N}=\{-1,0,\cdots,N\}$ and $\mathcal{E}_{N}=\{\{-1,0\},\{0,1\},\cdots,\{N-1,N\}$ ), and the maximum graph degree $D=2$ . From uBLH, uLICQ, and uSOSC, one can see that assumptions in Shin et al. (2021, Theorem 4.9) are satisfied. This implies that the singular values of $\nabla^{2}_{w_{0:N}w_{0:N}}\mathcal{L}_{0:N}(w^{\star}_{-1:N};d^{\star}_{-1:N})$ are uniformly upper and lower bounded and those of $\nabla^{2}_{w_{0:N}d_{-1:N}}\mathcal{L}_{0:N}(w^{\star}_{-1:N};d^{\star}_{-1:N})$ are uniformly upper bounded (uniform constants given by functions of $L,\beta,\gamma$ ; see Shin et al. (2021, Equation (4.15))). We then apply Shin et al. (2021, Theorem 3.5) to obtain $\Upsilon>0$ and $\rho\in(0,1)$ as functions of the upper and lower bounds of the singular values (see Shin et al. (2021, Equation (3.17))). This allows expressing $\Upsilon,\rho$ as functions of $L,\beta,\gamma$ . ∎

Theorem 7 establishes EDS under the regularity conditions of Assumption 5. It is important that $\Upsilon,\rho$ can be determined solely in terms of $L,\gamma,\beta$ (and do not depend on the horizon length $N$ ). Practical DO problems typically have additional equality/inequality constraints that are not considered in (1). Thus, Theorem 7 may not be directly applicable to those problems. However, the results in Shin et al. (2021) are applicable to such problems as long as the DO problem is a graph-structured NLP. Specifically, under uniformly strong SOSC and uLICQ, we can establish EDS using Shin et al. (2021, Theorem 3.5, 4.9). The graph structure breaks when there exist globally coupled variables; typical MPC and MHE problems do not have such variables, but parameter estimation problems may have such variables. Specifically, in the presence of globally coupled variables, the graph distance between any pair of stages is not greater than two.

2.2 Regularity from System-Theoretic Properties

Although uSOSC and uLICQ are standard notions of NLP solution regularity, they are not intuitive notions from a system-theoretic perspective. However, we now show that uSOSC and uLICQ can be obtained from uniform controllability and observability. We begin by defining:

$\displaystyle Q_{i}$	$\displaystyle:=\nabla^{2}_{x_{i}x_{i}}\mathcal{L}_{i}(z^{\star}_{i},\lambda^{\star}_{i-1:i};d^{\star}_{i})$	$\displaystyle R_{i}:=\nabla^{2}_{u_{i}u_{i}}\mathcal{L}_{i}(z^{\star}_{i},\lambda^{\star}_{i-1:i};d^{\star}_{i})$
$\displaystyle S_{i}$	$\displaystyle:=\nabla^{2}_{x_{i}u_{i}}\mathcal{L}_{i}(z^{\star}_{i},\lambda^{\star}_{i-1:i};d^{\star}_{i})$	$\displaystyle E_{i}:=\nabla^{2}_{x_{i}d_{i}}\mathcal{L}_{i}(z^{\star}_{i},\lambda^{\star}_{i-1:i};d^{\star}_{i})$
$\displaystyle F_{i}$	$\displaystyle:=\nabla^{2}_{u_{i}d_{i}}\mathcal{L}_{i}(z^{\star}_{i},\lambda^{\star}_{i-1:i};d^{\star}_{i})$	$\displaystyle A_{i}:=\nabla_{x_{i}}f_{i}(z^{\star}_{i};d^{\star}_{i})$
$\displaystyle B_{i}$	$\displaystyle:=\nabla_{u_{i}}f_{i}(z^{\star}_{i};d^{\star}_{i})$	$\displaystyle G_{i}:=\nabla_{d_{i}}f_{i}(z^{\star}_{i};d^{\star}_{i}).$

Definition 8.

$(\{A_{i}\}_{i=1}^{N-1},\{B_{i}\}_{i=0}^{N-1})$ is $(N_{c},\beta_{c})$ -uniformly controllable with $N_{c}\in\mathbb{I}_{\geq 0}$ and $\beta_{c}>0$ (independent of $N$ ) if, for any $i,j\in\mathbb{I}_{[0,N-1]}$ with $|i-j|\geq N_{c}$ , $\mathcal{C}_{i:j}\mathcal{C}_{i:j}^{\top}\succeq\beta_{c}I$ holds, where

\displaystyle\mathcal{C}_{i:j}:=\begin{bmatrix}A_{i+1:j}B_{i}&\cdots&A_{j}B_{j-1}&B_{j}\end{bmatrix}.

Definition 9.

$(\{A_{i}\}_{i=0}^{N-1},\{Q_{i}\}_{i=0}^{N})$ is $(N_{o},\gamma_{o})$ -uniformly observable with $N_{o}\in\mathbb{I}_{\geq 0}$ and $\gamma_{o}>0$ (independent of $N$ ) if for any $i,j\in\mathbb{I}_{[0,N-1]}$ with $|i-j|\geq N_{o}$ , $\mathcal{O}^{\top}_{i:j}\mathcal{O}_{i:j}\succeq\gamma_{o}I$ holds, where

\displaystyle\mathcal{O}_{i:j}:=\begin{bmatrix}Q_{j}A_{i:j-1}\\ \ddots\\ Q_{i+1}A_{i}\\ Q_{i}\end{bmatrix}.

Here

A_{a:b}:=\begin{cases}A_{b}A_{b-1}\cdots A_{a+1}A_{a},\text{ if }a\leq b\\ A_{b}A_{b+1}\cdots A_{a-1}A_{a},\text{ otherwise.}\end{cases}

Note that uniform controllability and observability are stronger versions of their standard counterparts. One can establish the following duality between uniform controllability and observability.

Proposition 10.

$(\{A_{i}\}_{i=1}^{N},\{B_{i}\}_{i=0}^{N})$ is $(N_{0},\alpha_{0})$ -uniformly controllable if and only if $(\{A^{\top}_{i}\}_{i=N}^{1},\{B^{\top}_{i}\}_{i=N}^{0})$ is $(N_{0},\alpha_{0})$ -uniformly observable (here, note that the orders of sequences $\{A^{\top}_{i}\}_{i=N}^{1},\{B^{\top}_{i}\}_{i=N}^{0}$ are inverted).

{pf}

The proof is straightforward and thus omitted. ∎

The following technical lemma is needed to show that uniform controllability implies uLICQ.

Lemma 11.

Consider a block row/column operator $U$ with $L$ -uniformly bounded above block $V$ of the form:

\displaystyle U:=\begin{bmatrix}I\\ V&I\\ &&\ddots\\ &&&I\end{bmatrix},\begin{bmatrix}I&&&V\\ &I\\ &&\ddots\\ &&&I\end{bmatrix}.

We have that $U,U^{-1}$ are $(L+1)$ -uniformly bounded above.

{pf}

The proof is straightforward and thus omitted. ∎ We now show that uniform controllability implies uLICQ.

Lemma 12.

$K$ -uniform upper boundedness of $\{A_{i}\}_{i=0}^{N-1}$ and $\{B_{i}\}_{i=0}^{N-1}$ , $TT^{\top}\succeq\delta I$ for uniformly lower bounded $\delta>0$ , and $(N_{c},\beta_{c})$ -uniform controllability of $(\{A_{i}\}_{i=1}^{N-1},\{B_{i}\}_{i=0}^{N-1})$ implies (6), where $\beta>0$ is a function of $K,\delta,N_{c},\beta_{c}$ .

{pf}

The Jacobian $\boldsymbol{J}_{0:N}$ has the following form:

\displaystyle\small\boldsymbol{J}_{0:N}=\begin{bmatrix}T\\ -A_{0}&-B_{0}&I\\ &&\ddots\\ &&-A_{N-2}&-B_{N-2}&I\\ &&&&-A_{N-1}&-B_{N-1}&I\end{bmatrix}.

By inspecting the block structure of $\boldsymbol{J}_{0:N}$ and Shin et al. (2021, Lemma 4.15), one can see that it suffices to show that the smallest non-trivial singular value of

\displaystyle\begin{bmatrix}S\\ -A_{i}&-B_{i}&I\\ &&\ddots\\ &&-A_{j-1}&-B_{j-1}&I\\ &&&&-A_{j}&-B_{j}\end{bmatrix}

(7)

is ${\beta}^{1/2}$ -uniformly bounded below for $S=T$ or $I$ and for any $i,j\in\mathbb{I}_{[0,N-1]}$ with $N_{c}\leq|i-j|\leq 2N_{c}$ , where $0<\beta\leq 1$ is a function of $K,\delta,N_{c},\beta_{c}$ . This follows from the observation that one can always partition $\mathbb{I}_{[0,N-1]}$ into a family of blocks with size between $N_{c}$ and $2N_{c}$ . For now, we assume $S=I$ . By applying a set of suitable block row and column operations (in particular, first apply block row operations to eliminate $A_{i},\cdots,A_{j}$ , and then apply block column operations to eliminate $-B_{i},\cdots,-A_{i:j-1}B_{j-2}$ ) and permutations, one can obtain the following:

\displaystyle\begin{bmatrix}I\\ &-A_{i+1:j}B_{i}&\cdots&-A_{j}B_{j-1}&-B_{j}\end{bmatrix}.

(8)

The lower-right blocks constitute the controllability matrix $\mathcal{C}_{i:j}$ ; from uniform controllability, the smallest non-trivial singular value of the matrix in (8) is uniformly lower bounded by $\min(1,\beta_{c}^{1/2})$ . Here, we have applied block-row and block-column operations as the ones that appear in Lemma 11 (each multiplied block is uniformly bounded above due to $K$ -uniform boundedness of $\{A_{i}\}_{i=0}^{N-1}$ and $\{B_{i}\}_{i=0}^{N-1}$ ). Also, we have applied such operations only uniformly bounded many times (the number of operations is independent of $N$ since the number of blocks in the matrix in (7) is bounded by $4(2N_{c}+1)(N_{c}+1)$ , which is uniformly bounded above). We thus have that the smallest non-trivial singular value of the matrix in (7) is uniformly lower bounded with uniform constant ${\beta_{0}}^{1/2}$ , and $\beta_{0}>0$ is given by a function of $K,N_{c},\beta_{c}$ . Now we consider the $S=T$ case. One can observe that the smallest non-trivial singular value of the matrix in (7) with $S=T$ is lower bounded by that with $S=[\widetilde{T};T]$ (here, $\widetilde{T}^{\top}$ is a null space matrix of $T$ ); and again, it is lower bounded by $\delta^{1/2}$ times that with $S=I$ . We thus have that the smallest non-trivial singular value of the matrix in (7) with $S=T$ is uniformly lower bounded by $\beta_{0}^{1/2}\delta^{1/2}$ . Therefore, the smallest non-trivial singular values of the matrices in (7) with $S=I$ or $T$ are $\beta^{1/2}$ -uniformly lower bounded for any $i,j\in\mathbb{I}_{[0,N-1]}$ with $N_{c}\leq|i-j|\leq 2N_{c}$ , where $\beta:=\min(\beta_{0},\delta\beta_{0},1)$ . Thus, by Shin et al. (2021, Lemma 4.15) we have (6). ∎

If $T\in\mathbb{R}^{0\times n_{x}}$ , the assumption $TT^{\top}\succeq\delta I$ for uniformly lower bounded $\delta>0$ holds for an arbitrary $\delta>0$ due to the convention introduced in the Notation in Section 1.

We now show that uniform observability implies uSOSC.

Lemma 13.

$K$ -uniform boundedness of $\{A_{i}\}_{i=0}^{N-1}$ , $\{B_{i}\}_{i=0}^{N-1}$ , and $\{Q_{i}\}_{i=0}^{N}$ , $Q_{i}\succeq 0$ , $S_{i}=0$ , $R_{i}\succeq rI$ ( $r>0$ is independent of $N$ ), and $(N_{o},\gamma_{o})$ -uniform observability of $(\{A_{i}\}_{i=0}^{N-1},\{Q_{i}\}_{i=0}^{N})$ implies (5), where $\gamma>0$ is a function of $K,N_{o},\gamma_{o},r$ .

{pf}

The primal Hessian $\boldsymbol{H}_{0:N}$ has the following form:

\displaystyle\boldsymbol{H}_{0:N}\begin{bmatrix}Q_{0}\\ &R_{0}\\ &&\ddots\\ &&&Q_{N-1}\\ &&&&R_{N-1}\\ &&&&&Q_{N}\end{bmatrix}.

By inspecting the block structure of $\boldsymbol{H}_{0:N}$ and $\boldsymbol{J}_{0:N}$ and Shin et al. (2021, Lemma 4.14), one can observe that it suffices to show that: first,

\displaystyle ReH\left(\begin{bmatrix}\boldsymbol{Q}_{i:j}\\ &\boldsymbol{R}_{i:j-1}\end{bmatrix},\begin{bmatrix}\boldsymbol{A}_{i:j}&\boldsymbol{B}_{i:j-1}\end{bmatrix}\right)

(9)

has $\gamma$ -uniformly lower bounded smallest eigenvalue with $\gamma>0$ for any $i,j\in\mathbb{I}_{[0,N-1]}$ with $N_{o}\leq|i-j|\leq 2N_{o}$ , where:

	$\displaystyle\boldsymbol{A}_{i:j}:=\begin{bmatrix}-A_{i}&I\\ &\ddots&\ddots\\ &&-A_{j-1}&I\end{bmatrix},\boldsymbol{B}_{i:j-1}:=\begin{bmatrix}-B_{i}\\ &&\ddots\\ &&&-B_{j-1}\end{bmatrix}$
	$\displaystyle\boldsymbol{Q}_{i:j}:=\begin{bmatrix}Q_{i}\\ &Q_{i+1}\\ &&\ddots\\ &&&Q_{j}\end{bmatrix},\boldsymbol{R}_{i:j-1}:=\begin{bmatrix}R_{i}\\ &R_{i+1}\\ &&\ddots\\ &&&R_{j-1}\end{bmatrix},$

and second, $R_{i}\succeq\gamma I$ for any $i\in\mathbb{I}_{[0,N-1]}$ . This follows from the observation that one can always partition $\mathbb{I}_{[0,N-1]}$ into a family of blocks with size between $N_{c}$ and $2N_{c}$ . We consider $\boldsymbol{x}_{i:j},\boldsymbol{u}_{i:j-1}$ such that $\boldsymbol{A}_{i:j}\boldsymbol{x}_{i:j}+\boldsymbol{B}_{i:j-1}\boldsymbol{u}_{i:j-1}=0$ holds. By uniform positive definiteness of $\{R_{i}\}_{i=0}^{N-1}$ and uniform boundedness of $\{B_{i}\}_{i=0}^{N-1}$ , for $\kappa:=r/2K^{2}$ , we have

	$\displaystyle\frac{1}{2}\boldsymbol{u}_{i:j-1}^{\top}\boldsymbol{R}_{i:j-1}\boldsymbol{u}_{i:j-1}$	$\displaystyle\geq\kappa\boldsymbol{u}_{i:j-1}^{\top}\boldsymbol{B}_{i:j-1}^{\top}\boldsymbol{B}_{i:j-1}\boldsymbol{u}_{i:j-1}$
		$\displaystyle=\kappa\boldsymbol{x}_{i:j}^{\top}\boldsymbol{A}_{i:j}^{\top}\boldsymbol{A}_{i:j}\boldsymbol{x}_{i:j},$

where the equality follows from $\boldsymbol{A}_{i:j}\boldsymbol{x}_{i:j}+\boldsymbol{B}_{i:j-1}\boldsymbol{u}_{i:j-1}=0$ . Furthermore, from $\boldsymbol{Q}_{i:j}\succeq 0$ , we have that:

\displaystyle\boldsymbol{x}_{i:j}^{\top}\boldsymbol{Q}_{i:j}^{2}\boldsymbol{x}_{i:j}=(\boldsymbol{Q}_{i:j}^{1/2}\boldsymbol{x}_{i:j})^{\top}\boldsymbol{Q}_{i:j}(\boldsymbol{Q}_{i:j}^{1/2}\boldsymbol{x}_{i:j})\leq K\boldsymbol{x}_{i:j}^{\top}\boldsymbol{Q}_{i:j}\boldsymbol{x}_{i:j},

where the inequality follows from that the largest eigenvalue of $\boldsymbol{Q}_{i:j}$ is bounded by $K$ . Thus, $\boldsymbol{x}_{i:j}^{\top}\boldsymbol{Q}_{i:j}\boldsymbol{x}_{i:j}+\boldsymbol{u}_{i:j-1}^{\top}\boldsymbol{R}_{i:j-1}\boldsymbol{u}_{i:j-1}$ is not less than:

\displaystyle\min(1/K,\kappa)\boldsymbol{x}_{i:j}^{\top}\begin{bmatrix}\boldsymbol{Q}_{i:j}&\boldsymbol{A}_{i:j}^{\top}\end{bmatrix}\begin{bmatrix}\boldsymbol{Q}_{i:j}\\ \boldsymbol{A}_{i:j}\end{bmatrix}\boldsymbol{x}_{i:j}+\frac{r}{2}\|\boldsymbol{u}_{i:j-1}\|^{2}.

Observe that $\begin{bmatrix}\boldsymbol{Q}_{i:j}&\boldsymbol{A}_{i:j}^{\top}\end{bmatrix}$ can be permuted to:

\displaystyle\begin{bmatrix}Q_{j}&I\\ &-A_{j-1}&Q_{j-1}&I\\ &&&\ddots\\ &&&-A^{\top}_{i+1}&Q_{i+1}&I\\ &&&&&-A^{\top}_{i}&Q_{i}\end{bmatrix}.

(10)

We apply block row and column operations (as those of Lemma 6) uniformly bounded many times to obtain:

\displaystyle\begin{bmatrix}I\\ &A^{\top}_{j-1:i}Q_{j}&\cdots&A^{\top}_{i}Q_{i+1}&Q_{i}\\ \end{bmatrix}.

(11)

From Proposition 10 and $(N_{o},\gamma_{o})$ -uniform observability of $(\{A_{i}\}_{i=0}^{N-1},\{Q_{i}\}_{i=0}^{N})$ , we have that

(\{A^{\top}_{i}\}_{i=N-1}^{0},\{Q_{i}\}_{i=N}^{0})

(12)

is $(N_{o},\gamma_{o})$ -uniformly controllable. We thus have that the matrix in (11) has $\min(1,\gamma_{o})$ -uniformly lower bounded smallest non-trivial singular value. This implies that the smallest non-trivial singular value of the matrix in (10) is uniformly lower bounded by $\gamma^{\prime}$ , where $\gamma^{\prime}$ is given by a function of $K$ , $N_{o}$ , $\gamma_{o}$ . Therefore, we have that: $\boldsymbol{x}_{i:j}^{\top}\boldsymbol{Q}_{i:j}\boldsymbol{x}_{i:j}+\boldsymbol{u}_{i:j-1}^{\top}\boldsymbol{R}_{i:j-1}\boldsymbol{u}_{i:j-1}\geq\gamma(\|\boldsymbol{x}_{i:j}\|^{2}+\|\boldsymbol{u}_{i:j-1}\|^{2})$ , where $\gamma:=\min(\gamma^{\prime}/K,\kappa\gamma^{\prime},r/2)$ . One can observe that $R_{i}\succeq\gamma I$ for any $i\in\mathbb{I}_{[0,N-1]}$ . Consequently, the smallest eigenvalues of the matrix in (9) for any $i,j\in\mathbb{I}_{[0,N-1]}$ with $N_{o}\leq|i-j|\leq 2N_{o}$ and $R_{i}$ are $\gamma$ -uniformly lower bounded. Thus, by Shin et al. (2021, Lemma 4.14), (5) holds. One can confirm that $\gamma$ is a function of $K,N_{o},\gamma_{o},r$ . ∎

Finally, we show that uniform boundedness of system matrices implies uBLH.

Lemma 14.

If $\{Q_{i}\}_{i=0}^{N}$ , $\{R_{i}\}_{i=0}^{N-1}$ , $\{S_{i}\}_{i=0}^{N-1}$ , $\{A_{i}\}_{i=0}^{N-1}$ , $\{B_{i}\}_{i=0}^{N-1}$ , $\{E_{i}\}_{i=0}^{N-1}$ , $\{F_{i}\}_{i=0}^{N-1}$ , $\{G_{i}\}_{i=0}^{N-1}$ , and $T$ are $K$ -uniformly bounded above, (3) holds, where $L<\infty$ is a function of $K$ .

{pf}

Uniform boundedness of the system matrices implies that for any $i,j\in\mathbb{I}_{[-1,N]}$ , $\nabla^{2}_{w_{i}\xi_{i}}\mathcal{L}_{0:N}(w^{\star}_{-1:N};d^{\star}_{-1:N})$ are uniformly bounded above by $4K$ (Shin et al. (2021, Lemma 4.6)). Furthermore, by inspecting the problem structure, we can see that $\|\nabla^{2}_{w_{i}\xi_{j}}\mathcal{L}_{0:N}(w^{\star}_{-1:N};d^{\star}_{-1:N})\|\leq 1$ for $i\neq j$ (there is only one identity block). Thus, $\|\nabla^{2}_{w_{i}\xi_{j}}\mathcal{L}_{0:N}(w^{\star}_{-1:N};d^{\star}_{-1:N})\|\leq\max(4K,1)$ . By noting that the maximum graph degree $D=2$ and applying Shin et al. (2021, Lemma 4.5), we have that $\nabla^{2}_{w_{-1:N}\xi_{-1:N}}\mathcal{L}_{0:N}(w^{\star}_{-1:N};d^{\star}_{-1:N})$ is $4\max(4K,1)$ -uniformly bounded above. We set $L:=4\max(4K,1)$ .∎ We now state EDS in terms of uniformly bounded system matrices and uniform controllability/observability.

Assumption 15.

Given twice continuously differentiable functions $\{\ell_{i}(\cdot)\}_{i=0}^{N}$ , $\{f_{i}(\cdot)\}_{i=0}^{N-1}$ , and data $d^{\star}_{-1:N}$ , there exists a primal-dual solution $w_{-1:N}^{\star}$ of $P_{0:N}(d_{-1:N}^{\star})$ at which the assumptions in Lemma 12, 13, 14 hold.

Corollary 16.

Under Assumption 15, there exist uniform constants $\Upsilon>0$ and $\rho\in(0,1)$ (functions of $K$ , $r$ , $N_{c}$ , $\beta_{c}$ , $N_{o}$ , $\gamma_{o}$ , $\delta$ ) and neighborhoods $\mathbb{D}^{\star}_{-1:N}$ of $d_{-1:N}^{\star}$ and $\mathbb{W}^{\star}_{-1:N}$ of $w_{-1:N}^{\star}$ such that (2) holds for any $d_{-1:N},d^{\prime}_{-1:N}\in\mathbb{D}^{\star}_{-1:N}$ and $i\in\mathbb{I}_{[-1,N]}$ .

{pf}

From Theorem 7 and Lemma 12, 13, 14. ∎

2.3 Time-Invariant Setting

Assume now that the system is time-invariant and focus on a region around a steady-state. A corollary of Theorem 7 for such a setting is derived. We present this result since this setting has been of particular interest in the MPC literature. Consider a time-invariant system with a stage-cost function $\ell(\cdot)$ , initial regularization function $\ell_{b}(\cdot)$ , terminal cost function $\ell_{f}(\cdot)$ , and dynamic mapping $f(\cdot)$ . The DO problem is given by (1) with $f_{i}(\cdot)=f(\cdot)$ for $i\in\mathbb{I}_{[0,N-1]}$ , $\ell_{i}(\cdot)=\ell(\cdot)$ for $i\in\mathbb{I}_{[1,N-1]}$ , $\ell_{0}(x,u)=\ell(x,u;d)+\ell_{b}(x;d)$ , and $\ell_{N}(x;d)=\ell_{f}(x;d)$ . The steady-state optimization problem is:

\displaystyle\min_{x,u}\;

\displaystyle\ell(x,u;d)\;\mathop{\text{s.t.}}\;x=f(x,u;d)\quad|\quad\lambda.

(13)

For given $d^{s}$ and an associated primal-dual solution $w^{s}:=[x^{s};u^{s};\lambda^{s}]$ of (13), we define:

	$\displaystyle Q$	$\displaystyle:=\nabla^{2}_{xx}\mathcal{L}(w^{s};d^{s}),\,S:=\nabla^{2}_{xu}\mathcal{L}(w^{s};d^{s}),$
	$\displaystyle R$	$\displaystyle:=\nabla^{2}_{uu}\mathcal{L}(w^{s};d^{s}),\,A:=\nabla_{x}f(z^{s};d^{s}),\,B:=\nabla_{u}f(z^{s};d^{s}),$

where $\mathcal{L}(w;d):=f(z;d)-\lambda^{\top}x+\lambda^{\top}f(z;d)$ ; for the initial and terminal cost functions $\ell_{b}(\cdot)$ and $\ell_{f}(\cdot)$ , we define:

	$\displaystyle\lambda_{b}$	$\displaystyle:=\nabla_{x}\ell_{b}(x^{s};d^{s}),\;Q_{b}:=\nabla^{2}_{xx}\ell_{b}(x^{s};d^{s})$
	$\displaystyle\lambda_{f}$	$\displaystyle:=\nabla_{x}\ell_{f}(x^{s};d^{s}),\;Q_{f}:=\nabla^{2}_{xx}\ell_{f}(x^{s};d^{s}).$

The quantities defined above ( $Q$ , $R$ , etc.) are independent of $N$ since $w^{s}$ can be determined independently of $N$ .

Assumption 17.

Given twice continuously differentiable $\ell(\cdot)$ , $\ell_{b}(\cdot)$ , $\ell_{f}(\cdot)$ , $f(\cdot)$ , and data $d^{s}$ , there exists a steady-state solution $w^{s}$ , at which $Q_{f}\succeq Q\succeq 0$ , $Q_{b}\succeq 0$ , $S=0$ , $R\succ 0$ , $(A,B)$ controllable, $(A,Q)$ observable, $TT^{\top}\succ 0$ , $\lambda_{b}+\lambda^{s}\in\text{Range}(T^{\top})$ and $\lambda_{f}=\lambda^{s}$ hold.

Corollary 18.

Under the time invariance setting and Assumption 17, there exist uniform constants $\Upsilon>0$ and $\rho\in(0,1)$ such that the following holds: for any $N\in\mathbb{I}_{\geq 0}$ , there exist neighborhoods $\mathbb{D}^{s}_{-1:N}$ of $d^{s}_{-1:N}:=[Tx^{s};d^{s};\cdots;d^{s}]$ and $\mathbb{W}^{s}_{-1:N}$ of $w_{-1:N}^{s}:=[\lambda^{s}_{-1};w^{s};\cdots;w^{s};x^{s}]$ such that (2) holds for any $d_{-1:N},d^{\prime}_{-1:N}\in\mathbb{D}^{s}_{-1:N}$ , where $\lambda^{s}_{-1}$ is the solution of $T^{\top}\lambda^{s}_{-1}=\lambda_{b}+\lambda^{s}$ .

{pf}

From the existence (follows from $\ell_{b}+\ell^{s}\in\text{Range}(T^{\top})$ ) and uniqueness (follows from $TT^{\top}\succ 0$ ) of the solution of $T^{\top}\lambda^{s}_{-1}=\lambda_{b}+\lambda^{s}$ , we have well-defined $\lambda^{s}_{-1}$ . From $T^{\top}\lambda^{s}_{-1}=\lambda_{b}+\lambda^{s}$ and the optimality of $w^{s}$ for (13), $w^{s}_{-1:N}$ satisfies the first-order optimality conditions for $P_{0:N}(d_{-1:N}^{s})$ . Furthermore, all the assumptions in Lemma 14 are satisfied with some uniform constant $K$ because $\ell(\cdot)$ , $\ell_{b}(\cdot)$ , $\ell_{f}(\cdot)$ , $f(\cdot)$ , $T$ , $w^{s}$ , and $d^{s}$ are independent of $N$ ; thus, by Lemma 14, we have (3) for a uniform constant $L<\infty$ . Moreover, $TT^{\top}\succeq\delta I$ holds for some uniform constant $\delta>0$ , and $R_{i}\succeq rI$ for $i\in\mathbb{I}_{[0,N-1]}$ with some uniform constant $r>0$ , since $\ell(\cdot)$ , $w^{s}$ , $d^{s},T$ are independent of $N$ . Similarly, $(A,B)$ controllability implies $(N_{c},\beta_{c})$ -uniform controllability of $(\{A_{i}\}_{i=1}^{N-1},\{B_{i}\}_{i=0}^{N-1})$ with some uniform constant $N_{c},\beta_{c}$ , and $(A,Q)$ observability implies $(N_{o},\gamma_{o})$ -uniform observability of $(\{A_{i}\}_{i=0}^{N-1},\{Q_{i}\}_{i=0}^{N})$ for some uniform constants $N_{o},\gamma_{o}$ (for now, we assume that $Q_{b}=0$ and $Q_{f}=Q$ ). From Lemma 12, 13, we have (5) and (6) for uniform $\beta,\gamma>0$ . Now, observe that (5) for $Q_{b}=0$ and $Q_{f}=Q$ implies (5) for any $Q_{b}\succeq 0$ and $Q_{f}\succeq Q$ ; thus, we have (5) with uniform $\gamma>0$ for any $Q_{b},Q_{f}$ . Since the first and second order conditions of optimality and constraint qualifications are satisfied, $w^{s}_{-1:N}$ is a strict minimizer for $P_{0:N}(d_{-1:N})$ . Since we have (3), (5), and (6) with uniform $L,\gamma,\beta$ , we have uBLH, uLICQ, and uSOSC at $(w^{s}_{-1:N},d^{s}_{-1:N})$ . By applying Theorem 7, we can obtain (2). Lastly, since the parameters $K,r,N_{c},\beta_{c},N_{o},\gamma_{o}$ are independent of $N$ , so do $\Upsilon$ and $\rho$ .

Initial and terminal cost functions that satisfy Assumption 17 can be constructed as:

	$\displaystyle\ell_{b}(x;d)$	$\displaystyle:=-((I-T^{+}T)\lambda^{s})^{\top}x$
	$\displaystyle\ell_{f}(x;d)$	$\displaystyle:=(x-x^{s})^{\top}Q(x-x^{s})+(\lambda^{s})^{\top}x,$

where $(\cdot)^{+}$ is the pseudoinverse of the argument. One can observe that $\ell_{b}(\cdot)$ can be set to constantly zero if $T=I$ .

3 Numerical Results

Refer to caption — Figure 1: Base and perturbed solutions. Left: Case 1 ( $q=1,b=1$ ). Right: Case 2 ( $q=0,b=0$ ).

We illustrate the results of Theorem 7 and of Corollaries 16, 18. In this study, we solve the problem with base data $d^{\star}_{-1:N}$ to obtain the base solution $w^{\star}_{-1:N}$ . We then solve a set of problems with perturbed data; in each of these problems, a random perturbation $\Delta d_{j}$ is introduced at a selected time stage $j$ , while the rest of the data do not have perturbation (i.e., $\Delta d_{i}=0$ for $i\neq j$ ). The obtained solutions $w^{\dagger}_{-1:N}(d^{\star}_{-1:N}+\Delta d_{-1:N})$ for the perturbed problems are visualized along with the base solution $w^{\star}_{-1:N}$ . The scripts can be found here https://github.com/zavalab/JuliaBox/tree/master/SensitivityNMPC. We consider a quadrotor motion planning problem (Hehn and D’Andrea, 2011) with the time-invariant setting; the cost functions are given by:

	$\displaystyle\ell(z;d):=$	$\displaystyle(x-d)^{\top}Q(x-d)+u^{\top}Ru$
	$\displaystyle\ell_{f}(x;d):=$	$\displaystyle(x-d)^{\top}Q_{f}(x-d),\quad\ell_{b}(x;d)=0,$

where $Q:=\mathop{\text{diag}}(1,1,1,q,q,q,1,1,1)$ , $R:=I$ , $Q_{f}:=I$ , and $T:=I$ ; and the dynamic mapping is obtained from:


$\displaystyle\frac{d^{2}X}{dt^{2}}$	$\displaystyle=a(\cos\gamma\sin\beta\cos\alpha+\sin\gamma\sin\alpha)$	(14a)
$\displaystyle\frac{d^{2}Y}{dt^{2}}$	$\displaystyle=a(\cos\gamma\sin\beta\sin\alpha-\sin\gamma\cos\alpha)$	(14b)
$\displaystyle\frac{d^{2}Z}{dt^{2}}$	$\displaystyle=a\cos\gamma\cos\beta-g$	(14c)
$\displaystyle\frac{d\gamma}{dt}$	$\displaystyle=(b\omega_{X}\cos\gamma+\omega_{Y}\sin\gamma)/\cos\beta$	(14d)
$\displaystyle\frac{d\beta}{dt}$	$\displaystyle=-b\omega_{X}\sin\gamma+\omega_{Y}\cos\gamma$	(14e)
$\displaystyle\frac{d\alpha}{dt}$	$\displaystyle=b\omega_{X}\cos\gamma\tan\beta+\omega_{Y}\sin\gamma\tan\beta\ +\omega_{Z},$	(14f)

where the state and control variables are defined as: $x:=(X,\dot{X},Y,\dot{Y},Z,\dot{Z},\gamma,\beta,\alpha)$ and $u:=(a,\omega_{X},\omega_{Y},\omega_{Z})$ . We use $q$ and $b$ as parameters that influence controllability and observability. In particular, the system becomes less observable if $q$ becomes small and the system loses controllability as $b$ becomes small (the effect of manipulation on $\omega_{X}$ becomes weak). We have empirically tested the sensitivity behavior for $q=b=1$ (Case 1) and $q=b=0$ (Case 2). One can see that some of the assumptions (e.g., $S_{i}=0$ in Corollary 16) may be violated, but one can also see that, qualitatively, the system is more observable and controllable in Case 1 than in Case 2. The results are presented in Figure 1. The base trajectories are shown as dashed lines, the perturbed trajectories are shown as solid gray lines, and the perturbed stages are highlighted using vertical lines. We can see that, for Case 1 ( $q=1,b=1$ ), the differences between the base and perturbed solutions become small as moving away from the perturbation point (EDS holds). On the other hand, for Case 2 ( $q=0,b=0$ ) one cannot observe EDS; this confirms that observability and controllability induce EDS.

4 Conclusions

We have shown that uniform controllability and observability provide sufficient conditions for exponential decay of sensitivity in dynamic optimization. As part of future work, we will aim to establish exponential decay of sensitivity under mesh refinement settings and will aim to establish formal connections with continuous-time results.

References

Dontchev and Rockafellar (2009) Dontchev, A.L. and Rockafellar, R.T. (2009). Implicit functions and solution mappings, volume 543. Springer.
Grüne et al. (2019) Grüne, L., Schaller, M., and Schiela, A. (2019). Sensitivity analysis of optimal control for a class of parabolic PDEs motivated by model predictive control. SIAM Journal on Control and Optimization, 57(4), 2753–2774.
Grüne et al. (2020a) Grüne, L., Schaller, M., and Schiela, A. (2020a). Abstract nonlinear sensitivity and turnpike analysis and an application to semilinear parabolic PDEs. arXiv preprint arXiv:2008.13001.
Grüne et al. (2020b) Grüne, L., Schaller, M., and Schiela, A. (2020b). Exponential sensitivity and turnpike analysis for linear quadratic optimal control of general evolution equations. Journal of Differential Equations, 268(12), 7311–7341.
Hehn and D’Andrea (2011) Hehn, M. and D’Andrea, R. (2011). A flying inverted pendulum. In 2011 IEEE International Conference on Robotics and Automation, 763–770. IEEE.
Na and Anitescu (2020a) Na, S. and Anitescu, M. (2020a). Exponential decay in the sensitivity analysis of nonlinear dynamic programming. SIAM Journal on Optimization, 30(2), 1527–1554.
Na and Anitescu (2020b) Na, S. and Anitescu, M. (2020b). Superconvergence of online optimization for model predictive control. arXiv preprint arXiv:2001.03707.
Na et al. (2020) Na, S., Shin, S., Anitescu, M., and Zavala, V.M. (2020). Overlapping schwarz decomposition for nonlinear optimal control. arXiv preprint arXiv:2005.06674.
Robinson (1980) Robinson, S.M. (1980). Strongly regular generalized equations. Mathematics of Operations Research, 5(1), 43–62.
Shin et al. (2021) Shin, S., Anitescu, M., and Zavala, V.M. (2021). Exponential decay of sensitivity in graph-structured nonlinear programs. arXiv preprint arXiv:2101.03067v1.
Shin and Zavala (2020) Shin, S. and Zavala, V.M. (2020). Diffusing-horizon model predictive control. arXiv preprint arXiv:2002.08556.