Original Article Process Dynamics and Operations Group, TU Dortmund, Germany
<EMAIL_ADDRESS>The research leading to these
results has received funding from the European Commission under grant
agreement number 291458 (MOBOCON). RP acknowledges the contribution of the
Slovak Research and Development Agency under the project APVV 15-0007.

# Tube-enhanced Multi-stage MPC for Flexible Robust Control of Constrained
Linear Systems with Additive and Parametric Uncertainties

Sankaranarayanan Subramanian  Process Dynamics and Operations Group, TU
Dortmund, Germany.  Sergio Lucia  Laboratory of Process Automation Systems, TU
Dortmund, Germany.  Radoslav Paulen  Faculty of Chemical and Food Technology,
Slovak University of Technology in Bratislava, Slovakia.  Sebastian Engell
Process Dynamics and Operations Group, TU Dortmund, Germany.

###### Abstract

The trade-off between optimality and complexity has been one of the most
important challenges in the field of robust Model Predictive Control (MPC). To
address the challenge, we propose a flexible robust MPC scheme by synergizing
the multi-stage and tube-based MPC approaches. The key idea is to exploit the
non-conservatism of the multi-stage MPC and the simplicity of the tube-based
MPC. The proposed scheme provides two options for the user to determine the
trade-off depending on the application: the choice of the robust horizon and
the classification of the uncertainties. Beyond the robust horizon, the
branching of the scenario-tree employed in multi-stage MPC is avoided with the
help of tubes. The growth of the problem size with respect to the number of
uncertainties is reduced by handling _small_ uncertainties via an invariant
tube that can be computed offline. This results in linear growth of the
problem size beyond the robust horizon and no growth of the problem size
concerning small magnitude uncertainties. The proposed approach helps to
achieve a desired trade-off between optimality and complexity compared to
existing robust MPC approaches. We show that the proposed approach is robustly
asymptotically stable. Its advantages are demonstrated for a CSTR example.

##  1 Introduction

Robust Model Predictive Control (MPC) schemes address the presence of
uncertainties in the model with the goal to achieve constraint satisfaction
and closed-loop stability. It is desirable that the robust MPC schemes are
computationally cheap and non-conservative. The dual goal of non-conservatism
and low complexity is a key challenge that is being actively researched in the
field of robust MPC, and often a trade-off is needed. Open-loop min-max MPC
was one of the earliest robust MPC schemes proposed [1]. In this approach, the
worst-case cost is minimized while satisfying the constraints for all
realizations of the uncertainty. The scheme, however, does not account for the
presence of feedback in the predictions and predicts a single control input at
every stage. Because of the lack of recourse, the robustness comes at the cost
of a significant loss of performance.

Feedback min-max MPC models the presence of feedback information explicitly in
the predictions and thus reduces the conservatism of the open-loop schemes
[2]. A general feedback min-max MPC optimizes the worst-case value of the cost
function over a sequence of control policies, leading to infinite-dimensional
optimization problems. One possibility to formulate a feedback MPC method with
a finite-dimensional optimization problem is to consider a tree-structure to
represent the evolution of the uncertainty [3] because, for each predicted
state at every stage, the possibility is considered to adapt the inputs in the
predictions. The tree structure grows exponentially with respect to the length
of the prediction horizon, making the approach inapplicable in practice for
long prediction horizons.

Other related robust MPC approaches optimize the expected value of the cost
function [4] or a weighted sum of all the predicted scenarios, as done in
multi-stage MPC [5]. The weights of the multi-stage MPC are tuning parameters
that provide additional degrees of freedom to improve the closed-loop
performance compared to a feedback min-max MPC scheme.

An alternative to the representation of feedback via a scenario tree consists
of restricting the optimization to control policies with a fixed structure,
linear policies [6], or affine policies [7, 8, 9, 10]. Tube-based MPC is one
of the most discussed robust MPC approaches in the literature that usually
considers an affine parameterization of the feedback policies [10, 11]. It was
shown in [11] that the problem size can be kept the same as that of nominal
MPC if the feedback gain is chosen offline and kept constant in the
predictions. However, this comes at the cost of performance loss. Tube-based
MPC approaches that relax the structure of the control policy or that predict
the tube online (as opposed to an invariant tube) can improve the performance
as shown in [12, 13, 14, 15]. The performance advantages come at the cost of
an increase in computational complexity with respect to the length of the
prediction horizon. To handle parametric uncertainties, tube-based MPC based
on Farkas’ Lemma was proposed. The complexity of the approach grows linearly
with respect to the length of the prediction horizon [16, 17]. Advanced tube-
based schemes such as [13, 14, 16, 17] use contractive sets for the prediction
of tubes online. The number of inequalities and the number of vertices that
characterize the tube can increase rapidly with respect to the dimension of
the states and this makes the approach difficult to implement for high
dimensional systems. If low complexity tubes are employed as proposed in [18,
19], the schemes can be highly conservative.

The aim of this paper is to propose a novel scheme to achieve the dual goal of
low computational cost and low conservatism. To achieve this goal, we combined
the multi-stage and the tube-based MPC approaches by the classification of
uncertainties in [20]. The multi-stage MPC is employed to handle _significant_
uncertainties, and the tube-based MPC is used to handle _small_ magnitude
disturbances. We extend the scheme proposed in [20] in this contribution in
such a way that the rapid increase in problem complexity in multi-stage MPC is
addressed both with respect to the number of uncertainties and with respect to
the length of the prediction horizon. The proposed scheme gives the user two
options that determine the trade-off depending on the requirements of an
application. The two options are the choice of the robust horizon in multi-
stage MPC and the classification of the uncertainties. The key aspects of the
proposed approach are as follows:

  1. 1.

The branching of the scenario tree is stopped beyond a certain prediction step
called robust horizon. An affine feedback policy is employed beyond the robust
horizon with the help of tubes to achieve robust constraint satisfaction and
recursive feasibility guarantees.

  2. 2.

Different scenarios are predicted in the proposed framework for any choice of
robust horizon greater than or equal to $1$. The resulting increase in the
number of degrees of freedom enables the employment of low complexity tubes
for high dimensional systems without a significant loss of performance when
compared to standard tube-based schemes.

  3. 3.

In addition, the growth of the problem size with respect to the number of
uncertainties is reduced by formulating an invariant tube for small
disturbances by making use of the ideas proposed in [20].

We investigate in detail the theoretical properties of the proposed approach
and demonstrate that the proposed approach is robustly asymptotically stable.
We present the resulting tube-enhanced multi-stage MPC scheme as a convex
optimization problem that is solved at every time step. This is achieved by
employing the tube-based formulations from [13, 16] and the multi-stage
formulation from [20]. The advantages of the scheme are demonstrated for a
CSTR example.

##  2 Preliminaries

We study discrete-time linear dynamical systems of the form:

$\displaystyle\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}^{+}$
$\displaystyle=\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}+\mathchoice{\mbox{$\displaystyle w$}}{\mbox{$\textstyle
w$}}{\mbox{$\scriptstyle w$}}{\mbox{$\scriptscriptstyle w$}},$ (1)

where $\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathbb{R}^{n_{x}}$ represents the state,
$\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}\in\mathbb{R}^{n_{u}}$ represents the input,
$\mathchoice{\mbox{$\displaystyle w$}}{\mbox{$\textstyle
w$}}{\mbox{$\scriptstyle w$}}{\mbox{$\scriptscriptstyle
w$}}\in\mathchoice{\mbox{$\displaystyle\mathsf{W}$}}{\mbox{$\textstyle\mathsf{W}$}}{\mbox{$\scriptstyle\mathsf{W}$}}{\mbox{$\scriptscriptstyle\mathsf{W}$}}\subset\mathbb{R}^{n_{x}}$
denotes additive disturbances, the matrix $\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}\in\mathbb{R}^{n_{x}\times n_{x}}$ represents the uncertain system matrix
and $\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}\in\mathbb{R}^{n_{x}\times n_{u}}$ denotes the uncertain input matrix of
the controlled system. The system matrix $\textstyle A$ and the input matrix
$\textstyle B$ are contained in a convex polytope and can be represented as
$(\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}},\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}})\in\mathrm{conv}(\\{(\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i},\,\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle B$}}_{i}),\,\forall
i\in\Gamma_{p}\\})$, where $\mathrm{conv}()$ denotes the convex-hull operator
and $\Gamma_{p}:=\\{1,\,\dots,\,n_{p}\\}$. We assume that there exists a
feedback gain $\textstyle K$ that is stabilizing for all
$(\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}},\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}})\in\mathrm{conv}(\\{(\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i},\,\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle B$}}_{i}),\,\forall
i\in\Gamma_{p}\\})$. $\textstyle\mathsf{W}$ is assumed to be a convex polytope
with the origin in its interior and is characterized by $n_{w}$ vertices. The
bounds of the additive disturbances can be defined in terms of vertices of the
set as $\mathsf{W}:=\\{w|w\in\mathrm{conv}(\\{w_{l},\,\forall
l\in\Gamma_{w}\\})\\}$, where $\Gamma_{w}=\\{1,\,\dots,\,n_{w}\\}$. The
following definitions of invariant sets adapted from [21, 22] will be used
throughout the paper.

######  Definition 2.1.

A set $\textstyle\mathsf{S}$ is said to be robust positively invariant (RPI)
for the system $\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}=(\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}})\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}+\mathchoice{\mbox{$\displaystyle w$}}{\mbox{$\textstyle
w$}}{\mbox{$\scriptstyle w$}}{\mbox{$\scriptscriptstyle w$}}$, if
$\forall\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$,
$\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}\in\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}},\,\forall\mathchoice{\mbox{$\displaystyle
w$}}{\mbox{$\textstyle w$}}{\mbox{$\scriptstyle w$}}{\mbox{$\scriptscriptstyle
w$}}\in\mathchoice{\mbox{$\displaystyle\mathsf{W}$}}{\mbox{$\textstyle\mathsf{W}$}}{\mbox{$\scriptstyle\mathsf{W}$}}{\mbox{$\scriptscriptstyle\mathsf{W}$}},\forall\mathchoice{\mbox{$\displaystyle
i$}}{\mbox{$\textstyle i$}}{\mbox{$\scriptstyle i$}}{\mbox{$\scriptscriptstyle
i$}}\in\Gamma_{p}$.

######  Definition 2.2.

A set
$\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}_{\mathrm{min}}$
is said to be the minimal robust positively invariant set (mRPI) if
$\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}_{\mathrm{min}}$
is contained in every closed robust positively invariant set.

######  Definition 2.3.

A set
$\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}_{\mathrm{max}}$
is said to be the maximal robust positively invariant set (MRPI) if
$\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}_{\mathrm{max}}$
contains every closed robust positively invariant set.

###  2.1 Multi-stage MPC

The robustness of multi-stage MPC is achieved by modeling the future evolution
of the system by a scenario tree as shown in Fig. 1.

Figure 1: Scenario tree representation of the uncertainty evolution for multi-
stage MPC for the system with additive and parametric uncertainties. The
vertex matrices are given by $\\{(A_{1},B_{1}),(A_{2},B_{2})\\}$ and the
vertices of the additive disturbances are given by $w_{1}$ and $w_{2}$.

Each branch of the tree denotes a realization of the uncertainties. Each node
denotes a predicted state at the corresponding point in time. If all the
extreme values of the uncertainties are realized in the predictions, the
predicted states form the convex hull of all the possible trajectories in the
future until the end of the prediction horizon. Realizations of the
uncertainties that are not extreme can also be included to improve the
resulting closed-loop performance. The tree branches until the end of the
prediction horizon for each predicted node. The availability of feedback
information in the predictions is explicitly modeled in the tree structure
without restricting the structure of the feedback policy. This makes the
approach less conservative than those which assume linear or affine feedback
policies, but exponentially complex [23]. The optimization problem that is
solved at every time step is given as follows:

$\displaystyle\min_{\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}_{k}^{j},\forall(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}}\;\;\;\sum_{k=0}^{N_{p}-1}\sum_{j=1}^{{n_{d}}^{k}}\omega_{k}^{j}\ell(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}_{k}^{j},\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}_{k}^{j})+\sum_{j=1}^{{n_{d}}^{N_{p}}}V_{f}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}_{N_{p}}^{j})$ (2a) subject to:
$\displaystyle\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}_{k+1}^{c}=\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}_{k}^{j}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle u$}}_{k}^{j}+w_{l},$
$\displaystyle\forall\,(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak N_{p}-1\rrbracket},\,\forall
i\in\Gamma_{p},\,\forall l\in\Gamma_{w},$ (2b)
$\displaystyle\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}_{k}^{j}\in\mathbb{X},\,\mathchoice{\mbox{$\displaystyle
u$}}{\mbox{$\textstyle u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}_{k}^{j}\in\mathbb{U},$
$\displaystyle\forall\,(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (2c)
$\displaystyle\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}_{N_{p}}^{j}\in\mathbb{X}_{f},\;$
$\displaystyle\forall\,(j,N_{p})\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{N_{p}},$ (2d)

where the set of all indices $(j,k)$ in the scenario tree is denoted as $I$
and the set of indices occurring from a stage $k_{1}$ until a certain stage
$k_{2}$ is denoted by $I_{\llbracket k_{1}\mathrel{,\,}\nobreak
k_{2}\rrbracket}$, where $0\leq k_{1}\leq N_{p}$ and $k_{1}\leq k_{2}\leq
N_{p}$. Also, the set of indices occurring at a stage at $k$ is denoted by
$I_{k}\triangleq I_{\llbracket k\mathrel{,\,}\nobreak k\rrbracket}$, where
$0\leq k\leq N_{p}$. $I_{\llbracket k_{1}\mathrel{,\,}\nobreak
k_{2}\rrbracket}\triangleq\emptyset$, if $k_{2}<k_{1}$. Each state
$\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}_{k+1}^{c}$
predicted at the time step $k+1$ is the child node in the scenario tree
obtained from the node $\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}_{k}^{j}$, the input $\mathchoice{\mbox{$\displaystyle
u$}}{\mbox{$\textstyle u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}_{k}^{j}$, the realization $i\in\Gamma_{p}$ of the parametric
uncertainties $(A_{i},B_{i})$, and the realization $l\in\Gamma_{w}$ of the
additive disturbances $w_{l}$. The weighted sum of the stage costs $\ell(x,u)$
along the prediction horizon and the terminal penalty function
$V_{f}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})$ constitute the
overall objective function. The number of branches at every predicted node is
given by $n_{d}=n_{p}\times n_{w}$.

