$\mathcal{K}\mathcal{L}$ and Lyapunov Approaches for Discrete-time Peak Computation Problems

Assalé Adjé
LAboratoire de Modélisation et Pluridisciplinaire et Simulations
LAMPS
Université de Perpignan Via Domitia
France

Abstract

In this paper, we propose a method to solve discrete-time peak computation problems (DPCPs for short). DPCPs are optimization problems that consist of maximizing a function over the reachable values set of a discrete-time dynamical system. The optimal value of a DPCP can be rewritten as the supremum of the sequence of optimal values. Previous results provide general techniques for computing the supremum of a real sequence from a well-chosen pair of a strictly increasing continuous function on $[0,1]$ and a positive scalar in $(0,1)$ . In this paper, we exploit the specific structure of the optimal value of the DPCP to construct such a pair from classical tools from stability theory: $\mathcal{K}\mathcal{L}$ certificate and Lyapunov functions.

1 Introduction

In this paper, we propose to solve discrete-time peak computation problems in finite-dimensional state spaces. A discrete-time peak computation problem can be viewed as a particular maximization problem for which the constraint on the decision variable is to belong to the reachable values set of a given discrete-time dynamical system. The objective function of this optimization problem is a function of the states. This particular maximization problem can model various situations in engineering, economics, physics, biology… For example, in population dynamics, for a predator-prey system, one may be interested in the maximal size of each species, even if the system asymptotically oscillates between several equilibria. This problem boils down to maximizing each coordinate of the state variable separately over the system modeling the population dynamics.

Besides its importance in analyzing critical concrete situations, the literature on discrete-time peak computation problems in the communities of dynamical systems analysis and optimization is quite thin. Discrete-time peak computation problems appear for linear systems, where the objective function is the Euclidean norm in [APS18]. This problem also appears in the analysis of stable linear systems with general quadratic objective functions in [Adj21] and in [Adj25a]. A more constrained version of the problem appears in [AG24]. The additional constraint for the state variable is to live in a given set. Discrete-time peak computation problems have a continuous-time counterpart (see e.g., [MHS20]). Note that in [MHS20], the authors address the problem of verifying safety properties (see, e.g., [BYG17] for verification problems on discrete-time systems) for dynamical systems and formulate the safety verification problem as a continuous-time peak computation problem. Safety verification problems aim to prove that the trajectories of a system are contained in a safe set. A safety verification problem can be translated into a peak computation problem when the safe set is a sublevel of sufficiently regular function. In this case, the objective function of the peak computation problem is the function associated with the sublevel set. A safety analysis from the peak computation point of view is also proposed for switched systems in [Adj17] and for program analysis in [AGM15]. For the safety analysis of dynamical systems, one can think that a reachability analysis (see e.g., [RKML06] and references therein), equivalent to a feasibility analysis in our context, is sufficient to prove some properties of the dynamical system. However, maximality in our context is synonymous with criticality. The optimal value in this situation can be viewed as the value that penalizes the system the most with respect to some criteria and defines the extreme conditions under which the system could enter.

In [MHS20], the authors are interested in computing an upper bound of the peak optimal value for the continuous-time case. The techniques used are based on Sums-Of-Squares (SOS) and Linear Matrix Inequalities (LMI) formulations (the interested reader can consult [Las15] for those subjects). The same goal motivates the authors of [APS18]. They limit their study to linear systems and norm objective functions they directly use semidefinite programming (see [BTN01] for further details on the subject). The purpose of the current paper is to develop a method for computing the exact value of a discrete-time peak computation problem. This purpose is shared by the authors of [AG24]. However, this latter cannot be fairly compared because of the additional constraint. Moreover, the studied systems are linear or piecewise linear, and the objective functions are linear.

The goal of the current paper is to provide a theoretical generalization of the works in [Adj21] and [Adj25a]. In [Adj21] and in [Adj25a], the resolution of discrete-time peak computation problems is restricted to stable affine systems and quadratic objective functions. In this paper, we consider wider classes of stable systems and general objective functions. The techniques developed in this paper combine the method proposed in [Adj25b] with the Lyapunov approach of [Adj25a]. In [Adj25b], the method aims to find the maximal term of a real sequence using homeomorphisms of convergent positive geometric sequences. In [Adj25a], homeomorphisms and geometric sequences are constructed from quadratic Lyapunov functions. In this paper, we also propose a construction of homeomorphisms and geometric sequences from $\mathcal{K}\mathcal{L}$ bounds. The use of such classical tools of dynamical systems stability theory (the interested reader can consult [Ela05, Chap. 4] for discrete-time stability notions) to solve an optimization problem appears to be unnatural. This is a consequence of a simple observation: the existence of a maximizer for a real sequence depends on its asymptotic behavior. More precisely, the existence of a maximizer relies on the finiteness of the limit superior and on the existence of a term strictly greater than the limit superior. Hence, tools for studying the asymptotic behavior of the system help in the existence of a peak and its characterization. Although general stability properties can be difficult to obtain, asymptotic stability properties can be easily presented and understood from $\mathcal{KL}$ bounds (e.g., [ATP10] or [NT04]), that is, the norms of the states are globally bounded from above by a $\mathcal{KL}$ function. However, verifying that the $\mathcal{KL}$ function is an upper bound over the norms of the states must be done for all integers, which can be difficult. In contrast, Lyapunov functions are functional certificates for system stability. Some results guarantee the existence of Lyapunov functions: a system is globally asymptotically stable if and only if there exists a Lyapunov function (see, e.g., [Kha02]). Being a Lyapunov function is a timeless property that depends only on the dynamics. In a few advantageous situations, Lyapunov functions can be computed using numerical optimization solvers (see the survey [GH15]).

The paper is organized as follows. Section 2 presents the discrete-time peak computation problems addressed in this paper. In Section 2, we also present a running example that illustrates the techniques developed in this paper. Section 3 recalls the useful results obtained in [Adj25b]. In Section 3, we also provide basic definitions of comparison functions. Then, in Section 4, we develop an approach based on $\mathcal{K}\mathcal{L}$ bounds. In Section 5 we develop the approach using general Lyapunov functions. In these two sections, we explain how to use $\mathcal{K}\mathcal{L}$ and Lyapunov functions to solve a discrete-time peak computation problem. We also apply these techniques to the running example presented in Section 2. Section 6 concludes the paper and discusses future research.

Notations: $\mathbb{R}$ stands for the set of reals, $\mathbb{R}_{+}$ the set of nonnegative reals, $\mathbb{R}^{*}$ the set of nonzero reals and $\mathbb{R}_{+}^{*}$ the set of strictly positive reals. The vector space of vectors of $d$ reals is denoted by $\mathbb{R}^{d}$ . The set of natural integers is denoted by $\mathbb{N}$ whereas $\mathbb{N}^{*}$ denotes the set of nonzero natural integers. The norm $\|\cdot\|$ stands for the Euclidean norm. Finally, $\overline{B}(0,\alpha)$ denotes the closed ball of radius $\alpha$ centered at zero i.e., $\overline{B}(0,\alpha):=\{x\in\mathbb{R}^{d}:\|x\|\leq\alpha\}$ .

2 Problem formulation

2.1 Problem formulation

Let us consider a discrete-time dynamical system $(X^{\mathrm{in}},T)$ on $\mathbb{R}^{d}$ where

•

$X^{\mathrm{in}}$ is the nonempty subset of $\mathbb{R}^{d}$ of initial conditions;
•

$T$ is a nonzero self-map on $\mathbb{R}^{d}$ that updates the state-variable.

The system is autonomous; it evolves without any control, disturbance, or external input. In this paper, we are interested in the reachable values that maximize a given function. Then, given $\varphi:\mathbb{R}^{d}\to\mathbb{R}^{d}$ , we define the discrete-time peak computation problem $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ as follows:

\begin{array}[]{lcl}\displaystyle{\operatorname*{Max}_{x,k}}&&\displaystyle{\varphi(T^{k}(x))}\\ &\text{ s. t.}&\displaystyle{x\in X^{\mathrm{in}},k\in\mathbb{N}}\end{array}

(DPCP)

where $T^{k}$ is the $k$ -fold composition of $T$ if $k$ is not null, and the identity, if $k=0$ .

Like any optimization problem, to solve a problem of form (DPCP), we must compute

•

its optimal value i.e., $\sup\{\varphi(T^{k}(x)):x\in X^{\mathrm{in}},\ k\in\mathbb{N}\}$ ;
•

its optimal solutions i.e., couples $(\overline{x},\overline{k})\in X^{\mathrm{in}}\times\mathbb{N}$ such that

$\varphi(T^{\overline{k}}(\overline{x}))=\sup\{\varphi(T^{k}(x)):x\in X^{\mathrm{in}},\ k\in\mathbb{N}\}.$

An optimal solution $(x,k)$ of $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ is thus composed of an initial condition $x$ leading to a peak and its associated date $k$ of peak realization.

Without loss of generality, we can assume that $\varphi(0)=0$ . Indeed, for the problem $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ , the optimal value is equal to the sum of the optimal values of $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi-\varphi(0))$ and $\varphi(0)$ . Moreover, the optimal solutions of $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ and $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi-\varphi(0))$ are equal.

The optimal value of $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ can be described using a sequence of optimal values. Indeed, we can introduce a static classical optimization problem where $k\in\mathbb{N}$ is fixed:

\begin{array}[]{lcl}\displaystyle{\operatorname*{Max}_{x}}&&\displaystyle{\varphi(T^{k}(x))}\\ &\text{ s. t.}&\displaystyle{x\in X^{\mathrm{in}}}\end{array}

(

P_{k}

)

Then, we introduce the sequence $\nu=(\nu_{k})_{k\in\mathbb{N}}$ defined, for all $k\in\mathbb{N}$ , by:

\nu_{k}:=\sup\{\varphi(T^{k}(x)):x\in X^{\mathrm{in}}\}

(1)

and its supremum:

\nu_{\rm opt}:=\sup\{\nu_{k}:k\in\mathbb{N}\}.

(2)

From these notations, $\nu_{\rm opt}$ is equal to the optimal value of $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ whereas $\nu_{k}$ is the optimal value of the static optimization problem ( $P_{k}$ ). Solving $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ boils down to compute $\nu_{\rm opt}$ , an integer $\overline{k}$ such that $\nu_{\overline{k}}=\nu_{\rm opt}$ and an optimal solution $x\in X^{\mathrm{in}}$ of $(P_{\overline{k}})$ . We concentrate our efforts on the computation of the integer $\overline{k}$ as the computation of the optimal solution $x\in X^{\mathrm{in}}$ of $(P_{\overline{k}})$ relies on an optimization solver (when a suitable one is available). The approach proposed in this paper consists in computing a stopping integer for $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ .

Definition 1 (Stopping integer).

An integer $K\in\mathbb{N}$ is a stopping integer for $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ if, for the sequence $\nu$ defined in Equation (1):

\nu_{\rm opt}=\max\{\nu_{k}:k=0,\ldots,K\}.

If there is no ambiguity, we will simply say that $K$ is a stopping integer for $\nu$ .

Obviously, any stopping integer $K$ for $\nu$ is greater than $\overline{k}$ and $\overline{k}$ is the smallest stopping integer for $\nu$ . Following [Adj25b], if the set $\{j\in\mathbb{N}:\nu_{j}>\limsup_{n\to+\infty}\nu_{n}\}$ is nonempty, a stopping integer for $\nu$ can deduced from the formula:

\min_{\begin{subarray}{c}k\in\mathbb{N}\\ \nu_{k}>h(0)\end{subarray}}\dfrac{\ln(h^{-1}(\nu_{k}))}{\ln(\beta)}

(3)

where $(h,\beta)$ is such that

1.

$h:\mathbb{R}\to\mathbb{R}$ is strictly increasing and continuous on $[0,1]$ ;
2.

$\beta\in(0,1)$ ;
3.

for all $k\in\mathbb{N}$ , $\nu_{k}\leq h(\beta^{k})$ ;
4.

there exists $k\in\mathbb{N}$ such that $\nu_{k}>h(0)$ .

In this paper, we extend the techniques developed in [Adj25a] for stable affine systems and quadratic objective functions to nonlinear stable systems and nonquadratic objective functions. In [Adj25a], we construct $(h,\beta)$ from quadratic Lyapunov functions. In this paper, we propose to construct $(h,\beta)$ from any $\mathcal{K}\mathcal{L}$ stability certificate and any Lyapunov function associated with the system $(X^{\mathrm{in}},T)$ . The interested reader can consult [Kel15] and references therein for complementary readings about those tools from stability theory.

2.2 Practical limitations

From a theoretical perspective, static optimization problems ( $P_{k}$ ) are classical optimization problems; consequently, their study and resolution are relegated to optimization theory. For example, when $\varphi\circ T^{k}$ is concave and $X^{\mathrm{in}}$ is convex, the problem ( $P_{k}$ ) is said to be convex, and numerous methods exist (see e.g., [BTN01, Ber15]), or when $\varphi\circ T^{k}$ is polynomial and $X^{\mathrm{in}}$ a basic semialgebraic set (see e.g., [AL11, Las15]), the problem ( $P_{k}$ ) falls into the class of polynomial optimization problems.

In practice, the most critical challenge for the computation of $\nu_{k}$ lies before the optimization procedure. Indeed, when $T$ is nonlinear, it is difficult to obtain a closed form for $T^{k}$ . For example, for logistic sequences, closed forms are only known for particular cases (see e.g., [GRR10]). Some specific difference equations or systems require intensive efforts to obtain closed forms (see e.g., [Els12, HR18, Ste14] and references therein). We could use instead at least an exact formulation of $T^{k}(X^{\mathrm{in}})$ when $X^{\mathrm{in}}$ is an infinite set. However, its computation is limited in practice. For example, in [MHL15], the authors approximate the polynomial image of a basic semialgebraic set using a sequence of semidefinite programs. The authors obtain the convergence in $L^{1}$ sense of the sequence of approximations to the polynomial image of the set.

Hopefully, when $T$ is nonlinear, there exist some situations making the computation of $T^{k}(X^{\mathrm{in}})$ ”easier” in practice. For example, if $X^{\mathrm{in}}$ is a finite set or $T$ is conjugate to a linear dynamics. Conjugate¹¹1In the literature, the term topologically conjugate is employed, but in this context, the bijection and its inverse are required to be continuous. In our case, continuity is not mandatory from an optimization perspective. means that there exists a bijection $B$ and a linear map identified with its matrix $A$ such that for all $x\in\mathbb{R}^{d}$ , $T(x)=B^{-1}(AB(x))$ . In this case, we simply have for all $x\in\mathbb{R}^{d}$ for all $k\in\mathbb{N}$ , $T^{k}(x)=B^{-1}(A^{k}B(x))$ .

In this paper, the theoretical part does not require finiteness concerning $T$ or $X^{\mathrm{in}}$ . We only require the finiteness of $\nu_{k}$ . In our numerical illustrations, to concentrate on the novelty and avoid entering too deep into optimization tools, we will only consider finite initial condition sets $X^{\mathrm{in}}$ . The consideration of more general initial condition sets in practice will be addressed in future works.

The developments made in this paper require real-valued sequences; hence the only assumption made in this paper is as follows:

Assumption 1.

For all $k\in\mathbb{N},\ \nu_{k}=\sup\left\{\varphi(T^{k}(x)):x\in X^{\mathrm{in}}\right\}$ is finite.

A simple situation where Assumption 1 holds when $X^{\mathrm{in}}$ is a bounded set, $T$ maps from bounded sets to bounded sets, and $\varphi$ is upper semicontinuous.

2.3 Running example

Throughout this paper, we experiment with our main tools on a nonlinear system found in [LHK14a]. The dynamics is defined as:

\mathsf{H}:\mathbb{R}^{2}\ni x\mapsto\dfrac{1}{8}\begin{pmatrix}\|x\|^{2}-1&-1\\ 1&\|x\|^{2}-1\end{pmatrix}x

(4)

To write a discrete-time peak computation problem, we also need an initial conditions set and an objective function. Before discussing the choice of the initial conditions set and the objective functions, it should be noted that starting outside a specific ball makes the norm of the state variable blow up. First, by a simple calculus, we obtain, for all $z\in\mathbb{R}^{2}$ :

\|\mathsf{H}(x)\|^{2}=\dfrac{1}{64}\|x\|^{2}\left(1+(\|x\|^{2}-1)^{2}\right).

Then, by introducing the following two functions:

