# Flexible-step Model Predictive Control
based on generalized Lyapunov functions

Annika Fürnsinn  Department of Mathematics and Statistics
Queen’s University, Kingston, ON K7L 3N6, Canada<EMAIL_ADDRESS>,
Christian Ebenbauer  Chair of Intelligent Control Systems
RWTH Aachen University, 52062 Aachen, Germany<EMAIL_ADDRESS>aachen.de and  Bahman Gharesifard  Department of Electrical and Computer
Engineering
University of California at Los Angeles, Los Angeles, CA 90095
<EMAIL_ADDRESS>
###### Abstract.

We present a novel model predictive control (MPC) scheme with relaxed
stability criteria, based on the idea of generalized discrete-time control
Lyapunov functions. Most notably, this scheme allows for implementing a
flexible number of control inputs in each iteration, while guaranteeing
recursive feasibility and stability. The advantages of our flexible-step
implementation are demonstrated on nonholonomic systems, where the one-step
standard implementation may suffer from lack of asymptotic convergence.

##  1\. Introduction

Model predictive control (MPC) is a method to approximate the solution of an
infinite-horizon optimal control problem by considering a sequence of finite-
horizon optimal control problems implemented in a receding horizon fashion. In
the standard discrete-time MPC scheme, the finite-horizon optimal control
problem is solved at each time step with the current state as the initial
state and the first element of the derived optimal control sequence is
implemented.

Since stability of MPC schemes does not follow from the associated infinite-
horizon optimal control problem, several approaches have been proposed to
guarantee stability [15]. In the standard MPC scheme, a terminal cost and a
terminal constraint are added to the optimal control problem. By considering
the optimal value function as the Lyapunov function, a strictly decreasing
sequence of Lyapunov function values is obtained, which implies convergence of
the state to zero. In this paper, we replace the _strict descent_ of the
Lyapunov function values with an _average descent_ while preserving stability.
We propose a new MPC scheme which enables the implementation of a flexible
number of elements of the optimal input sequence. Here, with flexible number
we mean that in each iteration the number of implemented elements of the
corresponding optimal input sequence is not constant (e.g. one) but instead
flexible (variable). The flexible-step implementation is enabled by the novel
notion of generalized discrete-time control Lyapunov functions (g-dclf), which
depend on the state _and_ the control. The existence of such a g-dclf for a
control system makes it possible to add a _feasible_ average decrease
constraint on the Lyapunov function values to the finite-horizon optimal
control problem of our MPC scheme. The average descent in turn guarantees that
at least one predicted Lyapunov function value along the trajectory of the
system is less than the Lyapunov function value at the beginning of the
prediction. In the proposed MPC scheme, we implement the elements of the
optimal input sequence until a descent occurs. Consequently, this part of our
scheme gives rise to a flexible-step implementation.

The present work can be related to previous research as follows. In so-called
“finite-step” approaches [19, 12, 10] the standard MPC assumptions are
relaxed. In [10], a stabilizing tube-based MPC for linear parameter-varying
systems is presented. The usual invariant set used in standard MPC is replaced
by finite-step contractive sets, which are easier to compute. In the latter
sets, the state of a control system is allowed to leave the set as long as it
returns after a finite number of time steps. Based on [6], the work in [19]
generalizes control Lyapunov functions by finite-step control Lyapunov
functions. Such functions are allowed to increase along the trajectory of a
system as long as at the end of the prediction horizon (after a finite number
of steps) they decay compared to the beginning of the prediction. In the
finite-step control Lyapunov function-based MPC scheme, the considered finite-
step control Lyapunov function is the objective function and is incorporated
as a constraint. The exact same finite number of steps (greater than one) is
implemented in each iteration of the scheme. In [12], finite-step control
Lyapunov functions are used alongside finite–step contractive sets. More
precisely, the finite-step Lyapunov functions are used in the terminal cost of
the MPC optimization problem. As in [19], the Lyapunov function only depends
on the state.

Our work, however, belongs to the category of so-called “flexible-step”
approaches [2, 23], where a flexible number of elements of the optimal input
sequence is implemented in the MPC scheme. A _variable_ prediction horizon
[17, 16] is employed in contractive MPC [23]. In the optimal control problem
of this setting, the prediction horizon is a decision variable. Hence, solving
the MPC scheme yields the optimal control sequence and the optimal prediction
horizon. In each iteration, the optimal control sequence is then implemented
over the whole optimal prediction horizon. In the discrete-time setting,
optimizing over the prediction horizon results in an undesirable integer
decision variable. In [2], a contraction-based MPC scheme is proposed, which
avoids the integer optimization for the price of solving two optimization
problems in each iteration.

In contrast to contractive MPC, the proposed MPC scheme allows for
guaranteeing the existence of a strictly smaller future Lyapunov function
value while implementing a flexible number of steps without the above-
mentioned computational drawbacks.

One main technical contribution of this paper is the introduction of
generalized discrete-time control Lyapunov functions, which cover classical
Lyapunov functions but also the control-dependent objective function. Notably,
the therewith proposed flexible-step approach includes many known MPC schemes,
such as terminal ingredient-based MPC and contraction-based MPC [15].
Furthermore, we derive theoretical results about recursive feasibility and
stability for our proposed scheme. We demonstrate the functionality of our
method by utilizing it to study the stabilization of nonholonomic systems,
which are typically a bottleneck for standard MPC schemes. Several simulation
studies confirm the anticipated benefits of the flexibility coming from the
g-dclfs.

###  1.1. Organization

The paper is organized as follows. We explain our notation in Section 1.2. In
Section 2, we present the main results of this paper, from which we derive a
novel implementation scheme for MPC. The proofs of the main results can be
found in Section 3. In Section 4, we apply the derived scheme to nonholonomic
systems. We present the numerical results and analyze these in detail.
Finally, we draw our conclusions and discuss some future directions in Section
5.

###  1.2. Notation

We denote the set of non-negative integers by $\mathbb{N}$, the set of reals
by , and the interior of a subset $S\subseteq\mathbb{R}^{n}$ by
$\operatorname{int}S$. The set of real matrices of the size $p\times q$ is
denoted by p,q. We make use of boldface when considering a sequence of finite
vectors, e.g. $\mathbf{u}=[u_{0},\dots,u_{N-1}]\in^{p,N}$, we refer to $j$th
component by $u_{j}$ and to the subsequence going from component $i$ to $j$ by
$\mathbf{u}_{[i:j]}$. Similarly,
$\mathbf{U}_{[0:N-1]}\subseteq\mathbb{R}^{p,N}$ denotes a set of (ordered)
sequences of vectors with components zero to $N-1$. When such a set depends on
the initial state $x$, it is expressed by $\mathbf{U}_{[0:N-1]}(x)$. As usual,
$\mathbf{u}^{*}$ denotes the solution to the optimal control problem solved in
the iteration of an MPC scheme, the symbol $\mathbf{u}^{*-}$ denotes the
optimal control sequence of the _previous_ iteration. For later use, we recall
that a function $V:\mathbb{R}^{n}\times\mathbb{R}^{p,q}\to\mathbb{R}$ is
called positive definite if $V(x,\mathbf{u})=0$ is equivalent to
$(x,\mathbf{u})=(0,\mathbf{0})$ and $V(x,\mathbf{u})>0$ for all
$(x,\mathbf{u})\in\mathbb{R}^{n}\times\mathbb{R}^{p,q}\setminus\\{(0,\mathbf{0})\\}$.
Furthermore, a function
$\alpha:\mathbb{R}^{n}\times\mathbb{R}^{p,q}\to\mathbb{R}$ is called radially
unbounded if $\|(x,\mathbf{u})\|\to\infty$ implies
$\alpha(x,\mathbf{u})\to\infty$, where $\|\cdot\|$ is the Euclidean norm. Note
that $x$ is a vector and $\mathbf{u}$ is a matrix here, so with
$\|(x,\mathbf{u})\|$ we implicitly refer to the norm of
$[x^{T},\operatorname{vec}(\mathbf{u})^{T}]$, where
$\operatorname{vec}(\mathbf{u})$ is the usual vectorization of a matrix into a
column vector.

In the setting of MPC, it is important to distinguish between predictions and
the actual implementations at a given time index $k\in\mathbb{N}$. In
particular, we use $x^{k},u^{k}$ to refer to _predictions_ , whereas we use
$x(k),u(k)$ to refer to the _actual_ states and _implemented_ inputs,
respectively.

##  2\. Main results

Our main objective in this work is to propose a new implementation scheme with
some key advantages that we discuss shortly. In order to introduce this
scheme, we require a few notions related to stability of control systems.
Throughout this paper, we consider nonlinear discrete-time control systems of
the form

$\displaystyle x^{k+1}$ $\displaystyle=f(x^{k},u^{k}),$ (2.1)

where $k\in\mathbb{N}$ denotes the time index, $x^{k}\in
X\subseteq\mathbb{R}^{n}$ is the state with the initial state $x^{0}\in X$ and
$u^{k}\in U\subseteq\mathbb{R}^{p}$ is an input. The state and input
constraints satisfy $0\in\operatorname{int}X$, $0\in\operatorname{int}U$ and
$f:X\times U\to\mathbb{R}^{n}$ is continuous with $f(0,0)=0$. For later use,
we recall the asymptotic stability of a time-varying system [9]. Consider

$\displaystyle x^{k+1}=F(k,x^{k}),\quad k\geq k_{0},$ (2.2)

where $F:\mathbb{N}\times X\to\mathbb{R}^{n}$ and $F(k,0)=0$ for all $k\geq
k_{0}$. The origin is an asymptotically stable equilibrium of (2.2) (with
region of attraction $X$) if

  1. (1)

for all $\varepsilon>0$ and any $k_{0}\in\mathbb{N}$, there exists
$\delta=\delta(\varepsilon,k_{0})>0$ such that $x^{k_{0}}\in X$ with
$0<\|x^{k_{0}}\|<\delta$ implies $\|x^{k}\|<\varepsilon$ for all $k\geq
k_{0}$;

  2. (2)

for any $k_{0}\in\mathbb{N}$ and $x^{k_{0}}\in X$, it holds
$\lim_{k\to\infty}x^{k}=~{}0$.

###  2.1. Generalized control Lyapunov function

We now introduce g-dclfs that are core to our proposed MPC scheme. We present
our stability results, which are the building blocks of our proposed scheme,
postponing the proofs to Section 3.

The classical condition for a Lyapunov function $V$ is $V(x^{k+1})<V(x^{k})$.
It requires that $V$ strictly decreases along the trajectories of a control
system and results in asymptotic stability of the origin. _Higher-order_
Lyapunov functions (continuous time) were originally introduced in [5] and
therewith replaced the classical Lyapunov condition. In [1] the classical
condition was relaxed by introducing so-called _non-monotonic_ Lyapunov
functions, which are characterized by the following condition in discrete-time

$\displaystyle\tau(V(x^{k+2})-V(x^{k}))+(V(x^{k+1})-V(x^{k}))<0,$ (2.3)

for $\tau\geq 0$. Note that for $\tau=1$, (2.3) imposes that the average of
the next two future values of the Lyapunov function should be less than the
current value of the Lyapunov function. We now generalize these ideas.

######  Definition 2.1 (Set of Feasible Controls).

For $x\in X$, we define a set of feasible controls as

$\displaystyle\mathbf{U}_{[0:N-1]}(x):=\\{\mathbf{u}_{[0:N-1]}\in\mathbb{R}^{p,N}:\text{
with $x^{0}=x$},u_{j}\in U,x^{j+1}=f(x^{j},u_{j})\in X,$ (2.4)
$\displaystyle\hskip 142.26378ptj=0,\dots,q-1\\}.$

An infinite sequence of control inputs is called feasible when equation (2.4)
is fulfilled for all times $j\in\mathbb{N}$.

######  Definition 2.2 (g-dclf).