The state and the input bounds, and the bounds on the terminal state are
enforced via (2c) using polytopic sets $\mathbb{X}$ and $\mathbb{U}$, and
$\mathbb{X}_{f}$, respectively.

The control input for a particular node must be the same for all the branches
to enforce the causality of the control policy. I.e., $u_{k}^{j}=u_{k}^{l}$ if
$z_{k}^{j}=z_{k}^{l}$ for all $(j,k),(l,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$. However, the
future inputs at different nodes can be different as measurement information
will be available at the next stages. I.e., $u_{k}^{j}$ can be different from
$u_{k}^{l}$ if $z_{k}^{j}\neq z_{k}^{l}$ for all
$(j,k),(l,k)\in\mathchoice{\mbox{$\displaystyle I$}}{\mbox{$\textstyle
I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle I$}}_{\llbracket
0\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$. The optimal input at the fist
prediction step $u_{0}^{1*}(x)$ obtained by solving the optimization problem
(2) is applied to the plant. The terminal region $\mathbb{X}_{f}$ is chosen as
the maximal RPI set for a stabilizing control law $K_{f}x$. The problem size
grows rapidly with respect to the number of uncertainties and the length of
the prediction horizon. Therefore we investigate solutions of reduced
complexity that approximately realize the performance of the multi-stage
scheme. This will be discussed in detail in the rest of the paper.

In the linear case considered here, since all the extreme realizations of the
uncertainties are used in the predictions, the scenario tree predicts the
reachable set of state trajectories. Every node of the scenario tree denotes
the vertices of the polytope that forms the reachable set of the system for
the predicted control policy.

##  3 Tube-enhanced multi-stage MPC

The problem defined in (2) suffers from rapid growth with respect to the
number of realizations of the uncertainties and the length of the prediction
horizon. We propose to employ two kinds of tubes to deal with the growth in
problem complexity as described below:

  1. 1.

An invariant tube using an affine feedback policy is employed to handle small-
magnitude disturbances.

     * •

The invariant tube is obtained offline and hence, the complexity of the
optimization problem does not grow with respect to the number of small
disturbances.

     * •

The invariant tube is employed only for small disturbances and hence the
method does not introduce a large conservatism.

  2. 2.

Different tubes for each scenario are introduced to handle the significant
uncertainties after a predefined horizon (robust horizon) in the prediction,
instead of further branching of the scenario tree (see Figure 2).

     * •

The problem complexity grows only linearly with respect to the prediction
horizon beyond the robust horizon.

     * •

The formulation optimizes for different feed-forward terms of the predicted
tubes at every stage that belong to different scenarios beyond the robust
horizon (in addition to modeling full recourse until the robust horizon) and
hence the approach is less conservative when compared to a pure tube-based
scheme. Low complexity tubes can also be employed for less conservatism making
the approach applicable to high dimensional systems.

The following subsections will elaborate the key points discussed above to
obtain an improved trade-off between optimality and complexity.

###  3.1 Handling small disturbances using an invariant tube

Because of the multiplicative nature of the parametric uncertainties, they
will have a large influence on the state trajectory far away from the origin.
Therefore, we classify all parametric uncertainties as large magnitude
uncertainties. The additive disturbances can be large or small depending on
the application. To reduce the computational complexity, the set of additive
disturbances $\mathsf{W}$ is decomposed into two polytopes
$\overline{\mathsf{W}}$ and $\underline{\mathsf{W}}$ that contain the origin
in their interiors such that
$\mathsf{W}\subseteq\overline{\mathsf{W}}\oplus\underline{\mathsf{W}}$, where
$\overline{\mathsf{W}},\,\underline{\mathsf{W}}\subset\mathbb{R}^{n_{x}}$ .

The set $\overline{\mathsf{W}}$ denotes large magnitude disturbances and the
set $\underline{\mathsf{W}}$ denotes small magnitude uncertainties. It is
recommended that the uncertain set $\mathsf{W}$ is decomposed such that the
number of vertices of the large uncertainties $\overline{\mathsf{W}}$ is small
while $\underline{\mathsf{W}}$ is of smaller volume. The model that accounts
for large uncertainties is defined as follows:

$\displaystyle\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle z$}}^{+}$
$\displaystyle=\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}+\mathchoice{\mbox{$\displaystyle w$}}{\mbox{$\textstyle
w$}}{\mbox{$\scriptstyle w$}}{\mbox{$\scriptscriptstyle w$}},$ (3)

for all $i\in\Gamma_{p}$ and for all $\mathchoice{\mbox{$\displaystyle
w$}}{\mbox{$\textstyle w$}}{\mbox{$\scriptstyle w$}}{\mbox{$\scriptscriptstyle
w$}}\in\overline{\mathsf{W}}$, where $\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}\in\mathbb{R}^{n_{x}}$ is the state and $\mathchoice{\mbox{$\displaystyle
v$}}{\mbox{$\textstyle v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}\in\mathbb{R}^{n_{u}}$ is the input of the model (3). The number of
vertices of the additive uncertainty set $\overline{\mathsf{W}}$ is denoted by
$n_{\overline{w}}$ and the set $\overline{\mathsf{W}}$ is defined as
$\overline{\mathsf{W}}:=\\{w|w\in\mathrm{conv}(\\{w_{l},\,\forall
l\in\Gamma_{\overline{w}})\\}$, where
$\Gamma_{\overline{w}}=\\{1,\,\dots,\,n_{\overline{w}}\\}$. The large
uncertainties are considered in the predictions using the multi-stage
approach. To handle small disturbance set $\underline{\mathsf{W}}$, an affine
feedback policy is employed as follows:

$\displaystyle\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}=\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}+\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}-\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle z$}}),$ (4)

where $\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle K$}}_{\mathrm{inv}}$
denotes the feedback gain associated with the invariant tube and is chosen
such that the parameter-varying closed-loop system
$\\{(\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}),\,\forall i\in\Gamma_{p}\\}$ is asymptotically stable.
For the system given in (1), the state $\textstyle x$ and the control law (4),
a set $\textstyle\mathsf{S}$ is defined as small disturbance invariant if
$(\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}})\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}\oplus\mathchoice{\mbox{$\displaystyle\underline{\mathsf{W}}$}}{\mbox{$\textstyle\underline{\mathsf{W}}$}}{\mbox{$\scriptstyle\underline{\mathsf{W}}$}}{\mbox{$\scriptscriptstyle\underline{\mathsf{W}}$}}\subseteq\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$
for all $i\in\Gamma_{p}$. This disturbance invariant set
$\textstyle\mathsf{S}$ can be chosen as the convex RPI over-approximation of
the minimal RPI set of the model (3). A convex outer-approximation
($\textstyle\mathsf{S}$) of the minimal RPI set $\textstyle\mathsf{S}$ can be
obtained from the algorithm given in [24]. This problem is solved offline and
hence does not affect the online computation time of the proposed algorithm.
In the implementation section, we propose a novel convex optimization problem
to over-approximate the minimal RPI set that is disturbance invariant using a
linear programming problem. Since the small magnitude uncertainties are
handled using an affine feedback policy, they will not be considered in the
online optimization problem and hence do not affect the problem complexity.

Figure 2: Scenario tree representation of the evolution of the uncertainties
for tube-enhanced multi-stage MPC with robust horizon $N_{r}=2$.

###  3.2 Handling long prediction horizons using predicted tubes

For the large uncertainties considered in the scenario tree, the problem
complexity increases exponentially with respect to the prediction horizon
$N_{p}$. To reduce the problem complexity, the branching of the tree can be
stopped beyond a certain prediction step called the robust horizon $N_{r}$.
Beyond the robust horizon, the affine policies ($v+K_{\mathrm{pred}}z$) are
employed to handle all large uncertainties considered in the scenario tree.
Here $K_{\mathrm{pred}}$ denotes the feedback gain associated with the tubes
predicted online. The dynamics of the system beyond $N_{r}$ can be described
using the following set recursion:

$\displaystyle\mathsf{Z}^{+}\supseteq(\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}K_{\mathrm{pred}})\mathsf{Z}\oplus\\{B_{i}v\\}\oplus\overline{\mathsf{W}},$
(5)

for all $i\in\Gamma_{p}$ and $\mathsf{Z}$ denotes the tube of states at the
current time step and $\mathsf{Z}^{+}$ denotes the tube at the successor time
step. The idea is illustrated in Fig. 2 for a robust horizon $N_{r}=2$. It can
be seen that the tubes replace branches beyond $N_{r}$ leading to a linear
growth of the complexity of the scenario tree with respect to the prediction
horizon. The feed-forward terms associated with the affine control law can be
different for different scenarios. This can improve the performance of the
controller when compared to the tube-based scheme [16], where the problem
formulation considers one feed-forward term per prediction step. The invariant
tube is shown on top of the scenario tree for representational purposes. The
invariant tube $\mathsf{S}$ is used to obtain a suitable back-off that
guarantees satisfaction of the original constraints for all possible values of
the small magnitude uncertainties $\underline{\mathsf{W}}$ and does not
contribute additional costs to the online optimization problem.

######  Remark 3.1.

The idea of robust horizon has been already proposed for nonlinear systems in
[5] by assuming that the uncertainty remains constant beyond the robust
horizon. However, no rigorous study on the recursive feasibility and the
stability of the closed-loop system was performed. In [25], it was proposed
that a terminal set must be employed at the end of robust horizon to achieve
stability but this is clearly restrictive. In this work, we propose a rigorous
solution using a robust horizon in the multi-stage MPC framework enhanced by a
tube-based formulation. We make use of affine control policies beyond the
robust horizon and formulate the problem such that the closed-loop system is
stable. The proposed formulation is not as restrictive as in [25], the
terminal constraints are enforced at the end of the prediction horizon as in
conventional MPC schemes and the proposed scheme does not assume that the
uncertainties remain constant beyond $N_{r}$.

###  3.3 Problem Formulation

The optimization problem $\mathtt{P}_{N_{p}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ that is solved at every time step is given by

$\displaystyle\min_{\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j}\forall(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}}\bigg{(}\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}+\sum_{k=N_{r}}^{N_{p}-1}J^{\mathrm{tube}}_{k}+J_{N_{p}}^{\mathrm{term}}\bigg{)}$
(6a) subject to: $\displaystyle\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{k+1}^{c}=\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{k}^{j}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j}+\mathchoice{\mbox{$\displaystyle w$}}{\mbox{$\textstyle
w$}}{\mbox{$\scriptstyle w$}}{\mbox{$\scriptscriptstyle w$}}_{l},$
$\displaystyle\forall\,(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak N_{r}-1\rrbracket},\forall
i\in\Gamma_{P},\forall l\in\Gamma_{\overline{w}},$ (6b)
$\displaystyle\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{k}^{j}\in\mathbb{Z},\,\mathchoice{\mbox{$\displaystyle
v$}}{\mbox{$\textstyle v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j}\in\mathbb{V},$
$\displaystyle\forall(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak N_{r}-1\rrbracket},$ (6c)
$\displaystyle\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{N_{r}}^{j}\in\mathsf{Z}_{N_{r}}^{j}\subseteq\mathbb{Z},\;$
$\displaystyle\forall(j,N_{r})\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{N_{r}},$ (6d) $\displaystyle(\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}K_{\mathrm{pred}})\mathsf{Z}_{k}^{j}\oplus\\{B_{i}v_{k}^{j}\\}\oplus\overline{\mathsf{W}}\subseteq\mathsf{Z}_{k+1}^{j},$
$\displaystyle\forall(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},\forall
i\in\Gamma_{p},$ (6e)
$\displaystyle\mathsf{Z}_{k}^{j}\subseteq\mathbb{Z},\tilde{z}_{k}^{j}\in\mathsf{Z}_{k}^{j},\,\\{v_{k}^{j}\\}\oplus\mathchoice{\mbox{$\displaystyle
K$}}{\mbox{$\textstyle K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{pred}}\mathsf{Z}_{k}^{j}\subseteq\mathbb{V},$
$\displaystyle\forall(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (6f)
$\displaystyle\mathsf{Z}_{N_{p}}^{j}\subseteq\mathbb{Z}_{f},\,$
$\displaystyle\forall(j,N_{p})\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{N_{p}},$ (6g) $\displaystyle\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\\{z_{1}^{0}\\}\oplus\mathsf{S},\,$ (6h) where $\displaystyle
J^{\mathrm{MS}}_{k}$
$\displaystyle=\sum_{j=1}^{{n_{d}}^{k}}\omega_{k}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{k}^{j},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{k}^{j}),$ (6i)
$\displaystyle J^{\mathrm{tube}}_{k}$
$\displaystyle=\max_{\tilde{z}_{k}^{j},\,\forall(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}}\sum_{j=1}^{{n_{d}}^{N_{r}}}\omega_{k}^{j}\ell(\tilde{z}_{k}^{j},\mathchoice{\mbox{$\displaystyle
v$}}{\mbox{$\textstyle v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j}+K_{\mathrm{pred}}\tilde{z}_{k}^{j}),$ (6j) $\displaystyle
J_{N_{p}}^{\mathrm{term}}$
$\displaystyle=\max_{\tilde{z}_{N_{p}}^{j},\,\forall(j,N_{p})\in
I_{N_{p}}}\sum_{j=1}^{{n_{d}}^{N_{r}}}V_{f}(\tilde{z}_{N_{p}}^{j}).$ (6k)

There are several differences in both the objective and the constraints in (6)
compared to that of the standard multi-stage MPC (2). In the optimization
problem (6), the objective can be divided into three parts: a multi-stage part
$J_{k}^{\mathrm{MS}}$, a tube-based part $J_{k}^{\mathrm{tube}}$ and the
terminal penalty part $J_{k}^{\mathrm{term}}$. The multi-stage part of the
objective function $J_{k}^{\mathrm{MS}}$ is applied until $N_{r}-1$, and
beyond $N_{r}-1$, the tube-based part of the objective function
$J_{k}^{\mathrm{tube}}$ is applied. As always, the terminal penalty
$J_{k}^{\mathrm{term}}$ is applied at the last prediction step $N_{p}$. The
multi-stage part of the objective function $J_{k}^{\mathrm{MS}}$ is the same
as in (2). The tube-based part of the objective function
$J_{k}^{\mathrm{tube}}$ and the terminal part of the objective function
$J_{k}^{\mathrm{term}}$ have maximization terms associated with them. For the
tube-based part of the optimization problem, the worst-case cost associated
with the predicted tubes $\mathsf{Z}_{k}^{j}$ are obtained at every prediction
step. This helps in establishing the optimal value function as a Lyapunov
function for the proposed scheme.

The state inside the tube that maximizes the objective function is defined as
$\tilde{z}_{k}^{j}$ and is constrained by
$\tilde{z}_{k}^{j}\in\mathsf{Z}_{k}^{j}$ as given in (6f). The variables
$\tilde{z}_{k}^{j}$ are formulated as decision variables for all $(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$. Equations
(6e)–(6g) represent the constraints beyond the robust horizon $N_{r}$.
Equation (6e) guarantees the recursive bounding of the state trajectories for
the chosen control law $v+K_{\mathrm{pred}}z$. It can also be seen that the
affine term $v_{k}^{j}$ can be freely chosen for all $(j,k)\in I_{\llbracket
0\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$. This can improve the resulting
solution even for a robust horizon of $N_{r}=1$ when compared to a pure tube-
based scheme. Equations. (6f)–(6g) denote the state, input and the terminal
constraints. The set of all $x\in\mathbb{X}$ for which there exists a feasible
feedback policy is denoted as $\mathtt{X}_{N_{p}}$. Equation (6d) is
formulated at the robust horizon to establish continuity between the predicted
scenarios until the robust horizon and the tubes predicted beyond the robust
horizon.

The initial state of the scenario tree $\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}^{1}_{0}$ is a function of the current state $\textstyle x$ as defined in
(6h) and is a decision variable of the optimization problem (6). The
optimization problem is solved with tightened constraints
$\mathbb{Z}=\mathbb{X}\ominus\mathsf{S}$ and $\mathbb{V}=\mathbb{U}\ominus
K_{\mathrm{inv}}\mathsf{S}$ in (6c) and (6f). The number of branches at every
node is given by $n_{d}=n_{p}\times n_{\overline{w}}$ until the robust horizon
$N_{r}$.

Note that the number of branches can be reduced dramatically if
$n_{\overline{w}}\ll n_{w}$ when compared to the consideration of all
uncertainties in a scenario tree. The control input $\textstyle u$ applied to
the system is given by $\mathchoice{\mbox{$\displaystyle
u$}}{\mbox{$\textstyle u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}=\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}^{1*}_{0}+\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}-\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}^{1*}_{0}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}))$, where
$\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}^{1*}_{0}$ is the
first element of the optimal control input sequence obtained by solving (6).
Since the polytope $\overline{\mathsf{W}}$ has smaller number of vertices
compared to $\mathsf{W}$, the problem size solved using (6) is reduced.
Despite the reduced complexity when compared to a standard multi-stage
problem, the proposed controller can often achieve a performance comparable to
that of multi-stage MPC for a fraction of the computational complexity by the
choice of $N_{r}$ and $\overline{\mathsf{W}}$.