\mathfrak{f}:\mathbb{R}_{+}\ni s\to\dfrac{1}{64}s(1+(s-1)^{2})\ \text{ and }\mathfrak{g}:\mathbb{R}_{+}\ni s\to\left\{\begin{array}[]{cr}\dfrac{\mathfrak{f}(s)}{s}&\text{if }s>0\\ \\ \dfrac{1}{32}&\text{if }s=0\end{array}\right.,

(5)

we get $\|\mathsf{H}(x)\|^{2}=\mathfrak{f}(\|x\|^{2})$ for all $x\in\mathbb{R}^{2}$ . Now as $\|\mathsf{H}(x)\|^{2}/\|x\|^{2}=\mathfrak{g}(\|x\|^{2})$ for all nonzero $x\in\mathbb{R}^{2}$ and since the assertion ( $\mathfrak{g}(s)<1$ and $s>0$ ) is equivalent to $s\in(0,\sqrt{63}+1)$ , we conclude that $\|\mathsf{H}(x)\|<\|x\|$ if and only if $\|x\|^{2}\in(0,\sqrt{63}+1)$ . Hence, we introduce:

\overline{\rho}:=\sqrt{63}+1\simeq 8.9373.

(6)

Finally, we have for all $r\in(0,\overline{\rho})$ , $\mathsf{H}(\overline{B}(0,\sqrt{r}))\subseteq\overline{B}(0,\sqrt{r})$ .

In future examples, an initial conditions set will be a subset $\mathsf{X}$ of $\mathbb{R}^{2}$ satisfying

\sup\{\|x\|:x\in\mathsf{X}\}\in(0,\sqrt{\overline{\rho}}).

(7)

The exact definition of $\mathsf{X}$ will depend on the statements that we want to highlight.

An objective function is also required. In the examples, we will analyze the behavior of each coordinate separately; thus, the objective functions are the coordinate functions:

\pi_{1}:\mathbb{R}^{2}\ni x=(x_{1},x_{2})^{\intercal}\mapsto x_{1}\text{ and }\pi_{2}:\mathbb{R}^{2}\ni x=(x_{1},x_{2})^{\intercal}\mapsto x_{2}.

(8)

For an initial condition set $\mathsf{X}$ satisfying the condition (7), we will define two discrete-time peak computation problems $\operatorname{DPCP}(\mathsf{X},\mathsf{H},\pi_{1})$ and $\operatorname{DPCP}(\mathsf{X},\mathsf{H},\pi_{2})$ . The optimal value of $\operatorname{DPCP}(\mathsf{X},\mathsf{H},\pi_{1})$ is written as

\omega_{\mathsf{X},{\rm opt}}^{1}:=\sup_{k\in\mathbb{N}}\omega_{\mathsf{X},k}^{1}\text{ where }\omega_{\mathsf{X},k}^{1}:=\sup_{x\in\mathsf{X}}\pi_{1}(\mathsf{H}^{k}(x)).

(9)

The optimal value of $\operatorname{DPCP}(\mathsf{X},\mathsf{H},\pi_{2})$ is written similarly:

\omega_{\mathsf{X},{\rm opt}}^{2}:=\sup_{k\in\mathbb{N}}\omega_{\mathsf{X},k}^{2}\text{ where }\omega_{\mathsf{X},k}^{2}:=\sup_{x\in\mathsf{X}}\pi_{2}(\mathsf{H}^{k}(x)).

(10)

The condition (7) for $\mathsf{X}$ ensures that for all $k\in\mathbb{N}$ and all $x\in\mathsf{X}$ , $\pi_{1}(\mathsf{H}^{k}(x))\leq\sup\{\|x\|:x\in\mathsf{X}\}$ and $\pi_{2}(\mathsf{H}^{k}(x))\leq\sup\{\|x\|:x\in\mathsf{X}\}$ . This guarantees that Assumption 1 holds for the sequences

\omega_{\mathsf{X}}^{1}:=(\omega_{\mathsf{X},k}^{1})_{k\in\mathbb{N}}\text{ and }\omega_{\mathsf{X}}^{2}:=(\omega_{\mathsf{X},k}^{2})_{k\in\mathbb{N}}.

(11)

3 Preliminary results

Before considering the main results of this paper, we recall some useful theoretical results. First, in Subsection 3.1, we bring details about the formula (3) obtained in [Adj25b]. Second, in Subsection 3.2, we introduce useful material about comparison functions, which constitute the underlying tool behind $\mathcal{K}\mathcal{L}$ and Lyapunov stability.

3.1 Results on the supremum of a real sequence

The developments made in [Adj25b] concern general real sequences, and in this subsection, we consider $u\in\mathbb{R}^{\mathbb{N}}$ for which we aim to compute:

\sup_{n\in\mathbb{N}}u_{n}\text{ and }k\in\mathbb{N}\text{ s.t. }u_{k}=\sup_{n\in\mathbb{N}}u_{n}

(12)

3.1.1 Notations and basic results

We introduce the subset of $\mathbb{R}^{\mathbb{N}}$ consisting of sequences bounded from above:

\Lambda:=\{u=(u_{0},u_{1},\ldots)\in\mathbb{R}^{\mathbb{N}}:\sup_{n\in\mathbb{N}}u_{n}<+\infty\}.

For an element of $\Lambda$ , we are interested in computing the supremum of its terms.

Proposition 1.

$u\in\Lambda\iff\displaystyle{\limsup_{n\to+\infty}u_{n}\in\mathbb{R}\cup\{-\infty\}}$ .

For $u\in\Lambda$ , we define $\operatorname{Argmax}(u):=\{k\in\mathbb{N}:u_{k}=\displaystyle{\sup_{n\in\mathbb{N}}u_{n}}\}$ and we introduce, for $u\in\Lambda$ , the two sets of ranks:

{\mathrm{R}}_{u}^{s}:=\left\{k\in\mathbb{N}:u_{k}>\limsup_{n\to+\infty}u_{n}\right\}\ \text{ and }\ \Delta^{s}_{u}:=\left\{k\in\mathbb{N}:\max_{0\leq j\leq k}u_{j}>\sup_{j>k}u_{j}\right\}

(13)

and we define

\mathbf{K}^{s}_{u}=\inf\Delta^{s}_{u}.

(14)

We recall that the infimum of the empty set is equal to $+\infty$ . Hence, $\mathbf{K}^{s}_{u}<+\infty$ if and only if $\Delta^{s}_{u}\neq\emptyset$ . Furthermore, if $\Delta^{s}_{u}$ is nonempty, then $\mathbf{K}^{s}_{u}\in\Delta^{s}_{u}$ .

Proposition 2.

Let $u\in\Lambda$ . The following assertions hold:

1.

$\Delta^{s}_{u}\neq\emptyset\iff{\mathrm{R}}_{u}^{s}\neq\emptyset$ ;
2.

$\Delta^{s}_{u}=\emptyset\iff\sup_{k\in\mathbb{N}}u_{k}=\limsup_{n\to+\infty}u_{n}$ ;
3.

If $\Delta^{s}_{u}\neq\emptyset$ then $\mathbf{K}^{s}_{u}=\max\operatorname{Argmax}(u)$ .

3.1.2 A formula based on pairs of strictly increasing continuous functions and convergent geometric sequences

In this subsection, we present how to construct the formula (3). All details can be found in [Adj25b]. The key tool to compute the supremum of a sequence $u\in\Lambda$ is the existence of a particular sequence $(h(\beta^{k}))_{k\in\mathbb{N}}$ that is an upper bound on $u$ . The particularity comes from the fact that $h$ is strictly increasing and continuous on $[0,1]$ and $\beta\in(0,1)$ . We then introduce the following set of real functions:

\Omega([0,1]):=\{h:\mathbb{R}\mapsto\mathbb{R}:\text{ is strictly increasing and continuous on }[0,1]\}.

It should be noted that we can define a function that is strictly increasing and continuous on $[0,1]$ on a set containing $[0,1]$ and then extend it as we want on the entire real line. Therefore, sometimes, we will partially define elements of $\Omega([0,1])$ on a set greater than $[0,1]$ but not everywhere on the real line.

We also introduce, for $u\in\mathbb{R}^{\mathbb{N}}$ the following sets:

\mathbb{\Gamma}(u):=\{(h,\beta)\in\Omega([0,1])\times(0,1):u_{k}\leq h(\beta^{k}),\ \forall\,k\in\mathbb{N}\}

and

\mathbb{\Gamma}_{\rm fun}(u):=\{h\in\Omega([0,1]):\exists\,\beta\in(0,1)\text{ s.t. }(h,\beta)\in\mathbb{\Gamma}(u)\}\kern 5.0pt.

Finally, we introduce for $u\in\mathbb{R}^{\mathbb{N}}$ and $h\in\mathbb{\Gamma}_{\rm fun}(u)$ :

\mathbb{\Gamma}_{\rm sc}(u,h):=\{\beta\in(0,1):(h,\beta)\in\mathbb{\Gamma}(u)\}\kern 5.0pt.

As all elements of $\mathbb{\Gamma}_{\rm fun}(u)$ are strictly increasing and continuous on $[0,1]$ , they have an inverse on $[0,1]$ . For the sake of simplicity, we will simply denote by $h^{-1}$ the inverse of $h\in\Omega([0,1])$ . Moreover, the fact that the elements of $\mathbb{\Gamma}_{\rm fun}(u)$ are strictly increasing and continuous allows for simple properties.

Proposition 3.

Let $u\in\Lambda$ . Then :

1.

For all $h\in\mathbb{\Gamma}_{\rm fun}(u)$ , we have $\limsup_{k\to+\infty}u_{k}\leq h(0)$ ;
2.

For all $k\in\mathbb{N}^{*}$ , $u_{k}<h(1)$ and $u_{0}\leq h(1)$ ;
3.

If there exists $h\in\mathbb{\Gamma}_{\rm fun}(u)$ such that $u_{0}=h(1)$ then $u_{0}=\max_{k\in\mathbb{N}}u_{k}$ .

We can also fully characterize the set $\Lambda$ from the nonemptiness of $\mathbb{\Gamma}(u)$ .

Proposition 4.

$u\in\Lambda$ if and only if $\mathbb{\Gamma}(u)\neq\emptyset$ .

In the formula (3), the natural logarithm is defined when $0<h^{-1}(\nu_{k}))$ , which is the same as $h(0)<\nu_{k}$ . Then, we must ensure that the function $h\in\mathbb{\Gamma}(u)$ satisfies $h(0)<\nu_{k}$ for some $k\in\mathbb{N}$ . This provides the notion of usefulness.

Definition 2 (Useful strictly increasing continuous functions).

Let $u\in\Lambda$ such that ${\mathrm{R}}_{u}^{s}\neq\emptyset$ . A function $h\in\mathbb{\Gamma}_{\rm fun}(u)$ is said to be useful for $u$ if the set

\mathcal{S}(u,h):=\{k\in\mathbb{N}:u_{k}>h(0)\}

(15)

is nonempty. By extension, $(h,\beta)\in\mathbb{\Gamma}(u)$ is useful for $u$ if $h$ is useful for $u$ .

From the first statement of Proposition 3, if $h$ is useful for $u$ , there exists $k\in\mathbb{N}$ such that $u_{k}>h(0)\geq\limsup_{n\to+\infty}u_{n}$ i.e., ${\mathrm{R}}_{u}^{s}\neq\emptyset$ .

The following result aims to prove that there exists an optimal useful affine function for $u$ when ${\mathrm{R}}_{u}^{s}\neq\emptyset$ .

Theorem 1 (Existence of a useful optimal affine function).

Let $u\in\Lambda$ such that ${\mathrm{R}}_{u}^{s}\neq\emptyset$ . Then, there exist $a>0$ , $b\in(0,1)$ and $c\in\mathbb{R}$ such that:

1.

$\{k\in\mathbb{N}:u_{k}>c\}\neq\emptyset$ ;
2.

$u_{k}\leq ab^{k}+c$ for all $k\in\mathbb{N}$ ;
3.

$u_{\mathbf{K}^{s}_{u}}=ab^{\mathbf{K}^{s}_{u}}+c$ .

Corollary 1.

Let $u\in\Lambda$ such that ${\mathrm{R}}_{u}^{s}\neq\emptyset$ . Then, there exists a pair $(h,\beta)\in\mathbb{\Gamma}(u)$ useful for $u$ such that $u_{\mathbf{K}^{s}_{u}}=h(\beta^{\mathbf{K}^{s}_{u}})$ .

Proposition 5.

Let $u\in\Lambda$ . Then, ${\mathrm{R}}_{u}^{s}\neq\emptyset$ if and only if there exists $h\in\mathbb{\Gamma}_{\rm fun}(u)$ useful for $u$ .

Theorem 1 provides a theoretical result and to have in hand an optimal function $h\in\mathbb{\Gamma}_{\rm fun}(u)$ useful for $u$ is very unlikely to happen. However, if we have any function $h\in\mathbb{\Gamma}_{\rm fun}(u)$ , we can produce a stopping integer for $u$ which is, in fact, an upper bound of $\mathbf{K}^{s}_{u}$ . To compute it, for $u\in\mathbb{R}^{\mathbb{N}}$ , we introduce the function $\mathfrak{F}_{u}:\mathbb{N}\times\Omega([0,1])\times(0,1)\mapsto\mathbb{R}\cup\{+\infty\}$ defined for all $k\in\mathbb{N}$ , $h\in\Omega([0,1])$ and $\beta\in(0,1)$ by:

\mathfrak{F}_{u}(k,h,\beta):=\left\{\begin{array}[]{lr}\dfrac{\ln(h^{-1}(u_{k}))}{\ln(\beta)}&\text{ if }(h,\beta)\in\mathbb{\Gamma}(u)\text{ and }k\in\mathcal{S}(u,h)\\ +\infty&\text{ otherwise}\end{array}\right.

(16)

3.1.3 Properties of $\mathfrak{F}_{u}$ and the computation of the supremum of a sequence

The function defined in (16) has useful properties for computing a stopping integer for $u$ as shown in Theorem 2. To obtain the results of Theorem 2, we need auxiliary results.

Proposition 6.

Let us take a pair $(h,\beta)\in\mathbb{\Gamma}(u)$ useful for $u$ and let $k\in\mathcal{S}(u,h)$ . The following statements are true:

1.

$\mathfrak{F}_{u}(k,h,\beta)$ is well-defined and strictly positive if $u_{0}<h(1)$ and null if $k=0$ and $u_{0}=h(1)$ ;
2.

$\lfloor\mathfrak{F}_{u}(k,h,\beta)\rfloor+1=\min\{j\in\mathbb{N}:h(\beta^{j})<u_{k}\}=\min\{j\in\mathbb{N}:\beta^{j}<h^{-1}(u_{k})\}$ ;
3.

$\mathfrak{F}_{u}(k,h,\beta)\geq k$ ;
4.

For all $j\in\mathbb{N}$ , $j>\mathfrak{F}_{u}(k,h,\beta)$ , $u_{j}<u_{k}$ ;
5.

Let $j\in\mathcal{S}(u,h)$ . If $u_{j}\leq u_{k}$ then $\mathfrak{F}_{u}(k,h,\beta)\leq\mathfrak{F}_{u}(j,h,\beta)$ .

Proposition 7.

Let $u\in\Lambda$ such that ${\mathrm{R}}_{u}^{s}\neq\emptyset$ . The following properties hold:

1.

Let $h\in\mathbb{\Gamma}_{\rm fun}(u)$ and $k\in\mathcal{S}(u,h)$ . Let $\beta,\beta^{\prime}\in\mathbb{\Gamma}_{\rm sc}(u,h)$ such that $\beta\leq\beta^{\prime}$ . Then $\mathfrak{F}_{u}(k,h,\beta)\leq\mathfrak{F}_{u}(k,h,\beta^{\prime})$ .
2.

Let $g,h\in\mathbb{\Gamma}_{\rm fun}(u)$ . Let $k\in\mathcal{S}(u,\min\{g,h\})$ . Let $\beta\in\mathbb{\Gamma}_{\rm sc}(u,\min\{g,h\})$ . Then $\mathfrak{F}_{u}(k,\min\{g,h\},\beta)\leq\min\{\mathfrak{F}_{u}(k,g,\beta),\mathfrak{F}_{u}(k,h,\beta)\}$ .

The first statement of Proposition 7 can be read as follows: we must choose the smallest possible $\beta\in\mathbb{\Gamma}_{\rm sc}(u,h)$ to reduce the approximation gap. The second statement has a similar meaning in a functional sense: if we have several functions in $\mathbb{\Gamma}_{\rm fun}(u)$ , we must consider the minimum functions to reduce the overapproximation gap.

Proposition 8.

Let $u\in\Lambda$ and $(h,\beta)\in\mathbb{\Gamma}(u)$ . Then for all $j\in\mathbb{N}$ , $\mathbf{K}^{s}_{u}\leq\lfloor\mathfrak{F}_{u}(j,h,\beta)\rfloor$ . Moreover, if $h$ is useful for $u$ , we have:

\min_{k\in\mathcal{S}(u,h)}\mathfrak{F}_{u}(k,h,\beta)=\mathfrak{F}_{u}(\mathbf{K}^{s}_{\nu},h,\beta)\kern 5.0pt.

We can go further than the results of Proposition 8 to obtain a solution to problem (12).

Theorem 2 (Solution for (12)).

Let $u\in\Lambda$ with ${\mathrm{R}}_{u}^{s}\neq\emptyset$ . Let $(h,\beta)\in\mathbb{\Gamma}(u)$ be useful for $u$ and let $k\in\mathcal{S}(u,h)$ . Then :

\max_{n\in\mathbb{N}}u_{n}=\max\{u_{k}:k=0,\ldots,\lfloor\mathfrak{F}_{u}(\mathbf{K}^{s}_{u},h,\beta)\rfloor\}.

Theorem 3 (Formula optimality).

For all $u\in\mathbb{R}^{\mathbb{N}}$ , we have the following formula:

\mathbf{K}^{s}_{u}=\inf_{(h,\beta)\in\Gamma(u)}\inf_{k\in\mathcal{S}(u,h)}\mathfrak{F}_{u}(k,h,\beta)=\inf_{(h,\beta)\in\Gamma(u)}\inf_{k\in\mathcal{S}(u,h)}\dfrac{\ln(h^{-1}(u_{k}))}{\ln(\beta)}

and the $\inf$ can be replaced by $\min$ when ${\mathrm{R}}_{u}^{s}\neq\emptyset$ .

We conclude this subsection with a summary in the form of an algorithm (Algorithm 1) to solve the problem (12).

Input :

u\in\Lambda

with

{\mathrm{R}}_{u}^{s}\neq\emptyset

and

(h,\beta)\in\mathbb{\Gamma}(u)

useful

Output :

u_{\rm opt}

and

\mathbf{K}_{u}=\min\operatorname{Argmax}(u)

2 begin

k=0

;

K=+\infty

u_{\rm max}=-\infty

k_{\rm max}=0

4 while $k\leq K$ do

5 if $k\in\mathcal{S}(u,h)$ then

6 if $u_{\rm max}<u_{k}$ then

K=\lfloor\mathfrak{F}_{u}(k,h,\beta)\rfloor

u_{\rm max}=u_{k}

k_{\rm max}=k

k=k+1

u_{\rm opt}=u_{\rm max}

\mathbf{K}_{u}=k_{\rm max}

Algorithm 1 Resolution of the problem described in (12) with a useful

(h,\beta)\in\mathbb{\Gamma}(u)

Algorithm 1 terminates as $h$ is supposed to be useful i.e., $\mathcal{S}(u,h)\neq\emptyset$ making $\mathfrak{F}_{u}(k,h,\beta)$ finite for all $k\in\mathcal{S}(u,h)$ . We can also improve $\mathfrak{F}_{u}(k,h,\beta)$ when the variable $u_{\rm max}$ is updated. Corollary 1 ensures that a useful function $h$ exists.

Returning to the discrete-time peak computation problem (DPCP), to compute a stopping integer for $\nu$ (defined in (1)), we need to construct a couple $(h,\beta)$ useful for $\nu$ .

Problem 1.

Construct a couple $(h,\beta)\in\mathbb{\Gamma}(\nu)$ useful for $\nu$ when ${\mathrm{R}}_{\nu}^{s}\neq\emptyset$ .

The next sections of the paper focus on classical tools from dynamical systems stability theory, such as $\mathcal{K}\mathcal{L}$ certificate and Lyapunov functions. To properly define these tools, we need to introduce the concept of comparison functions.

3.2 Elements of comparison functions

The global asymptotic stability of discrete-time systems can be studied by means of comparison functions (see e.g., [GGLW14]). For a comprehensive literature review on comparison functions, interested readers can refer to [Kel14]. In our context, as suggested in Subsection 3.1, the problem (DPCP) can be studied by analyzing the limit superior of the sequence $\nu$ defined in (1). Comparison functions will be used to study its limit superior.

Definition 3 ( $\mathcal{K}$ / $\mathcal{K}_{\infty}$ functions classes).

A function $\alpha:[0,a)\mapsto\mathbb{R}_{+}$ for some $a>0$ belongs to $\mathcal{K}$ if $\alpha$ is strictly increasing and continuous on $[0,a)$ , and $\alpha(0)=0$ . If moreover, $a=+\infty$ and $\lim_{x\to+\infty}\alpha(x)=+\infty$ , $\alpha$ is said to belong to $\mathcal{K}_{\infty}$ .

Definition 4 ( $\mathcal{L}$ functions class).

A function $\sigma:\mathbb{R}_{+}\to\mathbb{R}_{+}$ belongs to $\mathcal{L}$ if it is continuous, decreasing, and $\lim_{x\to+\infty}\sigma(x)=0$ .

Definition 5 ( $\mathcal{K}\mathcal{L}$ functions class).

A function $\gamma:\mathbb{R}_{+}\times\mathbb{R}_{+}\mapsto\mathbb{R}_{+}$ belongs to $\mathcal{K}\mathcal{L}$ if for all $t\in\mathbb{R}_{+}$ , $s\mapsto\gamma(s,t)$ belongs to $\mathcal{K}$ and if for all $s\in\mathbb{R}_{+}$ , $t\mapsto\gamma(s,t)$ belongs to $\mathcal{L}$ .

The class $\mathcal{K}$ is included in $\Omega([0,1])$ but $\mathcal{K}$ functions are strictly positive except at 0, where they are null. Hence, $h\in\mathcal{K}\cap\mathbb{\Gamma}_{\rm fun}(\nu)$ is useful for $\nu$ if at least one term $\nu_{k}$ is strictly positive. Thus, in this subsection, Assumption 2 must be satisfied

Assumption 2.

There exist $k\in\mathbb{N}$ and $x\in X^{\mathrm{in}}$ satisfying $\varphi(T^{k}(x))>0$ .

Let us consider the set of positive definite functions on a subset $X\subseteq\mathbb{R}^{d}$ containing 0:

\operatorname{PD}(X):=\{f:X\mapsto\mathbb{R}_{+}:f(x)=0\iff x=0\}.

that is the set of nonnegative functions on $X$ null at 0 and nowhere else.

We also need useful results linking positive definite functions and comparison functions. A proof can be found in [Kha02] (extensions can be found in [Adj24]).

Proposition 9 (Lemma 4.3/Appendix C.4 [Kha02]).

Let $X\subseteq\mathbb{R}^{d}$ containing 0 in its interior. Let $f$ be a continuous function in $\operatorname{PD}(X)$ . Let $r>0$ such that $\overline{B}(0,r)\subseteq X$ . Then, for all $x\in\overline{B}(0,r)$ , we have

\underline{\alpha}_{f}(\|x\|)\leq f(x)\leq\overline{\alpha}^{f}(\|x\|)

(17)

where:

\underline{\alpha}_{f}:[0,r)\ni s\mapsto\inf_{s\leq\|x\|\leq r}f(x)\quad\text{ and }\quad\overline{\alpha}^{f}:[0,r)\ni s\mapsto\sup_{\|x\|\leq s}f(x)

(18)

and $\underline{\alpha}_{f},\overline{\alpha}^{f}\in\mathcal{K}$ .

If, moreover, $X=\mathbb{R}^{d}$ and $f(x)$ tends to $+\infty$ as $\|x\|$ tends to $+\infty$ , then $\underline{\alpha}_{f},\overline{\alpha}^{f}\in\mathcal{K}_{\infty}$ and the inequality (17) holds for all $x\in\mathbb{R}^{d}$ .

Even if $\|\cdot\|$ represents the Euclidean norm, the result holds for any norm in $\mathbb{R}^{d}$ as they are equivalent.

4 Solving problem 1 from $\mathcal{K}\mathcal{L}$ bounds

In this section, we return to the resolution of $\operatorname{DPCP}(X^{\mathrm{in}},T,\varphi)$ defined in (DPCP). We recall that the data are the following:

•

an initial conditions set (nonempty) $X^{\mathrm{in}}\subseteq\mathbb{R}^{d}$ ;
•

a nonzero map $T:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ ;
•

a function $\varphi:\mathbb{R}^{d}\mapsto\mathbb{R}$ such that $\varphi(0)=0$ .

We recall that we want to compute $\nu_{\rm opt}=\sup\{\nu_{k}:k\in\mathbb{N}\}$ where $\nu_{k}=\sup\{\varphi(T^{k}(x):x\in X^{\mathrm{in}}\}$ . To use the results of Section 3 with the sequence $\nu=(\nu_{k})_{k\in\mathbb{N}}$ , we suppose that Assumption 1 holds.

To simplify the notation of the supremum of an objective function $f:\mathbb{R}^{d}\mapsto\mathbb{R}$ over a nonempty set $X$ , we introduce the following new notation:

\overline{f_{X}}:=\sup\{f(x):x\in X\}

and the set of functions that are bounded from above on $X^{\mathrm{in}}$ :

\operatorname{Fin}\left(X^{\mathrm{in}}\right):=\{f:\mathbb{R}^{d}\mapsto\mathbb{R}:\overline{f_{X^{\mathrm{in}}}}<+\infty\}

With these notations, $\nu_{k}=\overline{(\varphi\circ T^{k})_{X^{\mathrm{in}}}}$ and Assumption 1 is the same as for all $k\in\mathbb{N}$ , $\varphi\circ T^{k}\in\operatorname{Fin}\left(X^{\mathrm{in}}\right)$ .

In Subsection 4.1, we show how to solve Problem 1 from a $\mathcal{K}\mathcal{L}$ upper bound of the images of the reachable values of the dynamical system $(X^{\mathrm{in}},T)$ . Then, with some additional assumptions, we show that we can also solve Problem 1 from the classical $\mathcal{K}\mathcal{L}$ upper bound. Classical means that the upper bound is a $\mathcal{K}\mathcal{L}$ upper bound of the norm of the reachable values. The existence of such an upper bound is equivalent to the global asymptotic stability of the system. In Subsection 4.2, we apply the theoretical results obtained in Subsection 4.1 to the running example introduced in Subsection 2.3.

4.1 Theoretical constructions from $\mathcal{K}\mathcal{L}$ functions

We propose to combine $\mathcal{K}\mathcal{L}$ upper bounds with the celebrated result obtained by Sontag (recalled in Lemma 1) to construct a function $h\in\mathbb{\Gamma}_{\rm fun}(\nu)$ such that $e^{-1}\in\mathbb{\Gamma}_{\rm sc}(\nu,h)$ .

Lemma 1 (Proposition 7 of [Son98]).

For all $\gamma\in\mathcal{K}\mathcal{L}$ , there exists $\theta_{1},\theta_{2}\in\mathcal{K}_{\infty}$ such that for all $s,t\in\mathbb{R}_{+}$ , $\gamma(s,t)\leq\theta_{1}(\theta_{2}(s)e^{-t})$ .

In Subsection 3.1, we saw the importance of studying the limit superior of a real sequence to compute its maximal term. In general, this study is difficult. Here, we can exploit the particular structure of the sequence $\nu$ and the fact that its terms originate from the reachable values of a dynamical system. The limit superior of $\nu$ can be determined from the $\mathcal{K}\mathcal{L}$ upper bounds. Moreover, this functional approach provides natural functions $h\in\mathbb{\Gamma}_{\rm fun}(\nu)$ .

Theorem 4 (Relaxed $\mathcal{K}\mathcal{L}$ construction).

Assume that there exist $\gamma\in\mathcal{K}\mathcal{L}$ and a nonnegative function $\psi\in\operatorname{Fin}\left(X^{\mathrm{in}}\right)$ such that $\overline{\psi_{X^{\mathrm{in}}}}>0$ satisfying for all $x\in X^{\mathrm{in}}$ and for all $k\in\mathbb{N}$

\varphi(T^{k}(x))\leq\gamma(\psi(x),k)\kern 5.0pt.

(19)

Then:

1.

$\limsup_{n\to+\infty}\nu_{n}\leq 0$ and if, moreover, Assumption 2 holds then ${\mathrm{R}}_{\nu}^{s}\neq\emptyset$ ;
2.

there exists $h\in\mathcal{K}_{\infty}$ s.t. $(h,e^{-1})\in\mathbb{\Gamma}(\nu)$ and, if, moreover, Assumption 2 holds then $h$ is useful for $\nu$ .

Proof.

1. For all $k$ , the function $s\mapsto\gamma(s,k)$ is strictly increasing and then for all $x\in X^{\mathrm{in}}$ , for all $k\in\mathbb{N}$ , $\gamma(\psi(x),k)\leq\gamma(\overline{\psi_{X^{\mathrm{in}}}},k)$ . Taking the supremum over $X^{\mathrm{in}}$ , we have $\nu_{k}\leq\gamma(\overline{\psi_{X^{\mathrm{in}}}},k)$ . We conclude by taking the $\limsup$ as $k$ tends to $+\infty$ and recalling that $\gamma(\overline{\psi_{X^{\mathrm{in}}}},k)$ tends to 0 (as $k$ tends to $+\infty$ as $t\mapsto\gamma(s,t)\in\mathcal{L}$ for all $s\in\mathbb{R}_{+}$ ). Finally, under Assumption 2, there exists $k\in\mathbb{N}$ , such that $\nu_{k}>0\geq\limsup_{k\to+\infty}\nu_{k}$ .

2. This is a direct consequence of Sontag’s result (Lemma 1 here). Indeed, there exist $\theta_{1},\theta_{2}\in\mathcal{K}_{\infty}$ such that for all $x\in X^{\mathrm{in}}$ and for all $k\in\mathbb{N}$ , $\varphi(T^{k}(x))\leq\gamma(\psi(x),k)\leq\theta_{1}(\theta_{2}(\psi(x))e^{-k})$ . Then $\nu_{k}\leq h(e^{-k}):=\sup_{x\in X^{\mathrm{in}}}\theta_{1}(\theta_{2}(\psi(x)e^{-k}))$ . Then, as $\theta_{1}$ and $\theta_{2}$ are increasing and continuous, $h$ can also be written $\mathbb{R}_{+}\ni y\mapsto\theta_{1}(\theta_{2}(\overline{\psi_{X^{\mathrm{in}}}}y))$ . The function $h$ is thus the composition of $\theta_{1}$ , $\theta_{2}$ and $y\mapsto\overline{\psi_{X^{\mathrm{in}}}}y$ that belong to $\mathcal{K}_{\infty}$ (the third as $\overline{\psi_{X^{\mathrm{in}}}}$ ) and thus belongs to $\mathcal{K}_{\infty}$ . Finally, under Assumption 2, there exists $k\in\mathbb{N}$ such that $\nu_{k}>0=h(0)$ and so $h$ is useful in this case.

∎

Classically i.e., when $\varphi=\|\cdot\|$ , the inequality $\varphi(T^{k}(x))\leq\gamma(\psi(x),k)$ (for $\psi=\|\cdot\|$ ) is true for all $x\in\mathbb{R}^{d}$ and all $k\in\mathbb{N}$ if and only if the system $x_{k+1}=T(x_{k}),x_{0}\in\mathbb{R}^{d}$ is said to be uniformly global asymptotic stability (UGAS) (see for example [NT04, Prop. 1] or [ATP10, Th. 2]. This implies that $x_{k}$ tends to 0 as $k$ tends to $+\infty$ . Thus, with a general function $\varphi$ , we obtain one-sided information on the asymptotic behavior of the dynamics. However, from Proposition 9 when $\varphi$ is continuous and $X^{\mathrm{in}}$ is bounded, the classical $\mathcal{K}\mathcal{L}$ certificate of stability is sufficient to construct a function $h\in\mathbb{\Gamma}_{\rm fun}(\nu)$ such that $e^{-1}\in\mathbb{\Gamma}_{\rm sc}(\nu,h)$ .

Theorem 5 (Classical $\mathcal{K}\mathcal{L}$ construction).

Suppose that $\varphi$ is continuous and $X^{\mathrm{in}}$ is bounded and not reduced to $\{0\}$ . Assume that there exists $\gamma\in\mathcal{K}\mathcal{L}$ satisfying for all $x\in X^{\mathrm{in}}$ and for all $k\in\mathbb{N}$ :

\|T^{k}(x)\|\leq\gamma(\|x\|,k)\kern 5.0pt.

(20)

Then:

1.

$\limsup_{n\to+\infty}\nu_{n}\leq 0$ and if, moreover, Assumption 2 holds then ${\mathrm{R}}_{\nu}^{s}\neq\emptyset$ ;
2.

there exists $h\in\mathcal{K}_{\infty}$ s.t. $(h,e^{-1})\in\mathbb{\Gamma}(\nu)$ and, if, moreover, Assumption 2 holds then $h$ is useful for $\nu$ .

Proof.

It suffices to obtain an inequality of the form of (19) from the inequality (20) and then to use Theorem 4.

If $\varphi$ is continuous, then from Proposition 9, as $\overline{\varphi}:\mathbb{R}^{d}\ni x\mapsto\max\{\|x\|,\varphi(x)\}$ is continuous, belongs to $\operatorname{PD}(\mathbb{R}^{d})$ (as $\varphi(0)=0$ ) and satisfies $\overline{\varphi}(x)$ tends to $+\infty$ as $\|x\|$ tends to $+\infty$ . Hence, we have $\varphi\leq\overline{\varphi}\leq\overline{\alpha}^{\overline{\varphi}}\circ\|\cdot\|$ with $\overline{\alpha}^{\overline{\varphi}}\in\mathcal{K}_{\infty}$ . Then, from inequality (20), we obtain $\varphi(T^{k}(x))\leq\overline{\alpha}^{\overline{\varphi}}(\|T^{k}x\|)\leq\overline{\alpha}^{\overline{\varphi}}(\gamma(\|x\|,k))$ for all $x\in X^{\mathrm{in}}$ . Thus the inequality (19) holds with $\gamma:=\overline{\alpha}^{\overline{\varphi}}\circ\gamma\in\mathcal{K}\mathcal{L}$ and $\psi:=\|\cdot\|\in\operatorname{Fin}\left(X^{\mathrm{in}}\right)$ that verifies $\overline{\psi_{X^{\mathrm{in}}}}>0$ (as $X^{\mathrm{in}}$ bounded and non reduced to $\{0\}$ ). We conclude from Theorem 4.

∎

Remark 1.

The inequality (20) forces $T$ to be zero at the origin. This also implies that all sequences $(T^{k}(x))_{k}$ starting at $x\in X^{\mathrm{in}}$ converge to 0. The inequality (19) does not imply such properties for $T$ .

The approach using the functional upper bound detailed in (19) relies on Sontag’s result, which is not completely constructive. Therefore, it would be complicated to construct a function $h\in\mathbb{\Gamma}_{\rm fun}(\nu)$ from $\gamma$ and $\psi$ appearing in (20) in practice for general systems. Hopefully, we can develop the latter approach to solve, for well-chosen initial condition sets $\mathsf{X}$ , the problems $\operatorname{DPCP}(\mathsf{X},\mathsf{H},\pi_{i})$ presented in Subsection 2.3.

4.2 Application to the running example of Subsection 2.3

First, we recall that we want to compute, for a subset $\mathsf{X}$ satisfying the condition (7), $\omega_{\mathsf{X},{\rm opt}}^{1}$ and $\omega_{\mathsf{X},{\rm opt}}^{2}$ , which are respectively the supremum of the sequences $\omega_{\mathsf{X}}^{1}$ and $\omega_{\mathsf{X}}^{2}$ defined in (9) and in (10). We have to construct for all $i\in\{1,2\}$ , a function $h\in\mathbb{\Gamma}_{\rm fun}(\omega_{\mathsf{X}}^{i})$ such that $e^{-1}\in\mathbb{\Gamma}_{\rm sc}(\omega_{\mathsf{X}}^{i},h)$ . Actually, we will see that we can choose the same function $h$ for $\omega_{\mathsf{X}}^{1}$ and $\omega_{\mathsf{X}}^{2}$ and we can construct this function from a $\mathcal{K}\mathcal{L}$ upper bound. From this $h$ , we can define $\mathfrak{F}_{\omega_{\mathsf{X}}^{i}}$ for all $i\in\{1,2\}$ . Next, we explicitly define two finite initial condition sets, $\mathsf{X}$ . For each, we define two vectors with numerical values. Then, we apply Algorithm 1 to compute the supremum of $\omega_{\mathsf{X}}^{1}$ and $\omega_{\mathsf{X}}^{2}$ for the two finite initial condition sets.

4.2.1 Theoretical developments of the running example using a $\mathcal{K}\mathcal{L}$ upper bound function.

We observe, since:

\mathfrak{g}(s)<e^{-1}\text{ and }s>0\iff 0<s<\sqrt{64e^{-1}-1}+1=:\underline{\rho},

that $\|\mathsf{H}(x)\|^{2}<e^{-1}\|x\|^{2}$ if and only if $0<\|x\|^{2}<\underline{\rho}$ . Let $r\in(0,\underline{\rho})$ and $\{0\}\neq\mathsf{X}\subseteq\overline{B}(0,\sqrt{r})$ . Then, for $i\in\{1,2\}$ and for all $z\in\mathsf{X}$ and $k\in\mathbb{N}$ :

\pi_{i}(\mathsf{H}^{k}(x))\leq\sqrt{\|\mathsf{H}^{k}(x)\|^{2}}\leq e^{-k/2}\|x\|\kern 5.0pt.

Then we have $\pi_{i}(\mathsf{H}^{k}(x))\leq\gamma(\psi(x),k)$ for all $x\in\mathsf{X}$ and all $k\in\mathbb{N}$ , where:

\gamma(s,t):=s\sqrt{e^{-t}}\text{ and }\psi=\|\cdot\|\kern 5.0pt.

The function $\gamma$ is clearly in $\mathcal{K}\mathcal{L}$ and $\psi$ is clearly nonnegative. As $\mathsf{X}$ is not reduced to $\{0\}$ , $\overline{\psi_{\mathsf{X}}}$ is strictly positive.

Assumption 2 holds for both $\pi_{1}$ and $\pi_{2}$ . Indeed, if $x$ is a nonzero vector such that $\|\mathsf{H}^{k}(x)\|$ converges to 0, then for all $i\in\{1,2\}$ , $\pi_{i}(\mathsf{H}^{k}(x))$ is strictly positive for some integer $k$ . A proof is provided in the appendix. The existence of $\mathcal{K}\mathcal{L}$ bound implies that for all $x\in\mathsf{X}$ , $\|\mathsf{H}^{k}(x)\|$ converges to 0.

As mentioned previously, in general, the functions $\theta_{1},\theta_{2}$ of Sontag’s result (Lemma 1 here) are not known explicitly. As we have obtained an inequality of the form (4) where $e^{-1}$ appears explicitly, we have identified $\theta_{1},\theta_{2}$ and we can directly deduce a function $h_{\mathsf{X}}^{i}\in\mathbb{\Gamma}_{\rm fun}(\omega_{\mathsf{X}}^{i})$ such that $e^{-1}\in\mathbb{\Gamma}_{\rm sc}(\omega_{\mathsf{X}}^{i},h_{\mathsf{X}}^{i})$ . The same function can be chosen for $i=1$ and $i=2$ and we simply write $h_{\mathsf{X}}$ defined as follows:

h_{\mathsf{X}}:\mathbb{R}_{+}\ni s\mapsto\overline{\|\cdot\|_{\mathsf{X}}}\sqrt{s}\kern 5.0pt.

(21)

As $h_{\mathsf{X}}(0)=0$ , we have for $i=1,2$ , $\mathcal{S}(\omega_{\mathsf{X}}^{i},h)=\{k\in\mathbb{N}:\omega_{\mathsf{X},k}^{i}>0\}$ . It is straightforward to see that

h_{\mathsf{X}}^{-1}:\mathbb{R}_{+}\ni s\mapsto\left(\dfrac{s}{\overline{\|\cdot\|_{\mathsf{X}}}}\right)^{2}\kern 5.0pt.

Now since, for all $i\in\{1,2\}$ , we dispose of an element of $\mathbb{\Gamma}(\omega_{\mathsf{X}}^{i})$ , we can solve $\operatorname{DPCP}(\mathsf{X},\mathsf{H},\pi_{i})$ using $\mathfrak{F}_{\omega_{\mathsf{X}}^{i}}$ and Algorithm 1. Very simple calculi lead to the formula for all $i\in\{1,2\}$ and all $k$ such that $\omega_{\mathsf{X},k}^{i}>0$ :

\mathfrak{F}_{\omega_{\mathsf{X}}^{i}}(k,h,e^{-1})=\dfrac{\ln(h_{\mathsf{X}}^{-1}(\omega_{\mathsf{X},k}^{i}))}{\ln(e^{-1})}=2\ln(\overline{\|\cdot\|_{\mathsf{X}}})-2\ln(\omega_{\mathsf{X},k}^{i})\kern 5.0pt.

4.2.2 Numerical applications.

As discussed earlier, we consider two different finite initial condition sets:

1.

$\mathsf{X}_{a}:=\{x^{1},x^{2}\}$ where $x^{1}:=(-1.3,-0.3)^{\intercal}$ and $x^{2}:=(-1.1,-0.8)^{\intercal}$ ;
2.

$\mathsf{X}_{b}:=\{y^{1},y^{2}\}$ where $y^{1}:=(-2.3,0.013)^{\intercal}$ and $y^{2}:=(0.7,-2.29)^{\intercal}$ .

To simplify the notations, we write for all $i\in\{1,2\}$ , $\omega_{a}^{i}=(\omega_{a,k}^{i})_{k\in\mathbb{N}}$ and $\omega_{b}^{i}=(\omega_{b,k}^{i})_{k\in\mathbb{N}}$ instead of $\omega_{\mathsf{X}_{a}}^{i}$ and $\omega_{\mathsf{X}_{b}}^{i}$ . Recall that, for all $i\in\{a,b\}$ , $j\in\{1,2\}$ and $k$ :

\omega_{i,k}^{j}:=\sup_{x\in\mathsf{X}_{i}}\pi_{j}(\mathsf{H}^{k}(x)).

As $\mathsf{X}_{a}$ and $\mathsf{X}_{b}$ are now explicit, we can refine the definition of the function $h_{\mathsf{X}}$ . We write $h_{a}$ for the function associated with $\mathsf{X}_{a}$ and $h_{b}$ for the one associated with $\mathsf{X}_{2}$ . Thus, as

(\overline{\|\cdot\|_{\mathsf{X}_{a}}})^{2}=\max\{\|x^{1}\|^{2},\|x^{2}\|^{2}\}=1.85\text{ and }(\overline{\|\cdot\|_{\mathsf{X}_{b}}})^{2}=\max\{\|y^{1}\|^{2},\|y^{2}\|^{2}\}=5.7341

we get:

h_{a}^{-1}:s\mapsto\dfrac{s^{2}}{1.85}\text{ and }h_{b}^{-1}:s\mapsto\dfrac{s^{2}}{5.7341}

and we have, for all $j\in\{1,2\}$ and all $k$ such that $\omega_{a,k}^{j}>0$ :

\mathfrak{F}_{\omega_{a}^{j}}(k,h_{a},e^{-1})=\ln(1.85)-2\ln\left(\max\{\pi_{j}(\mathsf{H}^{k}(x^{1})),\pi_{j}(\mathsf{H}^{k}(x^{2}))\}\right)

and for all $j\in\{1,2\}$ and all $k$ such that $\omega_{b,k}^{j}>0$ :

\mathfrak{F}_{\omega_{b}^{j}}(k,h_{b},e^{-1})=\ln(5.7341)-2\ln\left(\max\{\pi_{j}(\mathsf{H}^{k}(y^{1})),\pi_{j}(\mathsf{H}^{k}(y^{2}))\}\right)

Then, we are able to apply Algorithm 1 to compute $\omega_{i,{\rm opt}}^{j}$ and the maximal integer solution $k_{i,{\rm max}}^{j}$ for $i\in\{a,b\}$ and $j\in\{1,2\}$ .

The case $\mathsf{X}_{a}=\{x^{1},x^{2}\}$ where $x^{1}=(-1.3,-0.3)^{\intercal}$ and $x^{2}=(-1.1,-0.8)^{\intercal}$

To determine the number of images required for the search of the maximum, we need to compute $\mathfrak{F}_{\omega_{a}^{j}}(k,h_{a},e^{-1})$ . However, this is only possible if and only if $\omega_{a,k}^{j}>0$ . So we have to wait for the first integer $k_{i}$ such that $\max\{\pi_{j}(\mathsf{H}^{k_{i}}(x^{1})),\pi_{j}(\mathsf{H}^{k_{j}}(x^{2}))\}$ is strictly positive. The coordinates of $x^{1}$ and $x^{2}$ are negative, so we move on and compute:

\mathsf{H}(x^{1})=\begin{pmatrix}-357/4000\\ -767/4000\end{pmatrix}\text{ and }\mathsf{H}(x^{2})=\begin{pmatrix}-27/1600\\ -89/400\end{pmatrix}

The vectors still have negative coordinates, and we compute

\mathsf{H}^{2}(x^{1})=\begin{pmatrix}0.03463\\ 0.01174\end{pmatrix}\text{ and }\mathsf{H}^{2}(x^{2})\simeq\begin{pmatrix}0.02982\\ 0.02432\end{pmatrix}.

The vectors $\mathsf{H}^{2}(x^{1})$ and $\mathsf{H}^{2}(x^{2})$ have strictly positive coordinates, and we can compute our stopping integers:

\begin{array}[]{ll}&\displaystyle{\mathfrak{F}_{\omega_{a}^{1}}(2,h_{a},e^{-1})=\ln(1.85)-2\ln\left(\max\{\pi_{1}(\mathsf{H}^{2}(x^{1}),\pi_{1}(\mathsf{H}^{2}(x^{2}))\}\right)\approx 7.3415}\\ \text{ and }&\displaystyle{\mathfrak{F}_{\omega_{a}^{2}}(2,h_{a},e^{-1})=\ln(1.85)-2\ln\left(\max\{\pi_{2}(\mathsf{H}^{2}(x^{1}),\pi_{2}(\mathsf{H}^{2}(x^{2}))\}\right)\approx 8.0482}\end{array}

This means that the stopping integer $K$ in Algorithm 1 is set to 7 for $\omega_{a}^{1}$ and to 8 for $\omega_{a}^{2}$ and

\omega_{a,{\rm opt}}^{1}=\max\{\omega_{a,k}^{1}:k\in\{0,1,\ldots,7\}\}\text{ and }\omega_{a,{\rm opt}}^{2}=\max\{\omega_{a,k}^{2}:k\in\{0,1,\ldots,8\}\}.

Following Algorithm 1, we compute the $\max\{\pi_{j}(\mathsf{H}^{k}(x^{1})),\pi_{j}(\mathsf{H}^{k}(x^{2}))\}$ until $k$ reaches the stopping integer. As during the process, we have not found greater values than $\omega_{a,2}^{i}$ , we conclude that $\omega_{a,{\rm opt}}^{j}=\omega_{a,2}^{j}$ and $k_{a,{\rm max}}^{j}=2$ for all $j\in\{1,2\}$ .

The case $\mathsf{X}_{b}=\{y^{1},y^{2}\}$ where $y^{1}=(-2.3,0.013)^{\intercal}$ and $y^{2}=(0.7,-2.29)^{\intercal}$

Contrary to the case $\mathsf{X}_{a}$ , as $y_{1}^{2}=\omega_{b,0}^{1}=0.7$ and $y_{2}^{1}=\omega_{b,0}^{2}=0.013$ , we can compute stopping integers at $k=0$ :

\begin{array}[]{cc}&\mathfrak{F}_{\omega_{b}^{1}}(0,h_{b},e^{-1})=\ln(5.7341)-2\ln(0.7)\approx 2.4598\\ \text{ and }&\mathfrak{F}_{\omega_{b}^{2}}(0,h_{b},e^{-1})=\ln(5.7341)-2\ln(0.013)\approx 10.432\kern 5.0pt.\end{array}

This leads to the stopping integer $K$ in Algorithm 1 being set to 2 for ${\omega_{b}^{1}}$ and 10 for ${\omega_{b}^{2}}$ . Hence

\omega_{b,{\rm opt}}^{1}=\max\{\omega_{b,0}^{1},\omega_{b,1}^{1},\omega_{b,2}^{1}\}\text{ and }\omega_{b,{\rm opt}}^{2}=\max\{\omega_{b,k}^{2}:k\in\{0,1,\ldots,10\}\}.

Now, we compute the images of $y^{1}$ and $y^{2}$ by $\mathsf{H}$ :

\mathsf{H}(y^{1})\simeq\begin{pmatrix}-1.23505\\ -0.28053\end{pmatrix}\text{ and }\mathsf{H}(y^{2})\simeq\begin{pmatrix}0.70048\\ -1.26764\end{pmatrix}.

As $\pi_{1}(\mathsf{H}(y^{2}))>0.7$ , we can update the stopping integer for ${\omega_{b}^{1}}$ and:

\mathfrak{F}_{\omega_{2}^{1}}(1,h_{b},e^{-1})=\ln(5.7341)-2\ln(\pi_{1}(\mathsf{H}(y^{2})))\approx 2.4584.

Following the fifth statement of Proposition 6, this is slightly smaller than $\mathfrak{F}_{\omega_{b}^{1}}(0,h_{b},e^{-1})$ but its integer part is still equal to 2 for ${\omega_{b}^{1}}$ . The second coordinate of $\mathsf{H}(y^{1})$ and of $\mathsf{H}(y^{2})$ are negative, then we cannot update the stopping integer for ${\omega_{b}^{2}}$ . Next, we have

\mathsf{H}^{2}(y^{1})\simeq\begin{pmatrix}-0.05819\\ -0.17556\end{pmatrix}\text{ and }\mathsf{H}^{2}(y^{2})\approx\begin{pmatrix}0.25456\\ -0.08636\end{pmatrix}.

As $\pi_{1}(\mathsf{H}^{2}(y^{2}))$ is strictly less than $\pi_{1}(\mathsf{H}(y^{2}))$ and the stopping integer for $\omega_{b}^{1}$ is equal to 2, it follows that $\omega_{b,{\rm opt}}^{1}=\pi_{1}(\mathsf{H}(y^{2}))$ and $k_{b,{\rm max}}^{1}=1$ . Since $\pi_{2}(\mathsf{H}^{2}(y^{1}))$ and $\pi_{2}(\mathsf{H}(y^{2}))$ are negative then nothing changes for ${\omega_{b}^{2}}$ . We continue to iterate for $\omega_{b}^{2}$ until $k=10$ . We have

\mathsf{H}^{3}(y^{1})\approx\begin{pmatrix}0.02897\\ 0.01392\end{pmatrix}\text{ and }\mathsf{H}^{3}(y^{2})\approx\begin{pmatrix}-0.01873\\ 0.04183\end{pmatrix}

thus $\omega_{b,3}^{2}=\pi_{2}(\mathsf{H}^{3}(y^{2}))>0.013$ , which was the maximal previous value. We then update the value of the stopping integer $K$ of Algorithm 1 for $\omega_{b}^{2}$ and obtain

\mathfrak{F}_{\omega_{b}^{2}}(3,h_{b},e^{-1})=\ln(5.7341)-2\ln(\pi_{2}(\mathsf{H}^{3}(y^{2})))\approx 8.0945.

The new stopping integer $K$ is equal to 8 for $\omega_{b}^{2}$ . The next values are smaller than $\pi_{2}(\mathsf{H}^{3}(y^{2}))$ , which implies that $\omega_{b,{\rm opt}}^{2}=\pi_{2}(\mathsf{H}^{3}(y^{2}))$ and $k_{b,{\rm max}}^{2}=3$ .

5 Solving Problem 1 from Lyapunov functions

Classically, Lyapunov functions are used as certificates of stability (see [Ela05] or [KP01]). They bring a constructive approach to prove the stability of the dynamical system through converse Lyapunov theorems, which proved that stability notions are equivalent to the existence of Lyapunov functions [Kha02]. For some linear, polynomial, or piecewise polynomial systems, Lyapunov functions can be computed using numerical optimization solvers based on linear or semidefinite programming (e.g., see [GH15] and references therein).

Classical quadratic Lyapunov functions solve Problem 1 when $T$ is affine and stable, and $\varphi$ is quadratic (see [Adj25a]). In this section, we prove that this approach can be generalized to all discrete-time systems for which a Lyapunov function exists.

5.1 Definition and useful facts

We begin by recalling the definition of classical Lyapunov functions for discrete-time systems. We briefly present the equivalent definitions of the decrease condition required to be a Lyapunov function. For topological notions, we recall that $\displaystyle{\|\cdot\|}$ is the Euclidean norm. However, the context of finite-dimensional space makes the results independent of the choice of the norm.

For $F:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ , we denote by $\operatorname{Sta}(F)$ the set of closed subsets of $\mathbb{R}^{d}$ containing 0 but non reduced to 0 and stable by $F$ i.e.,

\operatorname{Sta}(F):=\{\mathcal{D}\subseteq\mathbb{R}^{d}:\mathcal{D}\text{ closed },\ 0\in\mathcal{D}\neq\{0\},\ F(\mathcal{D})\subseteq\mathcal{D}\}

Following Lazar [Laz06], we define local Lyapunov functions on stable sets. We slightly relax the notion of stable sets, called classically positive or forward invariant sets. Indeed, classically, positive invariant sets are our stable sets with an auxiliary condition: 0 belongs to the interior of the stable set. This condition is not considered stability problems in this paper.

Definition 6 (Classical Lyapunov functions).

A function $V:\mathbb{R}^{d}\to\mathbb{R}$ is said to be a (local) Lyapunov function for $F:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ on $X\in\operatorname{Sta}(F)$ if and only if:

1.

There exist $\alpha_{1},\alpha_{2}\in\mathcal{K}$ such that, for all $x\in X$ :

$\alpha_{1}(\|x\|)\leq V(x)\leq\alpha_{2}(\|x\|)$
2.

There exists $\lambda\in(0,1)$ such that for all $x\in X$ :

$V(F(x))\leq\lambda V(x)$

Example 1.

In [LHK14a], the authors propose the following function:

\mathsf{V}:\mathbb{R}^{2}\ni x\mapsto\max\{\|x\|^{2},e\|\mathsf{H}(x)\|^{2}\}

(22)

as a (local) Lyapunov function for the dynamics $\mathsf{H}$ of our running example presented in Subsection 2.3.

Next, we prove that $\mathsf{V}$ is a Lyapunov function for $\mathsf{H}$ on any $\overline{B}(0,\sqrt{r})$ for which $r<\overline{\rho}$ . In this example, we prove the first statement of Definition 6. Let $r$ be in $(0,\overline{\rho})$ . Thus, from the discussion of Subsection 2.3, we have $\|\mathsf{H}(x)\|^{2}<\|x\|^{2}$ for all nonzero $x$ in $\overline{B}(0,\sqrt{r})$ . Then, for all $x$ in $\overline{B}(0,\sqrt{r})$ , $\|x\|^{2}\leq\mathsf{V}(x)\leq\max\{\|x\|^{2},e\|x\|^{2}\}=e\|x\|^{2}$ . We conclude that there exist $\alpha_{1},\alpha_{2}\in\mathcal{K}_{\infty}$ ( $\alpha_{1}:\mathbb{R}_{+}\ni s\mapsto s^{2}$ and $\alpha_{1}:\mathbb{R}_{+}\ni s\mapsto es^{2}$ ) such that $\alpha_{1}(\|x\|)\leq\mathsf{V}(x)\leq\alpha_{2}(\|x\|)$ .

We will prove the second statement by computing the local Lyapunov ratio operator of $\mathsf{H}$ .

First, due to the equivalence of norms in $\mathbb{R}^{d}$ and since any element of $\mathcal{K}$ is increasing if the first statement holds for $\|\cdot\|$ , it holds for all norms on $\mathbb{R}^{d}$ . Second, combining the results and discussions found in [GGLW14, Remark 5], [LHK14b, Def. 5, Th.4] and [Kel14, Lemma 25, Corollary 1], the condition that there exists $\lambda\in(0,1)$ such that $V\circ F\leq\lambda V$ can be equivalently replaced by one of those statements:

1.

there exists $\alpha:\mathbb{R}_{+}\mapsto\mathbb{R}_{+}$ positive definite and continuous such that $V\circ F\leq V-\alpha\circ\|\cdot\|$ ;
2.

there exists $\rho:\mathbb{R}_{+}\mapsto\mathbb{R}_{+}$ positive definite, continuous and such that $\mathrm{Id}-\rho$ is positive definite satisfying $V\circ F\leq\rho\circ V$ .

First, we remark that from the first statement of Definition 6, $V$ is positive definite on any closed ball for which the radius belongs to the domain of $\alpha_{1}$ . If we require $V$ to be continuous and $\mathcal{D}$ contains 0 in its interior, from Proposition 9, the first statement of Definition 6 is actually equivalent to $V\in\operatorname{PD}(\mathcal{D})$ . Second, if there exists a classical Lyapunov function for $F$ , $F$ must be null at zero²²2Actually, if $F(e)=e$ for a nonzero vector, we could replace $V$ by $V(\cdot-e)$ and the lower and the upper bounds on $V(\cdot-e)$ by respectively $\alpha_{1}(\|\cdot-e\|)$ and $\alpha_{2}(\|\cdot-e\|)$ . Finally, from the second statement of Definition 6, we can define a type of norm operator relative to a Lyapunov function. We propose a general definition of local positive definite ratio operators and then specify the results for local Lyapunov functions.

Definition 7 (Local positive definite ratio operators).

Let $F:\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that $F(0)=0$ and $X\in\operatorname{Sta}(F)$ . The local positive definite ratio operator of $F$ on $X$ is the following map:

\operatorname{PD}(X)\ni W:\to N_{F}^{X}(W):=\sup_{\begin{subarray}{c}x\in X\\ x\neq 0\end{subarray}}\dfrac{W(F(x))}{W(x)}

(23)

Note that the local positive definite ratio operator $N_{F}^{X}$ is always nonnegative and can take infinite values.

In Proposition 10, we present some useful properties of the local positive definite ratio operator $N_{F}^{X}$ .

Proposition 10.

Let $F:\mathbb{R}^{d}\to\mathbb{R}^{d}$ such that $F(0)=0$ and $X\in\operatorname{Sta}(F)$ . Then, for all $W\in\operatorname{PD}(X)$ :

1.

$N_{\mathrm{Id}}^{X}(W)=1$ where $\mathrm{Id}:\mathbb{R}^{d}\ni x\mapsto x$ ;
2.

for all $x\in X\backslash\{0\}$ , $W(F(x))\leq N_{F}^{X}(W)W(x)$ ;
3.

for all $k\in\mathbb{N}^{*}$ , $N_{F^{k}}^{X}(W)\leq(N_{F}^{X}(W))^{k}$ ;
4.

there exists $\lambda\in(0,1)$ such that for all $x\in X$ , $W(F(x))\leq\lambda W(x)$ if and only if $N_{F}^{X}(W)\in(0,1)$ .

Proof.

1. This is a straightforward application of the definitions.

2. The result clearly holds if $N_{F}^{X}(W)$ is equal to $+\infty$ . Then, if $N_{F}^{X}(W)$ is finite, directly applying the definition of $N_{F}^{X}(W)$ and the positivity of $W$ lead to the result.

3. The result holds when $N_{F}^{X}(W)$ is equal to $+\infty$ . Now, suppose that $N_{F}^{X}(W)$ is finite. If $N_{F}^{X}(W)=0$ , then $W(F(x))$ for all $x\in X\backslash\{0\}$ . It follows that $F(x)=0$ for all $x\in X$ . Finally, $F^{k}(x)=0$ for all $k\in\mathbb{N}^{*}$ and $x\in X$ . Then $N_{F^{k}}^{X}(W)=0$ and the inequality holds. If $N_{F^{k}}^{X}(W)=0$ for some $k\in\mathbb{N}$ the inequality obviously holds. We then suppose that $N_{F}^{X}(W)$ and for all $k\in\mathbb{N}^{*}$ $N_{F}^{k}(W)$ are strictly positive. We now apply induction. The result obviously holds for $k=1$ . Assume that it holds for some $k\in\mathbb{N}^{*}$ . Let $x\in X\backslash\{0\}$ such that $W(F^{k+1}(x))>0$ . It follows that $W(F^{k}(x))>0$ . Then $W(F^{k+1}(x))/W(x)=(W(F^{k+1}(x))/W(F^{k}(x)))\times(W(F^{k}(x))/W(x))$ . As $X\in\operatorname{Sta}(F)$ , $F^{k+1}(x)$ and $F^{k}(x)$ belong to $X$ and are not equal to 0. Finally, $W(F^{k+1}(x))/W(x)\leq N_{F}^{X}(W)\times N_{F^{k}}^{X}(W)\leq(N_{F}^{X}(W))^{k+1}$ using the induction hypothesis. We obtain the inequality by taking the supremum over $X\backslash\{0\}$ .

4. It follows readily from the definition. ∎

The fourth statement of Proposition 10 is not difficult to prove. However, it is worth noting that if there exists $\lambda\in(0,1)$ such that for all $x\in X$ , $W(F(x))\leq\lambda W(x)$ , then $N_{F}^{X}(W)\leq\lambda$ . For our applications, this latter inequality is important. Indeed, $N_{F}^{X}(W)$ will be used as an element $\beta\in\mathbb{\Gamma}_{\rm sc}(h,\nu)$ for a function $h$ to be determined. Since $\lambda$ also belongs to $\mathbb{\Gamma}_{\rm sc}(h,\nu)$ , following Proposition 7, we will have $\mathfrak{F}_{\nu}(k,h,N_{F}^{X}(W))\leq\mathfrak{F}_{\nu}(k,h,\lambda)$ . This will be highlighted in Paragraph 5.3.2.

Corollary 2.

Let $F$ be a self-map on $\mathbb{R}^{d}$ . Suppose that $F$ admits a local Lyapunov function $V$ on $X\in\operatorname{Sta}(F)$ . Then:

1.

$N_{F}^{X}(V)\in(0,1)$ ;
2.

for all $x\in X$ , $V(F(x))\leq N_{F}^{X}(V)V(x)$ ;
3.

for all $k\in\mathbb{N}$ , $N_{F^{k}}^{X}(V)\leq(N_{F}^{X}(V))^{k}$ .

Proof.

The first statement follows from the fourth statement of Proposition 10. The second statement is a reformulation of the second statement of Proposition 10, for which the inequality holds for $x=0$ as $N_{F}^{X}(V)$ is finite. The finiteness of $N_{F}^{X}(V)$ also extends the third statement of Proposition 10.

∎

Example 2 (The local positive definite ratio operator of $\mathsf{H}$ at $\mathsf{V}$ on closed balls).

Now, let us consider $r\in(0,\overline{\rho})$ . To go further into our computations, we must compute the local positive definite ratio operator on $\overline{B}(0,\sqrt{r})$ of $\mathsf{H}$ at the Lyapunov candidate $\mathsf{V}$ defined in (22). For sake of simplicity, we write $N_{\mathsf{H}}^{r}(\mathsf{V})$ instead of $N_{\mathsf{H}}^{\overline{B}(0,\sqrt{r})}(\mathsf{V})$ .

First, we suppose that $r\leq\underline{\rho}$ . It follows that $\mathsf{V}(x)=\|x\|^{2}$ . Moreover, as $r<\overline{\rho}$ , we also have $\|\mathsf{H}(x)\|^{2}<\|x\|^{2}\leq r$ and so, by assumption, $\|\mathsf{H}(x)\|^{2}\leq\underline{\rho}$ and $\mathsf{V}(\mathsf{H}(x))=\|\mathsf{H}(x)\|^{2}$ . Finally, in the case where $r\leq\underline{\rho}$ , we have

N_{\mathsf{H}}^{r}(\mathsf{V})=\sup_{\begin{subarray}{c}\|x\|^{2}\leq r\\ x\neq 0\end{subarray}}\dfrac{\mathsf{V}(\mathsf{H}(x))}{\mathsf{V}(x)}=\sup_{\begin{subarray}{c}\|x\|^{2}\leq r\\ x\neq 0\end{subarray}}\dfrac{\|\mathsf{H}(x)\|^{2}}{\|x\|^{2}}=\sup_{\begin{subarray}{c}\|x\|^{2}\leq r\\ x\neq 0\end{subarray}}\dfrac{1+(\|x\|^{2}-1)^{2}}{64}=\sup_{\begin{subarray}{c}\|x\|^{2}\leq r\\ x\neq 0\end{subarray}}\mathfrak{g}(\|x\|^{2})

The function $\mathfrak{g}$ is strictly decreasing on $[0,1]$ and strictly increasing on $[1,+\infty)$ and for all $0<s<2$ , $\mathfrak{g}(s)<1/32=\mathfrak{g}(0)=\mathfrak{g}(2)$ , hence for all $r\leq\overline{\rho}$ :

N_{\mathsf{H}}^{r}(\mathsf{V})=\left\{\begin{array}[]{lr}\dfrac{1}{32}&\text{ if }r\in(0,2]\\ \\ \dfrac{1+(r-1)^{2}}{64}&\text{ if }r\in(2,\underline{\rho}]\end{array}\right.

When $r=\underline{\rho}$ , we get the equality $N_{\mathsf{H}}^{r}(V)=\mathfrak{g}(\underline{\rho})=e^{-1}$ . Futhermore, since $\mathfrak{g}$ is increasing on $(2,\underline{\rho}]$ , $N_{\mathsf{H}}^{r}(\mathsf{V})\leq\mathfrak{g}(\underline{\rho})=e^{-1}$ .

Now, let consider $r\in(\underline{\rho},\overline{\rho})$ and $x\in\mathbb{R}^{2}$ such that $\|x\|^{2}\in(\underline{\rho},r]$ . Then we have $\mathsf{V}(z)=e\|\mathsf{H}(z)\|^{2}$ and $\mathsf{V}(\mathsf{H}(x))=e\|\mathsf{H}^{2}(x)\|$ if $\|\mathsf{H}(x)\|^{2}\geq\underline{\rho}$ and $\mathsf{V}(x)=\|\mathsf{H}(x)\|^{2}$ if $\|\mathsf{H}(x)\|^{2}<\underline{\rho}$ . Then:

\begin{array}[]{ll}N_{\mathsf{H}}^{r}(\mathsf{V})=\sup_{\begin{subarray}{c}\|x\|^{2}\leq r\\ x\neq 0\end{subarray}}\dfrac{\mathsf{V}(\mathsf{H}(x))}{\mathsf{V}(x)}&=\max\left\{\sup_{\begin{subarray}{c}\|x\|^{2}\leq\underline{\rho}\end{subarray}}\dfrac{\mathsf{V}(\mathsf{H}(x))}{\mathsf{V}(x)},\sup_{\begin{subarray}{c}\underline{\rho}<\|x\|^{2}\leq r\\ x\neq 0\end{subarray}}\dfrac{\mathsf{V}(\mathsf{H}(x))}{\mathsf{V}(x)}\right\}\\ &=\max\left\{\dfrac{1}{e},\sup_{\begin{subarray}{c}\underline{\rho}<\|x\|^{2}\leq r\\ \|\mathsf{H}(x)\|^{2}\leq\underline{\rho}\end{subarray}}\dfrac{\mathsf{V}(\mathsf{H}(x))}{\mathsf{V}(x)},\sup_{\begin{subarray}{c}\underline{\rho}<\|x\|^{2}\leq r\\ \|\mathsf{H}(x)\|^{2}>\underline{\rho}\end{subarray}}\dfrac{\mathsf{V}(\mathsf{H}(x))}{\mathsf{V}(x)}\right\}\\ &=\max\left\{\dfrac{1}{e},\sup_{\begin{subarray}{c}\underline{\rho}<\|x\|^{2}\leq r\\ \|\mathsf{H}(x)\|^{2}\leq\underline{\rho}\end{subarray}}\dfrac{\|\mathsf{H}(x)\|^{2}}{e\|\mathsf{H}(x)\|^{2}},\sup_{\begin{subarray}{c}\underline{\rho}<\|x\|^{2}\leq r\\ \|\mathsf{H}(x)\|^{2}>\underline{\rho}\end{subarray}}\dfrac{e\|\mathsf{H}^{2}(x)\|^{2}}{e\|\mathsf{H}(x)\|^{2}}\right\}\\ &=\max\left\{\dfrac{1}{e},\sup_{\begin{subarray}{c}\underline{\rho}<\|x\|^{2}\leq r\\ \|\mathsf{H}(x)\|^{2}>\underline{\rho}\end{subarray}}\dfrac{1}{64}\left(1+(\|\mathsf{H}(x)\|^{2}-1)^{2}\right)\right\}\\ &=\max\left\{\dfrac{1}{e},\sup_{\begin{subarray}{c}\underline{\rho}<\|x\|^{2}\leq r\\ \|\mathsf{H}(x)\|^{2}>\underline{\rho}\end{subarray}}\mathfrak{g}(\mathfrak{f}(\|x\|^{2}))\right\}\end{array}

Let us introduce the set

S_{r}:=\{s\in(\underline{\rho},r]:\mathfrak{f}(s)>\underline{\rho}\}.

(24)

We thus are interested in the supremum of $\mathfrak{g}(\mathfrak{f}(\|x\|^{2}))$ for all $\|x\|^{2}\in S_{r}$ . As $\mathfrak{f}$ is strictly increasing on $\mathbb{R}_{+}$ , there exists a unique real root denoted by $\beta^{*}$ for the polynomial function of degree 3, $\mathfrak{f}(\cdot)-\underline{\rho}$ . As $\mathfrak{f}(\underline{\rho})=\underline{\rho}/e<\underline{\rho}$ , we have $\beta^{*}>\underline{\rho}$ . We do not require the exact value of $\beta^{*}$ . In fact, $S_{r}$ is nonempty if and only if $\mathfrak{f}(r)>\underline{\rho}$ . Indeed, if there exists $s\in S_{r}$ , then, as $\mathfrak{f}$ strictly increases, $\mathfrak{f}(r)\geq\mathfrak{f}(s)>\underline{\rho}$ and $r\in S_{r}$ . Conversely, it is obvious that $S_{r}$ is nonempty if $r\in S_{r}$ . Note that if $S_{r}$ is empty, the supremum over it is $-\infty$ making $N_{\mathsf{H}}^{r}(\mathsf{V})=e^{-1}$ for all $r\in(\underline{\rho},\beta^{*}]$ . Suppose that $S_{r}$ is nonempty. As $\mathfrak{f}(\underline{\rho})=\underline{\rho}/e>1$ , $\mathfrak{g}\circ\mathfrak{f}$ is strictly increasing on $S_{r}$ and for all $s\in S_{r}$ :

\mathfrak{g}(\mathfrak{f}(s))\leq\mathfrak{g}(\mathfrak{f}(r))=\dfrac{1}{64}\left(1+\left(\dfrac{1}{64}r(1+(r-1)^{2})-1\right)^{2}\right)<\mathfrak{g}(\mathfrak{f}(\overline{\rho}))=1.

Finally, we obtain for all $r<\overline{\rho}$ :

N_{\mathsf{H}}^{r}(\mathsf{V})=\left\{\begin{array}[]{lr}\mathfrak{g}(\mathfrak{f}(r))&\text{ if }r>\underline{\rho}\text{ and }f(r)>\underline{\rho}\\ e^{-1}&\text{ if }r>\underline{\rho}\text{ and }\mathfrak{f}(r)\leq\underline{\rho}\\ \dfrac{1+(r-1)^{2}}{64}&\text{ if }r\in(2,\underline{\rho}]\\ \dfrac{1}{32}&\text{ if }r\in(0,2]\\ \end{array}\right.

(25)

We conclude that $\mathsf{V}$ satisfies for all $r<\overline{\rho}$ :

1.

for all $z\in\overline{B}(0,\sqrt{r})$ , $\|x\|^{2}\leq\mathsf{V}(x)\leq e\|x\|^{2}$ ;
2.

there exists $\lambda\in(0,1)$ such that for all $x\in\overline{B}(0,\sqrt{r}))$ , $\mathsf{V}(\mathsf{H}(x))\leq\lambda\mathsf{V}(x)$

and $\mathsf{V}$ is a Lyapunov function for $\mathsf{H}$ on all $\overline{B}(0,\sqrt{r})$ where $r<\overline{\rho}$ .

5.2 Theoretical constructions from Lyapunov functions

In this subsection, we explain how to construct a solution for Problem 1 from a Lyapunov function. We recall that a solution of Problem 1 is an $(h,\beta)\in\mathbb{\Gamma}(\nu)$ ( $\nu$ defined in (1)) useful when ${\mathrm{R}}_{\nu}^{s}\neq\emptyset$ . First, we establish a direct result derived from Theorem 4 without any continuity condition on $\varphi$ .

We formulate a simple lemma asserting that the supremum of a local Lyapunov function is finite over nonempty bounded sets contained in a suitable stable set. The result would be evident if the local Lyapunov function is (upper semi)continuous, but continuity is not mandatory in Definition 6.

Lemma 2.

Let $F:\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ . Assume that $F$ admits a local Lyapunov function $V$ on $X\in\operatorname{Sta}(F)$ . Then, for all nonempty bounded sets $B\subseteq X$ , $\overline{V_{B}}<+\infty$ .

Proof.

Let $F$ be a self-map on $\mathbb{R}^{d}$ and $V$ be a local Lyapunov function on $X\in\operatorname{Sta}(F)$ . Let $B$ be a nonempty bounded set contained in $X$ . By definition, there exists $\alpha\in\mathcal{K}$ , such that $V(x)\leq\alpha(\|x\|)$ for all $x\in X$ . Then, as $\alpha$ is strictly increasing, $\overline{V_{B}}\leq\sup_{x\in B}\alpha(\|x\|)=\alpha(\sup_{x\in B}\|x\|)=\alpha(\max_{x\in\overline{B}}\|x\|)=\alpha(\|\overline{y}\|)$ for some $\overline{y}\in X$ as $X$ is closed. We conclude that $\alpha$ is defined at $\overline{\|\cdot\|_{B}}$ and thus $\overline{V_{B}}<+\infty$ .

∎

Remark 2.

Lemma 2 justifies the closedness of elements on $\operatorname{Sta}(U)$ . As a matter of fact, the definition of being a Lyapunov function may allow functions $\alpha:[0,c)\ni x\mapsto(c-x)^{-1}-c^{-1}$ as functions $\alpha_{1},\alpha_{2}\in\mathcal{K}$ . If such a function is defined on the set $\{\|x\|:x\in X\}$ where $X$ is a closed set, then for all $x\in X$ , $\|x\|<c$ . This implies that $X$ is compact, and then $\sup_{x\in X}\|x\|=\|\overline{x}\|<c$ for some $\overline{x}\in X$ . On the contrary, let $Y=\{x\in\mathbb{R}^{d}:\|x\|<c\}$ . If the function $\alpha:[0,c)\ni x\mapsto(c-x)^{-1}-c^{-1}$ is defined on the set $\{\|y\|:y\in Y\}$ . As $\sup_{y\in Y}\|y\|=c$ , so $\alpha$ is not defined on $\sup_{y\in Y}\|y\|$ .

Theorem 6 (Direct Lyapunov construction).

Suppose that $X^{\mathrm{in}}$ is bounded and not reduced to $\{0\}$ . Suppose that there exists a Lyapunov function $V$ for $T$ on $\mathcal{D}\in\operatorname{Sta}(T)$ such that $X^{\mathrm{in}}\subseteq\mathcal{D}$ . If

\varphi(x)\leq V(x)\text{ for all }x\in\mathcal{D},

(26)

then:

1.

$\limsup_{n\to+\infty}\nu_{n}\leq 0$ and if, moreover, Assumption 2 holds then ${\mathrm{R}}_{\nu}^{s}\neq\emptyset$ ;
2.

the function:

$h:\mathbb{R}_{+}\ni s\mapsto s\overline{V_{X^{\mathrm{in}}}}$

belongs to $\mathbb{\Gamma}_{\rm fun}(\nu)$ and $N_{T}^{\mathcal{D}}(V)\in\mathbb{\Gamma}_{\rm sc}(\nu,h)$ and, if, moreover, Assumption 2 holds then $h$ is useful for $\nu$ .

Proof.

Let $x\in X^{\mathrm{in}}$ and $k\in\mathbb{N}$ . As $\mathcal{D}\in\operatorname{Sta}(T)$ and $X^{\mathrm{in}}\subseteq\mathcal{D}$ , then, $T^{k}(x)\in\mathcal{D}$ and, from (26), $\varphi(T^{k}(x))\leq V(T^{k}(x))$ . Moreover, as $V$ is a Lyapunov function, from Lemma 2, $\overline{V_{X^{\mathrm{in}}}}$ is finite and we have $\varphi(T^{k}(x))\leq N_{T^{k}}^{\mathcal{D}}(V)V(x)\leq(N_{T}^{\mathcal{D}}(V))^{k}\overline{V_{X^{\mathrm{in}}}}=h((N_{T}^{\mathcal{D}}(V))^{k})$ . The inequality involving $\nu_{k}$ follows by taking the supremum over $X^{\mathrm{in}}$ . As $V$ is a Lyapunov function on $\mathcal{D}$ , $N_{T}^{\mathcal{D}}(V)\in(0,1)$ . This implies that the first statement as $(N_{T}^{\mathcal{D}}(V))^{k}\overline{V_{X^{\mathrm{in}}}}$ tends to 0. As $X^{\mathrm{in}}\neq\{0\}$ , then $\overline{V_{X^{\mathrm{in}}}}>0$ and from Lemma 2, as $X^{\mathrm{in}}$ is bounded, $\overline{V_{X^{\mathrm{in}}}}<+\infty$ . We obtain the second statement from this.

∎

Remark 3.

Actually, the function $\gamma(s,t):\mathbb{R}_{+}\times\mathbb{R}_{+}\ni(s,t)\mapsto s\exp(t\ln(N_{T}^{\mathcal{D}}(V)))$ is a $\mathcal{K}\mathcal{L}$ function and as $X^{\mathrm{in}}$ is bounded and not reduced to $\{0\}$ , $V$ belongs to $\operatorname{Fin}\left(X^{\mathrm{in}}\right)$ and verifies $\overline{V_{X^{\mathrm{in}}}}>0$ . Theorem 4 thus applies. As we do not depend on Sontag’s lemma, we have an explicit description of the element $(h,\beta)\in\mathbb{\Gamma}(\nu)$ .

If we assume that $\varphi$ is continuous, the inequality (26) is no longer required. To recover a link between $\varphi$ and a Lyapunov function, it suffices to use Proposition 9.

Theorem 7 (Continuous Lyapunov construction).

Assume that $X^{\mathrm{in}}$ is bounded and not reduced to $\{0\}$ . Suppose that $\varphi$ is continuous and there exists a Lyapunov function $V$ for $T$ on $\mathcal{D}\in\operatorname{Sta}(T)$ such that $X^{\mathrm{in}}\subseteq\mathcal{D}$ . Finally, suppose that there exists $\alpha_{V}\in\mathcal{K}$ satisfying $\alpha_{V}(\|x\|)\leq V(x)$ for all $x\in\mathcal{D}$ and $\alpha_{V}(s)>\overline{V_{X^{\mathrm{in}}}}$ for some $s\in(0,+\infty)$ . Let $\alpha\in\mathcal{K}_{\infty}$ verifying $\varphi(x)\leq\alpha(\|x\|)$ for all $x\in\mathbb{R}^{d}$ . We define:

h:\mathbb{R}_{+}\ni s\mapsto\alpha\left(\alpha_{V}^{-1}(s\overline{V_{X^{\mathrm{in}}}})\right)

Then $(h,N_{T}^{\mathcal{D}}(V))\in\mathbb{\Gamma}(\nu)$ . If Assumption 2 holds, then $h$ is useful for $\nu$ .

Proof.

Let $x\in X^{\mathrm{in}}$ and $k\in\mathbb{N}$ . As $X^{\mathrm{in}}\subseteq\mathcal{D}$ and $\mathcal{D}\in\operatorname{Sta}(T)$ , $T^{k}(x)\in\mathcal{D}$ and thus $\alpha_{V}(\|T^{k}(x)\|)\leq V(T^{k}(x))$ . As $V$ is Lyapunov, we then have $\alpha_{V}(\|T^{k}(x)\|)\leq V(T^{k}(x))\leq N_{T^{k}}^{\mathcal{D}}(V)V(x)\leq N_{T}^{\mathcal{D}}(V)^{k}V(x)$ . As $x\in X^{\mathrm{in}}$ , it follows that $\alpha_{V}(\|T^{k}(x)\|)\leq N_{T}^{\mathcal{D}}(V)^{k}\overline{V_{X^{\mathrm{in}}}}$ . By assumption, $\overline{V_{X^{\mathrm{in}}}}<\alpha_{V}(s)$ for some $s\in(0,+\infty)$ . We also have $N_{T}^{\mathcal{D}}(V)^{k}\in(0,1)$ . Then, $\alpha_{V}^{-1}(N_{T}^{\mathcal{D}}(V)^{k}\overline{V_{X^{\mathrm{in}}}}))$ exists. Since $\varphi\leq\alpha\circ\|\cdot\|$ on $\mathbb{R}^{d}$ with $\alpha$ increasing, the inequality $\varphi(T^{k}(x))\leq\alpha(\|x\|)\leq\alpha(\alpha_{V}^{-1}((N_{T}^{\mathcal{D}}(V)^{k}\overline{V_{X^{\mathrm{in}}}})$ holds. Taking the supremum over $X^{\mathrm{in}}$ leads to $(h,N_{T}^{\mathcal{D}}(V))\in\mathbb{\Gamma}(\nu)$ . As $\alpha,\alpha_{V}\in\mathcal{K}$ , $h(0)=0$ and thus $h$ is useful if Assumption 2 holds.

∎

Remark 4.

If we impose the strongest condition: $\alpha_{V}(s)>\overline{V_{\mathcal{D}}}$ for some $s\in(0,+\infty)$ (instead of $\alpha_{V}(s)>\overline{V_{X^{\mathrm{in}}}}$ ), we can directly use Theorem 6. Indeed, if this stronger condition holds, we can deduce $\tilde{\varphi}:=\alpha_{V}(\alpha^{-1}(\varphi(x))\leq V(x)$ for all $x\in\mathcal{D}$ .

5.3 Numerical applications to our running example of Subsection 2.3

We propose to illustrate the theoretical results obtained in Subsection 5.2 on the running example presented in Subsection 2.3. First, we explicit the function $h\in\mathbb{\Gamma}(\omega_{\mathsf{X}}^{i})$ . Then, we compare the results obtained from the Lyapunov approach with those obtained with $\mathcal{K}\mathcal{L}$ upper bounds. Finally, we complete the numerical experiments with new data not treated with the $\mathcal{K}\mathcal{L}$ approach.

5.3.1 Theoretical developments of the running example using $\mathsf{V}$

We can return to the discrete-time peak computation problems presented in Subsection 2.3. Recall that the objective functions are the coordinate functions $\pi_{1}$ and $\pi_{2}$ . It is evident that $\varphi(x)\leq\|x\|=\alpha_{\varphi}(\|x\|)$ for all $x\in\mathbb{R}^{2}$ where $\alpha_{\varphi}:\mathbb{R}_{+}\ni:s\mapsto s$ . Recall that $\mathsf{V}$ defined in (22) is proved in Example 2 to be a Lyapunov function for $\mathsf{H}$ on all $\overline{B}(0,\sqrt{r})$ where $r<\overline{\rho}$ . It follows that $\alpha_{\mathsf{V}}(\|x\|)=\|x\|^{2}\leq\mathsf{V}(x)$ for all $x\in\mathbb{R}^{2}$ where $\alpha_{\mathsf{V}}:\mathbb{R}_{+}\ni s\mapsto s^{2}$ .

Now let $r<\overline{\rho}$ . Suppose that $\mathsf{X}$ is such that $\mathsf{X}\subseteq\overline{B}(0,\sqrt{r})$ and there exists $x\in\mathsf{X}$ with $\|x\|^{2}=r$ . As the computation depends on $r$ , we write $\overline{\mathsf{V}_{\mathsf{X}}}_{r}=\sup_{x\in\mathsf{X}}V(x)$ . Then, by definition of $\mathsf{V}$ , $\overline{\mathsf{V}_{\mathsf{X}}}_{r}=\sup_{x\in\mathsf{X}}\max\{\|x\|^{2},e\|\mathsf{H}(x)\|^{2}\}$ . By assumption on $\mathsf{X}$ , $\overline{\mathsf{V}_{\mathsf{X}}}_{r}=\max\{r,\mathfrak{f}(r)\}$ . Now, following Theorem 7,

h_{\mathsf{V},r}:\mathbb{R}^{+}\ni s\mapsto\sqrt{s\overline{\mathsf{V}_{\mathsf{X}}}_{r}}

(27)

satisfies $(h_{\mathsf{V},r},N_{\mathsf{H}}^{r}(\mathsf{V}))\in\mathbb{\Gamma}(\omega_{\mathsf{X}}^{i})$ for all $i\in\{1,2\}$ . This means that for all $k\in\mathbb{N}$

\omega_{\mathsf{X},k}^{1}=\sup_{x\in\mathsf{X}}\pi_{1}(\mathsf{H}^{k}(x))\leq\sqrt{N_{\mathsf{H}}^{r}(\mathsf{V})\overline{\mathsf{V}_{\mathsf{X}}}_{r}}\text{ and }\omega_{\mathsf{X},k}^{2}=\sup_{x\in\mathsf{X}}\pi_{2}(\mathsf{H}^{k}(x))\leq\sqrt{N_{\mathsf{H}}^{r}(\mathsf{V})\overline{\mathsf{V}_{\mathsf{X}}}_{r}}\kern 5.0pt.

Finally, it is easy to see that

h_{\mathsf{V},r}^{-1}:\mathbb{R}_{+}\ni s\to s^{2}/\overline{\mathsf{V}_{\mathsf{X}}}_{r}.

Since $h_{\mathsf{V},r}(0)=0$ , we only apply $h_{\mathsf{V},r}^{-1}$ to positive terms $\omega_{\mathsf{X},k}^{1}$ and $\omega_{\mathsf{X},k}^{2}$ .

5.3.2 Comparison with $\mathcal{K}\mathcal{L}$ upper bounds results

In Subsection 4.2.2, we considered the case where $\mathsf{X}\subseteq\overline{B}(0,\sqrt{r})$ with $r\leq\underline{\rho}$ . We recall that $\|x\|^{2}<\underline{\rho}$ is equivalent to $\|\mathsf{H}(x)\|^{2}<e^{-1}\|x\|^{2}$ , which is the same as $e\|\mathsf{H}(x)\|^{2}<\|x\|^{2}$ . Then, let $r<\underline{\rho}$ and $\mathsf{X}\subseteq\overline{B}(0,\sqrt{r})$ . We have for all $x\in\mathsf{X}$ , $\mathsf{V}(x)=\|x\|^{2}$ and thus $\overline{\|\cdot\|_{\mathsf{X}}}=\overline{\mathsf{V}_{\mathsf{X}}}_{r}$ . We conclude that $h_{\mathsf{V},r}$ defined in (27) and $h_{r}$ defined in (21) are equal. Moreover, in Subsection 4.2.2, we chose $(h_{r},e^{-1})\in\mathbb{\Gamma}(\omega_{\mathsf{X}}^{i})$ whereas we choose here $(h_{\mathsf{V},r},N_{\mathsf{H}}^{r}(\mathsf{V}))\in\mathbb{\Gamma}(\omega_{\mathsf{X}}^{i})$ . We proved that in Example 22 in the case where $r<\underline{\rho}$ , that $N_{\mathsf{H}}^{r}(\mathsf{V})<e^{-1}$ . From the first statement of Proposition 7, we have for all $k\in\mathbb{N}$ such that $\omega_{\mathsf{X},k}^{i}>0$ , $\mathfrak{F}_{\omega}(k,h_{\mathsf{V},r},N_{\mathsf{H}}^{r}(\mathsf{V}))\leq\mathfrak{F}_{\omega}(k,h_{r},e^{-1})$ .

For example, we go back the set $\mathsf{X}_{a}=\{x^{1},x^{2}\}$ where $x^{1}=(-1.3,-0.3)^{\intercal}$ and $x^{2}=(-1.1,-0.8)^{\intercal}$ . We have $\mathsf{X}_{a}\subseteq\overline{B}(0,\sqrt{1.85})$ with $\|x^{1}\|^{2}=1.85<\underline{\rho}$ . Then $h_{r}=h_{\mathsf{V},r}:\mathbb{R}_{+}\ni s:\mapsto s^{2}/1.85$ . However, in Example 2, the value of $N_{\mathsf{H}}^{1.85}(\mathsf{V})=1/32<e^{-1}$ and

\begin{array}[]{lcl}\mathfrak{F}_{\omega_{a}^{1}}(2,h_{\mathsf{V},r},N_{\mathsf{H}}^{1.85}(\mathsf{V}))&=&\dfrac{\ln(1.85)-2\ln\left(\max\{\pi_{1}(\mathsf{H}^{2}(x^{1}),\pi_{1}(\mathsf{H}^{2}(x^{2}))\}\right)}{\ln(32)}\approx 2.1183\\ &<&\mathfrak{F}_{\omega_{a}^{1}}(2,h_{r},e^{-1})\approx 7.3415\kern 5.0pt.\end{array}

This directly provides the stopping integer equal to 2 and saves computations for $\omega_{a}^{1}$ . We also have

\begin{array}[]{lcl}\mathfrak{F}_{\omega_{a}^{2}}(2,h_{\mathsf{V},r},N_{\mathsf{H}}^{1.85}(\mathsf{V}))&=&\dfrac{\ln(1.85)-2\ln\left(\max\{\pi_{2}(\mathsf{H}^{2}(x^{1}),\pi_{2}(\mathsf{H}^{2}(x^{2}))\}\right)}{\ln(32)}\approx 2.3222\\ &<&\mathfrak{F}_{\omega_{a}^{2}}(2,h_{r},e^{-1})\approx 8.0482\kern 5.0pt.\end{array}

Again, we save computations with respect to $\mathfrak{F}_{\omega_{a}^{2}}(2,h_{r},e^{-1})$ .

The case $\mathsf{X}_{b}=\{y^{1},y^{2}\}$ where $y^{1}=(-2.3,-0.013)^{\intercal}$ and $y^{2}=(0.7,-2.29)^{\intercal}$ is less significative as 5.7341 is close to $\underline{\rho}\approx 5.7481$ . We have $\mathsf{X}_{b}\subseteq\overline{B}(0,\sqrt{5.7341})$ with $\|y^{2}\|^{2}=5.7341<\underline{\rho}$ . Then $h_{r}=h_{\mathsf{V},r}:\mathbb{R}_{+}\ni s:\mapsto s^{2}/5.7341$ . However, in Example 2, the value of $N_{\mathsf{H}}^{5.7341}(\mathsf{V})=\dfrac{1+(5.7341-1)^{2}}{64}\approx 0.36581<e^{-1}\approx 0.36788$ and:

\mathfrak{F}_{\omega_{b}^{1}}(1,h_{\mathsf{V},r},N_{\mathsf{H}}^{5.7341}(\mathsf{V}))=\dfrac{2\ln(\pi_{1}(\mathsf{H}(y^{2}))-\ln(5.7341)}{\ln(N_{\mathsf{H}}^{5.7341}(\mathsf{V}))}\approx 2.44459<\mathfrak{F}_{\omega_{b}^{1}}(1,h_{r},e^{-1})\approx 2.4584;

We also have

\mathfrak{F}_{\omega_{b}^{2}}(3,h_{\mathsf{V},r},N_{\mathsf{H}}^{5.7341}(\mathsf{V}))=\dfrac{2\ln(\pi_{2}(\mathsf{H}^{3}(y^{1})))-\ln(5.7341)}{\ln(N_{\mathsf{H}}^{5.7341}(\mathsf{V}))}\approx 8.04905<\mathfrak{F}_{\omega_{b}^{2}}(3,h_{r},e^{-1})\approx 8.0945.

5.3.3 Numerical applications

In Subsection 4.2.2, we are limited to $\mathsf{X}\subseteq\overline{B}(0,\sqrt{r})$ where $r<\underline{\rho}$ . Considering such a radius $r$ , we obtain an upper bound of the form $\varphi(\mathsf{H}^{k}(z))\leq e^{-k/2}\|z\|$ . Now, we can consider a greater radius $r$ . We cannot exceed $\overline{\rho}$ since the norm explodes starting with vectors of norm greater than $\sqrt{\overline{\rho}}$ . As in Subsection 4.2.2, we consider two initial condition sets: the first is a singleton for which the norm of the vector is greater than $\sqrt{\underline{\rho}}$ . This will explain the difference from the cases developed in Subsection 4.2.2. In the second case, we start with two vectors with strictly negative coordinates, the norms of which are greater than $\sqrt{\underline{\rho}}$ . Let us define

1.

$\mathsf{X}_{c}=\{z^{0}\}$ where $z^{0}=(2.2,-2)^{\intercal}$ ;
2.

$\mathsf{X}_{d}=\{z^{1},z^{2}\}$ where $z^{1}=(-2.3,-1.9)^{\intercal}$ and $z^{2}=(-2.5,-1.5)^{\intercal}$ .

Again to simplify the notations, we write for all $i\in\{1,2\}$ , $\omega_{c}^{i}=(\omega_{c,k}^{i})_{k\in\mathbb{N}}$ and $\omega_{d}^{i}=(\omega_{d,k}^{i})_{k\in\mathbb{N}}$ instead of $\omega_{\mathsf{X}_{c}}^{i}$ and $\omega_{\mathsf{X}_{d}}^{i}$ . Recall that, for all $i\in\{c,d\}$ , $j\in\{1,2\}$ and $k\in\mathbb{N}$ :

\omega_{i,k}^{j}:=\sup_{x\in\mathsf{X}_{i}}\pi_{j}(\mathsf{H}^{k}(x)).

We can refine the definition of $h_{\mathsf{V},r}$ and $N_{\mathsf{H}}^{r}(\mathsf{V})$ . We write $h_{c}$ for the function associated with $\mathsf{X}_{c}$ and $h_{d}$ for the one associated with $\mathsf{X}_{d}$ . First, the smallest $r$ satisfying $\mathsf{X}_{c}\subseteq\overline{B}(0,\sqrt{r})$ is equal to $r^{c}:=\|z^{0}\|^{2}=8.84>\underline{\rho}$ . The smallest $r$ satisfying $\mathsf{X}_{d}\subseteq\overline{B}(0,\sqrt{r})$ is equal to $r^{d}=\max\{\|z^{1}\|^{2},\|z^{2}\|\}=8.9>\underline{\rho}$ . In both cases, the radius exceeds $\underline{\rho}$ , then $\overline{\mathsf{V}_{\mathsf{X}_{c}}}=e\|\mathsf{H}(z^{0})\|^{2}\approx 23.4535$ and $\overline{\mathsf{V}_{\mathsf{X}_{d}}}=e\max\{\|\mathsf{H}(z^{1})\|^{2},\|\mathsf{H}(z^{2})\|^{2}\}=e\|\mathsf{H}(z^{1})\|^{2}\approx 23.9697$ . To know the exact value of $N_{\mathsf{H}}^{r^{c}}(\mathsf{V})$ and $N_{\mathsf{H}}^{r^{d}}(\mathsf{V})$ , we have to check whether $\mathfrak{f}(r^{c})>\underline{\rho}$ and $f(r^{d})>\underline{\rho}$ . Since $\mathfrak{f}(r^{c})\approx 8.6281>\underline{\rho}$ and $\mathfrak{f}(r^{d})\approx 8.81795>\underline{\rho}$ , we conclude that $N_{\mathsf{H}}^{r^{c}}(\mathsf{V})=\mathfrak{g}(\mathfrak{f}(r^{c}))=\mathfrak{g}(\mathfrak{f}(8.84))\approx 0.9248$ and $N_{\mathsf{H}}^{r^{d}}(\mathsf{V})=\mathfrak{g}(\mathfrak{f}(r^{d}))=\mathfrak{g}(\mathfrak{f}(8.9))\approx 0.9706$ . Thus, we get:

h_{c}^{-1}:s\mapsto\dfrac{s^{2}}{e\|\mathsf{H}(z^{0})\|^{2}}\text{ and }h_{d}^{-1}:s\mapsto\dfrac{s^{2}}{e\|\mathsf{H}(z^{1})\|^{2}}

and we have, for all $j\in\{1,2\}$ and all $k$ such that $\omega_{c,k}^{j}>0$ :

\mathfrak{F}_{\omega_{c}^{j}}(k,h_{c},N_{\mathsf{H}}^{8.84}(\mathsf{V}))=\dfrac{2\ln(\pi_{j}(\mathsf{H}^{k}(z^{0}))-2\ln(\|\mathsf{H}(z^{0})\|)-1}{\ln(\mathfrak{g}(\mathfrak{f}(8.84)))}

and for all $j\in\{1,2\}$ and all $k$ such that $\omega_{d,k}^{j}>0$ :

\mathfrak{F}_{\omega_{d}^{j}}(k,h_{d},N_{\mathsf{H}}^{8.9}(\mathsf{V}))=\dfrac{2\ln(\max\{\pi_{j}(\mathsf{H}^{k}(z^{1})),\pi_{j}(\mathsf{H}^{k}(z^{2}))\})-2\ln(\|\mathsf{H}(z^{1})\|)-1}{\ln(\mathfrak{g}(\mathfrak{f}(8.9)))}

Then, we are able to apply Algorithm 1 to compute $\omega_{i,{\rm opt}}^{j}$ and the maximal integer solution $k_{i,{\rm max}}^{j}$ for $i\in\{c,d\}$ and $j\in\{1,2\}$ .

The case $\mathsf{X}_{c}=\{z^{0}\}$ where $z^{0}=(2.2,-2)^{\intercal}$

As $\pi_{1}(z^{0})>0$ we can compute directly a first stopping integer for $\omega_{c}^{1}$ and:

\mathfrak{F}_{\omega_{c}^{1}}(0,h_{\mathsf{V},r},N_{\mathsf{H}}^{8.84}(\mathsf{V}))=\dfrac{2\ln(2.2)-2\ln(\|\mathsf{H}(z^{0})\|)-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.84))\right)}\simeq 20.187

This means that we must compare the first 20 terms of $\omega_{c}^{1}$ . For $\omega_{c}^{2}$ , we cannot compute a stopping integer because $\pi_{2}(z^{0})\leq 0$ .

Then, we compute $\mathsf{H}(z^{0})$ (actually already computed since we need this value to compute $\mathfrak{F}_{\omega_{c}^{1}}$ ). Since

\mathsf{H}(z^{0})=\begin{pmatrix}2.406\\ -1.685\end{pmatrix}

we can update the stopping integer for $\omega_{c}^{1}$ and we have:

\mathfrak{F}_{\omega_{c}^{1}}(1,h_{c},N_{\mathsf{H}}^{8.84}(\mathsf{V}))=\dfrac{2\ln(2.406)-2\ln(\|\mathsf{H}(z^{0})\|-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.84))\right)}\simeq 17.897

This means that we finally compare the first 17 terms of $\omega_{c}^{1}$ . The second coordinate is still negative; thus, we cannot compute a stopping integer. Now, as

\mathsf{H}^{2}(z^{0})\approx\begin{pmatrix}2.50476\\ -1.30591\end{pmatrix}

we have

\mathfrak{F}_{\omega_{c}^{1}}(2,h_{c},N_{\mathsf{H}}^{8.84}(\mathsf{V}))=\dfrac{2\ln(\pi_{1}(\mathsf{H}^{2}(z^{0})))-2\ln(\|\mathsf{H}(z^{0})\|-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.84))\right)}\simeq 16.867

Then comparing the 16 first terms of $\omega_{c}^{1}$ leads to the conclusion that $\omega_{c,\rm opt}^{1}=\pi_{1}(\mathsf{H}^{2}(z^{0}))$ and $\operatorname{Argmax}(\omega_{c}^{1})=\{2\}$ .

For $\omega_{c}^{2}$ , we have to wait until $k=5$ to obtain $\pi_{2}(\mathsf{H}^{k}(z^{0}))>0$ . Then, we have:

\mathsf{H}^{5}(z^{0})\approx\begin{pmatrix}0.37921\\ 0.15155\end{pmatrix}

and

\mathfrak{F}_{\omega_{c}^{2}}(5,h_{c},N_{\mathsf{H}}^{8.84}(\mathsf{V}))=\dfrac{2\ln(\pi_{2}(\mathsf{H}^{5}(z^{0})))-2\ln(\|\mathsf{H}(z^{0})\|-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.84))\right)}\simeq 88.6294

We must compare the 88 first terms of $\omega_{c}^{2}$ to be guaranteed to pass the maximizer rank. However, the terms $\omega_{c,k}^{2}$ after $k=5$ are strictly smaller than $\pi_{2}(\mathsf{H}^{5}(z^{0}))$ (even the positive ones) and we conclude that $\omega_{c,\rm opt}^{2}=\pi_{2}(\mathsf{H}^{5}(z^{0}))$ and $\operatorname{Argmax}(\omega_{c}^{2})=\{5\}$ .

The case $\mathsf{X}_{d}=\{z^{1},z^{2}\}$ where $z^{1}=(-2.3,-1.9)^{\intercal}$ and $z^{2}=(-2.5,-1.5)^{\intercal}$

As both vectors have negative coordinates, we must wait for the first integers $k_{1}$ , $k_{2}$ such that $\omega_{d,k_{1}}^{1}>0$ and $\omega_{d,k_{2}}^{2}>0$ . We have, $\min\{k\in\mathbb{N}:\pi_{1}(T^{k}(z^{1}))>0\}=6$ , $\min\{k\in\mathbb{N}:\pi_{2}(T^{k}(z^{1}))>0\}=7$ , $\min\{k\in\mathbb{N}:\pi_{1}(T^{k}(z^{2}))>0\}=4$ and $\min\{k\in\mathbb{N}:\pi_{2}(T^{k}(z^{2}))>0\}=5$ . As $\pi_{1}(T^{4}(z^{2}))\approx 0.08955$ and $\pi_{2}(T^{5}(z^{2}))\approx 0.0309$ , we can compute:

\mathfrak{F}_{\omega_{d}^{1}}(4,h_{d},N_{\mathsf{H}}^{8.9}(\mathsf{V}))=\dfrac{2\ln(\pi_{1}(\mathsf{H}^{4}(z^{2})))-2\ln(\|\mathsf{H}(z^{1})\|-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.9))\right)}\simeq 268.47

and

\mathfrak{F}_{\omega_{d}^{2}}(5,h_{d},N_{\mathsf{H}}^{8.9}(\mathsf{V}))=\dfrac{2\ln(\pi_{2}(\mathsf{H}^{5}(z^{2})))-2\ln(\|\mathsf{H}(z^{1})\|-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.9))\right)}\simeq 339.85