Consider the control system (2.1). Let $1\leq m\in\mathbb{N}$ and
$q\in\mathbb{N}$. We call
$V:\mathbb{R}^{n}\times\mathbb{R}^{p,q}\to\mathbb{R}$ a generalized discrete-
time control Lyapunov function of order $m$ (g-dclf) for system (2.1) if $V$
is continuous, positive definite and additionally:

When $q=0$:

  1. i)

there exists a continuous, radially unbounded and positive definite function
${\alpha:\mathbb{R}^{n}\to\mathbb{R}}$ such that for any $x^{0}\in$
$\mathbb{R}^{n}$ we have

$\displaystyle V(x^{0})-\alpha(x^{0})\geq 0;$

  2. ii)

for any $x^{0}\in\mathbb{R}^{n}$ there exists
$\bm{\nu}_{[0:m-1]}\in\mathbf{U}_{[0:m-1]}(x^{0})$, which steers $x^{0}$ to
some $x^{m}$, such that

$\displaystyle\frac{\sigma_{m}V(x^{m})+\dots+\sigma_{1}V(x^{1})}{m}-V(x^{0})\leq-\alpha(x^{0}),$
(2.5)

where $\sigma_{m},\ldots,\sigma_{1}\geq 0$ and

$\frac{\sigma_{m}+\sigma_{m-1}+\ldots+\sigma_{1}}{m}-1\geq 0.$ (2.6)

When $q\neq 0$:

  1. i’)

there exists a continuous, radially unbounded and positive definite function
${\alpha:\mathbb{R}^{n}\times\mathbb{R}^{p,q}\to\mathbb{R}}$ such that for any
$(x^{0},\mathbf{u}_{[0:q-1]})\in$
${\mathbb{R}^{n}\times\mathbf{U}_{[0:q-1]}(x^{0})}$ we have

$\displaystyle
V(x^{0},\mathbf{u}_{[0:q-1]})-\alpha(x^{0},\mathbf{u}_{[0:q-1]})\geq 0;$ (2.7)

  2. ii’)

for any
$(x^{0},\mathbf{u}_{[0:q-1]})\in\mathbb{R}^{n}\times\mathbf{U}_{[0:q-1]}(x^{0})$
there exists $\bm{\nu}_{[0:q+m-1]}\in\mathbb{R}^{p,q+m}$ with
$\bm{\nu}_{[l:q+l-1]}\in\mathbf{U}_{[0:q-1]}(x^{l})$ for every
$l\in\\{0,1,\dots,m\\}$, which steers $x^{0}$ to some $x^{m}$, such that

$\displaystyle\frac{\sigma_{m}V\left(x^{m},\bm{\nu}_{[m:q+m-1]}\right)+\dots+\sigma_{1}V\left(x^{1},\bm{\nu}_{[1:q]}\right)}{m}-V(x^{0},\mathbf{u}_{[0:q-1]})\leq-\alpha(x^{0},\mathbf{u}_{[0:q-1]}),$
(2.8)

where $\sigma_{m},\ldots,\sigma_{1}\geq 0$ satisfy (2.6).

In contrast to the standard case, the interpretation of Definition 2.2 is that
the sequence of Lyapunov function values decreases not necessarily at every
step, but on average every $m$ steps (compare with condition (2.8)). Condition
(2.8) will provide a mean for relaxing the assumptions on the terminal
conditions that are frequently imposed in standard MPC schemes.

Definition 2.2 allows for a g-dclf $V$ to depend on a control sequence. The
variable $q$ determines how many components of the control sequence are
considered. If $q=0$, the Lyapunov function only explicitly depends on the
state. If $q=1$, the running cost of the optimal control problem could be
taken as the Lyapunov function. If $q=N_{p}$, then the objective function of
the optimal control problem could be taken as the Lyapunov function.

The following results demonstrate how a Lyapunov function in the sense of
Definition 2.2 leads to stability.

######  Theorem 2.3.

If there exists a g-dclf of order $m$ for the control system (2.1), then for
any $k_{0}\in\mathbb{N}$ and any state $x^{k_{0}}\in X$, there exists a
feasible control sequence such that $\lim_{k\to\infty}x^{k}=0$.

In the context of _control_ Lyapunov functions, the so-called small control
property [21] is often used. A generalization suitable for our framework is
given below.

######  Assumption 2.4 (Small Control Property).

Consider system (2.1) and let
$V:\mathbb{R}^{n}\times\mathbb{R}^{p,q}\to\mathbb{R}$ be a g-dclf of order $m$
with $q\neq 0$. We say that the small control property holds if for all
$\varepsilon>0$, there exists $\delta>0$ such that the following conditions
hold

  1. i)

for all $0<\|x^{0}\|<\delta$, there exist
$\mathbf{u}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x^{0})$ and
$\bm{\nu}_{[0:q+m-1]}$ with
$\bm{\nu}_{[l:q+l-1]}\in\mathbf{U}_{[0:q-1]}(x^{l})$ for every
$l\in\\{0,1,\dots,m\\}$;

  2. ii)

the controls $\mathbf{u}_{[0:q-1]}$ and $\bm{\nu}_{[0:q+m-1]}$ satisfy
$\max\\{\|\mathbf{u}_{[0:q-1]}\|,\|\bm{\nu}_{[0:q+m-1]}\|\\}<\varepsilon$;

  3. iii)

the inequalities (2.7) and (2.8) hold with $\mathbf{u}_{[0:q-1]}$ and
$\bm{\nu}_{[0:q+m-1]}$.

######  Theorem 2.5.

Let $V:\mathbb{R}^{n}\times\mathbb{R}^{p,q}\to\mathbb{R}$ be a g-dclf of order
$m$ for the control system (2.1) with positive weights $\sigma_{i}$ and
suppose that for $q\neq 0$ Assumption 2.4 holds. Then there exists a control
strategy which renders the origin asymptotically stable.

The proof of both results can be found in Section 3. It is worth connecting
the above results to the existing literature. In particular, a corollary of
Theorem 2.3 is obtained regarding so-called finite-step control Lyapunov
functions, recently introduced in [19]. By definition, finite-step control
Lyapunov functions decrease after finitely many, e.g. $m$, steps. This means
they satisfy (2.5) with $\sigma_{m-1},\dots,\sigma_{1}=0$.

######  Corollary 2.6.

If there exists a finite-step control Lyapunov function for the control system
(2.1), then for any initial state $x^{0}\in X$, there exists a feasible
control sequence such that $\lim_{k\to\infty}x^{k}=0$.

The proof of this corollary follows immediately, since the definition of
g-dclfs includes finite-step control Lyapunov functions. With these results at
hand, we are ready to introduce our novel MPC scheme.

###  2.2. Flexible-step MPC scheme

The proposed MPC scheme is based on the following optimal control problem; the
underlying idea is to add condition (2.8) as a constraint.

$\displaystyle\begin{aligned}
&\min\sum_{j=0}^{N_{p}-1}f_{0}(x^{j},u^{j})+\phi(x^{N_{p}})\\\ \ &\text{s.t.
}x^{j+1}=f(x^{j},u^{j}),\ x^{0}=x,\ \ u^{j}\in U,\,x^{j}\in X,\,x^{N_{p}}\in
X^{N_{p}},\\\ &\hphantom{\text{s.t.
}}[u^{l},\dots,u^{l+q-1}]\in\mathbf{U}_{[0:q-1]}(x^{l})\text{ for
}l=0,1,\dots,m\\\ &\hphantom{\text{s.t.
}}\frac{1}{m}\Big{(}\sigma_{m}V(x^{m},[u^{m},\dots,u^{m-1+q}])+\sigma_{m-1}V(x^{m-1},[u^{m-1},\dots,u^{m-2+q}])+\ldots+\sigma_{1}V(x^{1},[u^{1},\dots,u^{q}])\Big{)}\\\
&\hphantom{\text{s.t.
}\frac{1}{m}\Big{(}}-V(x^{0},\mathbf{u}^{*-}_{[0:q-1]})\leq-\alpha(x^{0},\mathbf{u}^{*-}_{[0:q-1]})\end{aligned}$
(2.9)

######  Problem 2.7.

Solve the finite-horizon optimal control problem (2.9), where $\mathbb{N}\ni
q\leq N_{p}$ and $\sigma_{m},\ldots,\sigma_{1}\geq 0$ satisfy (2.6) for $1\leq
m\leq N_{p}$, $m\in\mathbb{N}$. Here $x=x(k)$ is the current state and
$\mathbf{u}^{*-}_{[0:q-1]}$ is the previous control strategy. The optimization
is done over the $q+m$ control inputs $[u^{0},u^{1},\dots,u^{q+m-1}]$. The
function $f_{0}:\mathbb{R}^{n}\times\mathbb{R}^{p}\to\mathbb{R}$ is positive
definite, $\phi:\mathbb{R}^{n}\to\mathbb{R}$ is positive semi-definite,
$0\in\operatorname{int}U$,
$U\subseteq\mathbb{R}^{p},0\in\operatorname{int}X^{N_{p}},X^{N_{p}}\subseteq
X\subseteq\mathbb{R}^{n}$ and
$V:\mathbb{R}^{n}\times\mathbb{R}^{p,q}\to\mathbb{R}$ is a g-dclf of order
$m$.

Similar to prior literature and for the sake of simplicity, we will assume
from now on that a bounded solution to Problem 2.7 exists. Problem 2.7 is
written for the case $q\neq 0$; like in Definition 2.2, this can be adjusted
for the case $q=0$. From now on, we leave it to the reader to make the
necessary adjustments for the case $q=0$.

Since the fraction in (2.8) represents a weighted average, we will refer to
this constraint as the _average decrease constraint_ (adc). The flexible-step
MPC scheme is given in Algorithm 1.

Algorithm 1 Flexible-step MPC scheme

1: set $k=k_{0}$, initialize the initial state $x(k_{0})$ and choose an
arbitrary $\mathbf{u}^{*-}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x(k_{0}))$

2: measure the current state $x(k)$ of (2.1)

3: solve Problem 2.7 with $x=x(k)$ and obtain the optimal input
${\mathbf{u}^{*}_{[0:N-1]}}$, where $N=\max\\{q+m,N_{p}\\}$

4: choose an index $1\leq\ell_{\textup{decr}}\leq m$ for which
$V(x^{*\ell_{\textup{decr}}},\mathbf{u}^{*}_{[\ell_{\textup{decr}}:q+\ell_{\textup{decr}}-1]})-V(x,\mathbf{u}^{*-}_{[0:q-1]})\leq-\alpha(x,\mathbf{u}^{*-}_{[0:q-1]})$

5: implement
$\mathbf{u}^{*}_{[0:\ell_{\textup{decr}}-1]}=:[c^{k}_{mpc},\dots,c^{k+\ell_{decr}-1}_{mpc}]$
and redefine
$\mathbf{u}^{*-}_{[0:q-1]}:=\mathbf{u}^{*}_{[\ell_{\textup{decr}}:q+\ell_{\textup{decr}}-1]}$

6: increase $k:=k+\ell_{\textup{decr}}$ and go to 2

We find it useful to explain the idea behind our implementation with an
example, illustrated in Figure 1.

$k$$V$$V(x^{0})$$V(x^{1})$$V(x^{2})$$V(x^{3})$$V(x^{4})$ A Optimization at
${k=0}$ platzhalter

$k$$V$$V(x^{0})$$V(x^{1})$$V(x^{2})$$V(x^{3})$$V(x^{4})$ B Optimization at
${k=2}$ platzhalter

$k$$V$$V(x^{0})$$V(x^{1})$$V(x^{2})$$V(x^{3})$$V(x^{4})$ C Optimization at
${k=3}$ platzhalter

$k$$V$$V(x(0))$$V(x(1))$$V(x(2))$$V(x(3))$$V(x(4))$$V(x(5))$$V(x(6))$$V(x(7))$
D Lyapunov function values along actual states