######  Remark 3.2.

The proposed scheme is flexible and includes options to further improve it
which we do not analyze in this work. Two of the possible modifications are
listed below:

  1. 1.

The feedback gain is denoted as a constant $K_{\mathrm{pred}}$ for the
predicted tubes. This is done only to simplify the presentation. The feedback
gains can be different for different scenarios. The only necessary condition
is that the gain must be stabilizing and can be chosen freely for different
scenarios to improve the performance of the closed-loop.

  2. 2.

The number of tubes at the robust horizon is formulated equal to the number of
nodes predicted until that stage using the scenario tree in (6). The
constraint (6d) represents the continuity equation. However, different nodes
can be bundled together in one tube and the number of tubes can be smaller
than the number of nodes predicted until $N_{r}$ by modifying the continuity
constraint (6d). This can help to reduce problem complexity further.

###  3.4 Stabilizing objective function and choice of weights

Since a persisting disturbance $w\in\mathsf{W}$ is assumed, convergence to the
origin cannot be established. Instead, as described in [26], a robust
positively invariant set $\mathsf{T}$ will be shown to be asymptotically
stable using the proposed robust model predictive control scheme. To achieve
stability, we assume that the terminal set, the proposed stage cost and the
terminal penalty function satisfy the following properties:

  1. 1.

The terminal set $\mathbb{Z}_{f}:=\mathsf{T}$ is a robust positively invariant
set for a stabilizing control law $K_{f}z$.

  2. 2.

The stage cost $\ell(z,K_{f}z)=0$ and the terminal penalty $V_{f}(z)=0$,
$\forall z\in\mathsf{T}$.

A stage cost with these properties as proposed in [26] is given as follows:

$\displaystyle\ell(z,v)=\min_{y\in\mathbb{Z}_{f}}||Q(z-y)||_{p}+||R(v-K_{f}z)||_{p},$
(7)

where $Q$ and $R$ are positive semi-definite matrices. The terminal penalty
function can be simply set to zero i.e. $V_{f}(z)=0,\,\forall
z\in\mathbb{R}^{n_{x}}$. The choice of the stage cost is different from the
nominal cost $\ell_{\mathrm{nom}}(z,v)=||Qz||_{p}+||Rv||_{p}$ which is
generally used in the case of nominal MPC. The nominal stage cost
$\ell_{\mathrm{nom}}$ penalizes the distance to the origin and the control
effort depending on the choice of tuning matrices $Q$ and $R$. The stage cost
$\ell(z,v)$ penalizes the distance to the set $\mathbb{Z}_{f}$ and the
deviations from the control law $K_{f}z$. The terminal gain $K_{f}$ is chosen
equal to the gain of the predicted tubes $K_{\mathrm{pred}}$. The gain $K_{f}$
can be chosen freely when there is no tube-based part of the scheme. This is
further discussed in Section 4.4 and in Section 5.

Each realization of the uncertain matrices $(\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i},\,\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle B$}}_{i})$ and of
$w_{l}$ has a fixed positive weight $\omega_{i,l}>0$ associated with it for
all $i\in\Gamma_{p},\,l\in\Gamma_{\overline{w}}$. Appropriate weights can be
chosen depending on the applications. However, to establish stability the
weights must follow certain rules which are formalized in the following
assumption. The weights associated with the vertex matrices will be assigned
to the nodes that result from them in the predictions. For example, if
$z_{1}^{1}$ is realized because of $(\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{1},\,\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle B$}}_{1})$, the weight
associated with the node $z_{1}^{1}$ will be equal to $\omega_{1}$ (the
corresponding weight of $(\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{1},\,\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle B$}}_{1})$). The
requirement of weights associated with each node in the scenario tree is given
in the following assumption.

###### Assumption 1

The weight of the root node $\omega_{0}^{1}$ is smaller than or equal to the
minimum of all the weights (i.e.
$\omega_{0}^{1}\leq\min\\{\omega_{0},\omega_{1},\,\dots,\,\omega_{n_{d}}\\}$)
and it must be positive $\omega_{0}^{1}>0$. The weights $\omega_{k}^{j}$
associated with the other nodes $z_{k}^{j}$ are equal to the weights
associated with the realization of the uncertainty from which they are
obtained for all $(j,k)\in I_{\llbracket 1\mathrel{,\,}\nobreak
N_{r}-1\rrbracket}$. The weights associated with tubes are chosen as
$\omega_{k}^{j}=n_{d}^{k-N_{r}}\omega_{\mathrm{tube}},\,\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$ where
$\omega_{\mathrm{tube}}\geq\max\\{\omega_{0},\omega_{1},\,\dots,\,\omega_{n_{d}}\\}$
and is bounded.

######  Remark 3.3.

The choice of the weights is important in establishing the stability
properties of the proposed approach. The weights affect the objective function
and thus the value function. If the weights are chosen as per Assumption 1
stability can be proven, see Lemma 5.6. In the multi-stage part of the scheme,
the weights are chosen the same in each stage for the same realization of the
uncertainty. Then feasible values of the stage costs for the succeeding step
can be obtained by the convex combination of the stage costs that are realized
at the current time step. Since the branching stops beyond the robust horizon,
the weights must be updated to account for the receding horizon implementation
of the MPC scheme. Hence the weights of the tube-based part of the scheme are
employed as
$\omega_{k}^{j}=n_{d}^{k-N_{r}}\omega_{\mathrm{tube}},\,\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}.$

##  4 Implementation details

We employ the tube-based MPC approach based on Farkas’ Lemma as proposed in
[16] to account for the disturbances after the robust horizon. The proposed
approach works for any choice of robust horizon and in principle can be chosen
equal to $N_{r}=0$ in which case, the scheme reduces to the approach in [16]
if $\underline{\mathsf{W}}=\\{0\\}$.

The tightened state constraint set $\mathbb{Z}$ is defined as
$\mathbb{Z}:=\\{z|Fz\leq\textbf{1}\\}$, where $F$ is a $n_{c}\times n_{x}$
dimensional matrix, $n_{c}$ denotes the number of state constraints, and 1
denotes a vector with all elements $1$ of an appropriate dimension. The
tightened input constraint set $\mathbb{V}$ is defined as
$\mathbb{V}:=\\{v|Gv\leq\textbf{1}\\}$, where $G$ is a $n_{m}\times n_{u}$
matrix and $n_{m}$ denotes the number of input constraints. In the following,
we discuss three types of tubes: general complexity tube, homothetic tube and
low complexity tube. We show that how the proposed formulation (6) can be
implemented as convex optimization problem. In addition, we also discuss the
subtleties in the reformulation with respect to the proposed approach.

###  4.1 General complexity tube

The complexity of the tubes that are employed beyond the robust horizon can be
fixed and defined as

$\mathsf{Z}:=\\{z|Tz\leq\tau\\},$

where $T\in\mathbb{R}^{n_{r}\times n_{x}}$ is fixed for all prediction steps
and $\tau\in\mathbb{R}^{n_{r}}$ is a decision variable that is chosen online.
Here $n_{r}$ denotes the number of inequalities that describes the tube
$\mathsf{Z}$ and it is typically larger than $2n_{x}$. The matrix $T$ is
chosen such that the set $\Lambda:=\\{z\mid Tz\leq\textbf{1}\\}$ is
$\lambda-$contractive for $\lambda\in[\lambda_{\mathrm{min}},1)$, where
$\lambda_{\mathrm{min}}$ is the joint spectral radius of the closed-loop
uncertain system matrices for the chosen feedback gain $K_{\mathrm{pred}}$.
The details on algorithm for obtaining the largest $\lambda-$contractive set
can be found in [22] (pp. 171-184). One can also use off-the-shelf toolboxes
such as Multi-Parametric Toolbox [27] to obtain $\lambda-$contractive sets.

Now, let us have a look at the problem formulation (6), where the eqs.
(6e)–(6f) are in the form of set operations. Farkas’ Lemma can be employed to
convert them from set operations to a set of linear equalities and
inequalities. This reformulation will help us formulate the optimization
problem as a convex optimization problem that does not require any set
operations online. Equation (6e) bounds the error dynamics recursively as
$(A_{i}+B_{i}K_{\mathrm{pred}})\mathsf{Z}_{k}^{j}\oplus\mathsf{W}\subseteq\mathsf{Z}_{k+1}^{j}$
for all $i\in\Gamma_{p}$. Let $\mathsf{Z}_{k}^{j}$ be represented as

$\displaystyle\mathsf{Z}_{k}^{j}$ $\displaystyle=\\{z|Tz\leq\tau_{k}^{j}\\},$
(8)