meaning that $\omega_{d,{\rm opt}}^{1}=\max\{\omega_{d,k}^{1}:k=0,\ldots,268\}$ and $\omega_{d,{\rm opt}}^{2}=\max\{\omega_{d,k}^{2}:k=0,\ldots,339\}$ .

Then, we compute the next images of $z^{1}$ and $z^{2}$ by $\mathsf{H}$ . We find that $\pi_{1}(\mathsf{H}^{6}(z^{1}))\approx 0.1512>\pi_{1}(\mathsf{H}^{4}(z^{2}))$ and thus we update the stopping integer for $\omega_{d}^{1}$ and we find:

\mathfrak{F}_{\omega_{d}^{1}}(6,h_{d},N_{\mathsf{H}}^{8.9}(\mathsf{V}))=\dfrac{2\ln(\pi_{1}(\mathsf{H}^{6}(z^{1})))-2\ln(\|\mathsf{H}(z^{1})\|-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.9))\right)}\simeq 233.34.

The new stopping integer for $\omega_{d}^{1}$ is set to 233. The next values of $\omega_{d,k}^{1}$ are smaller than $\pi_{1}(\mathsf{H}^{6}(z^{1}))$ and thus we conclude that $\omega_{d,\rm opt}^{1}=\pi_{1}(\mathsf{H}^{6}(z^{1}))$ and $\operatorname{Argmax}(\omega_{d}^{1})=\{6\}$ .