Figure 1. Illustration of proposed MPC scheme: Consider Problem 2.7 with $m=4$
and $q=0$. The initial state is
${\color[rgb]{0,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,.5}x^{0}}=x(0)$,
whose Lyapunov function value is depicted in (a) and highlighted in green.
After solving the finite-horizon optimal control problem, we obtain four
predicted states and their corresponding Lyapunov function values
($V(x^{0}),V(x^{1}),V(x^{2}),V(x^{3}),V(x^{4})$). Since there are multiple
time indices for which the Lyapunov function decreases, we choose
$\ell_{\textup{decr}}$ here as the index where the greatest descent occurs. We
implement $\ell_{\textup{decr}}=2$ components of the control sequence and,
consequently, declare $x^{2}$ as the new initial state for the finite-horizon
optimal control problem at time $k=2$. This problem is solved in (B) and we
obtain again four states and their corresponding Lyapunov function values
($V(x^{0}),V(x^{1}),V(x^{2}),V(x^{3}),V(x^{4})$). We repeat the scheme and
after solving Problem 2.7 three times, we obtain the trajectory of the closed-
loop states and their Lyapunov function values shown in (D).

Consider Problem 2.7 with $m=4$ and a g-dclf $V$ with $q=0$. Let $x^{0}=x(0)$
be the initial state. After solving Problem 2.7, we obtain a trajectory of
states ($x^{0},x^{1},x^{2},x^{3},x^{4}$). The corresponding Lyapunov function
values are shown in Figure 1A in dark blue. By definition of adc, we know that
at least one of the four future Lyapunov function values will be strictly less
than $V(x^{0})$ (see Proposition 3.1). In order to ultimately reach
convergence of the state to zero, we need to implement the optimal control
sequence until a descent of the Lyapunov function value occurs. In this
example, we choose to implement until the greatest descent occurs. In Figure
1A, this is achieved at state $x^{2}$, thus, we implement the optimal control
sequence for two time steps and declare the actual states
$x(1)=x^{1},x(2)=x^{2}$. Now the new initial state for the finite-horizon
optimal control problem becomes $x(2)$, highlighted in light green. We repeat
this process, as demonstrated in Figure 1B. The greatest descent is achieved
after one time step. Thus, we only implement the optimal control sequence for
one step, $x(3)=x^{1}$. We define the new initial state and proceed as before.
This time, the greatest descent is achieved after four time steps, see Figure
1C. The yellow trajectory in Figure 1D shows the Lyapunov function values
along the actual states of our example after three iterations of Algorithm 1.

At this point, we would like to clarify steps four and five of Algorithm 1. By
Proposition 3.1, adc guarantees a descent of the Lyapunov function value, step
four captures where it occurs through the index $\ell_{\textup{decr}}$ and in
step five the control sequence is implemented until the descent. The term
flexible-step MPC is chosen to emphasize that steps four and five lead to
implementation of possibly different number of steps in each iteration.

######  Remark 2.8.

Algorithm 1 generates a feedback law
$c_{mpc}^{k}(x(\pi(k)),\mathbf{u}^{*-}(\pi(k)))$ that is time and state
dependent, common in continuous-time sampled-data MPC [8, 7]. Here, $\pi(k)$
is the time step of the most recent state measurement, i.e., the beginning of
each optimization instance of Problem 2.7 (step three in Algorithm 1) and
$\mathbf{u}^{*-}(\pi(k))$ is part of the control strategy of the previous
iteration (assigned in step five of the algorithm). The novel implementation
in Algorithm 1 naturally leads to a time-varying feedback law, and hence
system, because the actual states generated by the flexible-step MPC scheme
evolve according to the dynamics

$\displaystyle\begin{aligned}
x(k+1)&=f\big{(}x(k),c_{mpc}^{k}(x(\pi(k)),\mathbf{u}^{*-}(\pi(k)))\big{)},\,k\geq
k_{0}.\end{aligned}$ (2.10)

Alternatively, we can extend system (2.10) by an augmented variable
$y(k)\in\mathbb{R}^{n}\times\mathbb{R}^{p,q}$, which captures the state and
$\mathbf{u}^{*-}$ at the optimization instances, and allows us to write the
closed-loop dynamics as follows

$\displaystyle x(k+1)=f(x(k),c^{k}_{mpc}\big{(}y(k))\big{)}$ $\displaystyle
y(k+1)=\left\\{\begin{array}[]{ll}\Big{(}f\big{(}x(k),c^{k}_{mpc}(y(k))\big{)},\mathbf{u}^{*-}(k+1)\Big{)},&\text{if
optimization instance occurs at }k+1\\\
y(k),&\text{otherwise}\end{array}\right.$ (2.13)

with $y(k_{0})=(x(k_{0}),\mathbf{u}^{*-}(k_{0}))$. In the previous example,
illustrated in Figure 1, the optimization instances occur at $k=0,2,3,7$,
thus,

$\displaystyle[y(0),y(1),\dots,y(7)]=$
$\displaystyle[(x(0),\mathbf{u}^{*-}(0)),(x(0),\mathbf{u}^{*-}(0)),(x(2),\mathbf{u}^{*-}(2)),(x(3),\mathbf{u}^{*-}(3)),(x(3),\mathbf{u}^{*-}(3)),$
$\displaystyle\
(x(3),\mathbf{u}^{*-}(3)),(x(3),\mathbf{u}^{*-}(3)),(x(7),\mathbf{u}^{*-}(7))].$

The first component of $y(k)$ is determined by $x(k)$ through (2.8) and the
second component captures $\mathbf{u}^{*-}$. Since both components will
converge to zero if $x(k)$ converges to zero (the zero control is a feasible
control with minimal cost for Problem 2.7) and since the state extension leads
to a cumbersome formulation, we consider only the state variable $x(k)$ in the
following. $\bullet$

######  Remark 2.9.

The way we assign $\mathbf{u}^{*-}(\pi(k))$ in Algorithm 1 allows us to
guarantee a chain of inequalities needed for the stability proof (see
inequalities (A.1) in Appendix A). It is possible to change this assignment
while still guaranteeing the chain of inequalities. In fact, if we change step
five in Algorithm 1 to: implement
$\mathbf{u}^{*}_{[0:\ell_{\textup{decr}}-1]}=:[c^{k}_{mpc},\dots,c^{k+\ell_{decr}-1}_{mpc}]$,
find
$\bar{\mathbf{u}}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x^{*\ell_{\textup{decr}}})$
such that

$\displaystyle
V(x^{*\ell_{\textup{decr}}},\bar{\mathbf{u}}_{[0:q-1]})-V(x,\mathbf{u}^{*-}_{[0:q-1]})\leq-\alpha(x,\mathbf{u}^{*-}_{[0:q-1]})$

and redefine $\mathbf{u}^{*-}_{[0:q-1]}:=\bar{\mathbf{u}}_{[0:q-1]}$, then the
argument of the stability proof still applies. $\bullet$

We next state a sequence of results related to Algorithm 1. We start with the
following assumption. It is a generalization of the usual assumption made in
standard MPC, i.e. the existence of a feasible controller which renders the
set $X^{N_{p}}$ invariant and achieves a descent [15].

######  Assumption 2.10.

Consider the sets $U\subseteq\mathbb{R}^{p},X^{N_{p}}\subseteq
X\subseteq\mathbb{R}^{n}$ with $0\in\operatorname{int}U$ and
$0\in\operatorname{int}X^{N_{p}}$. Let
$V:\mathbb{R}^{n}\times\mathbb{R}^{p,N_{p}}\to\mathbb{R}$ be a g-dclf of order
$m$ for system (2.1). Assume that for any $(x^{0},\mathbf{u}_{[0:N_{p}-1]})\in
X\times\mathbf{U}_{[0:N_{p}-1]}(x^{0})$ there exists a feedback
$\mathbf{c}:X^{N_{p}}\to\mathbb{R}^{p,m},\tilde{x}\mapsto\mathbf{c}(\tilde{x})$
such that for all $\tilde{x}\in X^{N_{p}}$

  1. (1)

$c_{0}(\tilde{x}),c_{1}(\tilde{x}),\dots,c_{m-1}(\tilde{x})\in U$;

  2. (2)

with $x^{0}=\tilde{x}$, we have ${x^{j+1}=f(x^{j},c_{j}(\tilde{x}))}$ $\in
X^{N_{p}}$ for all $j=0,\dots,m-1$;

  3. (3)

$[\mathbf{u}_{[0:N_{p}-1]},\mathbf{c}(\tilde{x})]$ satisfies adc (2.8), i.e.
the control sequence $[\mathbf{u}_{[0:N_{p}-1]},\mathbf{c}(\tilde{x})]$ steers
$x^{0}$ to some $x^{m}$ such that

$\displaystyle\frac{1}{m}\left(\sigma_{m}V\left(x^{m},[\mathbf{u}_{[m:N_{p}-1]},\mathbf{c}(\tilde{x})]\right)+\dots+\sigma_{1}V\left(x^{1},[\mathbf{u}_{[1:N_{p}-1]},c_{0}(\tilde{x})]\right)\right)-V(x^{0},\mathbf{u}_{[0:N_{p}-1]})$
$\displaystyle\hskip 56.9055pt\leq-\alpha(x^{0},\mathbf{u}_{[0:N_{p}-1]}).$

The following theorem guarantees recursive feasibility as defined in e.g.
[14].

######  Theorem 2.11.

Let $V:\mathbb{R}^{n}\times\mathbb{R}^{p,N_{p}}\to\mathbb{R}$ be a g-dclf of
order $m$ for system (2.1). Suppose that Assumption 2.10 is satisfied and that
Problem 2.7 with $x=x(k_{0})$ is feasible. Then the MPC scheme given in
Algorithm 1 is recursively feasible.

###### Proof.

To prove recursive feasibility, we make use of the terminal set $X^{N_{p}}$.
As a first step, we add the terminal constraint of Problem 2.7 to the sets
$\mathbf{U}_{[0:N_{p}-1]}(x^{l})$ with $x^{l}\in X$ for $l=0,1,\dots,m$

$\displaystyle\mathbf{U}_{[0:N_{p}-1]}(x^{l})=\\{\mathbf{u}_{[0:N_{p}-1]}:\text{
with initial state }x^{l},u_{j}\in U,x^{j+1}=f(x^{j},u_{j})\in X,$
$\displaystyle\hskip 128.0374ptj=0,\dots,N_{p}-1,x^{N_{p}}\in X^{N_{p}}\\}.$

Consider now Algorithm 1 starting at some non-negative integer $k$, and
suppose that Problem 2.7 was feasible in the previous iteration. We show that
Problem 2.7 stays feasible after executing Algorithm 1. To that end, suppose
we arrived at the state $x(k)\in X$ and that the previous control strategy is
given by $\mathbf{u}^{*-}_{[0:N_{p}-1]}$. Thus, we define the initial state of
Problem 2.7 as $x^{0}=x(k)$. Since
$\mathbf{u}^{*-}_{[0:N_{p}-1]}\in\mathbf{U}_{[0:N_{p}-1]}(x(k))$, the states
steered by $\mathbf{u}^{*-}_{[0:N_{p}-1]}$ satisfy

$x^{1},\dots,x^{N_{p}-1}\in X,\quad x^{N_{p}}\in X^{N_{p}}.$

Additionally, all components of $\mathbf{u}^{*-}_{[0:N_{p}-1]}$ are elements
of $U$. By considering $\tilde{x}=x^{N_{p}}\in X^{N_{p}}$ in Assumption 2.10,
the control sequence $[\mathbf{u}^{*-}_{[0:N_{p}-1]},\mathbf{c}(x^{N_{p}})]$
and the corresponding states satisfy adc. Moreover, the controller renders
$X^{N_{p}}$ invariant. Therefore, we have $x^{N_{p}+1},\dots,x^{N_{p}+m}\in
X^{N_{p}}\subseteq X$. Hence, the choice of
$[\mathbf{u}^{*-}_{[0:N_{p}-1]},\mathbf{c}(x^{N_{p}})]$ yields a feasible
controller. ∎

######  Theorem 2.12.

Assume that Problem 2.7 is initially feasible with $x=x(k_{0})$,
$k_{0}\in\mathbb{N}$. Then under Algorithm 1, we have that $x(k)$ converges to
zero as $k$ goes to infinity.