where the variables $\tau_{k}^{j},\,\forall(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}\rrbracket}$ can be formulated as decision
variables in the optimization problem. Since an affine control law
$v+K_{\mathrm{pred}}z$ is employed beyond the robust horizon $N_{r}$,
$z^{+}\in\\{(A_{i}+B_{i}K_{\mathrm{pred}})z+B_{i}v\\}\oplus\overline{\mathsf{W}}$
for a given $i\in\Gamma_{p}$ and the tube at the next prediction step that
bounds all the trajectories for the predicted input and the arbitrary
realizations of the uncertainties for all $(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$ is given by

$\displaystyle\mathsf{Z}_{k+1}^{j}:=\\{z|T((A_{i}+B_{i}K_{\mathrm{pred}})z+B_{i}v_{k}^{j}+w_{l})\leq\tau_{k+1}^{j},\,\forall
i\in\Gamma_{p}\,\forall l\in\Gamma_{\overline{w}},\,\forall
z\in\mathsf{Z}_{k}^{j}\\}.$ (9)

To achieve the set recursion, Farkas’ Lemma is employed and it is given below
[22, 16] :

######  Lemma 4.1.

Given two non-empty sets $\mathsf{X}_{1}:=\\{x|T_{1}x\leq\tau_{1}\\}$,
$\mathsf{X}_{2}:=\\{x|T_{2}x\leq\tau_{2}\\}$,
$\mathsf{X}_{1}\subseteq\mathsf{X}_{2}$ holds iff there exists a non-negative
matrix $P$ that satisfies the equality $PT_{1}=T_{2}$ and the inequality
$P\tau_{1}\leq\tau_{2}$.

Using Lemma 4.1, we can employ non-negative matrices $P_{i},\,\forall
i\in\Gamma_{p},$ and
$\mathchoice{\mbox{$\displaystyle($}}{\mbox{$\textstyle($}}{\mbox{$\scriptstyle($}}{\mbox{$\scriptscriptstyle($}}A_{i}+B_{i}K_{\mathrm{pred}})\mathsf{Z}_{k}^{j}\oplus\overline{\mathsf{W}}\subseteq\mathsf{Z}_{k+1}^{j}$
holds for all $i\in\Gamma_{p}$ iff:

$\displaystyle P_{i}T=T(A_{i}+B_{i}K_{\mathrm{pred}}),$ $\displaystyle\forall
i\in\Gamma_{p},$ (10a) $\displaystyle
P_{i}\tau_{k}^{j}+TB_{i}v_{k}^{j}+Tw_{l}\leq\tau_{k+1}^{j},$
$\displaystyle\forall i\in\Gamma_{p},\,\forall
l\in\Gamma_{\overline{w}},\,(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}.$ (10b)

The set (9) is reformulated using linear equalities and inequalities as shown
in (10). Similarly, the set operations (6f)–(6g) can be reformulated using
Lemma 4.1. The state and input constraints can be formulated using non-
negative matrices $P_{x},\,P_{u},\,P_{T}$ as follows:

$\displaystyle P_{x}T=F,$ (11a) $\displaystyle
P_{x}\tau_{k}^{j}\leq\textbf{1},$ $\displaystyle\forall(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (11b) $\displaystyle
P_{u}T=GK_{\mathrm{pred}},$ (11c) $\displaystyle
Gv_{k}^{j}+P_{u}\tau_{k}^{j}\leq\textbf{1},$ $\displaystyle\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (11d)

The choice of non-negative matrices $P_{i},\,\forall
i\in\Gamma_{p},\,P_{x},\,P_{u}$ if obtained online, results in a non-convex
optimization problem. Hence as proposed in [16], the non-negative matrices can
be obtained offline such that the equality constraints are satisfied. This
reduces the computational load of the online problem and convexifies it. The
matrices $P_{i},\,\forall i\in\Gamma_{p}$ can be obtained by solving the
following problem for a given $i$:

$\displaystyle
P_{i}=\arg\min_{\tilde{P}_{i}}||\tilde{P}_{i}||_{\infty},\mathrm{s.t.}\tilde{P}_{i}T=T(A_{i}+B_{i}K_{\mathrm{pred}}).$
(12)

Similar to (12), the matrices $P_{x},\,P_{u},\,P_{T}$ can be obtained by
formulating linear programming problems that satisfy the equality constraints
(11a), and (11c). The terminal constraints are implemented as follows:

$\displaystyle{P}_{i}\tau_{N_{p}}^{j}+Tw_{l}\leq\tau_{N_{p}}^{j},\;\forall
i\in\Gamma_{p},\,\forall l\in\Gamma_{\overline{w}},\forall(j,N_{p})\in
I_{N_{p}},$ (13)

where the terminal set is defined as

$\displaystyle\mathbb{Z}_{f}\triangleq\\{z\mid
Tz\leq\tau,{P}_{i}T=T(A_{i}+B_{i}K_{\mathrm{pred}}),{P}_{i}\tau+Tw_{l}\leq\tau,\forall
i\in\Gamma_{p},\,\forall l\in\Gamma_{\overline{w}}\\},$ (14)

and $\mathbb{Z}_{f}\subseteq\mathbb{Z}$ and
$K_{f}\mathbb{Z}_{f}\subseteq\mathbb{V},K_{f}=K_{\mathrm{pred}}$ hold. The
terminal gain $K_{f}$ is chosen as the gain of the predicted gain to simplify
the implementation and the discussion that follows. Further discussions on the
computation of the terminal set can be found in Section 4.4. The minimal RPI
set can be obtained using the methods discussed in [24]. Another possible
over-approximation of the mRPI set can be obtained as
$\mathsf{S}:=\\{z|\hat{T}z\leq\tau\\}$. Here the matrix $\hat{T}$ is chosen
such that $\\{z\mid\hat{T}z\leq\textbf{1}\\}$ is $\lambda-$contractive for the
chosen feedback gain $K_{\mathrm{inv}}$. The right hand side of the inequality
that defines $\mathsf{S}$, $\tau$ can be obtained as follows:

$\displaystyle\min_{\mathchoice{\mbox{$\displaystyle\tau$}}{\mbox{$\textstyle\tau$}}{\mbox{$\scriptstyle\tau$}}{\mbox{$\scriptscriptstyle\tau$}}}||\tau||_{p}$
(15a) subject to: $\displaystyle\hat{P}_{i}\tau+\hat{T}w_{l}\leq\tau,\forall
i\in\Gamma_{p},\,\forall l\in\Gamma_{\overline{w}}.$ (15b)

The objective can be chosen as $1-$norm or $\infty-$norm so that the
optimization problem is an LP. The LP (15) guarantees that the set
$S:=\\{z|\hat{T}z\leq\tau\\}$ is robust positively invariant. The non-negative
matrices $\hat{P}_{i},$ for all $i\in\Gamma_{p}$ can be chosen as discussed in
(11). Since $\hat{T}$ and $\hat{P}_{i},\,\forall i\in\Gamma_{p}$ are fixed,
the set $\mathsf{S}$ can be a conservative over-approximation. The advantage
however is that the LP (15) can be solved much faster compared to the
algorithm given in [24].

In addition to the reformulation of the set operations in the constraints, the
objective function can be simplified by removing the maximization part with
the help of slack variables as shown in [28, 26]. If the stage cost (7) is
used with $p=1$,
$\min_{v\in\mathbb{V}}\max_{\tilde{z}}\ell(\tilde{z},v+K_{\mathrm{pred}}\tilde{z})$
can be obtained as follows:

$\displaystyle\min_{v\in\mathbb{V}}\max_{\tilde{z}\in\mathsf{Z}}\ell(\tilde{z},v+K_{\mathrm{pred}}\tilde{z})=\min_{v,\tilde{z},y,\mu,\eta,\gamma}\gamma$
(16a) subject to: $\displaystyle-\mu\leq
Q(\tilde{z}-y)\leq\mu,\,\forall\tilde{z}\in\mathsf{Z},y\in\mathbb{Z}_{f},$
(16b) $\displaystyle-\eta\leq
Rv+K_{\mathrm{pred}}\tilde{z}-K_{f}\tilde{z}\leq\eta,\,\forall\tilde{z}\in\mathsf{Z},$
(16c) $\displaystyle\textbf{1}^{T}\mu+\textbf{1}^{T}\eta\leq\gamma.$ (16d)

Note that $\tilde{z}$ is not known a priori and has been added as a decision
variable in (16). The constraint (16c) simplifies to $-\eta\leq Rv\leq\eta$
because the terminal gain $K_{f}$ is chosen equal to the gain employed in the
predicted tubes (i.e., $K_{f}=K_{\mathrm{pred}}$). The constraints of the
state are infinite dimensional. However, a simplification is possible by
reformulating the bounds on the state objective (16b) with the help of a non-
negative matrix $P_{Q}$ as discussed earlier and the constraint (16b) can be
satisfied for any given $\tilde{z}\in\mathsf{Z}$ if all $z\in\mathsf{Z}$
satisfy (16b) as proposed in [29]. Using Lemma 4.1, we can define a non-
negative matrix $P_{Q}$ such that the following equations hold to satisfy the
constraints (16b) and the constraints (16b)$-$(16d) can be rewritten as
follows for all $(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}$.:

$\displaystyle P_{Q}T=Q,$ (17a) $\displaystyle-\mu_{k}^{j}\leq
P_{Q}\tau_{k}^{j}-Qy_{k}^{j}\leq\mu_{k}^{j},$ $\displaystyle
y_{k}^{j}\in\mathbb{Z}_{f},\,\forall(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (17b)
$\displaystyle-\eta_{k}^{j}\leq Rv_{k}^{j}\leq\eta_{k}^{j},$
$\displaystyle\forall(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket},$ (17c)
$\displaystyle\textbf{1}^{T}\mu_{k}^{j}+\textbf{1}^{T}\eta_{k}^{j}\leq\gamma_{k}^{j},$
$\displaystyle\forall(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}.$ (17d)

The equality constraint (17a) can be obtained offline and the inequality
constraints (17b) and (17c) can be included as the constraints in the
optimization problem online. However, this reformulation of the inequality
constraints does not provide a tight upper bound which means that the obtained
cost is not the same as the one obtained using the original inner maximization
in (36a). The formulation, however, retains the theoretical properties of
recursive feasibility and stability of the original formulation (6). Combining
all the reformulations, the resulting optimization problem
$\mathtt{P}_{N_{p}}^{G}(x)$ can be formulated as

$\displaystyle\min_{\stackrel{{\scriptstyle\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j},y_{k}^{j},\,\forall(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}}}{{\tau_{k}^{j},\gamma_{k}^{j},\eta_{k}^{j},\mu_{k}^{j},\,\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}}}}$
$\displaystyle\sum_{k=0}^{N_{r}-1}\sum_{j=1}^{n_{d}^{k}}\omega_{k}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{k}^{j},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j})+\sum_{k=N_{r}}^{N_{p}-1}\sum_{j=1}^{n_{d}^{N_{r}}}\omega_{k}^{j}\gamma_{k}^{j}$
(18)

subject to:
(6b), (6c), (6h), (10b), (11b), (11d), (13), (17b), (17c), (17d),
$Tz_{N_{r}}^{j}\leq\tau_{N_{r}}^{j},\,\forall(j,N_{r})\in I_{N_{r}}$.

In (18), it can be seen that the set operations are replaced by inequality
constraints with the help of the non-negative matrices $P_{i},\forall
i\in\Gamma_{p},\,P_{x},\,P_{u},P_{Q}$ that are obtained offline. The
constraints (17b)$-$(17d) bound the objective from above using the slack
variables $\gamma_{k}^{j}\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}$. The set of all $x\in\mathbb{X}$ for which there exists a
feasible solution for the optimization problem (18) is denoted as
$\mathtt{X}_{N_{p}}^{G}$. The optimal value function obtained by solving the
optimization problem (18) is denoted as $V_{N_{p}}^{G*}(x)$. The stability
properties of the implementation (18) is proven in Section 5.

###  4.2 Homothetic tube

Since the tubes are characterized using inequalities in the general complexity
tube, explicit values of the vertices are not available online. Hence, the
tight upper bound for the stage costs of the tubes are difficult to obtain. By
formulating the predicted tubes as homothetic tubes (i.e. by fixing the shape
of the sets and only varying the scaling variable), the characterizations of
the vertices can be obtained as follows:

$\displaystyle\mathsf{Z}_{k}^{j}$
$\displaystyle=\\{z|T(z-\hat{z}_{k}^{j})\leq\alpha_{k}^{j}\textbf{1}\\},$
(19a) $\displaystyle=\hat{z}_{k}^{j}\oplus\alpha_{k}^{j}\Lambda,$ (19b)
$\displaystyle=\hat{z}_{k}^{j}\oplus\alpha_{k}^{j}\mathrm{conv}\\{\vee_{1},\vee_{2},\,\dots,\,\vee_{n_{v}}\\},$
(19c)

where $\alpha_{k}^{j}\geq 0$ is a non-negative scalar and the
$\lambda-$contractive set $\Lambda$ is characterized by the vertices
$\vee_{1},\vee_{2},\,\dots,\,\vee_{n_{v}}$, where $n_{v}$ denotes the number
of vertices. The constraints for the homothetic tube can be rewritten as
follows using Lemma 4.1.

$\displaystyle
P_{i}(\alpha_{k}^{j}\textbf{1}+T\hat{z}_{k}^{j})+TB_{i}v_{k}^{j}+Tw_{l}\leq
T\hat{z}_{k+1}^{j}+\alpha_{k+1}^{j}\textbf{1},$ $\displaystyle\forall
i\in\Gamma_{p},\,\forall l\in\Gamma_{\overline{w}},\,(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (20a) $\displaystyle
P_{x}(\alpha_{k}^{j}\textbf{1}+T\hat{z}_{k}^{j})\leq\textbf{1},$
$\displaystyle\forall(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket},$ (20b) $\displaystyle
Gv_{k}^{j}+P_{u}(\alpha_{k}^{j}\textbf{1}+T\hat{z}_{k}^{j})\leq\textbf{1},$
$\displaystyle\forall(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket},$ (20c)
$\displaystyle{P}_{i}(\alpha_{N_{p}}^{j}\textbf{1}+T\hat{z}_{N_{p}}^{j})+Tw_{l}\leq
T\hat{z}_{N_{p}}^{j}+\alpha_{N_{p}}^{j}\textbf{1},$ $\displaystyle\forall
i\in\Gamma_{p},\,\forall l\in\Gamma_{\overline{w}},\forall(j,N_{p})\in
I_{N_{p}}.$ (20d)

Note that the terminal feedback gain is chosen as the gain of the predicted
tubes $K_{\mathrm{pred}}$ as in the general complexity tube case. The
resulting terminal set is defined as

$\displaystyle\mathbb{Z}_{f}\triangleq\\{z\mid
T(z-\hat{z})\leq\alpha\textbf{1},{P}_{i}T=T(A_{i}+B_{i}K_{\mathrm{pred}}),{P}_{i}(T\hat{z}+\alpha\textbf{1})+Tw_{l}\leq
T\hat{z}+\alpha\textbf{1},\forall i\in\Gamma_{p},\,\forall
l\in\Gamma_{\overline{w}}\\}.$ (21)

The homothetic tube enables us to formulate the tube and obtain a tight upper
bound on the extreme stage costs of the tubes as follows:

$\displaystyle\sum_{k=N_{r}}^{N_{p}}J^{\mathrm{tube}}_{k}$
$\displaystyle=\min_{\alpha_{k}^{j},\gamma_{k}^{j},\eta_{k}^{j},\mu_{k}^{j}\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}}\sum_{k=N_{r}}^{N_{p}}\sum_{j=1}^{n_{d}^{N_{r}}}\omega_{k}^{j}\gamma_{k}^{j}$
(22a) subject to $\displaystyle-\mu_{k}^{j}\leq
Q(\hat{z}_{k}^{j}+\alpha\vee_{r}-y_{k}^{j,r})\leq\mu_{k}^{j},$
$\displaystyle\forall r\in\\{1,\,\dots,\,n_{v}\\},(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (22b)
$\displaystyle-\eta_{k}^{j}\leq Rv_{k}^{j}\leq\eta_{k}^{j},$
$\displaystyle\forall r\in\\{1,\,\dots,\,n_{v}\\},\,(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (22c) $\displaystyle
y_{k}^{j,r}\in\mathbb{Z}_{f},$ $\displaystyle\forall(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (22d)
$\displaystyle\textbf{1}^{T}\mu_{k}^{j}+\textbf{1}^{T}\eta_{k}^{j}\leq\gamma_{k}^{j}$
$\displaystyle\forall(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket},$ (22e)

where $(j,r)$ denotes the indices associated with the vertices of the tube
$\mathsf{Z}_{k}^{j}$ for all $(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$. The optimization formulation
in the case of homothetic tubes $\mathtt{P}_{N_{p}}^{H}(x)$ results as
follows:

$\displaystyle\min_{\stackrel{{\scriptstyle\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j},y_{k}^{j},\,\forall(j,k)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}_{\llbracket 0\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}}}{{\alpha_{k}^{j},\gamma_{k}^{j},\eta_{k}^{j},\mu_{k}^{j}\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}}}}$
$\displaystyle\sum_{k=0}^{N_{r}-1}\sum_{j=1}^{n_{d}^{k}}\omega_{k}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{k}^{j},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{k}^{j})+\sum_{k=N_{r}}^{N_{p}-1}\sum_{j=1}^{n_{d}^{N_{r}}}\omega_{k}^{j}\gamma_{k}^{j}$
(23)

subject to:
(6b), (6c), (6h), (20a)$-$(20d), (22b)$-$(22e),
$Tz_{N_{r}}^{j}\leq\alpha_{N_{r}}^{j}\textbf{1},\,\forall(j,N_{r})\in
I_{N_{r}}$.

As in the general complexity tube case, the non-negative matrices
$P_{i},\forall i\in\Gamma_{p},\,P_{x},\,P_{u}$ are obtained offline as defined
in (10), (11a), (11c). The set of all $x\in\mathbb{X}$ for which there exists
a feasible solution for the optimization problem (18) is denoted as
$\mathtt{X}_{N_{p}}^{H}$. The value function obtained by solving the
optimization problem (23) at every time step is denoted as
$V_{N_{p}}^{H*}(x)$.

######  Remark 4.2.

The homothetic tubes can also be implemented using the vertices of the tube as
proposed in [13]. However, the formulation proposed here using the approach in
[16] can be advantageous in terms of reduced computational complexity for a
small conservatism. For example, a low complexity tube for a system of $n_{x}$
dimensions require $2n_{x}$ inequalities only, while $2^{n_{x}}$ vertices are
required to represent the same tube (an exponential increase against a linear
increase). By restricting the vertices to get a tight upper bound on the stage
cost and not computing the reachable sets, applications to high dimensional
systems can be achieved. This is the motivation for the proposed formulation
of the tube-enhanced multi-stage MPC.

###  4.3 Low complexity tube

To reduce the computational complexity of the scheme, low complexity tubes can
be employed. A polytopic tube for the low complexity tube for a given
$(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$ can be
defined as follows:

$\displaystyle\mathsf{Z}_{k}^{j}$
$\displaystyle=\\{z|\underline{\tau}_{k}^{j}\leq\bar{T}z\leq\overline{\tau}_{k}^{j}\\},$
(24)

where $\bar{T}\in\mathbb{R}^{n_{x}\times n_{x}}$ and
$\underline{\tau}_{k}^{j},\overline{\tau}_{k}^{j}\in\mathbb{R}^{n_{x}}$.
Notice that the matrix $\bar{T}$ is a square matrix with $n_{x}$ rows and
columns. Because of the reduced number of inequalities describing the tube,
the complexity can be reduced significantly. In addition, there exists
efficient implementations of the tubes (See [7, 30]) to improve the online
computational time. The low complexity tubes can, however, lead to
conservatism of the resulting scheme. In the proposed formulation, because of
the presence of more degrees of freedom, the conservatism of low complexity
tubes can be mitigated to a certain extent while reducing the computational
time. A more detailed discussion is presented in Section 6.

###  4.4 Computation of feedback gains and invariant sets

The feedback gains $K_{\mathrm{inv}}$ and $K_{\mathrm{pred}}$ should be chosen
offline such that the joint spectral radii of the systems
$\\{(A_{i}+B_{i}K_{\mathrm{inv}}),i\in\Gamma_{p}\\}$ and
$\\{(A_{i}+B_{i}K_{\mathrm{pred}}),i\in\Gamma_{p}\\}$ are in the unit circle
of the complex plane. They can be chosen such that they optimize a performance
measure: for example, the feedback gain $K_{\mathrm{inv}}$ can be chosen such
that the volume of the invariant tube $\mathsf{S}$ is as small as possible and
the prediction gain $K_{\mathrm{pred}}$ can be chosen as the optimal gain for
the linear quadratic regulator either in the nominal or in the worst-case. As
we point out in Remark 2, instead of choosing a prediction gain, one can
choose different gains for different scenarios. However, a systematic way to
obtain multiple prediction gains is an issue for further investigations. If
$N_{r}=N_{p}$, the terminal gain $K_{f}$ can be chosen to maximize the volume
of the terminal set to improve the volume of the feasible domain for a chosen
prediction horizon $N_{p}$.

The implementation of the terminal ingredients is simplified and the
complexity is reduced by using (14) and (21) because these formulations can be
implemented directly in the optimization problem without computing additional
sets. As pointed in [16, 30], this simplifies the implementation but can lead
to a decrease in the feasible domain (for a fixed prediction horizon). In [16,
30], mode 2 dynamics are introduced to find a trade-off between improved
feasible domain and computational complexity. Another option is to choose the
terminal set as large as possible as described in [30] (pp. 216-219). Since
the proposed scheme offers additional feed-forward terms, the proposed
implementation of the terminal set is not as restrictive as in the standard
tube-based MPC schemes. The disturbance invariant set $\mathsf{S}$ can be
obtained by solving the optimization problem defined in (15).

##  5 Recursive feasibility and stability properties

We formulate the fundamental assumptions to establish the theoretical
properties of the proposed scheme as follows.

###### Assumption 2

A convex compact disturbance invariant polytopic set $\textstyle\mathsf{S}$ is
available for the system (3) if $\underline{\mathsf{W}}\neq\\{0\\}$, where
$\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}\subset\mathbb{X}$
and $\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}\subset\mathbb{U}$.
If $\underline{\mathsf{W}}=\\{0\\}$, $\mathsf{S}=\\{0\\}$.