The same situation holds for $\omega_{d}^{2}$ . Indeed, $\pi_{2}(\mathsf{H}^{7}(z^{1}))\approx 0.0435835>\pi_{2}(\mathsf{H}^{5}(z^{2}))$ and we have

\mathfrak{F}_{\omega_{d}^{2}}(7,h_{d},N_{\mathsf{H}}^{8.9}(\mathsf{V}))=\dfrac{2\ln(\pi_{2}(\mathsf{H}^{7}(z^{1})))-2\ln(\|\mathsf{H}(z^{1})\|-1}{\ln\left(\mathfrak{g}(\mathfrak{f}(8.9))\right)}\simeq 316.78

The new stopping integer for $\omega_{d}^{2}$ is set to 316. The next values of $\omega_{d,k}^{2}$ are smaller than $\pi_{2}(\mathsf{H}^{7}(z^{1}))$ and thus we conclude that $\omega_{d,\rm opt}^{2}=\pi_{2}(\mathsf{H}^{7}(z^{1}))$ and $\operatorname{Argmax}(\omega_{d}^{2})=\{7\}$ .

6 Concluding remarks

In this paper, we solved specific discrete-time peak computation problems. In general, discrete-time peak computation problems consist in searching, for a given objective function, for the reachable value of a given discrete-time system that maximizes the objective function. The optimal value of this maximization problem can be viewed as the supremum of a sequence of optimal values. The solution proposed in this paper is thus based on previous results, allowing us to compute the maximum of a real sequence. The computational method requires a particular sequence greater than the analyzed sequence. This particular sequence is the image of a positive convergent geometric sequence by a strictly increasing continuous function on $[0,1]$ . In this paper, we use the structure of the problem (i.e., the dynamical system) to compute the strictly increasing continuous and the positive convergent geometric sequence. The construction of these elements requires the stability of the discrete-time system, as they are constructed from $\mathcal{K}\mathcal{L}$ certificates and Lyapunov functions. We illustrate the techniques on an example from the literature.

Three main questions remain unsolved and are left for future work. First, how can we solve a discrete-time peak computation problem for which the underlying system diverges? Second, for nonlinear systems, how can discrete-time peak computation problems be managed with an infinite bounded initial conditions set? Finally, how can the number of unuseful computations be reduced?

References

[Adj17] A. Adjé. Proving properties on PWA systems using copositive and semidefinite programming. In Numerical Software Verification: 9th International Workshop, NSV 2016, Toronto, ON, Canada, July 17-18, 2016, Revised Selected Papers 9, pages 15–30. Springer, 2017.
[Adj21] A. Adjé. Quadratic maximization of reachable values of affine systems with diagonalizable matrix. J. Optim. Theory Appl., 189(1):136–163, 2021.
[Adj24] A. Adjé. A parametric optimization point-of-view of comparison functions. arXiv preprint arXiv:2408.14440, 2024.
[Adj25a] A. Adjé. Quadratic maximization of reachable values of stable discrete-time affine systems. To appear in Optimization, pages 1–52, 2025.
[Adj25b] Assalé Adjé. On the maximization of real sequences, 2025.
[AG24] A. A. Ahmadi and O. Günlük. Robust-to-dynamics optimization. Mathematics of Operations Research, 2024.
[AGM15] A. Adjé, P.-L. Garoche, and V. Magron. Property-based polynomial invariant generation using sums-of-squares optimization. In Static Analysis: 22nd International Symposium, SAS 2015, Saint-Malo, France, September 9-11, 2015, Proceedings 22, pages 235–251. Springer, 2015.
[AL11] M. F. Anjos and J.B Lasserre. Handbook on semidefinite, conic and polynomial optimization, volume 166. Springer Science & Business Media, 2011.
[APS18] U. M. Ahiyevich, S. E. Parsegov, and P. S. Shcherbakov. Upper bounds on peaks in discrete-time linear systems. Automation and Remote Control, 79:1976–1988, 2018.
[ATP10] A. Loria A.R. Teel, D. Nešić and E. Panteley. Summability characterizations of uniform exponential and asymptotic stability of sets for difference inclusions. Journal of Difference Equations and Applications, 16(2-3):173–194, 2010.
[Ber15] D. Bertsekas. Convex optimization algorithms. Athena Scientific, 2015.
[BTN01] A. Ben-Tal and A. Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001.
[BYG17] C. Belta, B. Yordanov, and E. A. Gol. Formal methods for fiscrete-time dynamical systems, volume 89. Springer, 2017.
[Ela05] S. Elaydi. An introduction to difference equations. 2005.
[Els12] E.M. Elsayed. Solutions of rational difference systems of order two. Mathematical and Computer Modelling, 55(3):378–384, 2012.
[GGLW14] R. Geiselhart, R. H. Gielen, M. Lazar, and F. R. Wirth. An alternative converse Lyapunov theorem for discrete-time systems. Systems & Control Letters, 70:49–59, 2014.
[GH15] P. Giesl and S. Hafstein. Review on computational methods for Lyapunov functions. Discrete and Continuous Dynamical Systems-B, 20(8):2291–2331, 2015.
[GRR10] M Ranferi Gutiérrez, M A Reyes, and H C Rosu. A note on verhulst’s logistic equation and related logistic maps. Journal of Physics A: Mathematical and Theoretical, 43(20):205204, apr 2010.
[HR18] Yacine Halim and Julius Fergy Rabago. On the solutions of a second-order difference equation in terms of generalized padovan sequences. Mathematica Slovaca, 68, 06 2018.
[Kel14] C. M. Kellett. A Compendium of comparison function results. Math. Control. Signals Syst., 26(3):339–374, 2014.
[Kel15] Christopher M. Kellett. Classical converse theorems in lyapunov’s second method. Discrete and Continuous Dynamical Systems - B, 20(8):2333–2360, 2015.
[Kha02] H.K. Khalil. Nonlinear systems. Pearson Education. Prentice Hall, 3rd edition, 2002.
[KP01] W. G. Kelley and A. C. Peterson. Difference equations: an introduction with applications. Academic press, 2001.
[Las15] J.-B. Lasserre. An introduction to polynomial and semi-algebraic optimization. Cambridge Texts in Applied Mathematics. Cambridge University Press, 2015.
[Laz06] M. Lazar. Model predictive control of hybrid systems: stability and robustness. Phd thesis, T.U. Eindhoven, Sept 2006.
[LHK14a] H. Li, S. Hafstein, and C. M. Kellett. Computation of lyapunov functions for discrete-time systems using the yoshizawa construction. In 53rd IEEE conference on decision and control, pages 5512–5517. IEEE, 2014.
[LHK14b] H. Li, S. Hafstein, and C. M. Kellett. Computation of Lyapunov functions for discrete-time systems using the Yoshizawa construction. In 53rd IEEE Conference on Decision and Control, pages 5512–5517, 2014.
[MHL15] Victor Magron, Didier Henrion, and Jean-Bernard Lasserre. Semidefinite approximations of projections and polynomial images of semialgebraic sets. SIAM Journal on Optimization, 25(4):2143–2164, 2015.
[MHS20] J. Miller, D. Henrion, and M. Sznaier. Peak estimation recovery and safety analysis. IEEE Control Systems Letters, 5(6):1982–1987, 2020.
[NT04] D. Nešić and A. R. Teel. Matrosov theorem for parameterized families of discrete-time systems. Automatica, 40(6):1025–1034, 2004.
[RKML06] S. V. Rakovic, E. C. Kerrigan, D. Q. Mayne, and J. Lygeros. Reachability analysis of discrete-time systems with disturbances. IEEE Transactions on Automatic Control, 51(4):546–561, 2006.
[Son98] E. D. Sontag. Comments on integral variants of ISS. Systems & Control Letters, 34(1):93–100, 1998.
[Ste14] Stevo Stevic. Representation of solutions of bilinear difference equations in terms of generalized fibonacci sequences. Electron. J. Qual. Theory Differ. Equ, 67(1):15, 2014.

Appendix

Lemma 3.

Let us consider the map $\mathsf{H}$ in (4). Let $x\in\mathbb{R}^{2}$ be a nonzero vector such that $\|\mathsf{H}^{k}(x)\|$ tends to 0 as $k$ tends to $+\infty$ . There exists $k_{1},k_{2}\in\mathbb{N}$ such that $\pi_{1}(\mathsf{H}^{k_{1}}(x))>0$ and $\pi_{2}(\mathsf{H}^{k_{2}}(x))>0$ .

Proof.

Actually, it suffices to prove that for all $x$ in the open unit ball, there exists $k_{1},k_{2}\in\mathbb{N}$ , such that $\pi_{1}(\mathsf{H}^{k_{1}}(x))>0$ and $\pi_{2}(\mathsf{H}^{k_{2}}(x))>0$ . Indeed, if $\|\mathsf{H}^{k}(x)\|$ converges to 0, then $\mathsf{H}^{k}(x)$ eventually enters the open unit ball. The worst situation is when $\mathsf{H}^{k}(x)$ has only negative coordinates before entering the open unit ball.

Therefore, let us consider $z\in\mathbb{R}^{2}$ not being 0 and such that $\|z\|<1$ . First, we consider $\pi_{1}$ . If $z_{1}>0$ the result obviously holds. Therefore, we suppose that $z_{1}\leq 0$ . If $z_{2}\leq 0$ (with $z_{2}\neq 0$ if $z_{1}=0$ ), as $\|z\|<1$ , we have $\pi_{1}(\mathsf{H}(z))>0$ . Now, suppose that $z_{2}>0$ . Since $z_{1}<0$ , we have $\pi_{2}(\mathsf{H}(z))<0$ . Recall that for all $y\in\overline{B}(0,\sqrt{r})$ where $r<\overline{\rho}$ , $\|\mathsf{H}(y)\|^{2}<\|y\|^{2}$ . If $\pi_{1}(\mathsf{H}(z))>0$ , the result follows. Thus, if $\pi_{1}(\mathsf{H}(z))\leq 0$ , we get $\pi_{1}(\mathsf{H}^{2}(z))>0$ since $\|\mathsf{H}(z)\|<1$ and $\pi_{1}(\mathsf{H}(z))<0$ and $\pi_{2}(\mathsf{H}(z))<0$ .

Now, we prove the result for $\pi_{2}$ . The result trivially holds if $z_{2}>0$ . So, we suppose that $z_{2}\leq 0$ . If $z_{1}\geq 0$ ( $z_{1}\neq 0$ if $z_{2}=0$ ), then, as $\|z\|<1$ , we get $\pi_{2}(\mathsf{H}(z))>0$ . Now, assume that $z_{1}<0$ . Then, it leads to $\pi_{1}(\mathsf{H}(z))>0$ . If $\pi_{2}(\mathsf{H}(z))>0$ , the results holds. Assuming that $\pi_{2}(\mathsf{H}(z))<0$ , then from the fact that $\|\mathsf{H}(z)\|<\|z\|<1$ , $\pi_{1}(\mathsf{H}(z))>0$ and $\pi_{2}(\mathsf{H}(z))<0$ , we get $\pi_{2}(\mathsf{H}^{2}(z))>0$ .

∎

𝒦​ℒ\mathcal{K}\mathcal{L} and Lyapunov Approaches for Discrete-time Peak Computation Problems

Abstract

1 Introduction

2 Problem formulation

2.1 Problem formulation

Definition 1 (Stopping integer).

2.2 Practical limitations

Assumption 1.

2.3 Running example

3 Preliminary results

3.1 Results on the supremum of a real sequence

3.1.1 Notations and basic results

Proposition 1.

Proposition 2.

3.1.2 A formula based on pairs of strictly increasing continuous functions and convergent geometric sequences

Proposition 3.

Proposition 4.

Definition 2 (Useful strictly increasing continuous functions).

Theorem 1 (Existence of a useful optimal affine function).

Corollary 1.

Proposition 5.

3.1.3 Properties of 𝔉u\mathfrak{F}_{u} and the computation of the supremum of a sequence

Proposition 6.

Proposition 7.

Proposition 8.

Theorem 2 (Solution for (12)).

Theorem 3 (Formula optimality).

Problem 1.

3.2 Elements of comparison functions

Definition 3 (𝒦\mathcal{K}/𝒦∞\mathcal{K}_{\infty} functions classes).

Definition 4 (ℒ\mathcal{L} functions class).

Definition 5 (𝒦​ℒ\mathcal{K}\mathcal{L} functions class).

Assumption 2.

Proposition 9 (Lemma 4.3/Appendix C.4 [Kha02]).

4 Solving problem 1 from 𝒦​ℒ\mathcal{K}\mathcal{L} bounds

4.1 Theoretical constructions from 𝒦​ℒ\mathcal{K}\mathcal{L} functions

Lemma 1 (Proposition 7 of [Son98]).

Theorem 4 (Relaxed 𝒦​ℒ\mathcal{K}\mathcal{L} construction).

Proof.

Theorem 5 (Classical 𝒦​ℒ\mathcal{K}\mathcal{L} construction).

Proof.

Remark 1.

4.2 Application to the running example of Subsection 2.3

4.2.1 Theoretical developments of the running example using a 𝒦​ℒ\mathcal{K}\mathcal{L} upper bound function.

4.2.2 Numerical applications.

The case 𝖷a={x1,x2}\mathsf{X}_{a}=\{x^{1},x^{2}\} where x1=(−1.3,−0.3)⊺x^{1}=(-1.3,-0.3)^{\intercal} and x2=(−1.1,−0.8)⊺x^{2}=(-1.1,-0.8)^{\intercal}

The case 𝖷b={y1,y2}\mathsf{X}_{b}=\{y^{1},y^{2}\} where y1=(−2.3,0.013)⊺y^{1}=(-2.3,0.013)^{\intercal} and y2=(0.7,−2.29)⊺y^{2}=(0.7,-2.29)^{\intercal}

5 Solving Problem 1 from Lyapunov functions

5.1 Definition and useful facts

Definition 6 (Classical Lyapunov functions).

Example 1.

Definition 7 (Local positive definite ratio operators).

Proposition 10.

Proof.

Corollary 2.

Proof.

Example 2 (The local positive definite ratio operator of 𝖧\mathsf{H} at 𝖵\mathsf{V} on closed balls).

5.2 Theoretical constructions from Lyapunov functions

Lemma 2.

Proof.

Remark 2.

Theorem 6 (Direct Lyapunov construction).

Proof.

Remark 3.

Theorem 7 (Continuous Lyapunov construction).

Proof.

Remark 4.

5.3 Numerical applications to our running example of Subsection 2.3

5.3.1 Theoretical developments of the running example using 𝖵\mathsf{V}

5.3.2 Comparison with 𝒦​ℒ\mathcal{K}\mathcal{L} upper bounds results

5.3.3 Numerical applications

The case 𝖷c={z0}\mathsf{X}_{c}=\{z^{0}\} where z0=(2.2,−2)⊺z^{0}=(2.2,-2)^{\intercal}

The case 𝖷d={z1,z2}\mathsf{X}_{d}=\{z^{1},z^{2}\} where z1=(−2.3,−1.9)⊺z^{1}=(-2.3,-1.9)^{\intercal} and z2=(−2.5,−1.5)⊺z^{2}=(-2.5,-1.5)^{\intercal}

6 Concluding remarks

References

Appendix

Lemma 3.

Proof.

$\mathcal{K}\mathcal{L}$ and Lyapunov Approaches for Discrete-time Peak Computation Problems

3.1.3 Properties of $\mathfrak{F}_{u}$ and the computation of the supremum of a sequence

Definition 3 ( $\mathcal{K}$ / $\mathcal{K}_{\infty}$ functions classes).

Definition 4 ( $\mathcal{L}$ functions class).

Definition 5 ( $\mathcal{K}\mathcal{L}$ functions class).

4 Solving problem 1 from $\mathcal{K}\mathcal{L}$ bounds

4.1 Theoretical constructions from $\mathcal{K}\mathcal{L}$ functions

Theorem 4 (Relaxed $\mathcal{K}\mathcal{L}$ construction).

Theorem 5 (Classical $\mathcal{K}\mathcal{L}$ construction).

4.2.1 Theoretical developments of the running example using a $\mathcal{K}\mathcal{L}$ upper bound function.

The case $\mathsf{X}_{a}=\{x^{1},x^{2}\}$ where $x^{1}=(-1.3,-0.3)^{\intercal}$ and $x^{2}=(-1.1,-0.8)^{\intercal}$

The case $\mathsf{X}_{b}=\{y^{1},y^{2}\}$ where $y^{1}=(-2.3,0.013)^{\intercal}$ and $y^{2}=(0.7,-2.29)^{\intercal}$

Example 2 (The local positive definite ratio operator of $\mathsf{H}$ at $\mathsf{V}$ on closed balls).

5.3.1 Theoretical developments of the running example using $\mathsf{V}$

5.3.2 Comparison with $\mathcal{K}\mathcal{L}$ upper bounds results

The case $\mathsf{X}_{c}=\{z^{0}\}$ where $z^{0}=(2.2,-2)^{\intercal}$

The case $\mathsf{X}_{d}=\{z^{1},z^{2}\}$ where $z^{1}=(-2.3,-1.9)^{\intercal}$ and $z^{2}=(-2.5,-1.5)^{\intercal}$