######  Theorem 2.13.

Assume that Problem 2.7 is initially feasible with $x=x(k_{0})$,
$k_{0}\in\mathbb{N}$. Then under Algorithm 1, we have that $x(k)$ converges to
zero as $k$ goes to infinity. Moreover, if all the weights $\sigma_{i}$ in adc
are positive and for $q\neq 0$ Algorithm 1 generates a control sequence which
satisfies the conditions in Assumption 2.4, then the origin is rendered
asymptotically stable by Algorithm 1.

Assumption 2.4 is admittedly difficult to verify, but the convergence to zero
is achieved independently of it. Without the assumption, Algorithm 1 yields
results similar to sampled-data MPC [8, 7].

The proofs of Theorem 2.12 and 2.13 are a consequence of Theorem 2.3 and 2.5
and are presented in Appendix A for the sake of completeness. Now that we have
established the properties of the flexible-step MPC scheme, some remarks are
in order.

######  Remark 2.14.

To recover the standard MPC scheme from our framework, we consider the case of
$q=N_{p},m=1$ and $\sigma_{1}=1$. An appropriate terminal cost
$\phi(x^{N_{p}})$, i.e. an (ordinary) control Lyapunov function on
$X^{N_{p}}$, ultimately makes the objective function a suitable choice for the
g-dclf $V$. Since $m=1$, adc reads

$\displaystyle\begin{aligned}
&V(x^{1},[u^{1},\dots,u^{N_{p}}])-V(x^{0},\mathbf{u}^{*-}_{[0:N_{p}-1]})\leq-\alpha(x^{0},\mathbf{u}^{*-}_{[0:N_{p}-1]}),\end{aligned}$
(2.14)

where $\mathbf{u}^{*-}_{[0:N_{p}-1]}$ is the previous control strategy.
Theorem 2.11 guarantees that there exists a feasible $u^{N_{p}}$, such that
the resulting controller $[\mathbf{u}^{*-}_{[0:N_{p}-1]},u^{N_{p}}]$ will
satisfy adc. This implies that with the standard MPC assumption, which was
generalized by Assumption 2.10, constraint (2.14) is always satisfied, meaning
that it does not further restrict the feasible controls. Here, the constraint
adc demands a strict descent of the objective function $V$ after _one_ time
step; this corresponds exactly to the standard MPC setting. $\bullet$

######  Remark 2.15.

In the standard MPC setting, as discussed in Remark 2.14, the Lyapunov
function is chosen to be the objective function. In Problem 2.7 the Lyapunov
function can generally be a different function. It has already been shown in
the past [20, 3, 22] that a different Lyapunov function than the objective
function can be used to guarantee stability. However, the consideration of
g-dclfs is novel, as they do not only depend on the state but also on the
control input. Moreover, note that if $m=N_{p}$ and $q$ is greater than zero,
the last function value that is considered in adc in Problem 2.7 is
$V(x^{N_{p}},[u^{N_{p}},\dots,u^{N_{p}+q-1}])$. In other words, we will
consider control inputs which go beyond the prediction horizon and help us
decrease $V$ on average. This occurs in general if $m+q>N_{p}$. $\bullet$

##  3\. Stability proofs

In this section, we provide the proofs of the stability results of Section
2.1. To obtain a better intuition about Algorithm 1, the reader can skip this
section in the first read and instead visit Section 4 for case studies.

To prove the first result, we need the following proposition.

######  Proposition 3.1.

If there exists a g-dclf of order $m$ for the control system (2.1), then for
any $(x^{0},\mathbf{u}_{[0:q-1]})\in$
${\mathbb{R}^{n}\times\mathbf{U}_{[0:q-1]}(x^{0}})$ there exists
$\bm{\nu}_{[0:q+m-1]}$ such that

$\displaystyle
V(x^{l},\bm{\nu}_{[l:q+l-1]})-V(x^{0},\mathbf{u}_{[0:q-1]})\leq-\alpha(x^{0},\mathbf{u}_{[0:q-1]})$

holds for some $l\in\\{1,\dots,m\\}$ with
$\bm{\nu}_{[l:q+l-1]}\in\mathbf{U}_{[0:q-1]}(x^{l})$.

###### Proof.

To ease notation, we present this proof for the case $m=2$; the general case
follows similarly. Let $x^{0}\in\mathbb{R}^{n}$ be some arbitrary state and
let $\mathbf{u}_{[0:q-1]}$ be an arbitrary $q$ long control sequence belonging
to the set $\mathbf{U}_{[0:q-1]}(x^{0})$.We claim that condition (2.8) and
(2.6) imply that there exists a control sequence $\bm{\nu}_{[0:q+1]}$, which
steers $x^{0}$ to some $x^{2}$, such that either

$\displaystyle
V(x^{1},\bm{\nu}_{[1:q]})-V(x^{0},\mathbf{u}_{[0:q-1]})\leq-\alpha(x^{0},\mathbf{u}_{[0:q-1]})$

or

$\displaystyle
V(x^{2},\bm{\nu}_{[2:q+1]})-V(x^{0},\mathbf{u}_{[0:q-1]})\leq-\alpha(x^{0},\mathbf{u}_{[0:q-1]})$

holds, meaning that either $V(x^{1},\bm{\nu}_{[1:q]})$ or
$V(x^{2},\bm{\nu}_{[2:q+1]})$ is strictly less than
$V(x^{0},\mathbf{u}_{[0:q-1]})$, as $\alpha$ is positive definite. Suppose
otherwise. Then

$\displaystyle\frac{\sigma_{2}V(x^{2},\bm{\nu}_{[2:q+1]})+\sigma_{1}V(x^{1},\bm{\nu}_{[1:q]})}{2}-V(x^{0},\mathbf{u}_{[0:q-1]})+\alpha(x^{0},\mathbf{u}_{[0:q-1]})$
$\displaystyle\hskip
10.0pt>\frac{\sigma_{2}(V(x^{0},\mathbf{u}_{[0:q-1]})-\alpha(x^{0},\mathbf{u}_{[0:q-1]}))}{2}+\frac{\sigma_{1}(V(x^{0},\mathbf{u}_{[0:q-1]})-\alpha(x^{0},\mathbf{u}_{[0:q-1]}))}{2}$
$\displaystyle\hskip
21.0pt-V(x^{0},\mathbf{u}_{[0:q-1]})+\alpha(x^{0},\mathbf{u}_{[0:q-1]})$
$\displaystyle\hskip
10.0pt=\left(\frac{\sigma_{2}+\sigma_{1}}{2}-1\right)(V(x^{0},\mathbf{u}_{[0:q-1]})-\alpha(x^{0},\mathbf{u}_{[0:q-1]}))$
$\displaystyle\hskip 10.0pt\geq\hskip 2.84544pt0$

for all control sequences $\bm{\nu}_{[0:q+1]}$, where the last inequality
follows by the virtue of (2.7) and (2.6). The derived inequality contradicts
(2.8), finishing the proof. ∎

Using Proposition 3.1, we now prove Theorem 2.3; the proof is a modification
of a standard Lyapunov argument, see for instance [11].

###### Proof of Theorem 2.3.

Fix $k_{0}\in\mathbb{N}$ and $x^{k_{0}}\in X$. If the state $x^{k_{0}}$ is
zero, there is nothing to show. So we may assume $x^{k_{0}}\neq 0$. Suppose,
by contradiction, that there does not exist a feasible control sequence which
steers $x^{k}$ to zero as $k$ goes to infinity. Note that this implies that
$x^{k}$ is non-zero for all $k\geq k_{0}$. Our goal is to define a subsequence

$\displaystyle\\{(x^{k_{n}},\mathbf{u}^{k_{n}}_{[0:q-1]})\\}_{n=0}^{\infty}$
(3.1)

with the help of Proposition 3.1, so that the Lyapunov function values
evaluated at these states and controls strictly decrease. To this end, let
$\mathbf{u}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x^{k_{0}})$ be a fixed, but
arbitrary, control sequence. By Proposition 3.1, there exists
$\bm{\nu}^{k_{0}}_{[0:q+m-1]}$, which steers $x^{k_{0}}$ to $x^{k_{0}+m}$
along (2.1), such that for some $l\in\\{1,\dots,m\\}$

$\displaystyle
V(x^{k_{0}+l},\bm{\nu}^{k_{0}}_{[l:q+l-1]})<V(x^{k_{0}},\mathbf{u}_{[0:q-1]}),$
(3.2)

where $\bm{\nu}^{k_{0}}_{[l:q+l-1]}\in\mathbf{U}_{[0:q-1]}(x^{k_{0}+l})$. As a
result, we can define the first two members of our subsequence:

$\displaystyle\bm{\omega}^{k_{0}}$
$\displaystyle:=(x^{k_{0}},\mathbf{u}_{[0:q-1]})$
$\displaystyle\bm{\omega}^{k_{1}}$
$\displaystyle:=(x^{k_{0}+l^{k_{0}}},\bm{\nu}^{k_{0}}_{[l^{k_{0}}:q+l^{k_{0}}-1]}),$
where $\displaystyle l^{k_{0}}$
$\displaystyle=\operatorname*{arg\,min}_{l=1,\dots,m}V(x^{k_{0}+l},\bm{\nu}^{k_{0}}_{[l:q+l-1]})-V(\bm{\omega}^{k_{0}}).$

We define $\bm{\omega}^{k_{1}}$ in this fashion because there might be
multiple pairs of states and controls that achieve a strict descent; in this
proof we choose the pair with the greatest descent as $\bm{\omega}^{k_{1}}$.
Other choices are possible, as long as equation (3.2) is satisfied. To define
the rest of the subsequence, we proceed as follows. Suppose
$\bm{\omega}^{k_{n}}$ has been defined. By Proposition 3.1, there exists again
$\bm{\nu}^{k_{n}}_{[0:q+m-1]}$ such that for some $l\in\\{1,\dots,m\\}$ the
Lyapunov function value is strictly below $V(\bm{\omega}^{k_{n}})$ and
$\bm{\nu}^{k_{n}}_{[l:q+l-1]}\in\mathbf{U}_{[0:q-1]}(x^{k_{n}+l})$. We can
define $\bm{\omega}^{k_{n+1}}$ accordingly

$\displaystyle\bm{\omega}^{k_{n+1}}$
$\displaystyle:=(x^{k_{n}+l^{k_{n}}},\bm{\nu}^{k_{n}}_{[l^{k_{n}}:q+l^{k_{n}}-1]}),$
where $\displaystyle l^{k_{n}}$
$\displaystyle=\operatorname*{arg\,min}_{l=1,\dots,m}V(x^{k_{n}+l},\bm{\nu}^{k_{n}}_{[l:q+l-1]})-V(\bm{\omega}^{k_{n}}).$

Along the subsequence $\\{\bm{\omega}^{k_{n}}\\}_{n=0}^{\infty}$, we obtain
the following inequalities

$\displaystyle V(\bm{\omega}^{k_{0}})>V(\bm{\omega}^{k_{1}})$
$\displaystyle>\dots>V(\bm{\omega}^{k_{n}})>\dots\geq 0.$ (3.3)

The last inequality follows from the non-negativity of the g-dclf $V$. Hence,
the sequence $\\{V(\bm{\omega}^{k_{n}})\\}_{n=0}^{\infty}$ converges to some
$\delta\in\mathbb{R}$ as $n\to\infty$. Since $x^{k_{n}}\neq 0$ for all
$n\in\mathbb{N}$, it follows that $\delta>0$ and that

$\displaystyle\delta\leq V(\bm{\omega}^{k_{n}})\leq
V(\bm{\omega}^{k_{0}})\hskip 8.5359pt\forall n\in\mathbb{N}.$ (3.4)

Next, we define

$\displaystyle
C:=\\{(z^{0},\bm{\zeta})\in\mathbb{R}^{n}\times\mathbf{U}_{[0:q-1]}(z^{0}):\delta\leq
V(z^{0},\bm{\zeta})\leq V(\bm{\omega}^{k_{0}})\\}.$