Assumption 2 is required to obtain a non-empty feasible domain. The proposed
formulation (6) offers flexibility to decompose the given uncertainty set
$\mathsf{W}$. Only the disturbances considered in $\underline{\mathsf{W}}$ is
used to build the set $\mathsf{S}$. Hence, satisfying the assumptions is
always possible because $\underline{\mathsf{W}}=\\{0\\}$ is always a possible
choice. If $\underline{\mathsf{W}}=\\{0\\}$, there is no tightening of the
constraints required, but this can result in increased computational
complexity.

###### Assumption 3

An RPI polytopic set
$\mathbb{Z}_{f}\subseteq\mathbb{X}\ominus\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$
that contains the origin is available for the system (3) for the feedback gain
$K_{f}=K_{\mathrm{pred}}$ that satisfies $\mathchoice{\mbox{$\displaystyle
K$}}{\mbox{$\textstyle K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{f}\mathbb{Z}_{f}\subseteq\mathbb{U}\ominus\mathchoice{\mbox{$\displaystyle
K$}}{\mbox{$\textstyle K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$
such that for all $z\in\mathsf{Z}\subseteq\mathbb{Z}_{f}$,
$(A_{i}+B_{i}K_{f})\mathsf{Z}\oplus\overline{W}\subseteq\mathsf{Z}^{+}\subseteq\mathbb{Z}_{f},\,\forall
i\in\Gamma_{p}$ holds, where $\mathsf{Z}$ and $\mathsf{Z}^{+}$ represent the
employed tubes (that over-approximates the reachable set) in the optimization
problem (6).

If $N_{r}=N_{p}$, there is no tube-based part in the predictions. Hence it is
sufficient that the terminal set is robustly invariant with respect to the
system (3) for a terminal feedback gain $K_{f}$. In this case, the tube
$\mathsf{Z}$ in Assumption 3 is defined as a singleton $\mathsf{Z}=\\{z\\}$
and
$\mathsf{Z}^{+}=\\{(A_{i}+B_{i}Kf)z+w_{l},i\in\Gamma_{p},l\in\Gamma_{\overline{w}}\\}$.
However , if $N_{r}<N_{p}$, the tube-based part of the scheme requires that
the set recursion (5) employed by the tube is also robustly invariant. I.e.,
it is also necessary that the terminal set in robust positively invariant with
the employed tubes that over-approximate the reachable sets of the system at
every time step for the feedback gain $K_{\mathrm{pred}}$.

######  Remark 5.1.

We propose to keep the terminal feedback gain $K_{f}$ the same as that of gain
of the predicted tubes. If $K_{f}$ is chosen different from
$K_{\mathrm{pred}}$, then the requirement in Assumption 3 should be modified
as follows to guarantee recursive feasibility: An RPI polytopic set
$\mathbb{Z}_{f}\subseteq\mathbb{X}\ominus\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$
that contains the origin is available for the system (3) for the control law
$\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{pred}}\mathbb{Z}_{f}\subseteq\mathbb{U}\ominus\mathchoice{\mbox{$\displaystyle
K$}}{\mbox{$\textstyle K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$
and
$K_{f}\mathbb{Z}_{f}\subseteq\mathbb{U}\ominus\mathchoice{\mbox{$\displaystyle
K$}}{\mbox{$\textstyle K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$
such that for all $\mathsf{Z}\subseteq\mathbb{Z}_{f}$,
$(A_{i}+B_{i}K_{\mathrm{pred}})\mathsf{Z}\oplus\overline{W}\subseteq\mathsf{Z}^{+}\subseteq\mathbb{Z}_{f},\,\forall
i\in\Gamma_{p}$ and
$(A_{i}+B_{i}K_{f})\mathsf{Z}_{f}\oplus\overline{W}\subseteq\mathbb{Z}_{f},\,\forall
i\in\Gamma_{p}$ hold. This leads to additional complexity in the terminal set
and it is not clear if it leads to advantages in terms of performance. Keeping
$K_{f}=K_{\mathrm{pred}}$ simplifies the requirement and is consistent with
the tube-based schemes proposed in [16, 30].

###### Assumption 4

The stage cost $\ell(z,v)$ and the terminal penalty $V_{f}(z)$ are convex and
positive definite functions and satisfy the following relationships:

  1. 1.

$\ell(z,v)\geq c|z|_{\mathbb{Z}_{f}},\,\forall
z\in\mathbb{Z}\setminus\mathbb{Z}_{f}$, $\ell(z,K_{f}z)=0,\,\forall
z\in\mathbb{Z}_{f}$, $V_{f}(z)=0,\,\forall z\in\mathbb{Z}_{f}$, where
$|z|_{\mathbb{Z}_{f}}:=\min_{y\in\mathbb{Z}_{f}}\|z-y\|_{p}$ and $c$ is a
positive constant.

  2. 2.

$\max_{\tilde{z}\in\mathsf{Z}}\ell(\tilde{z},v+K_{\mathrm{pred}}\tilde{z})\geq
c^{\prime}|\tilde{z}|_{\mathbb{Z}_{f}},\,\forall\mathsf{Z}\subseteq\mathbb{Z}\setminus\mathbb{Z}_{f}$,
$\max_{\tilde{z}\in\mathsf{Z}}\ell(\tilde{z},K_{f}\tilde{z})=0,\,\forall\mathsf{Z}\subseteq\mathbb{Z}_{f}$,
$\max_{\tilde{z}\in\mathsf{Z}}V_{f}(\tilde{z})=0,\forall\mathsf{Z}\subseteq\mathbb{Z}_{f}$,
where $c^{\prime}$ is a positive constant.

######  Lemma 5.2.

Suppose Assumptions 2 and 3 hold and $x\in\mathtt{X}_{N_{p}}$ such that
$\mathtt{P}_{N_{p}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})$ (6) has a
feasible solution, then $\mathtt{P}_{N_{p}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})$ is feasible for all $\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}\in\mathrm{conv}(\\{\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}\\})\oplus\mathchoice{\mbox{$\displaystyle\mathsf{W}$}}{\mbox{$\textstyle\mathsf{W}$}}{\mbox{$\scriptstyle\mathsf{W}$}}{\mbox{$\scriptscriptstyle\mathsf{W}$}},\,\forall
i\in\Gamma_{p}$ if the control input applied to the system (1) follows the
control policy $\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}=\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}+\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}-\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle z$}})$.

Proof. Let the sequence of optimal control inputs obtained by solving the
problem (6) be defined as

$\textbf{v*}=\\{v_{0}^{1*},\,\,\dots,\,v_{N_{r}}^{j*},\,v_{N_{r}+1}^{j*}+K_{\mathrm{pred}}z_{N_{r}+1}^{j*},\,\,\dots,\,v_{N_{p}-1}^{j*}+K_{\mathrm{pred}}z_{N_{p}-1}^{j*},\,\forall(j,k)\in
I_{\llbracket 0\mathrel{,\,}\nobreak N_{p}-1\rrbracket}\\}.$ (25)