Since $V$ is continuous and by (2.7) radially unbounded, $C$ is closed and
bounded, and hence a compact subset of $\mathbb{R}^{n}\times\mathbb{R}^{p,q}$.
Since there exist states and controls such that (3.4) follows, it holds
$\bm{\omega}^{k_{n}}\in C$ for all $n\in\mathbb{N}$. For
$(z^{0},\bm{\zeta}_{[0:q-1]})\in C$, Proposition 3.1 lets us conclude that
there exists a control sequence $\bm{\xi}_{[0:q+m-1]}$ and some
$l\in\\{1,\dots,m\\}$ for which
$V(z^{l},\bm{\xi}_{[l:q+l-1]})-V(z^{0},\bm{\zeta}_{[0:q-1]})\leq-\alpha(z^{0},\bm{\zeta}_{[0:q-1]})$
and $\bm{\xi}_{[l:q+l-1]}\in\mathbf{U}_{[0:q-1]}(z^{l})$. Therefore,

$\displaystyle\min_{l=1,\dots,m}V(z^{l},\bm{\xi}_{[l:q+l-1]})-V(z^{0},\bm{\zeta}_{[0:q-1]})$
$\displaystyle\hskip 40.0pt\leq-\alpha(z^{0},\bm{\zeta}_{[0:q-1]}),\hskip
8.5359pt\hskip 14.22636pt\forall(z^{0},\bm{\zeta}_{[0:q-1]})\in C$ and
consequently, $\displaystyle\sup_{(z^{0},\bm{\zeta})\in
C}\left[\min_{l=1,\dots,m}V(z^{l},\bm{\xi}_{[l:q+l-1]})-V(z^{0},\bm{\zeta}_{[0:q-1]})\right]$
$\displaystyle\hskip 40.0pt\leq\sup_{(z^{0},\bm{\zeta})\in
C}-\alpha(z^{0},\bm{\zeta}_{[0:q-1]})$ $\displaystyle\hskip
40.0pt=\max_{(z^{0},\bm{\zeta})\in
C}-\alpha(z^{0},\bm{\zeta}_{[0:q-1]})=:-S<0.$

The above supremum is attained for some $(z^{0},\bm{\zeta}_{[0:q-1]})\in C$
because $C$ is compact and $\alpha$ is continuous. For any
$(z^{0},\bm{\zeta}_{[0:q-1]})\in C$ we have
$V(z^{0},\bm{\zeta}_{[0:q-1]})\geq\delta>0$. The positive definiteness of $V$
implies that $(z^{0},\bm{\zeta}_{[0:q-1]})$ is non-zero and thus the positive
definiteness of $\alpha$ implies that the above maximum is strictly less than
zero. Since $\bm{\omega}^{k_{n}}\in C$ for all $n\in\mathbb{N}$, we have that

$\displaystyle V(\bm{\omega}$ ${}^{k_{n+1}})-V(\bm{\omega}^{k_{n}})$
$\displaystyle\leq$ $\displaystyle\sup_{(z^{0},\bm{\zeta})\in
C}\left[\min_{l=1,\dots,m}V(z^{l},\bm{\xi}_{[l:q+l-1]})-V(z^{0},\bm{\zeta}_{[0:q-1]})\right]$
$\displaystyle\leq$ $\displaystyle-S\hskip 8.5359pt\forall n\in\mathbb{N}.$
(3.5)

To come to a contradiction, we now observe that

$\displaystyle V(\bm{\omega}^{k_{N}})=$ $\displaystyle
V(\bm{\omega}^{k_{0}})+\sum_{n=0}^{N-1}V(\bm{\omega}^{k_{n+1}})-V(\bm{\omega}^{k_{n}})$
$\displaystyle\leq$ $\displaystyle V(\bm{\omega}^{k_{0}})-N\cdot S,$ (3.6)

where the last inequality follows from equation (3). If
$N>V(\bm{\omega}^{k_{0}})/S$, then the inequality (3) implies
$V(\bm{\omega}^{k_{N}})<0$. This contradicts the positive definiteness of $V$.
Hence, our assumption must have been incorrect and there exists a feasible
control sequence, which achieves $\lim_{k\to\infty}x^{k}=0$. ∎

The above proof is constructive; it provides us with a control sequence which
steers the state to zero. This is summarized in the following proposition.

######  Proposition 3.2.

For any $n\in\mathbb{N}$ consider $V(x^{k_{n}},\mathbf{u}^{k_{n}}_{[0:q-1]})$,
where $k_{n}$ is the index of the subsequence (3.1), and let
$\bm{\nu}^{k_{n}}_{[0:q+m-1]}$ be a control sequence that can be found for
$(x^{k_{n}},\mathbf{u}^{k_{n}}_{[0:q-1]})$ to satisfy equation (2.8).
Furthermore, let $l^{k_{n}}\in\\{1,\dots,m\\}$ be the index of the state and
control pair which achieves the descent of the g-dclf $V$ and thus defines
$(x^{k_{n+1}},\mathbf{u}^{k_{n+1}}_{[0:q-1]})$. Then the control sequence

$\displaystyle[\bm{\nu}^{k_{0}}_{[0:l^{k_{0}}-1]},\bm{\nu}^{k_{1}}_{[0:l^{k_{1}}-1]},\dots,\bm{\nu}^{k_{n}}_{[0:l^{k_{n}}-1]},\dots]$
(3.7)

is feasible and steers the state to zero. Each
$\bm{\nu}^{k_{n}}_{[0:l^{k_{n}}-1]}$ has $l^{k_{n}}$ elements and steers the
system to the next state $x^{k_{n+1}}$.

The way the above control sequence was constructed and is used to steer the
state gives rise to its time and state dependency. Thus, considering control
system (2.1) with the control strategy (3.7) results in a time-varying system,
explaining the used stability notion. It remains to prove Theorem 2.5.

###### Proof of Theorem 2.5.

This proof is along the lines of classical Lyapunov theory [11]. To ease
notation, we will present it again for the case $m=2$; the general case
follows similarly. Theorem 2.3 already guarantees that any state $x^{k_{0}}$
can be steered to zero. To obtain asymptotic stability, we still need to show
that for all $\varepsilon>0$ and any $k_{0}\in\mathbb{N}$, there exists
$\bar{\delta}>0$ such that for any state $x^{k_{0}}\in X$ with
$0<\|x^{k_{0}}\|<\bar{\delta}$, there exists a feasible control strategy which
yields $\|x^{k}\|<\varepsilon$, for all $k\geq k_{0}$. To this end, fix
$\varepsilon>0$ and $k_{0}\in\mathbb{N}$. Due to the radial unboundedness of
$V$ by (2.7), we can choose
$\mathbf{0}\neq\mathbf{p}\in\mathbb{R}^{n}\times\mathbb{R}^{p,q}$ such that
there exists $r\in(0,\varepsilon)$, where $\|(x,\mathbf{u})\|>r$ implies
$V(x,\mathbf{u})>V(\mathbf{p})$, or equivalently,

$\displaystyle V(x,\mathbf{u})\leq
V(\mathbf{p})\Rightarrow\|(x,\mathbf{u})\|\leq r.$ (3.8)

Now define
$B_{r}:=\\{(x,\mathbf{u})\in\mathbb{R}^{n}\times\mathbb{R}^{p,q}:\|(x,\mathbf{u})\|\leq
r\\}$, $\beta:=V(\mathbf{p})>0$ and $\Omega_{\beta}:=\\{(x,\mathbf{u})\in
B_{r}:V(x,\mathbf{u})\leq\beta\\}$. It follows $\Omega_{\beta}\subseteq
B_{r}$. Suppose for now we have

$\displaystyle
V(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})<\min\\{0.5\beta\sigma_{1},0.5\beta\sigma_{2},\beta\\}$
(3.9)

for some $x^{k_{0}}\in X\setminus\\{0\\}$ and
$\mathbf{u}^{k_{0}}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x^{k_{0}})$. Then we
claim that there exists a control strategy such that
$V(x^{k},\mathbf{u}^{k}_{[0:q-1]})\leq\beta$ for all $k\geq k_{0}$. Together
with equation (3.8), this would imply that $(x^{k},\mathbf{u}^{k}_{[0:q-1]})$
stays in $\Omega_{\beta}$ for $k\geq k_{0}$. To prove the claim, let us first
consider the case $\sigma_{1}\leq\sigma_{2}$. Clearly,
$V(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})<0.5\beta\sigma_{1}$. Since $V$ is a
g-dclf there exists a control strategy $\bm{\nu}_{[0:q+1]}$ such that

$\displaystyle\sigma_{2}V(x^{k_{0}+2},\bm{\nu}_{[2:q+1]}$
$\displaystyle)+\sigma_{1}V(x^{k_{0}+1},\bm{\nu}_{[1:q]})<2V(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})<2\frac{\beta\sigma_{1}}{2}=\beta\sigma_{1}.$

Hence, $V(x^{k_{0}+1},\bm{\nu}_{[1:q]})<\beta$. Similarly,
$V(x^{k_{0}+2},\bm{\nu}_{[2:q+1]})$ $<\beta$. The case $\sigma_{1}>\sigma_{2}$
follows likewise. By Proposition 3.1, either $V(x^{k_{0}+1},\bm{\nu}_{[1:q]})$
or $V(x^{k_{0}+2},\bm{\nu}_{[2:q+1]})$ is less than
$V(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})$ and determines the index of the
descent $\ell\in\\{1,2\\}$ (compare with proof of Theorem 2.3). If $\ell=1$,
we have found $x^{k_{0}+1}$ and
$\mathbf{u}^{k_{0}+1}_{[0:q-1]}:=\bm{\nu}_{[1:q]}$, if $\ell=2$, we have also
found $x^{k_{0}+2}$ and $\mathbf{u}^{k_{0}+2}_{[0:q-1]}:=\bm{\nu}_{[2:q+1]}$.
The above argument can be repeated with the new state control pair
$(x^{k_{0}+\ell},\mathbf{u}^{k_{0}+\ell}_{[0:q-1]})$. Repeating this argument
proves the claim. We hence conclude that

$(x^{k},\mathbf{u}^{k}_{[0:q-1]})\in\Omega_{\beta}\Rightarrow(x^{k},\mathbf{u}^{k}_{[0:q-1]})\in
B_{r}\quad\forall k\geq k_{0}.$

Thus, we obtain $\|x^{k}\|\leq\|(x^{k},\mathbf{u}^{k}_{[0:q-1]})\|\leq
r<\varepsilon$ for all $k\geq k_{0}$. It remains to guarantee that we can find
$x^{k_{0}}\in X\setminus\\{0\\}$ and
$\mathbf{u}^{k_{0}}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x^{k_{0}})$ with

$\displaystyle
V(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})<\min\\{0.5\beta\sigma_{1},0.5\beta\sigma_{2},\beta\\}.$

Due to the fact that $V$ is continuous and $V(0,\mathbf{0})=0$, there exists
$\delta>0$ such that $\|(x,\mathbf{u}_{[0:q-1]})\|<\delta$ implies

$\displaystyle
V(x,\mathbf{u}_{[0:q-1]})<\min\\{0.5\beta\sigma_{1},0.5\beta\sigma_{2},\beta\\}.$

If $q=0$, then the continuity of $V$ is enough, for $q\neq 0$ we need to evoke
Assumption 2.4. It guarantees that for all $\bar{\varepsilon}>0$, there exists
$\bar{\delta}>0$ such that for all $0<\|x^{k_{0}}\|<\bar{\delta}$ there exists
$\mathbf{u}^{k_{0}}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x^{k_{0}})$ with
$\|\mathbf{u}^{k_{0}}_{[0:q-1]}\|<~{}\bar{\varepsilon}$ satisfying the
inequalities (2.7) and (2.8). Thus, for small enough $\bar{\varepsilon}$ we
have $\bar{\varepsilon}+\bar{\delta}<\delta$ and obtain that for any
$x^{k_{0}}\in X$ with $0<\|x^{k_{0}}\|<\bar{\delta}$ there exists
$\mathbf{u}^{k_{0}}_{[0:q-1]}\in~{}\mathbf{U}_{[0:q-1]}(x^{k_{0}})$ such that