The root node of the scenario tree is a decision variable as defined in (6g).
Let the optimal value be denoted as $z=z_{0}^{1*}$. The first element in the
input sequence sequence $v=v_{0}^{1*}$ and the optimal root node
$z=z_{0}^{1*}$ are used in the control law $u=v+K_{\mathrm{inv}}(x-z)$, where
$x$ is the current state of the plant. The input $u$ is then applied to the
plant. The plant evolves from the current state $x$ to the state $x^{+}$ for
the applied input $u$ and the realizations of the uncertainties
$w\in\mathsf{W}$ and the system matrices
$(A,B)\in\mathrm{conv}\\{(\\{A_{i},B_{i},\,\forall i\in\Gamma_{p}\\})\\}$.
$x^{+}$ satisfies the constraints because, the additive disturbances
$w\in\overline{\mathsf{W}}$ and the vertex matrices
$\\{(A_{i},B_{i}),\,\forall i\in\Gamma_{p}\\}$ are explicitly considered in
the scenario tree in the predictions and the invariant set $\mathsf{S}$
accounts for the disturbances $w\in\underline{\mathsf{W}}$. At the next time
step, the optimization problem (6) is solved again for the realized state
$x^{+}$. Since $\mathsf{S}$ is invariant with respect to the additive
disturbances $w\in\underline{\mathsf{W}}$, there exists a
$z^{+}\in\mathrm{conv}(\\{z_{1}^{j*},\,\forall(j,1)\in
I_{1}\\})\subseteq\mathbb{Z}=\mathbb{X}\ominus\mathsf{S}$ from Assumption 2.
There exists a feasible input sequence for the optimization problem
$\mathtt{P}_{N_{p}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}^{+})$ that is in
the convex hull of inputs predicted in the previous time step for the
optimization problem $\mathtt{P}_{N_{p}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ for all prediction steps until $N_{p}-1$. For the last prediction step,
there exists a control law $K_{f}z$ for all $z\in\mathbb{Z}_{f}$ from
Assumption 3. A feasible input sequence for the next time step can be obtained
as the convex combination of the predicted inputs as follows:

$\displaystyle\textbf{v}(x^{+})$ $\displaystyle=\bigg{\\{}\sum_{(j,1)\in
I_{1}}\lambda_{1}^{j}v_{1}^{j*},\,\dots,\,\sum_{(j,N_{r})\in
I_{N_{r}}}\lambda_{N_{r}}^{j}v_{N_{r}}^{j*},\sum_{(j,N_{r}+1)\in
I_{N_{r}+1}}\lambda_{N_{r}+1}^{j}v_{N_{r}+1}^{j*}+K_{\mathrm{pred}}z_{N_{r}+1}^{j*},\,\dots,\,\sum_{(j,N_{p})\in
I_{N_{p}}}\lambda_{N_{p}}^{j*}K_{f}z_{N_{p}}^{j*}\bigg{\\}},$ (26)

where $\lambda_{k}^{j}$ denote the associated convex weights for all $(j,k)\in
I$ ($\lambda_{k}^{j}\geq 0,$ and $\sum_{j=1}^{n_{d}}\lambda_{k}^{j}=1$). Since
there exists a feasible root node $z^{+}$ and a feasible input sequence
$\textbf{v}(x^{+})$, problem
$\mathtt{P}_{N_{p}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}^{+})$ is feasible
for all $\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}\in\\{\mathchoice{\mbox{$\displaystyle A$}}{\mbox{$\textstyle
A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}\\}\oplus\mathchoice{\mbox{$\displaystyle\mathsf{W}$}}{\mbox{$\textstyle\mathsf{W}$}}{\mbox{$\scriptstyle\mathsf{W}$}}{\mbox{$\scriptscriptstyle\mathsf{W}$}}$
for all $i\in\Gamma_{p}$ if
$\mathtt{P}_{N_{p}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})$ is feasible.∎

We now show that the recursve feasibility property is retained if the convex
optimization problems (18) and (23) related to the formulation (6) are solved.

######  Corollary 5.3.

Suppose Assumptions 2 and 3 hold and $x\in\mathtt{X}_{N_{p}}$ such that
$\mathtt{P}_{N_{p}}^{\mathrm{G}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ (18) has a feasible solution for the tube
$\mathsf{Z}_{k}^{j}=\\{z|Tz\leq\tau_{k}^{j}\\},\forall(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$, then
$\mathtt{P}_{N_{p}}^{\mathrm{G}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})$ is feasible for all $\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}\in\mathrm{conv}(\\{\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}\\})\oplus\mathchoice{\mbox{$\displaystyle\mathsf{W}$}}{\mbox{$\textstyle\mathsf{W}$}}{\mbox{$\scriptstyle\mathsf{W}$}}{\mbox{$\scriptscriptstyle\mathsf{W}$}},\,\forall
i\in\Gamma_{p}$ if the control input applied to the system (1) follows the
control policy $\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}=\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}+\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}-\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle z$}})$.

Proof. The constraints of the optimization problems (6) and (18) can be
compared one to one. The constraints (6b), (6c), (6h) are retained in
optimization problem (18). The remaining constraints are direct results of
Lemma 4.1 which establishes sufficient conditions for the set recursion and
guaranteeing that a set is a subset of another. Hence, the feasibility
arguments discussed in Lemma 5.2 directly applies to the formulation (18).
Hence, $\mathtt{P}_{N_{p}}^{\mathrm{G}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})$ is feasible for all $\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}\in\mathrm{conv}(\\{\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}\\})\oplus\mathchoice{\mbox{$\displaystyle\mathsf{W}$}}{\mbox{$\textstyle\mathsf{W}$}}{\mbox{$\scriptstyle\mathsf{W}$}}{\mbox{$\scriptscriptstyle\mathsf{W}$}},\,\forall
i\in\Gamma_{p}$ if the control input applied to the system (1) follows the
control policy $\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}=\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}+\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}-\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle z$}})$.∎

######  Corollary 5.4.

Suppose Assumptions 2 and 3 hold and $x\in\mathtt{X}_{N_{p}}$ such that
$\mathtt{P}_{N_{p}}^{\mathrm{H}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ (23) has a feasible solution for the tube
$\mathsf{Z}_{k}^{j}=\\{z|T(z-\hat{z}_{k}^{j})\leq\alpha_{k}^{j}\textbf{1}\\},\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$, then
$\mathtt{P}_{N_{p}}^{\mathrm{H}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})$ is feasible for all $\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}\in\mathrm{conv}(\\{\mathchoice{\mbox{$\displaystyle
A$}}{\mbox{$\textstyle A$}}{\mbox{$\scriptstyle A$}}{\mbox{$\scriptscriptstyle
A$}}_{i}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}+\mathchoice{\mbox{$\displaystyle B$}}{\mbox{$\textstyle
B$}}{\mbox{$\scriptstyle B$}}{\mbox{$\scriptscriptstyle
B$}}_{i}\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}\\})\oplus\mathchoice{\mbox{$\displaystyle\mathsf{W}$}}{\mbox{$\textstyle\mathsf{W}$}}{\mbox{$\scriptstyle\mathsf{W}$}}{\mbox{$\scriptscriptstyle\mathsf{W}$}},\,\forall
i\in\Gamma_{p}$ if the control input applied to the system (1) follows the
control policy $\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}=\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}+\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}-\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle z$}})$.

Proof. The same arguments in Corollary 5.3 directly apply here as well. ∎

######  Lemma 5.5.

If Assumptions 1, 2, 3 and 4 hold, then
$V^{*}_{N_{p}+1}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})\leq
V^{*}_{N_{p}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}),\,\forall\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}$, where $V^{*}_{N_{p}}(x)$ is the optimal value
function of (6) with the length of the prediction horizon $N_{p}$.

Proof. Since the stage costs $\ell(z,K_{f}z)=0$ and
$\max_{\tilde{z}\in\mathsf{Z}}\ell(z,K_{f}z)=0$ in the terminal set and the
control law $K_{f}z$ is feasible, the additional prediction step does not add
any cost to the optimal value function
$V^{*}_{N_{p}+1}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})$ and hence
$V^{*}_{N_{p}+1}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})\leq
V^{*}_{N_{p}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}),\,\forall\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}$.∎

######  Lemma 5.6.

If Assumptions 1, 2, 3 and 4 hold and $\mathtt{X}_{N_{p}}$ is compact, then
the optimal value function fulfills the following properties

$\displaystyle V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ $\displaystyle=0,\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathbb{Z}_{f}\oplus\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}},$
(27) $\displaystyle V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ $\displaystyle\geq
c_{1}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}},$ (28) $\displaystyle
V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}^{+})$
$\displaystyle\leq V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})-c_{1}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}},$ (29)

where $c_{1}$ is a positive constant.

Proof. Since $\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathbb{Z}_{f}\oplus\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$
implies that $\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})\in\mathbb{Z}_{f}$ is a feasible point, the stage cost $\ell(z,K_{f}z)=0$
from Assumption 4 and the control law $K_{f}z$ keeps the state $z$ in the
terminal set $\mathbb{Z}_{f}$ from Assumption 3. Since $V_{f}(z)=0$ and all
the stage costs are zero $V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})=0$ for all $x\in\mathbb{Z}_{f}\oplus\mathsf{S}$. This proves (27).

From Assumption 4, $\ell(z,v)\geq k|z|_{\mathbb{Z}_{f}}$ and the optimal value
function satisfies the property
$V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})\geq\omega_{0}^{1}\ell(z_{0}^{1*},v_{0}^{1*})$. Since $\omega_{0}^{1}\geq
0$, we have $V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})\geq c_{1}|z|_{\mathbb{Z}_{f}}$ for all
$z\in\mathbb{Z}\setminus\mathbb{Z}_{f}$, where $c_{1}=k\omega_{0}^{1}$ a
positive constant. Note that $V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})=0$ for all $x\in\mathbb{Z}_{f}\oplus\mathsf{S}$ and
$|z|_{\mathbb{Z}_{f}}=0$ for all $z\in\mathbb{Z}_{f}$. Hence
$V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})\geq
c_{1}|z|_{\mathbb{Z}_{f}}$ for all $\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\ \mathtt{X}_{N_{p}}$.

In the following, the descent property of the optimal value function will be
proven. This property establishes the optimal value function as a Lyapunov
function and is an important contribution of this paper.

Figure 3: Illustration of the descent property of the proposed scheme.

As shown in Lemma 1, the initial state $\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})$ and the control
policy given in (26) are feasible for all $x\in\mathtt{X}_{N_{p}}$. Since
$\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}^{+}\in\mathrm{conv}(\\{z_{1}^{j*},\,\forall(j,1)\in\mathchoice{\mbox{$\displaystyle
I$}}{\mbox{$\textstyle I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle
I$}}\\})$, the optimal value function $V_{N_{p}}^{*}(x)$ and a feasible value
function at the next time step $(V_{N_{p}}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+}))$ can be written as:

$\displaystyle
V_{N_{p}}^{*}(x)=\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS*}}_{k}(x)+J^{\mathrm{tube*}}_{N_{r}}(x)+\sum_{k=N_{r}+1}^{N_{p}-1}J^{\mathrm{tube*}}_{k}(x),$
(30a) $\displaystyle
V_{N_{p}}(x^{+})=\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x^{+})+\sum_{k=N_{r}}^{N_{p}-1}J^{\mathrm{tube}}_{k}(x^{+}).$
(30b)

The proof will be accomplished in two parts. Initially the multi-stage part of
the value function $V_{N_{p}}(x^{+})$ will be compared to the optimal value
function $V_{N_{p}}^{*}(x)$ obtained one step before. Because of the receding
horizon nature of the MPC, the comparison of the multi-stage part of
$V_{N_{p}}(x^{+})$ will be performed with the multi-stage part and the one-
step tube-based part ($J^{\mathrm{MS*}}_{k}(x)+J^{\mathrm{tube*}}_{N_{r}}(x)$)
of the optimal value function $V_{N_{p}}^{*}(x)$. It will be shown that
$\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x^{+})\leq\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS*}}_{k}(x)+J^{\mathrm{tube*}}_{N_{r}}(x)-c_{1}|z|_{\mathbb{Z}_{f}}$.
The multi-stage part of the value function
$\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x^{+})$ can be written as (refer to
Figure 3):

$\displaystyle\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x^{+})=$
$\displaystyle\,\omega_{0}^{1}\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{1}^{j}z_{1}^{j*},\sum_{j=1}^{n_{d}}\lambda_{1}^{j}v_{1}^{j*}\bigg{)}+\cdots+\sum_{j=1}^{n_{d}^{N_{r}-2}}\omega_{N_{r}-2}^{j}\,\,\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{N_{r}-1}^{j}z_{N_{r}}^{j*},\sum_{j=1}^{n_{d}}\lambda_{N_{r}-1}^{j}v_{N_{r}}^{j*}\bigg{)}+$
$\displaystyle+\sum_{j=1}^{n_{d}^{N_{r}-1}}\omega_{N_{r}-1}^{j}\,\,\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{N_{r}}^{j}z_{N_{r}+1}^{j+},\sum_{j=1}^{n_{d}}\lambda_{N_{r}}^{j}(v_{N_{r}}^{j*}+K_{\mathrm{pred}}z_{N_{r}}^{j+})\bigg{)},$
(31)

where
$z_{N_{r}}^{j+}\in\mathrm{conv}(\\{\mathsf{Z}_{N_{r}}^{j}(x)\\},\,\forall(j,N_{r})\in
I_{N_{r}})$. Since the proposed stage cost is convex from Assumption 4, the
following inequality holds for the stage cost of the root node of the tree at
$\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}^{+}$.

$\displaystyle\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{1}^{j}z_{1}^{j*},\sum_{j=1}^{n_{d}}\lambda_{1}^{j}v_{1}^{j*}\bigg{)}$
$\displaystyle\leq\sum_{j=1}^{n_{d}}\lambda_{1}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{1}^{j*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{1}^{j*}).$ (32)

Multiplying both sides with $\omega_{0}^{1}$, we get

$\displaystyle\omega_{0}^{1}\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{1}^{j}z_{1}^{j*},\sum_{j=1}^{n_{d}}\lambda_{1}^{j}v_{1}^{j*}\bigg{)}$
$\displaystyle\leq\omega_{0}^{1}\sum_{j=1}^{n_{d}}\lambda_{1}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{1}^{j*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{1}^{j*}).$ (33)