$\|(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})\|\leq\|x^{k_{0}}\|+\|\mathbf{u}^{k_{0}}_{[0:q-1]}\|<\bar{\delta}+\bar{\varepsilon}<\delta.$

We can deduce that the Lyapunov function value of
$(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})$ satisfies the desired bound (3.9).
In summary, if $x^{k_{0}}\in X$ satisfies $0<\|x^{k_{0}}\|<\bar{\delta}$, then
$\|x^{k}\|<\varepsilon$ for all $k\geq k_{0}$. This completes the proof. ∎

The proofs of Theorem 2.12 and 2.13 can be found in Appendix A.

##  4\. Applications to nonholonomic systems

In this section, we demonstrate the performance of our algorithm for a
nonholonomic system. In particular, we consider a variation of the classical
Brockett integrator [4] in discrete-time. Let $x^{0}\in\mathbb{R}^{4}$ be the
initial state, $h=0.1$ the sampling time and $u^{j}=[u^{j}_{1}\
u^{j}_{2}]^{T}\in\mathbb{R}^{2}$ the control input at time step $j$. The
dynamics of the state $x^{j+1}=[x^{j+1}_{1}\ x^{j+1}_{2}\ x^{j+1}_{3}\
x^{j+1}_{4}]^{T}\in\mathbb{R}^{4}$ at time step $j+1$ are given by

$\displaystyle\begin{split}x^{j+1}&=x^{j}+h\begin{bmatrix}1\\\ 0\\\
-x_{2}^{j}\\\ x_{3}^{j}\end{bmatrix}u^{j}_{1}+h\begin{bmatrix}0\\\ 1\\\
x^{j}_{1}\\\ x_{2}^{j}\end{bmatrix}u^{j}_{2}+h\begin{bmatrix}0\\\ 0\\\ 0\\\
|x_{4}^{j}|\end{bmatrix}.\end{split}$ (4.1)

It is worth pointing out that in (4.1) we have added the last term to “break
the symmetry”, inducing the need for a richer class of control inputs. This
system is difficult to stabilize because it does not satisfy Brockett’s
necessary condition as stated in the next proposition. Therefore, there does
not exist a smooth state feedback control law which renders $(0,0)$ locally
asymptotically stable.

######  Proposition 4.1.

The control system (4.1) does not satisfy Brockett’s necessary condition.

The proof of this result can be found in Appendix B. The difficulty in
stabilizing the above system makes it suitable for our scheme. In particular,
standard MPC schemes with quadratic costs are known to encounter issues in
such settings [18]. Before we look at the simulation results, we will first
propose a g-dclf for system (4.1) in the next section.

###  4.1. Choice of generalized control Lyapunov function

We take the function $V:\mathbb{R}^{n}\to\mathbb{R},x\mapsto\|x\|^{2}$ as a
g-dclf candidate, corresponding to the case $q=0$. Although system (4.1) does
not satisfy Brockett’s necessary condition, we are able to decrease the state
in multiple steps with respect to $\|\cdot\|^{2}$. The multiplicity of steps
is the key feature that enables the descent. In particular, let
$e_{i}\in\mathbb{R}^{4}$ be the unit vector with the $i$th entry of one.
Suppose that initially $x^{0}=e_{4}$. Hence, we wish to decrease the fourth
component of the state. According to our dynamics, one way to do so is to set
$u^{0}_{1}=0$ and to choose $u^{0}_{2}=5$ so that we increase $x^{1}_{2}$:

$\displaystyle x^{1}$
$\displaystyle=e_{4}+0e_{1}+0.5e_{2}+0.1e_{4}=\begin{bmatrix}0&0.5&0&1.1\end{bmatrix}^{T}.$
This increases the squared norm of the state after one step, but in the second
step we are able to reduce $x^{2}_{4}$ through $x_{2}^{1}$. By choosing
$u^{1}_{1}=0$ and $u^{1}_{2}=-u^{0}_{2}$, we reverse the previous increase of
the second component of the state: $\displaystyle x^{2}$
$\displaystyle=\begin{bmatrix}0&0.5&0&1.1\end{bmatrix}^{T}+0\begin{bmatrix}1&0&-0.5&0\end{bmatrix}^{T}-0.5\begin{bmatrix}0&1&0&0.5\end{bmatrix}^{T}+0.11e_{4}=0.96e_{4}.$

Note that $\|x^{0}\|^{2}=1,\|x^{1}\|^{2}=1.46$ and $\|x^{2}\|^{2}=0.9216$,
demonstrating a descent in two steps. The above control strategy obviously
strongly depends on the initial state. These computations motivate the
approach of using multiple steps to decrease a Lyapunov function value. Our
analytical computations match Figure 2, where a control strategy found by
simulations decreases the squared norm of the states in ten steps.

In summary, the above observations demonstrate that the function value of
$\|\cdot\|^{2}$ can be decreased in multiple steps along trajectories of
system (4.1). Therefore, we choose $V(x)=\|x\|^{2}$ as the g-dclf for system
(4.1).

Figure 2. The function value of $\|x\|^{2}$ along trajectories of system
(4.1). The function value of five random initial states was successfully
decreased in ten steps.

###  4.2. Simulation results

Let us investigate Algorithm 1, when applied to the following optimal control
problem.

######  Problem 4.2.

$\displaystyle\begin{aligned}
\min&\sum_{j=0}^{9}\|x^{j}\|^{2}+5\,\|u^{j}\|^{2}\\\
\mathrm{s.t.}&\mathrm{~{}\eqref{sys:plus_000abs}~{}holds~{}with~{}}x^{0}=x\\\
&\frac{5.5}{10}\Big{(}\|x^{6}\|^{2}+\|x^{5}\|^{2}+\|x^{4}\|^{2}+\|x^{3}\|^{2}\Big{)}-\|x^{0}\|^{2}\leq-\varepsilon\|x^{0}\|^{4}\end{aligned}$

We take the prediction horizon to be $N_{p}=10$. The initial state is set to
be $[1\ 2\ 3\ 5]^{T}$ and we use

$\displaystyle\begin{bmatrix}1&1&\dots&1\\\
1&1&\dots&1\end{bmatrix}\in\mathbb{R}^{2,10}$

as the initial control. As discussed, we choose $V(x)=\|x\|^{2}$ as the
g-dclf. In step four of Algorithm 1, we find an index
$\ell_{decr}\in\\{1,\dots,m\\}$ which achieves a descent for this g-dclf. We
do so by choosing the index $\ell_{decr}$ that corresponds to the minimal
predicted Lyapunov function value $V(x^{\ell_{decr}})$. To achieve a descent,
we choose $\alpha(x)=\varepsilon\|x\|^{4}$, where $\varepsilon=10^{-5}$.
Although only the weights of the sixth, fifth, fourth and third Lyapunov
function value are non-zero, we choose $m=N_{p}=10$ for adc. This means, in
every iteration of Algorithm 1 we can implement up to ten steps.

The solution to Problem 4.2 computed by flexible-step MPC is shown in Figure
3.

Figure 3. Solution to Problem 4.2

The resulting trajectories of the states are shown in Figure 5. We observe
that after a transient phase, the states have practically converged to zero.

A First period

B Second period

Figure 4. Two periods of the Lyapunov function value according to the solution
of Problem 4.2. The Lyapunov function value of the initial state in the
current iteration is circled in black. It is followed by the $m=10$ Lyapunov
function values over the prediction horizon. The minimal Lyapunov function
value of each iteration is highlighted in red. The dashed arrow symbolizes
that the state, which achieves the minimum, will be the initial state for the
next iteration, while the gray Lyapunov function values following the minimum
will be discarded. This is why the time axis is unconventional; the time does
not continue until the new iteration with the just declared initial state
starts. Figure 5. State trajectories according to the solution of Problem 4.2

In Figure 4, we can see the Lyapunov function values for two selected periods;
the outcome of adc can be clearly recognized in this figure. The Lyapunov
function value of the initial state of the current iteration is circled in
black. The red star indicates the minimum of the Lyapunov function values in
every iteration. The Lyapunov function values following the minimum are gray
because they will be discarded in our implementation. Instead, the controls
will be implemented until the minimum occurs and the resulting state will be
the new initial state. Displaying the Lyapunov function values over the whole
prediction horizon in each optimization instance results in an unconventional
time axis. For example, in Figure 4A the minimal Lyapunov function value of
the first optimization instance of Problem 2.7 occurs at time step six and the
time does not continue until after the next black circle which indicates the
Lyapunov function value of the new initial state. Altogether, we can see in
Figure 4 how the Lyapunov function values evolve and how various optimization
instances present a different minimal index. A summary of the implemented
steps at each optimization instance of Problem 4.2 is given in Figure 6. This
figure can be interpreted as follows: The solution of the first optimization
instance of Problem 4.2 results in the implementation of six steps. The second
optimization, which starts at $k=6$, yields the implementation of nine steps
and so on.

Figure 6. In each optimization instance, Problem 4.2 is solved. The solution
yields the number of implemented steps, depicted on the vertical axis. Note
that the sum of implemented steps of the optimization instances corresponds to
the time step of the implementation.

Note that the algorithm is truly making use of the flexible steps in the
transient phase of the state trajectory (optimization instances one to
thirteen).

We will compare our solution of Problem 4.2 to standard MPC with a terminal
cost, weighted by $\gamma>0$, see Problem 4.3, where a fixed number of ten
steps is always implemented.

######  Problem 4.3.

$\displaystyle\begin{aligned}
\min&\sum_{j=0}^{9}\|x^{j}\|^{2}+5\,\|u^{j}\|^{2}+\gamma\|x^{10}\|^{2}\\\
\mathrm{s.t.}&\mathrm{~{}\eqref{sys:plus_000abs}~{}holds~{}with~{}}x^{0}=x\end{aligned}$

We have verified through simulations that the following observations remain
qualitatively the same with other numbers of implemented steps. As a first
choice for the weight of the terminal cost, we take $\gamma=22$. The state
trajectories resulting from the solution to Problem 4.3 computed by standard
MPC with $\gamma=22$ are depicted in Figure 7, where we do not observe
convergence to zero.

Figure 7. State trajectories according to the solution of Problem 4.3 with
$\gamma=22$

This is why we increased the weight of the terminal cost, while keeping the
same Lyapunov function $V(x)=\|x\|^{2}$. Increasing the weight does help, as
seen in Figure 8, but $x_{2}$ and $x_{4}$ keep oscillating.

Figure 8. State trajectories according to the solution of Problem 4.3 with
$\gamma=480$

We can increase the weight even further, see Figure 8, but the oscillations
remain.

Figure 9. State trajectories according to the solution of Problem 4.3 with
$\gamma=1920$

Even with very high weights in the terminal cost, as in Figure 9, we never
reach convergence of the states to zero. The weight of the terminal cost only
damps the oscillations of $x_{2}$ and $x_{4}$. In summary, the desired
stability behavior was not achieved by increasing the weight of the terminal
cost. Apparently, the standard approach involves more challenges in terms of
terminal ingredients than our approach to obtain convergence of the state to
zero, even though the same g-dclf of $\|\cdot\|^{2}$ was used. Finally, we
compare the total function value of the standard MPC scheme to our approach in
Figure 10. The total function value is the value of
$\sum_{j=0}^{k-1}\|x(j)\|^{2}+5\|u(j)\|^{2}$, where $k$ is the current time
step. The oscillations also have consequences here: The total function value
always slightly increases because the states have not converged to zero.

Figure 10. The total function value, i.e.
$\sum_{j=0}^{k-1}\|x(j)\|^{2}+5\|u(j)\|^{2}$, where $k$ is the current time
step, is displayed. The total function values according to the solution of
Problem 4.2 by flexible-step MPC and the solution of Problem 4.3 with
different weights $\gamma$ by standard MPC are compared.

##  5\. Conclusion

We generalized the idea of higher-order and non-monotonic Lyapunov functions
by introducing g-dclfs. Through the idea of adding the crucial condition (2.8)
from the definition of g-dclfs as a constraint, we obtained a novel MPC
scheme. This constraint alone facilitated the flexibility in the number of
implemented steps in each iteration of our proposed scheme. We demonstrated
the benefits of this flexibility through an application example.

There are several theoretical aspects of our work, where we would like to make
further advancement in the future. One goal is to prove recursive feasibility
for $q\neq N_{p}$, i.e. we would like to extend the result of Theorem 2.11.
Another goal is to provide a computationally efficient way for computing the
terminal set $X^{N_{p}}$ of Problem 2.7. We would also like to find a way to
bypass Assumption 2.4 (Small Control Property). The current choice of
$\mathbf{u}^{*-}_{[0:q-1]}$ in Algorithm 1 guarantees the chain of
inequalities (A.1). We believe that there are other possible choices (see
Remark 2.9), which we would like to investigate. Furthermore, we would like to
explore the idea of using g-dclfs in the terminal cost, as opposed to
incorporating them in a constraint.

Our simulations showed that variations of the classical Brockett integrator
provide an area of application for this novel implementation. In that sense,
it would be interesting to study the performance of our scheme for
applications like mobile robots, where the underlying dynamics are
nonholonomic, in the future. Moreover, it would be interesting to apply our
flexible-step implementation to large scale systems, where implementing more
than one step could make a significant difference for the running time.

Another promising direction is to generalize our framework to systems subject
to disturbances or to systems with an unknown model. It is especially
attractive for the latter case; the relaxed stability requirement of adc
enables more exploration compared to the classical one. Lastly, we would like
to rigorously study the performance of our novel implementation.

## References

  * [1] A. Ahmadi and P. Parrilo.  Non-monotonic Lyapunov Functions for Stability of Discrete Time Nonlinear and Switched Systems.  In 2008 47th IEEE Conference on Decision and Control, pages 614–621. IEEE, 2008.
  * [2] M. Alamir.  Contraction-based nonlinear model predictive control formulation without stability-related terminal constraints.  Automatica, 75:288–292, 2017.
  * [3] A. Bemporad.  A predictive controller with artificial Lyapunov function for linear systems with input/state constraints.  Automatica, 34(10):1255–1260, 1998.
  * [4] R. Brockett.  Asymptotic Stability and Feedback Stabilization.  Differential Geometric Control Theory, 27(1):181–191, 1983\.
  * [5] A. Butz.  Higher order derivatives of Liapunov functions.  IEEE Transactions on Automatic Control, 14(1):111–112, 1969.
  * [6] S. de Oliveira Kothare and M. Morari.  Contractive model predictive control for constrained nonlinear systems.  IEEE Transactions on Automatic Control, 45(6):1053–1071, 2000.
  * [7] F. Fontes.  Discontinuous feedbacks, discontinuous optimal controls, and continuous-time model predictive control.  International Journal of Robust and Nonlinear Control: IFAC-Affiliated Journal, 13(3-4):191–209, 2003.
  * [8] F. Fontes, L. Magni, and É. Gyurkovics.  Sampled-data Model Predictive Control for Nonlinear Time-Varying Systems: Stability and Robustness.  In Assessment and Future Directions of Nonlinear Model Predictive Control, pages 115–129. Springer, 2007.
  * [9] W. Haddad and V. Chellaboina.  Nonlinear Dynamical Systems and Control.  Princeton University Press, 2008.
  * [10] J. Hanema, M. Lazar, and R. Tóth.  Stabilizing Tube-Based Model Predictive Control for LPV Systems.  Automatica, 85:137–144, 2017.
  * [11] H. Khalil.  Nonlinear Systems Third Edition.  Prentice Hall, 2002.
  * [12] M. Lazar and V. Spinu.  Finite-step terminal ingredients for stabilizing model predictive control.  IFAC-PapersOnLine, 48(23):9–15, 2015.
  * [13] W. Lin and C. Byrnes.  Design of discrete-time nonlinear control systems via smooth feedback.  IEEE Transactions on Automatic Control, 39(11):2340–2346, 1994\.
  * [14] D. Mayne.  Model predictive control: Recent developments and future promise.  Automatica, 50(12):2967–2986, 2014.
  * [15] D. Mayne, J. Rawlings, C. Rao, and P. Scokaert.  Constrained model predictive control: Stability and optimality.  Automatica, 36(6):789–814, 2000.
  * [16] H. Michalska.  A new formulation of receding horizon stabilising control without terminal constraint on the state.  European Journal of Control, 3(1):2–14, 1997.
  * [17] H. Michalska and D. Mayne.  Robust receding horizon control of constrained nonlinear systems.  IEEE Transactions on Automatic Control, 38(11):1623–1633, 1993\.
  * [18] M. Müller and K. Worthmann.  Quadratic costs do not always work in MPC.  Automatica, 82:269–277, 2017.
  * [19] N. Noroozi, R. Geiselhart, L. Grüne, and F. Wirth.  Control of discrete-time nonlinear systems via finite-step control Lyapunov functions.  Systems & Control Letters, 138:104631, 2020.
  * [20] J. Primbs, V. Nevistic, and J. Doyle.  On receding horizon extensions and control Lyapunov functions.  In Proceedings of the 1998 American Control Conference. ACC (IEEE Cat. No. 98CH36207), volume 6, pages 3276–3280. IEEE, 1998.
  * [21] E. Sontag.  A ‘universal’ construction of Artstein’s theorem on nonlinear stabilization.  Systems & Control Letters, 13(2):117–123, 1989.
  * [22] M. Sznaier and M. Damborg.  Heuristically enhanced feedback control of constrained discrete-time linear systems.  Automatica, 26(3):521–532, 1990.
  * [23] T.H. Yang and E. Polak.  Moving horizon control of nonlinear systems with input saturation, disturbances and plant uncertainty.  International Journal of Control, 58(4):875–903, 1993.

##  Appendix A Proofs of Theorem 2.12 and 2.13

For the sake of completeness, we present the proofs of Theorem 2.12 and 2.13.
Recall that we are considering system (2.1) with the time-varying MPC
controller $c^{k}_{mpc}$ resulting in the time-varying system (2.10). This in
turn has to be studied with the appropriate stability notion.

###### Proof of Theorem 2.12.

Fix $k_{0}\in\mathbb{N}$ and $x(k_{0})\in X$. We may assume again that
$x(k_{0})$ is unequal to zero. Suppose, by contradiction, that the control law
generated by Algorithm 1 does not steer $x(k)$ to zero as $k$ goes to
infinity. This implies that $x(k)$ is non-zero for all $k\geq k_{0}$, as the
zero control is a feasible control with minimal cost for Problem 2.7. As
before, our goal is to define a subsequence
$\\{(x(k_{n}),\mathbf{u}^{k_{n}}_{[0:q-1]})\\}_{n=0}^{\infty}$, where the
Lyapunov function values evaluated at these states and controls strictly
decrease. To this end, consider $x(k_{0})$ as the current state of the
flexible-step MPC scheme, which defines the initial state of Problem 2.7,
$x^{0}=x(k_{0})$, and let
$\mathbf{u}^{*-}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x(k_{0}))$ be a fixed, but
arbitrary, control sequence. Let $\mathbf{u}^{*}(x(k_{0}))_{[0:N-1]}$ be the
control sequence generated by Algorithm 1 in step three, where
$N=\max\\{q+m,N_{p}\\}$. Since adc is satisfied, Algorithm 1 can find an index
$1\leq\ell_{decr}\leq m$ in step four for which

$\displaystyle
V(x^{*\ell_{decr}},\mathbf{u}^{*}(x(k_{0}))_{[\ell_{decr}:q+\ell_{decr}-1]})<V(x(k_{0}),\mathbf{u}^{*-}_{[0:q-1]}),$

where
$\mathbf{u}^{*}(x(k_{0}))_{[\ell_{decr}:q+\ell_{decr}-1]}\in\mathbf{U}_{[0:q-1]}(x^{*\ell_{decr}})$
(compare with Proposition 3.1). In this proof, we choose the index with the
greatest descent in the above inequality as $\ell_{decr}$. Following the
flexible-step MPC scheme, the control sequence
$\mathbf{u}^{*}(x(k_{0}))_{[0:\ell_{decr}-1]}$ is implemented and as a result,
we can define the first two members of our subsequence:

$\displaystyle\bm{\omega}^{k_{0}}$
$\displaystyle:=(x(k_{0}),\mathbf{u}^{*-}_{[0:q-1]})$
$\displaystyle\bm{\omega}^{k_{1}}$
$\displaystyle:=(x(k_{0}+\ell_{decr}),\mathbf{u}^{*}(x(k_{0}))_{[\ell_{decr}:q+\ell_{decr}-1]}).$

To define the rest of the subsequence, we proceed as follows. Suppose
$\bm{\omega}^{k_{n}}$ has been defined. Then Algorithm 1 with the current
state $x(k_{n})$ produces again a control sequence
$\mathbf{u}^{*}(x(k_{n}))_{[0:N-1]}$ such that for some $1\leq\ell_{decr}\leq
m$ the Lyapunov function value is strictly below $V(\bm{\omega}^{k_{n}})$ and
$\mathbf{u}^{*}(x(k_{n}))_{[\ell_{decr}:q+\ell_{decr}-1]}\in\mathbf{U}_{[0:q-1]}(x^{*\ell_{decr}})$.
We can define $\bm{\omega}^{k_{n+1}}$ accordingly

$\displaystyle\bm{\omega}^{k_{n+1}}$
$\displaystyle:=(x(k_{n}+\ell_{decr}),\mathbf{u}^{*}(x(k_{n}))_{[\ell_{decr}:q+\ell_{decr}-1]}).$

Along the subsequence $\\{\bm{\omega}^{k_{n}}\\}_{n=0}^{\infty}$, we obtain
the following inequalities

$\displaystyle V(\bm{\omega}^{k_{0}})>V(\bm{\omega}^{k_{1}})$
$\displaystyle>\dots>V(\bm{\omega}^{k_{n}})>\dots\geq 0.$ (A.1)

Like in the proof of Theorem 2.3, the sequence
$\\{V(\bm{\omega}^{k_{n}})\\}_{n=0}^{\infty}$ converges to some $\delta>0$ as
$n\to\infty$, which allows us to define the set $C$ once more. Similarly, we
conclude that

$\displaystyle\sup_{(z^{0},\bm{\zeta})\in
C}\left[\min_{l=1,\dots,m}V(z^{l},\bm{\xi}_{[l:q+l-1]})-V(z^{0},\bm{\zeta}_{[0:q-1]})\right]$
$\displaystyle\hskip 40.0pt=\max_{(z^{0},\bm{\zeta})\in
C}-\alpha(z^{0},\bm{\zeta}_{[0:q-1]})=:-S<0$ and $\displaystyle\hskip
10.0ptV(\bm{\omega}^{k_{n+1}})-V(\bm{\omega}^{k_{n}})\leq-S\quad\forall
n\in\mathbb{N},$

where $\\{\bm{\omega}^{k_{n}}\\}_{n=0}^{\infty}$ are produced by Algorithm 1,
as described above. We obtain the same contradiction as before by observing

$\displaystyle V(\bm{\omega}^{k_{\bar{N}}})=$ $\displaystyle
V(\bm{\omega}^{k_{0}})+\sum_{n=0}^{\bar{N}-1}V(\bm{\omega}^{k_{n+1}})-V(\bm{\omega}^{k_{n}})$
$\displaystyle\leq$ $\displaystyle V(\bm{\omega}^{k_{0}})-\bar{N}\cdot S.$
(A.2)