From Assumption 1,
$\omega_{0}^{1}\leq\min\\{\omega_{1},\,\dots,\,\omega_{p}\\}$, so
$\omega_{0}^{1}\sum_{j=1}^{n_{d}}\lambda_{1}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{1}^{j*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}_{1}^{j*})\leq\sum_{j=1}^{n_{d}}\lambda_{1}^{j}\omega_{1}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{1}^{j*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{1}^{j*})$ and
$\sum_{j=1}^{n_{d}}\lambda_{1}^{j}=1$, which results in:

$\displaystyle\omega_{0}^{1}\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{1}^{j}z_{1}^{j*},\sum_{j=1}^{n_{d}}\lambda_{1}^{j}v_{1}^{j*}\bigg{)}$
$\displaystyle\leq\sum_{j=1}^{n_{d}}\omega_{1}^{j}\lambda_{1}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{1}^{j*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{1}^{j*}).$ (34)

Similarly the stage costs for the prediction steps until $N_{r}-2$ of the
value function $V_{N_{p}}(x^{+})$ can be compared for all
$(j,k)\in\mathchoice{\mbox{$\displaystyle I$}}{\mbox{$\textstyle
I$}}{\mbox{$\scriptstyle I$}}{\mbox{$\scriptscriptstyle I$}}_{\llbracket
0\mathrel{,\,}\nobreak N_{r}-2\rrbracket}$ by grouping the nodes that are
established for a particular realization of the uncertainty $i\in\Gamma_{p}$
and $l\in\Gamma_{\overline{w}}$ together. Note that, if $N_{r}=0$, there is no
multi-stage part in the objective. If $N_{r}=1$ only the root node belongs to
the multi-stage part and it will be compared with the tube-based part (first-
stage) of the optimal value function in the previous time-step
$V_{N_{p}}^{*}(x)$ as will be discussed later. If $N_{r}=2$, the root node
will be compared to the multi-stage part as in (34) and for the comparison of
the further stages onwards one can skip to (36). The following relationship
for the case is discussed whenever $N_{r}>2$ until $N_{r}-2$ of the value
function $V_{N_{p}}(x^{+})$. Since the weights $\omega_{k}^{j}$ associated
with each node $z_{k}^{j}$ are the same as the weights associated with a
realized uncertainty until $N_{r}-1$ of the problem
$\mathtt{P}_{N_{p}}(x^{+})$, we have

$\displaystyle\omega_{k}^{j}\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{k}^{j}z_{k}^{j*},\sum_{j=1}^{n_{d}}\lambda_{k}^{j}v_{k}^{j*}\bigg{)}$
$\displaystyle\leq\sum_{j=1}^{n_{d}}\omega_{k+1}^{j}\lambda_{k}^{j}\ell(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{k}^{j*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{k}^{j*}).$ (35)

The stage cost at the prediction step $N_{r}-1$ of the problem
$\mathtt{P}_{N_{p}}(x^{+})$ can be compared with the tube-based part of the
optimal value function $V_{N_{p}}^{*}(x)$. Again using convexity, the
following relationship can be established.

$\displaystyle\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{N_{r}}^{j}z_{N_{r}}^{j+},$
$\displaystyle\sum_{j=1}^{n_{d}}\lambda_{N_{r}}^{j}(v_{N_{r}}^{j*}+K_{\mathrm{pred}}z_{N_{r}}^{j+})\bigg{)}\leq\ell(\tilde{z}_{N_{r}}^{j*},v_{k}^{j*}+K_{\mathrm{pred}}\tilde{z}_{N_{r}}^{j*}),$
(36)

where $z_{N_{r}}^{j+}$ belongs to the convex hull of the tubes
$\mathsf{Z}_{N_{r}}^{j*}$ predicted in the problem $\mathtt{P}_{N_{p}}(x)$.
Note that the stage cost of the tube-based part of the optimal value function
$V_{N_{p}}^{*}(x)$ contains the maximization objective, the optimal states
$\tilde{z}_{N_{r}}^{j*}$ give the worst-case cost for all $(j,N_{r})\in
I_{N_{r}}$. Since the weight associated with $J^{\mathrm{tube*}}_{N_{r}}(x)$
is greater than the weights associated with all the realizations of the
uncertainty from Assumption 1, we have

$\displaystyle\omega^{j}_{N_{r}-1}$
$\displaystyle\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{N_{r}}^{j}z_{N_{r}}^{j+},\sum_{j=1}^{n_{d}}\lambda_{N_{r}}^{j}(v_{N_{r}}^{j*}+K_{\mathrm{pred}}z_{N_{r}}^{j+})\bigg{)}\leq\sum_{j=1}^{n_{d}}\omega_{\mathrm{tube}}\lambda_{N_{r}}^{j}\ell(\tilde{z}_{N_{r}}^{j*},v_{k}^{j*}+K_{\mathrm{pred}}\tilde{z}_{N_{r}}^{j*}),$
(37)

Substituting (34), (35), (37) in (5), we get

$\displaystyle\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x^{+})$
$\displaystyle\leq\sum_{k=1}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x)+J^{\mathrm{tube*}}_{N_{r}}(x),$
(38)
$\displaystyle\leq\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x)+J^{\mathrm{tube*}}_{N_{r}}(x)-\omega_{0}^{1}{\ell}(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{0}^{1*}).$ (39)

The tube-based part of the optimal value function $V_{N_{p}}(x^{+})$ can be
compared with the tube-based part of $V_{N_{p}}^{*}(x)$. Since the predicted
tubes of the problem $\mathtt{P}_{N_{p}}(x^{+})$ from the prediction step
$N_{r}$ until $N_{p}-2$ belong to the convex hull of $\mathtt{P}_{N_{p}}(x)$,
we have

$\displaystyle\sum_{k=N_{r}}^{N_{p}-2}J^{\mathrm{tube}}_{k}(x^{+})\leq\sum_{k=N_{r}+1}^{N_{p}-1}J^{\mathrm{tube*}}_{k}(x).$
(40)

The stage costs at the prediction step $N_{p}-1$ are
$\ell\bigg{(}\sum_{j=1}^{n_{d}}\lambda_{N_{p}}^{j}\tilde{z}_{N_{p}}^{j*}(x),\,\sum_{j=1}^{n_{d}}\lambda_{N_{p}}^{j}K_{f}\tilde{z}_{N_{p}}^{j*}\bigg{)}=0$
by definition. Hence the following relationship holds:

$\displaystyle\sum_{k=N_{r}}^{N_{p}-1}J^{\mathrm{tube}}_{k}(x^{+})\leq\sum_{k=N_{r}+1}^{N_{p}-1}J^{\mathrm{tube*}}_{k}(x).$
(41)

From (39) and (41), the value function $V_{N_{p}}(x^{+})$ can then be written
in terms of $V_{N_{p}}(x)$ as follows:

$\displaystyle V_{N_{p}}(x^{+})\leq
V_{N_{p}}^{*}(x)-\omega_{0}^{1}{\ell}(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{0}^{1*}).$ (42)

Since $V^{*}_{N_{p}}(x^{+})\leq V_{N_{p}}(x^{+})$, we have

$\displaystyle V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})$ $\displaystyle\leq V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})-\omega_{0}^{1}{\ell}(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{0}^{1*}),$ (43)
$\displaystyle V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})$ $\displaystyle\leq V_{N_{p}}^{*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})-c_{1}|z|_{\mathbb{Z}_{f}},\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}.$ (44)

This proves (29) and with this Lemma 3 is established.∎

######  Remark 5.7.

The proof of descent (29) is valid for all values of robust horizon in the
range $N_{r}\in[0,N_{p}]$. If $N_{r}=0$, then the scheme is simplified into a
tube-based MPC scheme enhanced by an invariant tube. If $N_{r}=N_{p}$, the
scheme simplifies into a multi-stage MPC scheme enhanced by an invariant tube.
The proof was established for a generic case where both the multi-stage and
tube components are present. If one of the components is absent, it can be
shown that the proof still holds by removing the corresponding elements in the
proof.

######  Lemma 5.8.

If Assumptions 1, 2, 3 and 4 hold and $\mathtt{X}_{N_{p}}^{G}$ is compact, the
optimal value function $V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ of the optimization problem (18) fulfills the following properties for
the system (1)

$\displaystyle V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ $\displaystyle=0,\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathbb{Z}_{f}\oplus\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}},$
(45) $\displaystyle V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ $\displaystyle\geq
c_{2}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}^{G},$ (46) $\displaystyle
V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}^{+})$
$\displaystyle\leq V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})-c_{2}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}^{G},$ (47)

where $c_{2}$ is a positive constant.

Proof. Because of the choice of the stage costs, the proofs are (45) and (46)
are similar to Lemma 5.6. In here, we show that the reformulation (18) retains
these properties.

To prove (45), it is sufficient to show that the stage costs are $0$ for a
feasible solution for all $x\in\mathbb{Z}_{f}\oplus\mathsf{S}$. For all
$x\in\mathbb{Z}_{f}\oplus\mathsf{S}$, it can be seen that $z\in\mathbb{Z}_{f}$
is a feasible point. The terminal control law $K_{f}z$ keeps the trajectory of
the primary controller in the terminal set $\mathbb{Z}_{f}$. The stage costs
associated with the multi-stage part of the scheme are $0$. I.e.,
$\ell(z_{k}^{j},v_{k}^{j})=0$ for all $z_{k}^{j}\in\mathbb{Z}_{f}$, for all
$(j,k)\in I_{\llbracket 0\mathrel{,\,}\nobreak N_{r}-1\rrbracket}$. For the
tube-based part of the scheme, the stage cost is reformulated as in
(17a)$-$(17c). Equivalently, the stage cost can be represented as

$\displaystyle\max_{\tilde{z}_{k}^{j}\in\mathsf{Z}_{k}^{j}}\ell(\tilde{z}_{k}^{j},v_{k}^{j})=$
$\displaystyle\min_{y_{k}^{j}\in\mathbb{Z}_{f},\eta_{k}^{j},\mu_{k}^{j},\gamma_{k}^{j},\forall(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}.}\gamma_{k}^{j}$
(48a) subject to:
$\displaystyle-\mu_{k}^{j}\leq(P_{Q}\tau_{k}^{j}-Qy_{k}^{j})\leq\mu_{k}^{j},(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (48b)
$\displaystyle-\eta_{k}^{j}\leq Rv_{k}^{j}\leq\eta_{k}^{j},(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (48c)
$\displaystyle\textbf{1}^{T}\mu_{k}^{j}+\textbf{1}^{T}\eta_{k}^{j}\leq\gamma_{k}^{j},(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}.$ (48d)

For all $x\in\mathbb{Z}_{f}\oplus\mathsf{S}$ and $N_{r}=0$,
$\mathsf{Z}_{0}^{j}=\mathbb{Z}_{f}$ is a feasible set for all $(j,0)\in
I_{0}$. If $N_{r}\geq 1$, the terminal control law keeps the state in the
terminal set and hence $z_{N_{r}}^{j}\in\mathbb{Z}_{f},\,\forall(j,N_{r})\in
I_{N_{r}}$. Hence, $\mathsf{Z}_{N_{r}}^{j}=\mathbb{Z}_{f}$ is a feasible set
for all $(j,N_{r})\in I_{N_{r}}$. Since the set $\mathbb{Z}_{f}$ is robustly
positive invariant for the control law $K_{f}\mathsf{Z}_{k}^{j}$,
$v_{k}^{j}=0$ is a feasible control law for the tube-based part of the scheme.
Substituting $v_{k}^{j}=0$, and $Q=P_{Q}T$ from (17a), the constraints (48b)
and (48c) can be rewritten as follows:

$\displaystyle-\mu_{k}^{j}\leq
P_{Q}(\tau_{k}^{j}-Ty_{k}^{j})\leq\mu_{k}^{j},(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (49a)
$\displaystyle-\eta_{k}^{j}\leq Rv_{k}^{j}\leq\eta_{k}^{j},(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket},$ (49b)

Since $\mathsf{Z}_{k}^{j}=\mathbb{Z}_{f}$ is a feasible solution, there exists
a feasible solution $y_{k}^{j}=z_{k}^{j}$ such that $Tz_{k}^{j}=\tau_{k}^{j}$
holds for any $(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}$. Hence, $\mu_{k}^{j}=\eta_{k}^{j}=\gamma_{k}^{j}=0$ is a
feasible solution for all $(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}$, if $\mathsf{Z}_{k}^{j}\subseteq\mathbb{Z}_{f}$. This
implies that the stage costs remain $0$ for all
$x\in\mathbb{Z}_{f}\oplus\mathsf{S}$ for the tube-based part of the scheme in
addition to the multi-stage part of the scheme for the formulation (18). Hence
$V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})=0,\,\forall\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathbb{Z}_{f}\oplus\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}}$.

The proof of (46) is straight forward as shown in Lemma 5.6. Because of the
choice of $Q$ and $R$ matrices as positive definite and that the tube-based
part of the scheme over-approximates the cost,
$V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})\geq
c_{2}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}^{G}$, where $c_{2}\geq c_{1}$.

To prove (47), the multi-stage part of the scheme follows the same arguments
given in the proof of Lemma 5.6. For the tube-based part, because of the
reformulation (17) and choosing the non-negative matrices offline, we can only
establish a sufficient condition online. Hence $J_{k}^{\mathrm{tube}*}$ solved
using (18) will always over-approximate the true solution obtained using the
formulation (6). From this, we see that the following inequality holds:

$\displaystyle\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x^{+})$
$\displaystyle\leq\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x)+J^{\mathrm{tube*}}_{N_{r}}(x)-\omega_{0}^{1}{\ell}(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{0}^{1*}).$ (50)

To compare the tube-based part of the scheme, we must establish the following
inequality:

$\displaystyle\sum_{k=N_{r}}^{N_{p}-1}J^{\mathrm{tube}}_{k}(x^{+})\leq\sum_{k=N_{r}+1}^{N_{p}-1}J^{\mathrm{tube*}}_{k}(x).$
(51)