If $\bar{N}>V(\bm{\omega}^{k_{0}})/S$, then the inequality (A) implies
$V(\bm{\omega}^{k_{\bar{N}}})<0$, contradicting the positive definiteness of
$V$. Hence, Algorithm 1 generates a control sequence which steers $x(k)$ to
zero as $k$ goes to infinity. ∎

######  Remark A.1.

The sequence $\\{(x(k_{n}),\mathbf{u}^{k_{n}}_{[0:q-1]})\\}_{n=0}^{\infty}$,
defined in the proof of Theorem 2.12, is related to $y(k)$, which was
introduced earlier to extend (2.10): The augmented variable $y(k)$ is
basically equal to $(x(k_{n}),\mathbf{u}^{k_{n}}_{[0:q-1]})$, except that the
elements between the $k_{n+1}$-th and $k_{n}$-th element are filled up with
the constant $(x(k_{n}),\mathbf{u}^{k_{n}}_{[0:q-1]})$ for all
$n\in\mathbb{N}$, i.e.

$\displaystyle[\underbrace{y(k_{0}),\dots,y(k_{1}-1)}_{\ell^{k_{0}}_{decr}\text{
elements}},\underbrace{y(k_{1}),\dots,y(k_{2}-1)}_{\ell_{\textup{decr}}^{k_{1}}\text{
elements}},y(k_{2}),\dots]=$
$\displaystyle\quad[\underbrace{(x(k_{0}),\mathbf{u}^{k_{0}}_{[0:q-1]}),\dots,(x(k_{0}),\mathbf{u}^{k_{0}}_{[0:q-1]})}_{\ell^{k_{0}}_{decr}\text{
times}},\underbrace{(x(k_{1}),\mathbf{u}^{k_{1}}_{[0:q-1]}),\dots,(x(k_{1}),\mathbf{u}^{k_{1}}_{[0:q-1]})}_{\ell_{\textup{decr}}^{k_{1}}\text{
times}},(x(k_{2}),\mathbf{u}^{k_{2}}_{[0:q-1]}),\dots],$

where $\ell_{decr}^{k_{0}}$ is the index $\ell_{decr}$ found in Algorithm 1
through the first optimization instance, occurring at $k_{0}$,
$\ell_{decr}^{k_{1}}$ is found through the next optimization instance,
occurring at $k_{1}$, and so on. $\bullet$

###### Proof of Theorem 2.13.

By solving Problem 2.7 repeatedly using Algorithm 1, we generate a control
sequence which, by Theorem 2.12, steers any state $x(k_{0})$ in the set $X$ to
zero. This proves the first statement. For the second statement we show that
for all $\varepsilon>0$ and any $k_{0}\in\mathbb{N}$, there exists
$\bar{\delta}>0$ such that for any state $x(k_{0})\in X$ with
$0<\|x(k_{0})\|<\bar{\delta}$, the state governed by (2.10) satisfies
$\|x(k)\|<\varepsilon$, for all $k\geq k_{0}$. To this end, fix
$\varepsilon>0$ and $k_{0}\in\mathbb{N}$. As before, we choose
$\mathbf{p}\in\mathbb{R}^{n}\times\mathbb{R}^{p,q}$ such that there exists
$r\in(0,\varepsilon)$ satisfying equation (3.8) and define $B_{r},\beta$ and
$\Omega_{\beta}$ accordingly. By using again the continuity of $V$ and
Assumption 2.4, we deduce that there exists $\bar{\delta}>0$ such that for any
$x(k_{0})\in X$ with $0<\|x(k_{0})\|<\bar{\delta}$, there exists
$\mathbf{u}^{k_{0}}_{[0:q-1]}\in\mathbf{U}_{[0:q-1]}(x(k_{0}))$ with which
(3.9) holds, i.e.

$\displaystyle
V(x(k_{0}),\mathbf{u}^{k_{0}}_{[0:q-1]})<\min\\{0.5\beta\sigma_{1},0.5\beta\sigma_{2},\beta\\}.$

We claim that with the bound (3.9) at hand, Algorithm 1 produces control
inputs such that $V(x(k),\mathbf{u}^{k}_{[0:q-1]})\leq\beta$ for all $k\geq
k_{0}$. Together with equation (3.8), this would imply that
$(x(k),\mathbf{u}^{k}_{[0:q-1]})$ stays in $\Omega_{\beta}$ for $k\geq k_{0}$.
We first consider the case $\sigma_{1}\leq\sigma_{2}$ to prove the claim.
Clearly, $V(x(k_{0}),\mathbf{u}^{k_{0}}_{[0:q-1]})<0.5\beta\sigma_{1}$.
Consider $x(k_{0})$ as the current state in the flexible-step MPC scheme,
which defines the initial state of Problem 2.7, $x^{0}=x(k_{0})$, and let
${\mathbf{u}^{*}_{[0:N-1]}}(x(k_{0}))$ with $N=\max\\{q+m,N_{p}\\}$ be the
optimal input that is obtained in step three of Algorithm 1. Using the
constraint adc of Problem 2.7, we have

$\displaystyle\sigma_{2}V(x^{2},\mathbf{u}^{*}$
${}_{[2:q+1]}(x(k_{0})))+\sigma_{1}V(x^{1},\mathbf{u}^{*}_{[1:q]}(x(k_{0})))<2V(x(k_{0}),\mathbf{u}^{k_{0}}_{[0:q-1]})<2\frac{\beta\sigma_{1}}{2}=\beta\sigma_{1},$

and therefore, $V(x^{1},\mathbf{u}^{*}_{[1:q]}(x(k_{0})))<\beta$ and in an
analogous manner $V(x^{2},\mathbf{u}^{*}_{[2:q+1]}(x(k_{0})))$ $<\beta$. The
case $\sigma_{1}>\sigma_{2}$ follows similarly. By Proposition 3.1, either
$V(x^{1},\mathbf{u}^{*}_{[1:q]}(x(k_{0})))$ or
$V(x^{2},\mathbf{u}^{*}_{[2:q+1]}(x(k_{0})))$ is less than
$V(x^{k_{0}},\mathbf{u}^{k_{0}}_{[0:q-1]})$ and determines
$\ell_{\textup{decr}}\in\\{1,2\\}$. If $\ell_{\textup{decr}}=1$, Algorithm 1
has found $x(k_{0}+1):=x^{1}$ and
$\mathbf{u}^{k_{0}+1}_{[0:q-1]}:=\mathbf{u}^{*}_{[1:q]}(x(k_{0}))$, if
$\ell_{\textup{decr}}=2$ the algorithm has also found $x(k_{0}+2):=x^{2}$ and
$\mathbf{u}^{k_{0}+2}_{[0:q-1]}:=\mathbf{u}^{*}_{[2:q+1]}(x(k_{0}))$. The
control input $\mathbf{u}^{*}_{[0:\ell_{\textup{decr}}-1]}(x(k_{0}))$ is
implemented and the above argument can be repeated with the new state control
pair $(x(k_{0}+l_{decr}),\mathbf{u}^{k_{0}+l_{decr}}_{[0:q-1]})$. The
repetition of this process ultimately proves the claim. Therefore,

$(x(k),\mathbf{u}^{k}_{[0:q-1]})\in\Omega_{\beta}\Rightarrow(x(k),\mathbf{u}^{k}_{[0:q-1]})\in
B_{r}\quad\forall k\geq k_{0},$

and hence, we obtain $\|x(k)\|\leq\|(x(k),\mathbf{u}^{k}_{[0:q-1]})\|\leq
r<\varepsilon$ for all $k\geq k_{0}$. As a result, if $x(k_{0})\in X$
satisfies $0<\|x(k_{0})\|<\bar{\delta}$, then $\|x(k)\|<\varepsilon$ for all
$k\geq k_{0}$. ∎

##  Appendix B Proof of Proposition 4.1

In this appendix, we prove Proposition 4.1. Let us first recall Brockett’s
necessary condition for the discrete-time case [13].

######  Theorem B.1.

Consider a discrete-time nonlinear control system governed by

$\displaystyle x^{k+1}=f(x^{k},u^{k}),$

with $f(0,0)=0$ and $f$ being smooth in a neighborhood of $(0,0)$. A necessary
condition for the existence of a smooth state feedback control law
$u^{k}=u(x^{k})$ which renders $(0,0)$ locally asymptotically stable is that
for the mapping

$\displaystyle\varphi:(x,u)$ $\displaystyle\mapsto f(x,u)-x$ the equation
$\displaystyle\varphi(x,u)$ $\displaystyle=y$ (B.1)

shall be solvable for all sufficiently small $y$.

In other words, if we can find a sufficiently small $y$ such that (B.1) is not
solvable, then Brockett’s necessary condition is violated. This is precisely
what we will do in the next proof.

###### Proof of Proposition 4.1.

To show this result, we will apply Theorem B.1 to system (4.1):

$\displaystyle\varphi(x,u)$ $\displaystyle=x+h\begin{bmatrix}1\\\ 0\\\
-x_{2}\\\ x_{3}\end{bmatrix}u_{1}+h\begin{bmatrix}0\\\ 1\\\ x_{1}\\\
x_{2}\end{bmatrix}u_{2}+h\begin{bmatrix}0\\\ 0\\\ 0\\\
|x_{4}|\end{bmatrix}-x=h\begin{bmatrix}1\\\ 0\\\ -x_{2}\\\
x_{3}\end{bmatrix}u_{1}+h\begin{bmatrix}0\\\ 1\\\ x_{1}\\\
x_{2}\end{bmatrix}u_{2}+h\begin{bmatrix}0\\\ 0\\\ 0\\\ |x_{4}|\end{bmatrix}.$
For all $\varepsilon>0$ the equation $\varphi(x,u)=[0\ 0\ 0\ -y_{4}]^{T}$ has
no solution for any $0<y_{4}<\varepsilon$. To see this, let us write out the
above equation $\displaystyle\begin{bmatrix}0\\\ 0\\\ 0\\\
-y_{4}\end{bmatrix}$ $\displaystyle=h\left(\begin{bmatrix}1\\\ 0\\\ -x_{2}\\\
x_{3}\end{bmatrix}u_{1}+\begin{bmatrix}0\\\ 1\\\ x_{1}\\\
x_{2}\end{bmatrix}u_{2}+\begin{bmatrix}0\\\ 0\\\ 0\\\
|x_{4}|\end{bmatrix}\right)=h\begin{bmatrix}u_{1}\\\ u_{2}\\\
-x_{2}u_{1}+x_{1}u_{2}\\\ x_{3}u_{1}+x_{2}u_{2}+|x_{4}|\end{bmatrix}.$ The
first and second component of the equation imply that the controls need to be
zero. If the controls are zero, the right-hand side of the fourth component
becomes $\displaystyle h(x_{3}u_{1}$
$\displaystyle+x_{2}u_{2}+|x_{4}|)=h(0+0+|x_{4}|).$

Now this shall be equal to the left-hand side of the fourth component, i.e.
$-y_{4}=h|x_{4}|.$ This equation demands that $-y_{4}$, which is negative,
shall equal $h|x_{4}|$, which is non-negative, thus it is not solvable.
Brockett’s necessary condition is not satisfied for the system (4.1). ∎


replacing rel | 54.5 | 54.5
replacing ent & rel | 57.5 | 55.6
Table 17: Comparison of replacing entity labels in deductive reasoning
experiment (ChatGPT). Results are in %.

##  Appendix R Multi-short rules

Besides, a single rule can be equivalent to multiple rules. For example, the
rule $\forall
x,y,z:\text{parentOf}(x,y)\land\text{parentOf}(y,z)\land\text{gender}(x,\text{female})\rightarrow\text{GrandmotherOf}(x,z)$
can be represented as $\forall
x,y,z:\text{parentOf}(x,y)\land\text{parentOf}(y,z)\rightarrow\text{GrandparentOf}(x,z),\text{GrandparentOf}(x,z)\land\text{gender}(x,\text{female})\rightarrow\text{GrandmotherOf}(x,z)$.
We conduct the experiments with both rule representations and find single-
longer rules perform better than multiple-short rules. Results are presented
in Table 12.

  *[LLMs]: Large Language Model