for all $(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}$. To compare the components of the stage costs at
consecutive time steps, let us look at the constraint (48b) in the
optimization problem (48). Since the predicted tubes at the next time step can
be given as the convex combination of the tubes predicted at the current time
step, the following holds for all $(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-2\rrbracket}$.

$\displaystyle|P_{Q}\tau_{k}^{j}(x^{+})-Qy_{k}^{j}(x^{+})|$
$\displaystyle=|P_{Q}\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}\tau_{k+1}^{j*}(x)-Q\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}y_{k+1}^{j*}(x)|,$
(52a)
$\displaystyle\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}(|P_{Q}\tau_{k+1}^{j*}(x)-Qy_{k+1}^{j*}(x)|),$
(52b)
$\displaystyle\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}(|\mu_{k+1}^{j*}(x)|),$
(52c)

where $\lambda_{k}^{j}$ denotes the convex weights associated with the tubes
for all $(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}$. Minkowski’s inequality leads to (52b) from (52a) and
(52c) follows from (48b). Similarly, the following holds for the constraint
(48c) in the optimization problem (48) for all $(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-2\rrbracket}$.

$\displaystyle|Rv_{k}^{j}(x^{+})|$
$\displaystyle=|R\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}v_{k+1}^{j*}(x)|$
(53a)
$\displaystyle\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}(|Rv_{k+1}^{j*}(x)|),$
(53b)
$\displaystyle\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}(|\eta_{k+1}^{j*}(x)|),$
(53c)

Substituting (52) and (53) in (48d), there exist a feasible
$\gamma_{k}^{j}(x^{+})$ for all $(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-2\rrbracket}$ such that the following holds:

$\displaystyle\gamma_{k}^{j}(x^{+})\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}\gamma_{k+1}^{j*}(x)$
(54)

Combining (54) with Assumption 1, we have

$\displaystyle\sum_{j=1}^{n_{d}^{N_{r}}}\omega_{k}^{j}\gamma_{k}^{j}(x^{+})\leq\sum_{j=1}^{n_{d}^{N_{r}}}\omega_{k+1}^{j}\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}\gamma_{k+1}^{j*}(x)$
(55)

for all $k\in\\{N_{r},\,\dots,\,N_{p}-2\\}$. As shown in (48), the stage costs
remain zero for the additional step. Summing up across the horizon for the
tube-based part of the scheme, we get,

$\displaystyle\sum_{k=N_{r}}^{N_{p}-1}J^{\mathrm{tube}}_{k}(x^{+})\leq\sum_{k=N_{r}+1}^{N_{p}-1}J^{\mathrm{tube*}}_{k}(x).$
(56)

This leads to the condition $V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})\leq V_{N_{p}}^{G*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})-c_{2}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}^{G}$. This proves (47).∎

######  Lemma 5.9.

If Assumptions 1, 2, 3 and 4 hold and $\mathtt{X}_{N_{p}}^{H}$ is compact, the
optimal value function $V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ fulfills the following properties

$\displaystyle V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ $\displaystyle=0,\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathbb{Z}_{f}\oplus\mathchoice{\mbox{$\displaystyle\mathsf{S}$}}{\mbox{$\textstyle\mathsf{S}$}}{\mbox{$\scriptstyle\mathsf{S}$}}{\mbox{$\scriptscriptstyle\mathsf{S}$}},$
(57) $\displaystyle V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})$ $\displaystyle\geq
c_{3}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}^{H},$ (58) $\displaystyle
V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}}^{+})$
$\displaystyle\leq V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})-c_{3}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}^{H},$ (59)

where $c_{3}$ is a positive constant.

Proof. First, we prove (57). The multi-stage part of the scheme inherits the
same properties discussed in Lemma 5.6 and 5.8 and the stage cost
$\ell(z_{k}^{j},v_{k}^{j})=0,\,\forall(j,K)\in I_{\llbracket
0\mathrel{,\,}\nobreak N_{r}-1\rrbracket}$, if
$x\in\mathbb{Z}_{f}\oplus\mathsf{S}$ . If $N_{r}=0$, for all
$x\in\mathbb{Z}_{f}\oplus\mathsf{S}$, $\mathsf{Z}_{0}^{j}=\mathbb{Z}_{f}$ is a
feasible set for all $(j,0)\in I_{0}$. Also, if $N_{r}\geq 1$, if
$z_{N_{r}}^{j}\in\mathbb{Z}_{f},\,\mathsf{Z}_{N_{r}}^{j}=\mathbb{Z}_{f}$ is a
feasible set for each $(j,N_{r})\in I_{N_{r}}$. Since the set $\mathbb{Z}_{f}$
is robustly positive invariant for the control law
$K_{\mathrm{pred}}\mathsf{Z}_{k}^{j}$ , $v_{k}^{j}=0$ is a feasible control
law for the tube-based part of the scheme. All the vertex points of the tube
$\hat{z}_{k}^{j}+\alpha\vee_{r}$ is contained in the set $\mathbb{Z}_{f}$. For
each $\hat{z}_{k}^{j}+\alpha\vee_{r}$, there exists a feasible
$y_{k}^{j,r}\in\mathbb{Z}_{f}$. Hence, the upper bound of
$|Q(\hat{z}_{k}^{j}+\alpha\vee_{r}-y_{k}^{j,r})|$ is $0$ in (22). Also
$|Rv_{k}^{j}|\leq 0$ is a feasible solution. Hence, $\gamma_{k}^{j}=0,(j,k)\in
I_{\llbracket N_{r}\mathrel{,\,}\nobreak N_{p}-1\rrbracket}$ is feasible in
(22). Since the optimal cost is smaller than or equal to the feasible value,
the upper bound of the stage cost is $0$. From the definition of the terminal
set $(A+BK_{\mathrm{pred}})\mathbb{Z}_{f}\subseteq\mathbb{Z}_{f}$, implying
$\mathsf{Z}_{k+1}^{j}\subseteq\mathsf{Z}_{k}^{j}$. This leads to the case
where the stage cost remains $0$ until $N_{p}$. Hence if
$x\in\mathbb{Z}_{f}\oplus\mathsf{S}$,
$V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle x$}})=0$.

The proof of (58) follows directly from the choice of the stage cost. Since
$Q$ and $R$ are positive definite, (58) holds.

To prove (59), the proof of the multi-stage part of the scheme follows the
same arguments in Lemma 5.6. Hence the following inequality holds:

$\displaystyle\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x^{+})$
$\displaystyle\leq\sum_{k=0}^{N_{r}-1}J^{\mathrm{MS}}_{k}(x)+J^{\mathrm{tube*}}_{N_{r}}(x)-\omega_{0}^{1}{\ell}(\mathchoice{\mbox{$\displaystyle
z$}}{\mbox{$\textstyle z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}_{0}^{1*},\mathchoice{\mbox{$\displaystyle v$}}{\mbox{$\textstyle
v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle v$}}_{0}^{1*}).$ (60)

For the tube-based part of the scheme, the tubes at the next step can be
represented as the convex combination of tubes predicted at the previous time
step. Hence the following relationship holds $(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-2\rrbracket}$.

$\displaystyle|Q(\hat{z}_{k}^{j}(x^{+})+\alpha_{k}^{j}\vee_{r}-y_{k}^{j,r}(x^{+}))|$
$\displaystyle=|Q\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}\hat{z}_{k+1}^{j*}(x)+\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}\alpha_{k+1}^{j*}\vee_{r}-\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}y_{k+1}^{j,r*}(x)|,\,r\in\\{1,\dots,\,n_{v}\\},$
(61a)
$\displaystyle\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}|Q(\hat{z}_{k+1}^{j*}(x)+\alpha_{k+1}^{j*}\vee_{r}-y_{k+1}^{j,r*}(x)|),\,r\in\\{1,\dots,\,n_{v}\\},$
(61b)
$\displaystyle\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}|\mu_{k+1}^{j*}|,\,\forall
r\in\\{1,\dots,\,n_{v}\\},$ (61c)

here $\lambda_{k}^{j}$ denotes the convex weights associated with the
predicted tubes for all $(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-1\rrbracket}$. Following the same arguments for the inputs, we arrive at
the following inequality

$\displaystyle|Rv_{k}^{j}(x^{+})|\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}|\eta_{k+1}^{j*}|,$
(62)

for all $(j,k)\in I_{\llbracket N_{r}\mathrel{,\,}\nobreak
N_{p}-2\rrbracket}$. Combining (61) and (62) in (22e), we can see that there
exists a feasible $\gamma_{k}^{j}(x^{+})$ for all $(j,k)\in I_{\llbracket
N_{r}\mathrel{,\,}\nobreak N_{p}-2\rrbracket}$ such that the following
inequality holds as in Lemma 5.8:

$\displaystyle\gamma_{k}^{j}(x^{+})\leq\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}\gamma_{k+1}^{j*}(x)$
(63)

Combining (63) with Assumption 1, we have

$\displaystyle\sum_{j=1}^{n_{d}^{N_{r}}}\omega_{k}^{j}\gamma_{k}^{j}(x^{+})\leq\sum_{j=1}^{n_{d}^{N_{r}}}\omega_{k+1}^{j}\sum_{j=1}^{n_{d}^{N_{r}}}\lambda_{k+1}^{j}\gamma_{k+1}^{j*}(x)$
(64)

As shown in (57), the stage costs remain zero for the additional step, because
it is contained in the terminal set. Summing up across the horizon for the
tube-based part of the scheme, we get,

$\displaystyle\sum_{k=N_{r}}^{N_{p}-1}J^{\mathrm{tube}}_{k}(x^{+})\leq\sum_{k=N_{r}+1}^{N_{p}-1}J^{\mathrm{tube*}}_{k}(x).$
(65)

This leads to the condition $V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}^{+})\leq V_{N_{p}}^{H*}(\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})-c_{3}|z|_{\mathbb{Z}_{f}},\,\forall\mathchoice{\mbox{$\displaystyle
x$}}{\mbox{$\textstyle x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}\in\mathtt{X}_{N_{p}}^{H}$. This proves (59).∎

The terminal set $\mathbb{Z}_{f}\oplus\mathsf{S}$ is asymptotically stable for
the proposed scheme as it is shown in the following theorem.

###### Theorem 1

Suppose the assumptions 1-4 are satisfied, then the set
$\mathbb{Z}_{f}\oplus\mathsf{S}$ is robustly asymptotically stable for the
controlled uncertain system given in (1) using the proposed scheme (6) with
the implementation (18) or (23).

Proof. Since the optimal value function is established as a Lyapunov function
in Lemma 5.6, Lemma 5.8, and Lemma 5.9 with respect to the terminal set
$\mathbb{Z}_{f}$, the state $z$ of (3) converges to the terminal set
asymptotically. The state of the system (1) satisfies the property
$x\in\\{z\\}\oplus\mathsf{S}$ and converges robustly asymptotically to the set
$\mathbb{Z}_{f}\oplus\mathsf{S}$. ∎

Finite time reachability of the terminal set and robust asymptotic stability
of the minimal RPI set can be proven for the proposed scheme using a dual mode
control policy as proposed in [26]. The required conditions are formalized in
the following assumption.

###### Assumption 5

There exists a dual mode control policy that is employed as follows:

$\displaystyle\mathchoice{\mbox{$\displaystyle u$}}{\mbox{$\textstyle
u$}}{\mbox{$\scriptstyle u$}}{\mbox{$\scriptscriptstyle
u$}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}})=\begin{cases}\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{f}\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}},&\text{if}\,x\in\mathbb{X}_{max},\\\ \mathchoice{\mbox{$\displaystyle
v$}}{\mbox{$\textstyle v$}}{\mbox{$\scriptstyle v$}}{\mbox{$\scriptscriptstyle
v$}}+\mathchoice{\mbox{$\displaystyle K$}}{\mbox{$\textstyle
K$}}{\mbox{$\scriptstyle K$}}{\mbox{$\scriptscriptstyle
K$}}_{\mathrm{inv}}(\mathchoice{\mbox{$\displaystyle x$}}{\mbox{$\textstyle
x$}}{\mbox{$\scriptstyle x$}}{\mbox{$\scriptscriptstyle
x$}}-\mathchoice{\mbox{$\displaystyle z$}}{\mbox{$\textstyle
z$}}{\mbox{$\scriptstyle z$}}{\mbox{$\scriptscriptstyle
z$}}),&\text{otherwise},\end{cases}$ (66)

where $\mathbb{X}_{max}$ is an RPI set for the asymptotically stabilizing
control law $u=K_{f}x$ for the system (1) that satisfies the conditions
$\mathbb{Z}_{f}\oplus\mathsf{S}\subset\mathbb{X}_{max}$ and
$\mathbb{X}_{max}\subseteq\mathbb{X}$ and $v$ and $z$ are optimal solutions of
the proposed scheme (6) with an asymptotically stabilizing feedback gain
$K_{\mathrm{inv}}$.

###### Theorem 2

Suppose the assumptions 1-5 are satisfied, the minimal RPI set
$\mathsf{S}_{min}$ of the system (1) is robustly asymptotically stable for the
controlled uncertain system defined in (1) employed using the dual mode
control policy (66).

Proof. As $\mathbb{Z}_{f}\oplus\mathsf{S}\subset\mathbb{X}_{max}$ and
$\mathbb{Z}_{f}\oplus\mathsf{S}$ is robustly asymptotically stable from
Theorem 1, the state enters $\mathbb{X}_{max}$ in finitely many time steps.
Since the control policy is switched to $K_{f}x$ when $x\in\mathbb{X}_{{max}}$
and that the control law $K_{f}x$ is asymptotically stabilizing for the system
(1), the state $x$ converges to the minimal RPI set asymptotically. Hence for
the uncertain system defined in (1) controlled using the dual mode control
policy (66), the minimal RPI set $\mathsf{S}_{min}$ is robustly asymptotically
stable.∎

######  Corollary 5.10.

Suppose the assumptions 1-5 are satisfied, the set
$\mathbb{Z}_{f}\oplus\mathsf{S}$ can be reached in finite time steps if