# Computationally efficient robust MPC
using optimized constraint tightening

Anilkumar Parsi, Panagiotis Anagnostaras, Andrea Iannelli, Roy S. Smith  This
work is supported by the Swiss National Science Foundation under grant no.
$200021\\_178890$. The authors are with the Automatic Control Lab, ETH Zürich,
Switzerland. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A robust model predictive control (MPC) method is presented for linear, time-
invariant systems affected by bounded additive disturbances. The main
contribution is the offline design of a disturbance-affine feedback gain
whereby the resulting constraint tightening is minimized. This is achieved by
formulating the constraint tightening problem as a convex optimization problem
with the feedback term as a variable. The resulting MPC controller has the
computational complexity of nominal MPC, and guarantees recursive feasibility,
stability and constraint satisfaction. The advantages of the proposed approach
compared to existing robust MPC methods are demonstrated using numerical
examples.

##  I INTRODUCTION

Model predictive control (MPC) is a powerful control design technique which
can naturally handle multiple input multiple output systems and hard
constraints on states and inputs while guaranteeing stability of the closed-
loop [1].

Robust MPC methods consider the case where an exact model of the system is not
available. The simplest form of uncertainty is represented by an additive
disturbance acting on the state dynamics (or process noise). This problem has
been extensively studied for linear systems in the robust MPC literature [2]
and a typical approach is to split the design problem into two parts. In the
first part, called the prediction horizon, a sequence of control laws is
computed such that the system’s state at the end of the prediction horizon
reaches a terminal set. Then, the terminal set is designed such that it is an
invariant set of the uncertain system under linear feedback and lies within
feasible region of the state space.

In order to achieve tractable formulations, various parameterizations of the
control law have been proposed in the literature. One of the early approaches,
referred to in the rest of the paper as Tube MPC (TMPC), uses an affine state
feedback policy in the prediction horizon [3]. In [4], a similar
parameterization is used in combination with a state tube. The state tube is a
sequence of parameterized sets containing all feasible trajectories of the
system. Whereas [4] computes the evolution of the state tube online, [3] uses
a constraint tightening approach to ensure that all future realizations of the
state lie within the constraint set. A comparison between these two methods
can be found in [5], where it was shown that the constraint tightening
approach in [3] results in a slightly improved performance. Various methods
have been proposed which use alternative parameterizations of the state
feedback controller within the prediction horizon [6], or use a flexible
formulation to represent the state tube [7].

An alternative parameterization, which alleviates the conservatism associated
with a fixed state-feedback policy, was proposed in [8] in terms of
disturbance-affine feedback control actions. Such a parameterization enables
online optimization of the disturbance affine feedback gain. This results in
much larger regions of attraction compared to strategies such as [3, 4], where
the state feedback term is computed offline. However, the size of the online
optimization problem grows quadratically with the length of the prediction
horizon.  The aforementioned robust MPC methods have been combined with
reinforcement learning techniques [9], and successfully implemented on real-
world systems [10]. Nevertheless, the previously discussed aspects concerning
conservatism and scalability remain open problems and thus motivated the
current work.  A recent, related work is [11], where conservatism is reduced
by parameterizing state and input trajectories of the system using future
disturbances.

In this paper, a novel way to design robust MPC controllers for linear time-
invariant systems affected by additive disturbances is presented. In order to
guarantee robust constraint satisfaction with a computationally efficient
program that can be efficiently solved online, a constraint tightening
approach is used. Owing to the improved performance of disturbance affine
feedback [8] compared to state feedback, a similar parameterization of the
control law is used within the prediction horizon. The main contribution of
this work is to formulate the constraint tightening as a convex function of
the disturbance affine feedback gain. This effectively allows offline
optimization over the constraint tightening and thus, indirectly, over the
size of the region of attraction. The optimized tightened constraints are used
to formulate the online MPC problem whose size grows linearly with the length
of the prediction horizon. Numerical simulations show that the computation
times are one order of magnitude faster compared to the approach presented in
[8], while improving on the region of attraction obtained with TMPC [3].

#### Notation

The $i^{th}$ row of a matrix $A$ is denoted by $[A]_{i}$. The value of $x$ at
the $k^{th}$ time-step is denoted by $x_{k}$, and $x_{k,i}$ denotes the value
of $x$ $i$ steps after the current time-step $k$. For a matrix $A$, vector $y$
and a set $Y$ of appropriate dimensions, $\max_{y\in Y}Ay$ refers to row-wise
maximization. The set of real numbers is denoted by $\mathbb{R}$ and the
sequence of non-negative integers from $a$ to $b$ is represented by
$\mathbb{Z}_{[a,b]}$. The symbol $\geq$ when used for matrices denotes
element-wise comparison, $\preccurlyeq$ denotes a conic constraint  and
$\otimes$ denotes the Kronecker product.

##  II BACKGROUND

###  II-A Problem formulation

This work considers discrete-time, linear, time-invariant systems of the
following form

$\displaystyle x_{k+1}=Ax_{k}+Bu_{k}+B_{w}w_{k},$ (1)

where $x_{k}\in\mathbb{R}^{n_{x}},u_{k}\in\mathbb{R}^{n_{u}}$ and
$w_{k}\in\mathbb{R}^{n_{w}}$ denote the state of the system, the control input
and the additive disturbance respectively at time-step $k$.  The matrices
$A,B$ and $B_{w}$ are known and no assumptions are made on their structure.
Full state feedback is assumed, and the state and the input are constrained as

$\displaystyle(x_{k},u_{k})\in\mathbb{C}:=\\{(x,u)|Fx+Gu\leq b\\},$ (2)

where $F\in\mathbb{R}^{n_{c}\times n_{x}},G\in\mathbb{R}^{n_{c}\times n_{u}}$
and $b\in\mathbb{R}^{n_{c}}$.

###### Assumption 1

The additive disturbance $w_{k}$ lies in a bounded polytope $\mathbb{W}$ which
contains the origin, defined as

$\displaystyle\mathbb{W}\subseteq\mathbb{R}^{n_{w}}=\\{w|Dw\leq d\\}.$ (3)

where $D\in\mathbb{R}^{n_{d}\times n_{w}}$ and $d\in\mathbb{R}^{n_{d}}$,

The goal is to design a control policy in order to steer the system governed
by (1) from a given initial condition $x_{0}$, to a region around the origin
while guaranteeing that the constraints in (2) are robustly satisfied, i.e.,
for all noise realizations compatible with (3). Moreover, the following cost
function is desired to be minimized

$\displaystyle
J=\textstyle\sum_{i=0}^{\infty}{x}_{k}^{T}Q{x}_{k}+{u}_{k}^{T}R{u}_{k}.$ (4)

A MPC algorithm will be used to achieve the above control task. The infinite
horizon problem is relaxed by considering a finite prediction horizon of $N$
time-steps, introducing appropriate terminal ingredients, and solving a
receding horizon optimization problem [1]. Because the cost function (4)
depends on future disturbances, a disturbance-free prediction is used to
formulate the MPC cost function.

###  II-B Existing methodologies

The existing methodologies in the relevant robust MPC literature differ in the
way the control input is parameterized within the prediction horizon. In tube
MPC methods [3] [4], the prediction of the future states $x_{k,i}$ is split
into nominal $\hat{x}_{k,i}$ and error $e_{k,i}$ components such that
$e_{k,i}=x_{k,i}-\hat{x}_{k,i}$.  In [3], the parameterization
$u_{k,i}=\hat{u}_{k,i}+Ke_{k,i},\>\>i\in\mathbb{Z}_{[0,N-1]}$ is used to
obtain the following dynamics for $i\in\mathbb{Z}_{[0,N-1]}$,

$\displaystyle\hat{x}_{k,i+1}=A\hat{x}_{k,i}+B\hat{u}_{k,i},\quad\hat{x}_{k,0}=x_{k},$
(5a) $\displaystyle e_{k,i+1}=(A+BK)e_{k,i}+B_{w}w_{k,i},\quad e_{k,0}=0,$
(5b)

where $K\in\mathbb{R}^{n_{u}\times n_{x}}$ is a precomputed feedback gain and
$\hat{u}_{k,i}$ are online optimization variables. The state at the end of the
prediction horizon is driven into a terminal set, where the control law
$u_{k,i}{=}Kx_{k,i}$ is always feasible and  ensures forward invariance of the
terminal set. Because the dynamics in (5b) are completely determined by $A,B$
and $K$, the worst-case evolution of the error components are used to tighten
the constraint set $\mathbb{C}$ offline, thereby ensuring constraint
satisfaction under any possible disturbance sequence in the future. The method
in [4] computes a robust invariant set for the dynamics (5b) which is then
used to tighten $\mathbb{C}$.  However, both these strategies lead to a
reduction in the region of attraction (ROA) of the closed loop system, and
there is not a systematic way of choosing $K$ to reduce the conservatism.

An alternative approach which yields larger ROA is presented in [8], which
uses a disturbance affine feedback gain to parameterize the control input, as
${u}_{k,0}{=}\hat{u}_{k,0}$ and
${u}_{k,i}=\hat{u}_{k,i}+\sum_{j=0}^{i-1}M_{i,j}B_{w}{w}_{k,j}$, for
$i{\in}\mathbb{Z}_{[1,N-1]}$ where $\hat{u}_{k,i}$ and
$M_{i,j}\in\mathbb{R}^{n_{u}\times n_{x}}$ are online optimization variables.
This method is referred to as fully parameterized disturbance affine MPC (FPD)
in the remainder of this paper.

The input parameterization used in TMPC and FPD are related to each other, as
shown below. Define
$\mathbf{u}_{k}=[u_{k,0}^{T},u_{k,1}^{T},\ldots,u_{k,N-1}^{T}]^{T}$,
$\mathbf{\hat{u}}_{k}=[\hat{u}_{k,0}^{T},\hat{u}_{k,1}^{T},\ldots,\hat{u}_{k,N-1}^{T}]^{T}$
and $\mathbf{w}_{k}=[w_{k,0}^{T},w_{k,1}^{T},\ldots,w_{k,N-1}^{T}]^{T}$. Then,
the control laws for TMPC and FPD can be compactly written as

$\displaystyle\begin{split}\mathbf{u}_{k}=\mathbf{\hat{u}}_{k}+\mathbf{H}\mathbf{B_{w}}\mathbf{w}_{k},\;\;\mathbf{H}=\begin{cases}\mathbf{K}\quad&\textnormal{for
TMPC \cite[cite]{[\@@bibref{}{Chisci}{}{}]}},\\\
\mathbf{M}\quad&\textnormal{for FPD
\cite[cite]{[\@@bibref{}{Goulart}{}{}]}},\end{cases}\end{split}$ (6)

where $\mathbf{B_{w}}=I_{N}\otimes B_{w}$. In (6), the gain $\mathbf{K}$ is
given by

$\displaystyle\mathbf{K}:=\begin{bmatrix}0&...&...&...&0\\\ K&0&...&...&0\\\
K(A+BK)&K&...&...&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
K(A+BK)^{N-2}&...&...&K&0\end{bmatrix},$ (7)

and $\mathbf{M}$ is also a strictly lower triangular matrix where the non-zero
blocks are the individual feedback gains $M_{i,j}$. Because the latter are
chosen online, the control parameterization used in FPD is much more flexible
than TMPC. This results in improved closed loop performance and a larger ROA
compared to TMPC. This comes at an increase in the required computational
effort. By fixing $\mathbf{K}$ offline, the computational complexity of TMPC
is the same as that of nominal MPC. In contrast, the number of optimization
variables in FPD grows quadratically with the length of the prediction horizon
and the number of state variables. Another recent method, called fusion of
tubes MPC [12] tries to improve the performance of TMPC by choosing the
feedback gain as a linear combination of a finite number of predefined gains
$K^{[j]}$. However, a systematic design procedure of the predefined gains is
not provided.

##  III Offline design for constraint tightening

A disturbance affine feedback policy is used for control in light of its
ability to parameterize closed loop trajectories as optimization variables
[8]. In this section, the relationship between the disturance feedback gain
and the resulting constraint tightening will be established. In addition,
design conditions for the terminal controller and terminal set will be
formulated.

###  III-A Input parameterization and tightened constraint sets

The control input is parameterized as

$\displaystyle\mathbf{u}_{k}=\hat{\mathbf{u}}_{k}+\mathbf{M}_{\text{off}}\mathbf{B_{w}}\mathbf{w}_{k}$
(8)

where $\hat{\mathbf{u}}_{k}$ are online optimization variables and
$\mathbf{M}_{\text{off}}$ is a matrix computed offline. In order to ensure
causality and recursive feasibility by design, $\mathbf{M}_{\text{off}}$
satisfies the structure

$\displaystyle\begin{split}\mathbf{M}_{\text{off}}=\begin{bmatrix}0&0&0&...&0\\\
M_{1}^{\text{off}}&0&0&...&0\\\
M_{2}^{\text{off}}&M_{1}^{\text{off}}&0&...&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
M_{N-1}^{\text{off}}&...&...&M_{1}^{\text{off}}&0\end{bmatrix}\end{split}$ (9)

where $M^{\text{off}}_{i}{\in}\mathbb{R}^{n_{u}{\times}n_{x}}$. Let
$\mathcal{M}$ denote the set of matrices satisfying (9).  Because
$M_{1}^{\text{off}},\ldots,M_{N-1}^{\text{off}}$ can be independently chosen,
(9) is less restrictive compared to (7).

Under the proposed feedback law (8), the state dynamics follow (5a) and the
error dynamics can be written as

$\displaystyle e_{k,i+1}$
$\displaystyle=Ae_{k,i}+B\textstyle\sum_{j=0}^{i}M_{i{\color[rgb]{0,0,0}-j}}^{\text{off}}B_{w}w_{k,j},$
(10)

where $e_{k,0}=0$, $i\in\mathbb{Z}_{[0,N-1]}$ and
$BM_{0}^{\text{off}}:=I_{n_{x}}$ is a notational overload used for simplicity.
The predicted error can be compactly written for $i\in\mathbb{Z}_{[0,N-1]}$ as

$\displaystyle\begin{split}e_{k,i+1}&=\textstyle\sum_{l=0}^{i}\bigr{(}\textstyle\sum_{j=0}^{i-l}A^{j}BM^{\text{off}}_{i-l-j}\bigr{)}B_{w}w_{k,l}.\end{split}$
(11)

For $i{\in}\mathbb{Z}_{[0,N-1]}$, define
$\mathbb{E}_{i}:=\\{(e_{k,i},u_{k,i}-\hat{u}_{k,i})|\>\eqref{eq:CompactError},\>w_{k,l}\in\mathbb{W},\>\forall
l\in\mathbb{Z}_{[0,i-1]}\\}$. Using this sequence of sets, tightened
constraints can be imposed on the nominal state and input sequences. For this
purpose, define $\forall i\in\mathbb{Z}_{[0,N-1]}$

$\mathbb{C}_{i}:=\mathbb{C}\ominus\mathbb{E}_{i}=\\{(x,u)|Fx+Gu\leq
b-t_{i}\\},$ (12)

where $t_{i}{\in}\mathbb{R}^{n_{c}}$ represents the tightening applied on
$\mathbb{C}$ $i$ time-steps into the future. The predicted trajectories in the
online optimization problem must thus satisfy
$(\hat{x}_{k,i},\hat{u}_{k,i})\in\mathbb{C}_{i}$ for all
$i\in\mathbb{Z}_{[0,N-1]}$.

In order to compactly represent the tightened state and input constraints, the
following notation is introduced. Let
$\mathbf{x}_{k}=[x_{k,0}^{T},x_{k,1}^{T},...,x_{k,N-1}^{T}]^{T}$,
$\mathbf{t}=[t_{0}^{T},\ldots,t_{N-1}^{T}]^{T}$ and
$\mathcal{W}=\mathbb{W}\times\mathbb{W}\times...\times\mathbb{W}$.
Substituting the control law (8) into dynamics (1), the state of the system
can be written as

$\displaystyle\mathbf{x}_{k}=\mathbf{C}_{xx}x_{k}+\mathbf{C}_{xu}\hat{\mathbf{u}}_{k}+(\mathbf{C}_{xw}+\mathbf{C}_{xu}\mathbf{M}_{\text{off}})\mathbf{B}_{w}\mathbf{w}_{k},$
(13)

where

$\displaystyle\mathbf{C}_{xx}:=\begin{bmatrix}I,A,\ldots,A^{N-1}\end{bmatrix}^{T},\quad\mathbf{B}_{w}=I_{N-1}\otimes
B_{w},$ $\displaystyle\mathbf{C}_{xu}{:=}\begin{bmatrix}0&...&...&0\\\
B&0&...&0\\\ AB&B&...&0\\\ \vdots&\vdots&\ddots&\vdots\\\
A^{N{-}2}B&...&AB&B\end{bmatrix},\mathbf{C}_{xw}{:=}\begin{bmatrix}0&...&...&0\\\
I&0&...&0\\\ A&I&...&0\\\ \vdots&\vdots&\ddots&\vdots\\\
A^{N{-}2}&...&...&I\end{bmatrix}.$

By denoting $\mathbf{F}:=I_{N}\otimes F$, $\mathbf{G}:=I_{N}\otimes G$,
$\mathbf{b}:=1_{N}\otimes b$, $\mathbf{D}:=I_{N-1}\otimes D$, and
$\mathbf{d}:=\mathbf{1}_{N-1}\otimes d$, the constraints on the system
trajectory in the prediction horizon of MPC are

$\displaystyle\mathbf{F}\mathbf{x}_{k}+\mathbf{G}\mathbf{u}_{k}\leq\mathbf{b}.$
(14)

Using (13), (14) can be written as

$\displaystyle(\mathbf{F}\mathbf{C}_{xu}+\mathbf{G})\hat{\mathbf{u}}_{k}+\mathbf{F}\mathbf{C}_{xx}x_{k}\leq\mathbf{b}-\mathbf{t},$
(15a) $\displaystyle\mathbf{t}$
$\displaystyle=\max_{\mathbf{w}_{k}\in\mathcal{W}}(\mathbf{F}\mathbf{C}_{xw}+\mathbf{F}\mathbf{C}_{xu}\mathbf{M}_{\text{off}}+\mathbf{G}\mathbf{M}_{\text{off}})\mathbf{B}_{w}\mathbf{w}_{k}.$
(15b)

Note that the maximization in (15b) is performed row-wise. For
$j\in\mathbb{Z}_{[1,Nn_{c}]}$, $[t]_{j}$ represents the tightening to be
performed on the $j^{th}$ constraint. Using strong duality, the $j^{th}$ row
in (15b) can be equivalently written as

$\displaystyle\min_{z_{(j)},[t]_{j}}\quad$ $\displaystyle[t]_{j}$ (16a)
$\displaystyle\text{s.t.}\quad[t]_{j}$
$\displaystyle=z_{(j)}^{T}\mathbf{d},\quad z_{(j)}\geq 0,\quad[t]_{j}\geq 0,$
(16b) $\displaystyle z_{(j)}^{T}\mathbf{D}$
$\displaystyle=[(\mathbf{F}\mathbf{C}_{xw}+\mathbf{F}\mathbf{C}_{xu}\mathbf{M}_{\text{off}}+\mathbf{G}\mathbf{M}_{\text{off}})\mathbf{B}_{w}]_{j}.$
(16c)

Thus, for a fixed $\mathbf{M}_{\text{off}}$, (15b) can be formulated as
$Nn_{c}$ linear programs in the variables $z_{(j)}$ and $[t]_{j}$.  The key
observation leveraged here is that, if $\mathbf{M}_{\text{off}}$ is an
optimization variable, it can be chosen such that the tightenings in
$\mathbf{t}$ are minimized.

###  III-B Terminal sets

A terminal set is to be chosen such that a linear feedback policy of the form
$u=K_{f}x$ is always feasible inside the terminal set. In order to ensure
recursive feasibility of the online optimization problem, the following
assumption needs to be satisfied by the terminal set and the terminal
controller.

###### Assumption 2

There exists a terminal set $\mathcal{X}_{T}$, a disturbance feedback gain
$M_{N}^{\text{off}}\in\mathbb{R}^{n_{u}\times n_{x}}$ and a terminal feedback
gain $K_{f}\in\mathbb{R}^{n_{u}\times n_{x}}$ such that for all
$x\in\mathcal{X}_{T}$ and $w\in\mathbb{W}$,

$\displaystyle\bigr{(}x{+}\textstyle\sum_{j=0}^{N-1}A^{j}BM_{N{-}1{-}j}^{\text{off}}B_{w}w,\>K_{f}x{+}M_{N}^{\text{off}}B_{w}w\bigr{)}\in\mathbb{C}_{N{-}1},$
(17a)
$\displaystyle(A+BK_{f})x{+}\textstyle\sum_{j=0}^{N}A^{j}BM_{N{-}j}^{\text{off}}B_{w}w\in\mathcal{X}_{T}.$
(17b)

###### Remark 1

Note that conditions similar to (17) are imposed on the terminal set to ensure
recursive feasibility of TMPC in [3, 12].

It can be seen that Assumption 2 results in a coupling of the design of the
terminal set $\mathcal{X}_{T}$, the terminal feedback gain $K_{f}$ and the
disturbance affine feedback gains $\mathbf{M}_{\text{off}}$ and
$M_{N}^{\text{off}}$. Even when the feedback gains are known, the design of
terminal sets is a difficult problem, since they are computed by iterative
set-intersections performed on polytopic sets [2]. In this work, the design
process is simplified by first choosing the terminal components as is done in
standard tube MPC methods [3]. The gain $K_{f}$ is chosen such that
$(A+BK_{f})$ is Schur stable, and the terminal set is constructed as a
polytope of the form $\mathcal{X}_{T}:=\\{x|Yx\leq z\\}$. Then, (17) will be
reformulated as convex constraints on the disturbance affine feedback gains
$\mathbf{M}_{\text{off}}$ and $M_{N}^{\text{off}}$ in the following
proposition.

###### Proposition 1

Given the terminal ingredients $\mathcal{X}_{T}$ and $K_{f}$, define
$c_{F}=\max_{x\in\mathcal{X}_{T}}(F+GK_{f})x$ and
$c_{Y}=\max_{x\in\mathcal{X}_{T}}Y(A+BK_{f})x$. If there exist
$\Lambda_{1}\in\mathbb{R}^{n_{c}\times n_{d}}$ and
$\Lambda_{2}\in\mathbb{R}^{n_{t}\times n_{d}}$, such that

$\displaystyle\begin{split}\Lambda_{1}\geq 0,\quad\Lambda_{2}\geq
0,\quad\Lambda_{1}d+c_{F}\leq b&-t_{N-1},\\\
F\textstyle\sum_{j=0}^{N-1}A^{j}BM_{N{-}1{-}j}^{\text{off}}B_{w}+GM_{N}^{\text{off}}B_{w}&=\Lambda_{1}D,\\\
Y\textstyle\sum_{j=0}^{N}A^{j}BM_{N{-}j}^{\text{off}}B_{w}=\Lambda_{2}D,\quad\Lambda_{2}d&+c_{Y}\leq
z,\end{split}$ (18)

then Assumption 2 is satisfied.

###### Proof:

For a given $\mathcal{X}_{T}$ and $K_{f}$, (17a) is satisfied if

$\displaystyle\max_{w\in\mathbb{W}}\>F\textstyle\sum_{j=0}^{N-1}A^{j}$
$\displaystyle BM_{N{-}1{-}j}^{\text{off}}B_{w}w+GM_{N}^{\text{off}}B_{w}w+$
$\displaystyle\max_{x\in\mathcal{X}_{T}}Fx+GK_{f}x\leq b-t_{N-1}.$ (19)

Similarly, (17b) is satisfied if

$\displaystyle\max_{w\in\mathbb{W}}\>\sum_{j=0}^{N}A^{j}BM_{N{-}j}^{\text{off}}B_{w}w+\max_{x\in\mathcal{X}_{T}}Y(A+BK_{f})x\leq
z.$ (20)

In (III-B) and (20), the maximizations over $\mathcal{X}_{T}$ can be performed
to compute $c_{F},c_{Y}$ before choosing $\mathbf{M}_{\text{off}}$ and
$M_{N}^{\text{off}}$, as the terminal ingredients are known. Then, applying
strong duality to the maximization over $\mathbb{W}$, (III-B) and (20) are
satisfied iff there exist $\Lambda_{1}$ and $\Lambda_{2}$ such that (18)
holds. ∎

##  IV Robust MPC controller

This section presents the algorithm defining the robust MPC controller
proposed in this work. First, the offline and online optimization problems to
be solved are described. Then, the system theoretic properties of the closed
loop system are presented.

###  IV-A Offline optimization

Building on the formulation illustrated in Section III of convex constraints
on $\mathbf{M}_{\text{off}}$ and $M_{N}^{\text{off}}$, these design matrices
can be computed as the solution of an optimization problem. In order to reduce
the conservatism of the robust MPC controller, it is desired that the feasible
region of the online optimization problem is large. This feasible region is
represented by a polytope in a high dimensional space, whose volume is
difficult to compute. One way to approximate this objective is to minimize the
amount of constraint tightening to be performed. To this aim, the following
optimization problem is solved

$\displaystyle\min_{\begin{subarray}{c}Z,\mathbf{t},\Gamma,\mathbf{M}_{\text{off}},\\\
M^{\text{off}}_{N},\Lambda_{1},\Lambda_{2}\end{subarray}}\quad\|\mathbf{t}\|_{2}$
(21a) s.t. $\displaystyle
Z^{T}\mathbf{D}=(\mathbf{F}\mathbf{C}_{xw}+\mathbf{F}\mathbf{C}_{xu}\mathbf{M}_{\text{off}}+\mathbf{G}\mathbf{M}_{\text{off}})\mathbf{B}_{w},$
(21b) $\displaystyle Z^{T}\mathbf{d}=\mathbf{t},\quad Z\geq
0,\quad\mathbf{t}\geq 0,$ (21c) $\displaystyle\mathbf{b}-\mathbf{t}\geq
0,\quad\mathbf{M}_{\text{off}}\in\mathcal{M},\quad\eqref{eq:TermSetDesign_Cond},$
(21d)

where $Z=[z_{(1)},\ldots,z_{(Nn_{c})}]$. In problem (21), (21b)-(21c) are
obtained by stacking the individual constraints from (16). Note that
$\mathbf{M}_{\text{off}}$ is an optimization variable in (21). The  first
constraint in (21d) is introduced to preserve the feasibility of the online
MPC optimization problem. Using an epigraph reformulation, (21) can be
transformed into a convex second-order cone program which can be efficiently
solved [13].

###### Remark 2

Problem (21) provides a formal way to design constraint tightening by
optimizing offline over the disturbance feedback gains. Following a similar
approach to [12], the proposed methodology can be easily extended to fuse
multiple feedback gains online. If this strategy is pursued, additional
feedback gains can be designed, for example, by using a weighted norm in the
objective function of (21).

###### Remark 3

Problem (21) minimizes $\|\mathbf{t}\|_{2}$ as a surrogate for the
maximization of the feasible region. Note that the TMPC solution [3] is
feasible for (21), which can be verified by choosing $\mathbf{M}_{\text{off}}$
to be of the structure in (7) with $K=K_{f}$ and
$M_{N}^{\text{off}}=K_{f}(A+BK_{f})^{N-1}$. In simulation studies, it was
found that the proposed method could sometimes lead to smaller ROA compared to
TMPC  using $K_{f}$ for feedback. This might be justified considering that
minimizing $\|\mathbf{t}\|_{2}$ is a heuristic to maximize the size of the
feasible region. A possible remedy for this problem, which can be detected
offline, is to explicitly enforce that the tightenings in $\mathbf{t}$ are
smaller than those resulting from TMPC.

###  IV-B Receding horizon control

Once the constraint tightenings are computed from (21), the online
optimization problem can be formulated as

$\displaystyle\min_{\hat{\mathbf{u}}_{k}}\quad\textstyle\sum_{i=0}^{N-1}(\hat{x}_{k,i}^{\top}Q\hat{x}_{k,i}$
$\displaystyle{+}\hat{u}_{k,i}^{\top}R\hat{u}_{k,i}){+}\hat{x}_{k,N}^{\top}P\hat{x}_{k,N}$
(22a) $\displaystyle\text{s.t.}\quad A\hat{x}_{k,i}+B\hat{u}_{k,i}$
$\displaystyle=\hat{x}_{k,i+1},\quad\hat{x}_{k,0}=x_{k},$ (22b) $\displaystyle
F\hat{x}_{k,i}+G\hat{u}_{k,i}$ $\displaystyle\leq b-t_{i},\quad
i\in\mathbb{Z}_{[0,N-1]},$ (22c) $\displaystyle Y\hat{x}_{k,N}$
$\displaystyle\leq z.$ (22d)

In (22), the terminal cost is defined using a positive definite matrix $P$
chosen such that

$\displaystyle(A+BK_{f})^{\top}P(A+BK_{f})+Q+K_{f}^{\top}RK_{f}\preccurlyeq
P.$ (23)

It is worth observing that the computational complexity of (22) is the same as
that of nominal MPC, and thus grows only linearly with the length of the
prediction horizon. The robust MPC design scheme is summarized in Algorithm 1.

Algorithm 1 Optimized constraint tightening for robust MPC

1:Offline:

2:Choose $K_{f}$ such that $(A+BK_{f})$ is Schur stable

3:Design $\mathcal{X}_{T}$ following [3], compute $c_{F}$ and $c_{Y}$

4:Solve (21) to compute $\mathbf{t}$

1:Online: At each time-step $k\geq 0$:

2:Obtain the measurement $x_{k}=x_{k,0}=\hat{x}_{k,0}$

3:Solve (22)

4:Apply $\pi(x_{k})=\hat{u}^{*}_{k,0}\in\mathbb{R}^{n_{u}}$

###  IV-C Closed-loop properties

In this section, it will be shown that problem (22) is recursively feasible
and that the closed loop system is input-to-state stable (ISS). The set of
admissible policies and the feasible set of (22) are first defined.

######  Definition 1 (Admissible control inputs)

Given a state $x_{k}$, $\Pi_{W}(x_{k})$ is the set of all admissible sequences
$\hat{\mathbf{u}}_{k}$ in (22). That is,
$\Pi_{W}(x_{k}):=\left\\{\hat{\mathbf{u}}_{k}\>|\>\eqref{OptProb_PM2},\eqref{OptProb_PM3},\eqref{OptProb_PM4}\right\\}$.

######  Definition 2 (Feasible set)

The feasible set of the optimization problem (22) is defined as the set of all
initial states for which there exists at least one admissible control policy,
that is, $X_{W}:=\\{x_{0}\rvert\quad\Pi_{W}(x_{0})\neq\emptyset\\}$.

######  Proposition 2 (Recursive Feasibility)

Let Assumptions 1 and 2 be satisfied and the offline optimization problem (21)
have a feasible solution. Then, the receding horizon policy generated by
Algorithm 1 and applied to system (1) results in a recursively feasible online
optimization problem (22).

###### Proof:

Assume $x_{k}\in X_{W}$, and let the optimal solution to (22) at time-step $k$
be given by the nominal state and control input sequences
$\\{\hat{x}_{k,i}^{*}\\}_{i=0}^{N},\\{\hat{u}_{k,i}^{*}\\}_{i=0}^{N-1}$. The
state of the system at time-step $k+1$ is given by
$x_{k+1}=Ax_{k}+B\hat{u}_{k,0}^{*}+B_{w}w_{k}=\hat{x}_{k,1}^{*}+B_{w}w_{k}$.
The online optimization problem (22) is recursively feasible if there exists a
feasible state and control input sequence at time-step $k+1$.

Consider the candidate state and input sequences given as

$\displaystyle\hat{u}_{k+1,i}=\hat{u}_{k,i+1}^{*}+M^{\text{off}}_{i+1}B_{w}w_{k},\quad
i\in\mathbb{Z}_{[0,N-2]},$
$\displaystyle\hat{u}_{k+1,N-1}=K_{f}\hat{x}_{k,N}^{*}+M_{N}^{\text{off}}B_{w}w_{k},$
(24)
$\displaystyle\hat{x}_{k+1,i}=\hat{x}_{k,i+1}^{*}+\textstyle\sum_{j=0}^{i}A^{j}BM^{\text{off}}_{i-j}B_{w}w_{k},\quad
i\in\mathbb{Z}_{[0,N-1]},$
$\displaystyle\hat{x}_{k+1,N}=(A+BK_{f})\hat{x}_{k,N}^{*}+\textstyle\sum_{j=0}^{N}A^{j}BM^{\text{off}}_{N-j}B_{w}w_{k}.$

It can be easily verified that the candidate solution (24) satisfies the
dynamics constraint (22b) in the online optimization problem. Moreover, for
$i\in\mathbb{Z}_{[0,N-2]}$, the terms in the state and input constraints can
be written as

$\displaystyle F\hat{x}_{k+1,i}+G\hat{u}_{k+1,i}$
$\displaystyle=F\hat{x}_{k,i+1}^{*}+G\hat{u}_{k,i+1}^{*}+$ (25) $\displaystyle
F\textstyle\sum_{j=0}^{i}$ $\displaystyle
A^{j}BM^{\text{off}}_{i-j}B_{w}w_{k}+GM^{\text{off}}_{i+1}B_{w}w_{k}.$

The first two terms on the right hand side in (25) can be upper bounded by
$b-t_{i+1}$, because the trajectory computed at time $k$ satisfies (22b).
Moreover, the following relationship holds between $t_{i}$ and $t_{i+1}$ for
$i\in\mathbb{Z}_{[0,N-2]}$,

$\displaystyle t_{i+1}$
$\displaystyle=\max_{\\{w_{l}\in\mathbb{W}\\}_{l=0}^{i}}F\textstyle\sum_{l=0}^{i}\sum_{j=0}^{i{-}l}A^{j}BM_{i{-}j}^{\text{off}}B_{w}w_{l}$
$\displaystyle\qquad+G\textstyle\sum_{l=0}^{i}M_{l+1}^{\text{off}}B_{w}w_{i-l}$
(26)
$\displaystyle=t_{i}+\max_{w_{0}\in\mathbb{W}}F\textstyle\sum_{j=0}^{i}A^{j}BM_{i{-}j}^{\text{off}}B_{w}w_{0}+GM_{i}^{\text{off}}B_{w}w_{0}.$

Thus, using (25) and (IV-C), (22c) holds for $i\in\mathbb{Z}_{[0,N-2]}$ at
time-step $k+1$. Similarly, the feasibility of (22c) for $i{=}N{-}1$ and the
terminal constraints (22d) is a direct consequence of the proposed design
satisfying (17a) and (17b), respectively. Thus, (22) is recursively feasible.
∎

######  Proposition 3 (Input-to-state stability)

Let Assumptions 1 and 2 be satisfied and the offline optimization problem (21)
have a feasible solution. Then, the closed loop formed by system (1) and the
receding horizon policy $\pi(x_{k})$ is ISS. That is, there exists a
$\mathcal{KL}$-function $\beta(\cdot)$ and a $\mathcal{K}$-function
$\gamma(\cdot)$ as defined in [14], such that for
$\bar{w}=\sup_{\tau\in\mathbb{Z}_{[0,k-1]}}\|w_{\tau}\|$,

$\displaystyle\|x_{k}\|\leq\beta(\|x_{0}\|,k)+\gamma(\bar{w}),\>\forall
k\in\mathbb{Z}_{[0,\infty)},x_{0}\in X_{W}.$ (27)

###### Proof:

The proof follows the approach presented in [8], where it is shown that the
optimal cost function $J^{*}_{N}(x)$ is a ISS Lyapunov function [14] for the
closed loop system. Let $f(x_{k},w_{k})=Ax_{k}+B\pi(x_{k})+B_{w}w_{k}$
describe dynamics of the closed loop system. As a consequence of 2, $X_{W}$ is
a RPI set of $f(\cdot)$.

First, it can be seen that $J^{*}_{N}(\cdot)$ is a Lyapunov function for the
undisturbed system. This is because, by using Proposition 17 from [8], it
holds that $J^{*}_{N}(\cdot)$ and $\pi(\cdot)$ are Lipschitz continuous on
$X_{W}$. It follows from Lemma 4.3 in [15] that there exist
$\mathcal{K}_{\infty}$ functions $a_{2}(\cdot)$ and $a_{3}(\cdot)$ such that
$a_{2}(\|x\|)\leq J_{N}^{*}(x)\leq a_{3}(\|x\|)$. Finally, using the candidate
solution in (24), the optimal value function satisfies
$J^{*}_{N}(f(x,0))-J^{*}_{N}(x)\leq-a_{1}(\|x\|)$ for a $\mathcal{K}_{\infty}$
function $a_{1}(\cdot)$.

Now let $L_{J}$ and $L_{f}$ be the Lipschitz constants of $J^{*}_{N}(\cdot)$
and $f(x,\cdot)$, respectively. Then,

$\displaystyle J^{*}_{N}(f(x,w))-J_{N}^{*}(x)$
$\displaystyle=J^{*}_{N}(f(x,0))-J^{*}_{N}(x)+J^{*}_{N}(f(x,w))-J^{*}_{N}(f(x,0))$
$\displaystyle\leq-a_{1}(\|x\|)+L_{J}L_{f}\|w\|.$ (28)

Thus, $J^{*}_{N}(x)$ is a ISS Lyapunov function for the closed loop system,
and using Lemma 3.5 from [14], the closed loop system is ISS with region of
attraction $X_{W}$. ∎

##  V NUMERICAL EXAMPLES

In this section, the proposed optimized constraint tightening (OCT) algorithm
is compared to Tube MPC (TMPC) [3] and the fully parameterized disturbance-
affine MPC (FPD) [8] methods. The algorithms are implemented in MATLAB using
MOSEK [16], YALMIP [17] and MPT3 [18]. The reported statistics correspond to
the time that the solver requires to solve the optimization problems on a AMD
EPYC 7H12 processor with 6GB RAM. The code for simulating these examples is
available in the online repository [19].

Two simple mechanical spring-mass systems are used as working examples. System
1 consists of a mass connected to a fixed end by a spring and a damper. System
2 consists of three masses connected along a line using springs and dampers,
with the first mass connected to a fixed end similar to System 1. The dynamics
of System 1 can be described by

$\displaystyle\frac{d}{dt}x=\begin{bmatrix}0&1\\\
-k&-b\end{bmatrix}x+\begin{bmatrix}0\\\ 20\end{bmatrix}u+\begin{bmatrix}1&0\\\
0&1\end{bmatrix}w$ (29)

where the spring constant $k=1\mathrm{Nm^{-1}}$, the damping coefficient
$b=0.1\mathrm{Nsm^{-1}}$. The dynamics are discretized using forward Euler
method with a sampling time of $T=0.1\mathrm{s}$. The state, the input and the
disturbance of System 1 are subject to linear inequality constraints described
by

$\displaystyle\|x\|_{\infty}\leq 25,\|u\|_{\infty}$ $\displaystyle\leq
1,-2\leq[w]_{1}\leq 2,-5\leq[w]_{2}\leq 5.$

The parameters and constraints on System 2 are similarly defined. Moreover,
the cost matrices are given as $Q=I_{n_{x}}$ and $R=I_{n_{u}}$. The terminal
feedback gain $K_{f}$ is computed as the solution to the infinite horizon
linear quadratic regulator problem and $P$ is chosen such that it satisfies
(23) with an equality. The terminal set for the TMPC and OCT controllers is
computed as suggested in [3], and the terminal set of the FPD controller is
chosen as the maximal robust positively invariant set under the terminal
controller [2].

Figure 1: Comparison of average online computational times and ROA for OCT,
TMPC and FPD controllers. Figure 2: Colorbar shows the ratio of averaged
closed loop costs of TMPC and OCT as a function of the initial state for
System 1 with $N=10$. The red dots indicate initial states where TMPC is
infeasible but OCT is feasible.

To compare the performance of the control algorithms, the ROA and the
computational times of each controller for Systems 1 and 2 are plotted in
Figure 1. For System 1, the ROA is estimated by dividing the state space into
a grid of 2500 uniformly distributed points. The number of points for which
the online optimization problem is feasible for TMPC and OCT controllers is
shown as a percentage of the number of points for which the FPD controller was
feasible. For System 2, this analysis was performed using a grid consisting of
125,000 points on the $[x]_{2}-[x]_{4}-[x]_{6}$ subspace, by setting all the
other states to zero. It can be seen that the proposed method results in a
larger ROA compared to the TMPC approach. It must be noted that for System 1
with $N=15$, OCT using (21) resulted in a smaller ROA compared to TMPC.
However, imposing the additional constraint proposed in Remark 3 allowed a
strictly larger ROA for OCT compared to TMPC as shown in Figure 1.

Figure 1 also shows the computation times required to solve the online
optimization problem for each controller, averaged over all feasible
initializations used in the ROA analysis. It can be seen that the proposed
method is an order of magnitude faster than the FPD approach, and requires a
similar run time to TMPC. This is because the number of optimization variables
and constraints for OCT and TMPC are the same, whereas FPD has a quadratic
growth in the size of the optimization problem with increase in the prediction
horizon. Thus, the proposed method is able to strictly improve on the ROA of
the TMPC approach at no increase in computational cost.

The closed-loop performances of TMPC and OCT methods are compared in Figure 2.
The closed-loop costs achieved by TMPC and OCT are averaged over 50
realizations of $w_{k}$ generated randomly such that Assumption 1 is
satisfied. It can be seen that the costs are within 0.5% of each other, and
that OCT results in a larger feasible region as indicated by the red dots.

##  VI Conclusions and Outlook

A novel algorithm is presented for the offline optimization of constraint
tightening to be used in robust MPC controllers. The constraint tightenings
are formulated as convex functions of a disturbance affine feedback gain. A
convex program is solved to minimize the constraint tightening in order to
increase the region of attraction. The proposed method guarantees recursive
feasibility and input-to-state stability, and numerical examples demonstrate
the computational efficiency and improved region of attraction compared to
existing methods from the literature. One promising direction to improve the
proposed approach is to design multiple feedback gains which can be fused
online.

## References

  * [1] F. Borrelli, A. Bemporad, and M. Morari, _Predictive Control for Linear and Hybrid Systems_. Cambridge University Press, 2017.
  * [2] B. Kouvaritakis and M. Cannon, “Model predictive control: Classical, robust and stochastic,” _Advanced Textbooks in Control and Signal Processing_ , 01 2016.
  * [3] L. Chisci, J. Rossiter, and G. Zappa, “Systems with persistent disturbances: predictive control with restricted constraints,” _Automatica_ , vol. 37, no. 7, pp. 1019–1028, 2001.
  * [4] D. Mayne, M. Seron, and S. Raković, “Robust model predictive control of constrained linear systems with bounded disturbances,” _Automatica_ , vol. 41, no. 2, pp. 219–224, 2005.
  * [5] M. Zanon and S. Gros, “On the similarity between two popular tube MPC formulations,” in _European Control Conf._ , 2021, pp. 651–656.
  * [6] D. Munoz-Carpintero, B. Kouvaritakis, and M. Cannon, “Striped parameterized tube model predictive control,” _IFAC Proceedings Volumes_ , vol. 47, no. 3, pp. 11 998–12 003, 2014.
  * [7] S. V. Raković, B. Kouvaritakis, R. Findeisen, and M. Cannon, “Homothetic tube model predictive control,” _Automatica_ , vol. 48, 2012.
  * [8] P. J. Goulart, E. C. Kerrigan, and J. M. Maciejowski, “Optimization over state feedback policies for robust control with constraints,” _Automatica_ , vol. 42, no. 4, pp. 523–533, 2006.
  * [9] M. Zanon and S. Gros, “Safe reinforcement learning using robust MPC,” _IEEE Trans. on Automatic Control_ , vol. 66, no. 8, pp. 3638–3652, 2020\.
  * [10] M. Mammarella, E. Capello, H. Park, G. Guglieri, and M. Romano, “Tube-based robust model predictive control for spacecraft proximity operations in the presence of persistent disturbance,” _Aerospace Science and Technology_ , vol. 77, pp. 585–594, 2018.
  * [11] J. Sieber, A. Zanelli, S. Bennani, and M. N. Zeilinger, “System level disturbance reachable sets and their application to tube-based MPC,” _European Journal of Control_ , 2022.
  * [12] M. Kögel and R. Findeisen, “Fusing multiple time varying tubes for robust MPC,” _IFAC-PapersOnLine_ , vol. 53, no. 2, pp. 7055–7062, 2020, 21st IFAC World Congress.
  * [13] S. Boyd and L. Vandenberghe, _Convex optimization_. Cambridge University Press, 2004.
  * [14] Z.-P. Jiang and Y. Wang, “Input-to-state stability for discrete-time nonlinear systems,” _Automatica_ , vol. 37, no. 6, pp. 857–869, 2001.
  * [15] H. K. Khalil, _Nonlinear Systems, Third Edition_. Prentice Hall, Upper Saddle River, New Jersey 07458, 2002.
  * [16] MOSEK ApS, _The MOSEK optimization toolbox for MATLAB manual. Version 9.0._ , 2019.
  * [17] J. Löfberg, “YALMIP : A toolbox for modeling and optimization in MATLAB,” in _In Proceedings of the CACSD Conference_ , Taipei, 2004.
  * [18] M. Herceg, M. Kvasnica, C. Jones, and M. Morari, “Multi-Parametric Toolbox 3.0,” in _European Control Conf._ , Zürich, 2013, pp. 502–510.
  * [19] “Supplemental material to the paper ”Computationally efficient robust MPC using optimized constraint tightening”,” DOI: 10.3929/ethz-b-000537515, 2022, ETH Research Collection.


# Applications of the Tarski-Kantorovitch Fixed-Point Principle to the study
of Infinite Iterated Function Systems

Bogdan-Alexandru Luchian  Faculty of Mathematics and Computer Science
University of Bucharest
Academiei Street, 14
010014 Bucharest
Romania<EMAIL_ADDRESS>
###### Abstract.

The aim of this paper is to establish some results regarding Infinite Iterated
Function Systems with the help of the Tarski-Kantorovitch fixed-point
principles for maps on partially ordered sets. To this end we introduce two
new classes of Infinite Iterated Function Systems which are well suited for
applying the aforementioned principle. We also study some properties of the
canonical projection from the shift space of an Infinite Iterated Function
System belonging to one of the two introduced classes to its attractor.

###### Key words and phrases:

Attractor of an Infinite Iterated Function System, Canonical Projection,
Continuity with respect to a partial order and topology, Contraction, Infinite
Iterated Function Systems, Iterated Function Systems, Metric Spaces, Shift
Space, Tarski-Kantorovitch Fixed-Point Principle

###### 1991 Mathematics Subject Classification:

Primary 06A06, 26A18, 37C25, 47H10, 54H25; Secondary 54C05, 54D55, 54E35

##  1\. Introduction

Let $(X,d)$ be a complete metric space and $\mathcal{S}=(X,(f_{i})_{i\in I})$
an Infinite Iterated Function System (IIFS for short) and define the operator
$F_{\mathcal{S}}$ on the family of nonempty closed and bounded sets of $X$ as
follows: $F_{\mathcal{S}}(B)\mathrel{\mathop{\mathchar 58\relax}}={}\mkern
3.0mu\overline{\mkern-3.0mu\bigcup_{i\in I}f_{i}(B)}$ for all $B\subseteq X$
neonempty, closed and bounded. The fundamental result regarding IIFS’s states
that if $sup_{i\in I}lip(f_{i})<1,$ where $lip(f_{i})$ is the Lipschitz
constant associated to $f_{i},$ then there exists a unique nonempty, closed
and bounded subset of $X,$ $A(\mathcal{S}),$ such that
$F_{\mathcal{S}}(A(\mathcal{S}))=A(\mathcal{S}),$ which is called the
attractor of the IIFS.
In this paper we follow in the footsteps of the article [8] and study
possibilities of applying the Tarski-Kantorovitch fixed-point principle in the
theory of IIFS’s, which naturally conducts us to consider two new classes of
IIFS’s in certain topological spaces. The idea of applying the Tarki-
Kantorovitch principle to deduce results about the fixed points of some
classes of maps is not necessarily new - for other applications one may
consult [1], [3], [7].
Our paper is organized in the following way. In the second section we will
recall some definitions and results regarding IIFS’s and introduce two new
classes of IIFS’s.
In the third section of the article we shall study possibilities of applying
the Tarski-Kantorovitch fixed point principle for the partially ordered set
(poset for short) $(\raisebox{1.79993pt}{\Large$\wp$ }(X),\supseteq),$ where
$X$ is an arbitrary set. In this case we give sufficient conditions for the
existence of a (greatest) fixed point of the Hutchinson-Barnsley operator
associated to an IIFS. These conditions turn out to be also necessary if one
is interested in applying the Tarski-Kantorovitch principle.
In the fourth section we turn our attention to the poset
$(\mathcal{F}(X),\supseteq),$ where $\mathcal{F}(X)$ denotes the family of all
nonempty closed subsets of a Hausdorff topological space $X.$ As seen in [8],
the countable chain condition in this poset forces $X$ to be countably
compact. In the case that $X$ is also a sequential space, the main result of
this section provides sufficient conditions for the existence of a greatest
fixed point of the Hutchinson-Barnsley operator associated to an IIFS. As in
the previous section, the specified conditions are also necessary for applying
the Tarski-Kantorovitch principle.
In the fifth section we are employing similar techniques as in the previous
sections in order to apply the Tarski-Kantorovitch principle to the poset
$(\mathcal{K}(X),\supseteq),$ where $\mathcal{K}(X)$ denotes the family of
nonempty compact subsets of a topological space $X.$ In particular, we
discover that in the same way as in [8], in order to apply the Tarski-
Kantorovitch principle in this case, we can actually assume that $X$ is
compact. We also show that if $(X,d)$ is a bounded Heine-Borel metric space,
then the Hutchinson-Barnsley operator associated to an IIFS of contractions
admits a nonempty compact fixed point (though we cannot posit that this fixed
point is unique from the proof provided).
In the final section of the article we turn our attention to the shift space
associated to an IIFS and the canonical projection from the shift space to the
attractor of said IIFS and investigate what special properties this projection
has in the cases of the two new classes of IIFS’s introduced in this article.
We also provide the reader with a sufficient condition for the canonical
projection to be a homeomorphism and state a few immediate corollaries.
As a final remark in this introductory part of the article, we want to stress
the fact that the generality of the setting in which we work, i.e. that of
Infinite Iterated Function Systems, has forced us to impose (fairly natural)
conditions on the systems we work with in order to apply the Tarski-
Kantorovitch Fixed-Point Principle and the two examples we provide tell us the
introduction of these classes is in fact necessary.
For more work on Infinite Iterated Function Systems, you can also check [9],
[10], [11], [12], [13].

##  2\. Preliminaries

######  Definition 2.1.

Let $(X,d_{X}),(Y,d_{Y})$ be two metric spaces and $(f_{i})_{i\in I}\subseteq
Y^{X}$ a family of maps. We say that this family is bounded if the set
$\bigcup_{i\in I}f_{i}(A)$ is bounded for any $A\subseteq X$ bounded.

######  Definition 2.2.

Let $(X,d_{X}),(Y,d_{Y})$ be metric spaces and $f\mathrel{\mathop{\mathchar
58\relax}}X\xrightarrow{}Y$ a function. The quantity
$lip(f)\mathrel{\mathop{\mathchar 58\relax}}=\sup_{x,y\in X,x\neq
y}\frac{d_{Y}(f(x),f(y))}{d_{X}(x,y)}\in[0,\infty]$ is called the Lipschitz
constant associated to $f.$ We say that $f$ is Lipschitz if $lip(f)<\infty$
and that $f$ is a contraction if $lip(f)<1.$

As an immediate consequence of the previous definition, we have the following
lemma.

######  Lemma 2.1.

Let $(X,d_{X}),(Y,d_{Y})$ be two metric spaces and
$f\mathrel{\mathop{\mathchar 58\relax}}X\xrightarrow{}Y$ a map. Then if we
denote the diameter of a subset $A\subseteq X$ with $\delta(A),$ we have that
$\delta(f(A))\leq lip(f)\delta(A)$ for any $A\subseteq X.$ In particular, if
$x,y\in X,$ then $d_{Y}(f(x),f(y))\leq lip(f)d_{X}(x,y).$

######  Remark 2.1.

For an arbitrary topological space $X,$ we shall denote by
$\raisebox{1.79993pt}{\Large$\wp$ }(X)$ the family of subsets of $X,$
$\raisebox{1.79993pt}{\Large$\wp$ }^{\ast}(X)\mathrel{\mathop{\mathchar
58\relax}}=\raisebox{1.79993pt}{\Large$\wp$ }(X)\setminus\\{\emptyset\\},$
$\mathcal{K}(X)$ the family of nonempty compact subsets of $X$ and by
$\mathcal{F}(X)$ we mean the family of nonempty closed sets of $X.$ If $X$ is
also metrizable, we shall denote by $\mathcal{B}(X)$ the family of nonempty
closed and bounded subsets of $X.$ In the latter case, note that we have the
inclusions
$\mathcal{K}(X)\subseteq\mathcal{B}(X)\subseteq\raisebox{1.79993pt}{\Large$\wp$
}^{\ast}(X).$ However, if $X$ is not necessarily metrizable, but it is
Hausdorff, we have that
$\mathcal{K}(X)\subseteq\mathcal{F}(X)\subseteq\raisebox{1.79993pt}{\Large$\wp$
}^{\ast}(X).$

######  Definition 2.3.

Let $X,Y$ be two arbitrary sets, $f\mathrel{\mathop{\mathchar
58\relax}}X\xrightarrow{}Y$ a function and $y\in Y.$ We shall call the set
$f^{-1}(y)$ the fibre of $f$ over $y.$

######  Definition 2.4.

We say that a topological space $X$ is sequential if every sequentially closed
subset $A\subseteq X$ is closed.

We recall the following characterisation of continuity on countably compact
sequential spaces from [8].

######  Theorem 2.1.

Let $X,Y$ be countably compact and sequential spaces and
$f\mathrel{\mathop{\mathchar 58\relax}}X\xrightarrow{}Y$ a map. The following
conditions are equivalent:

  1. a)

$f$ is continuous;

  2. b)

if $A\in\mathcal{F}(X),$ then $f(A)\in\mathcal{F}(Y)$ and all fibres of $f$
are closed;

  3. c)

if $A\in\mathcal{F}(X),$ then $f(A)\in\mathcal{F}(Y)$ and given a decreasing
sequence $(A_{n})_{n\in\mathbb{N}}\subseteq\mathcal{F}(X),$ then
$f(\bigcap_{n\in\mathbb{N}}A_{n})=\bigcap_{n\in\mathbb{N}}f(A_{n});$

  4. d)

if $A\in\mathcal{K}(X),$ then $f(A)\in\mathcal{K}(Y)$ and given a decreasing
sequence $(A_{n})_{n\in\mathbb{N}}\subseteq\mathcal{K}(X),$ then
$f(\bigcap_{n\in\mathbb{N}}A_{n})=\bigcap_{n\in\mathbb{N}}f(A_{n}).$

######  Definition 2.5.

Let $(X,d)$ be a metric space. The generalised Hausdorff-Pompeiu semimetric on
the family of subsets of $X$ induced by $d$ is defined as
$h\mathrel{\mathop{\mathchar 58\relax}}\raisebox{1.79993pt}{\Large$\wp$
}^{\ast}(X)\times\raisebox{1.79993pt}{\Large$\wp$
}^{\ast}(X)\xrightarrow{}[0,\infty],$ where

$h(A,B)\mathrel{\mathop{\mathchar 58\relax}}=\max\\{d(A,B),d(B,A)\\}$ (1)

and

$d(A,B)\mathrel{\mathop{\mathchar 58\relax}}=\sup_{x\in A}\inf_{y\in B}d(x,y)$
(2)

for all $A,B\in\raisebox{1.79993pt}{\Large$\wp$ }^{\ast}(X).$

Several properties of the Hausdorff-Pompeiu semimetric can be found in [2],
[6], [14].

######  Definition 2.6.

Let $X$ be a topological space. We say that $\mathcal{S}=(X,(f_{i})_{i\in I})$
is an IIFS if $f_{i}$ is a selfmap of $X$ for all $i\in I.$

######  Definition 2.7.

An IIFS $\mathcal{S}=(X,(f_{i})_{i\in I})$ is said to be non-overlapping if
$f_{i}(B)\cap f_{j}(B)=\emptyset$ for any $B\subseteq X$ and $i,j\in I,$
$i\neq j.$

######  Remark 2.2.

Obviously, an IIFS as above is non-overlapping if and only if $f_{i}(X)\cap
f_{j}(X)=\emptyset$ for any $i,j\in I,i\neq j.$

######  Definition 2.8.

An IIFS $\mathcal{S}=(X,(f_{i})_{i\in I})$ is said to be locally finite if for
any $y\in X$ there exists a neighbourhood $V_{y}$ of $y$ such that $\\#\\{i\in
I\mathrel{\mathop{\mathchar 58\relax}}V_{y}\cap
f_{i}(X)\neq\emptyset\\}<\infty.$

######  Remark 2.3.

Let $\mathcal{S}=(X,(f_{i})_{i\in I})$ be a locally finite IIFS, $y\in X,$
$A\subseteq X$ and $V_{y}$ as in the definition above. Then the set $\\{i\in
I\mathrel{\mathop{\mathchar 58\relax}}V_{y}\cap f_{i}(A)\neq\emptyset\\}$ is
finite.

######  Definition 2.9.

An IIFS $\mathcal{S}=(X,(f_{i})_{i\in I})$ on a metric space $(X,d)$ is said
to be an IIFS of contractions if $(f_{i})_{i\in I}\subseteq X^{X}$ is a
bounded family of contractions such that $\sup_{i\in
I}lip(f_{i})=\mathrel{\mathop{\mathchar 58\relax}}c<1.$

######  Definition 2.10.

To an IIFS $\mathcal{S}=(X,(f_{i})_{i\in I})$ we can associate two Hutchinson-
Barnsley operators, namely
$F_{\mathcal{S}},G_{\mathcal{S}}\mathrel{\mathop{\mathchar
58\relax}}\raisebox{1.79993pt}{\Large$\wp$
}^{\ast}(X)\xrightarrow{}\raisebox{1.79993pt}{\Large$\wp$ }^{\ast}(X)$ given
by

$F_{\mathcal{S}}(A)\mathrel{\mathop{\mathchar 58\relax}}=\bigcup_{i\in
I}f_{i}(A)$ (3)

and

$G_{\mathcal{S}}(A)\mathrel{\mathop{\mathchar 58\relax}}={}\mkern
3.0mu\overline{\mkern-3.0mu\bigcup_{i\in I}f_{i}(A)}$ (4)

for all $\emptyset\neq A\subseteq X.$

######  Remark 2.4.

Note that if $\mathcal{S}$ is an IIFS of contractions, then $G_{\mathcal{S}}$
is a contraction with respect to the Hausdorff-Pompeiu metric on
$\mathcal{B}(X)$ and in fact $lip(G_{\mathcal{S}})\leq c=\sup_{i\in
I}lip(f_{i}).$

A straightforward application of the Banach-Caccioppoli-Picard contraction
principle yields the following result, which is the fundamental result in the
theory of IIFS’s (for the proof, you can check [14])

######  Theorem 2.2.

Let $(X,d)$ be a complete metric space and $\mathcal{S}=(X,(f_{i})_{i\in I})$
an IIFS of contractions. Then we may consider
$G_{\mathcal{S}}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(X)\xrightarrow{}\mathcal{B}(X)$ and in this case there
exists a unique set $A=A(\mathcal{S})\in\mathcal{B}(X)$ such that
$G_{\mathcal{S}}(A)=A.$ We call this set the attractor of $\mathcal{S}.$
Moreover, if $A_{0}\in\mathcal{B}(X)$ and $A_{n}\mathrel{\mathop{\mathchar
58\relax}}=G_{\mathcal{S}}(A_{n-1})$ for any $n\in\mathbb{N},$ then
$\lim_{n\to\infty}A_{n}=A.$ As for the speed of convergence, we have the
following estimate:

$h(A_{n},A)\leq\frac{c^{n}}{1-c}h(A_{0},A_{1})$ (5)

for all $n\geq 0.$

Regarding the shift space associated to an IIFS of contractions on a metric
space $(X,d),$ we have the following definitions and main theorem from [10].

######  Definition 2.11.

Let $I\neq\emptyset.$ We define:

  1. a)

the space $\Lambda=\Lambda(I)\mathrel{\mathop{\mathchar
58\relax}}=I^{\mathbb{N}}$ as the space of infinite words with letters from
the alphabet $I.$ An element $\omega\in\Lambda(I)$ will be written as
$\omega=\omega_{1}\omega_{2}\dots\omega_{n}\omega_{n+1}\dots;$

  2. b)

for $m\in\mathbb{N},$ the space $\Lambda_{m}=\Lambda_{m}(I)$ of words of
length $m$ with letters from the alphabet $I.$ An element
$\omega\in\Lambda_{m}(I)$ will be written as
$\omega=\omega_{1}\omega_{2}\dots\omega_{m}.$ For $\omega\in\Lambda_{m}$ or
$\omega\in\Lambda$ and $n\in\mathbb{N},n\leq m,$ we denote
$[\omega]_{n}\mathrel{\mathop{\mathchar 58\relax}}=\omega_{1}\dots\omega_{n};$

  3. c)

the space $\Lambda^{\ast}=\Lambda^{\ast}(I)\mathrel{\mathop{\mathchar
58\relax}}=\bigcup_{m\in\mathbb{N}}\Lambda_{m}(I)\cup\\{\lambda\\}$ of finite
words, where $\lambda$ is the empty word;

  4. d)

for $m,n\in\mathbb{N}$ and $\alpha\in\Lambda_{n}(I),$ $\beta\in\Lambda_{m}(I)$
or $\beta\in\Lambda(I),$ one may define the concatenated words
$\alpha\beta\mathrel{\mathop{\mathchar
58\relax}}=\alpha_{1}\dots\alpha_{n}\beta_{1}\dots\beta_{m}\in\Lambda_{m+n}$
and
$\alpha\beta=\alpha_{1}\dots\alpha_{n}\beta_{1}\dots\beta_{m}\beta_{m+1}\dots\in\Lambda,$
respectively;

  5. e)

the metric $d_{\Lambda}$ on $\Lambda(I)$ given by
$d_{\Lambda}(\alpha,\beta)\mathrel{\mathop{\mathchar
58\relax}}=\sum_{n\in\mathbb{N}}\frac{1-\delta_{\alpha_{n}}^{\beta_{n}}}{3^{n}},$
where $\delta_{x}^{y}$ denotes the Kronecker delta of $x$ and $y.$ Note that
$(\Lambda(I),d_{\Lambda})$ is a complete metric space and convergence in
$\Lambda(I)$ coincides with the convergence on components;

  6. f)

for $i\in I,$ the right shift function $F_{i}\mathrel{\mathop{\mathchar
58\relax}}\Lambda(I)\xrightarrow{}\Lambda(I)$ given by
$F_{i}(\omega)\mathrel{\mathop{\mathchar 58\relax}}=i\omega$ for all
$\omega\in\Lambda(I).$ Note that $F_{i}$ is a $\frac{1}{3}-$similarity of
$\Lambda(I);$

  7. g)

for $m\in\mathbb{N}$ and $\omega\in\Lambda_{m}(I),$
$F_{\omega}\mathrel{\mathop{\mathchar 58\relax}}=F_{\omega_{1}}\circ\dots\circ
F_{\omega_{m}}$ and $\Lambda_{\omega}\mathrel{\mathop{\mathchar
58\relax}}=F_{\omega}(\Lambda).$ By convention
$F_{\lambda}\mathrel{\mathop{\mathchar 58\relax}}=id_{\Lambda(I)}$ and
$\Lambda_{\lambda}=\Lambda.$ Note that $\Lambda(I)=\bigcup_{i\in
I}F_{i}(\Lambda(I)),$ so $\Lambda(I)$ is the attractor of the IIFS of
contractions $(\Lambda(I),(F_{i})_{i\in I})$ and for every $m\in\mathbb{N}$
and $\omega\in\Lambda^{\ast},$
$\Lambda=\bigcup_{\alpha\in\Lambda_{m}}\Lambda_{\alpha}$ and
$\Lambda_{\omega}=\bigcup_{\alpha\in\Lambda_{m}}\Lambda_{\omega\alpha};$

  8. h)

if $(X,d)$ is a metric space, $\mathcal{S}=(X,(f_{i})_{i\in I})$ is an IIFS of
contractions on $X,$ $B\subseteq X$ and $\omega\in\Lambda_{m}(I),$ let
$f_{\omega}\mathrel{\mathop{\mathchar 58\relax}}=f_{\omega_{1}}\circ\dots\circ
f_{\omega_{m}}$ and $B_{\omega}\mathrel{\mathop{\mathchar
58\relax}}=f_{\omega}(B).$ By convention
$f_{\lambda}\mathrel{\mathop{\mathchar 58\relax}}=id_{X}$ and $B_{\lambda}=B;$

  9. i)

in the setting above, if $f\mathrel{\mathop{\mathchar
58\relax}}X\xrightarrow{}X$ is a contraction and $(X,d)$ is complete, we
denote its fixed point by $e_{f}.$ If $f=f_{\omega}$ for some
$\omega\in\Lambda^{\ast},$ we denote $e_{f}=e_{f_{\omega}}=e_{\omega}.$

######  Theorem 2.3.

Let $(X,d)$ be a complete metric space, $\mathcal{S}=(X,(f_{i})_{i\in I}),$
$A=A(\mathcal{S})$ its attractor and $c\mathrel{\mathop{\mathchar
58\relax}}=\sup_{i\in I}lip(f_{i})<1.$ Then the assertions below hold:

  1. a)

for any $m\in\mathbb{N}$ and $\omega\in\Lambda(I),$ we have that
$A_{[\omega]_{m+1}}\subseteq A_{[\omega]_{m}}$ and
$\delta(A_{[\omega]_{m}})\to 0.$ More precisely,
$\delta(A_{[\omega]_{m}})=\delta({}\mkern
3.0mu\overline{\mkern-3.0muA_{[\omega]_{m}}})\leq c^{m}\delta(A);$

  2. b)

if $a_{\omega}$ is defined by $\\{a_{\omega}\\}\mathrel{\mathop{\mathchar
58\relax}}=\bigcap_{m\in\mathbb{N}}A_{[\omega]_{m}},$ where
$\omega\in\Lambda(I),$ then
$\lim_{m\to\infty}d(e_{[\omega]_{m}},a_{\omega})=0;$

  3. c)

for every $a\in A$ and $\omega\in\Lambda(I),$ we have
$\lim_{m\to\infty}f_{[\omega]_{m}}(a)=a_{\omega};$

  4. d)

for every $\alpha\in\Lambda^{\ast},$ we have $A=A(\mathcal{S})={}\mkern
3.0mu\overline{\mkern-3.0mu\bigcup_{\omega\in\Lambda}\\{a_{\omega}\\}}$ and
${}\mkern 3.0mu\overline{\mkern-3.0muA_{\alpha}}={}\mkern
3.0mu\overline{\mkern-3.0mu\bigcup_{\omega\in\Lambda}\\{a_{\alpha\omega}\\}}.$
If $A=\bigcup_{i\in I}f_{i}(A),$ then
$A=A(\mathcal{S})=\bigcup_{\omega\in\Lambda}\\{a_{\omega}\\};$

  5. e)

we have $A={}\mkern
3.0mu\overline{\mkern-3.0mu\\{e_{[\omega]_{m}}\mathrel{\mathop{\mathchar
58\relax}}\omega\in\Lambda,m\in\mathbb{N}\\}};$

  6. f)

the function $\pi\mathrel{\mathop{\mathchar
58\relax}}\Lambda(I)\xrightarrow{}A,$ defined by $\pi(\omega)=a_{\omega}$ for
every $\omega\in\Lambda(I),$ has the following properties:

    1. i)

$\pi$ is continuous;

    2. ii)

${}\mkern 3.0mu\overline{\mkern-3.0mu\pi(\Lambda)}=A;$

    3. iii)

if $A=\bigcup_{i\in I}f_{i}(A),$ then $\pi$ is surjective;

  7. g)

for every $i\in I,$ we have that $\pi\circ F_{i}=f_{i}\circ\pi.$

Finally we shall state the Tarski-Kantorovitch fixed-point principle.

######  Definition 2.12.

Let $(P,\leq)$ be a poset and $F\mathrel{\mathop{\mathchar
58\relax}}P\xrightarrow{}P.$ We say that $F$ is $\leq-$continuous if for every
countable chain $\mathcal{C}$ admitting a supremum, we have that
$F(\mathcal{C})$ has a supremum and $F(\sup\mathcal{C})=\sup F(\mathcal{C}).$
Note that in this case $F$ is increasing.

######  Theorem 2.4.

(Tarski-Kantorovitch) Let $(P,\leq)$ be a poset in which every countable chain
admits a supremum and $F\mathrel{\mathop{\mathchar 58\relax}}P\xrightarrow{}P$
a $\leq-$continuous map such that there exists $a\in P$ with $a\leq F(a).$
Then $F$ has a fixed point. Moreover, $\sup_{n\in\mathbb{N}}F^{n}(a)$ is the
least fixed point of $F$ in the set $\\{p\in P\mathrel{\mathop{\mathchar
58\relax}}p\geq a\\}.$

######  Remark 2.5.

Note that we can replace the assumption that every countable chain
$\mathcal{C}$ admits a supremum with the assumption that each increasing
sequence $(p_{n})_{n\in\mathbb{N}}\subseteq P$ admits a supremum.

As in [5] we shall assume that every compact or countably compact space is
Hausdorff.

##  3\. The Hutchinson-Barnsley operator on $(\raisebox{1.79993pt}{\Large$\wp$
}(X),\supseteq)$

Let $X$ be an arbitrary set and $f\mathrel{\mathop{\mathchar
58\relax}}X\xrightarrow{}X$ a selfmap of $X.$ Proposition $1$ from [8] shows
that the function $F\mathrel{\mathop{\mathchar
58\relax}}\raisebox{1.79993pt}{\Large$\wp$
}(X)\xrightarrow{}\raisebox{1.79993pt}{\Large$\wp$ }(X)$ defined by
$F(A)\mathrel{\mathop{\mathchar 58\relax}}=f(A)$ for all $A\subseteq X$ is
$\supseteq-$continuous if and only if all fibres of $f$ are finite.

######  Remark 3.1.

Note that the poset $(\raisebox{1.79993pt}{\Large$\wp$ }(X),\supseteq)$
satisfies the countable chain condition, as if
$(A_{n})_{n\in\mathbb{N}}\subseteq\raisebox{1.79993pt}{\Large$\wp$ }(X),$ then
$\sup_{n\in\mathbb{N}}A_{n}=\bigcap_{n\in\mathbb{N}}A_{n}$ (and, of course,
$\inf_{n\in\mathbb{N}}A_{n}=\bigcup_{n\in\mathbb{N}}A_{n}$).

Our main result in this section is the following:

######  Theorem 3.1.

Let $\mathcal{S}=(X,(f_{i})_{i\in I})$ be a non-overlapping IIFS such that all
the fibres of $f_{i}$ are finite for each $i\in I$ and let
$F_{\mathcal{S}}(A)\mathrel{\mathop{\mathchar 58\relax}}=\bigcup_{i\in
I}f_{i}(A)$ for any $A\subseteq X.$ Then for each $A\subseteq X$ such that
$F_{\mathcal{S}}(A)\subseteq A,$ the set
$\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(A)$ is a fixed point of
$F_{\mathcal{S}}.$ In particular,
$\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)$ is the greatest fixed point
of $F_{\mathcal{S}}.$ It follows that $\mathcal{S}$ admits a nonempty fixed
point if and only if
$\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)\neq\emptyset.$

###### Proof.

We have seen that the poset $(\raisebox{1.79993pt}{\Large$\wp$
}(X),\supseteq)$ satisfies the countable chain condition and obviously
$F_{\mathcal{S}}(A)\in\raisebox{1.79993pt}{\Large$\wp$ }(X)$ for every
$A\subseteq X.$ We shall prove that $F_{\mathcal{S}}$ is
$\supseteq-$continuous.
Let $(C_{n})_{n\in\mathbb{N}}\subseteq\raisebox{1.79993pt}{\Large$\wp$ }(X)$
be a $\supseteq-$increasing sequence, i.e. decreasing in the usual sense.
Obviously, $F_{\mathcal{S}}$ is increasing, so
$(F_{\mathcal{S}}(C_{n}))_{n\in\mathbb{N}}\subseteq\raisebox{1.79993pt}{\Large$\wp$
}(X)$ is a decreasing sequence as well. It remains to prove that
$F_{\mathcal{S}}(\sup_{n\in\mathbb{N}}C_{n})=\sup_{n\in\mathbb{N}}F_{\mathcal{S}}(C_{n}),$
i.e.
$F_{\mathcal{S}}(\bigcap_{n\in\mathbb{N}}C_{n})=\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}(C_{n}).$
Let $y\in F_{\mathcal{S}}(\bigcap_{n\in\mathbb{N}}C_{n})=\bigcup_{i\in
I}f_{i}(\bigcap_{n\in\mathbb{N}}C_{n}).$ Then there exist $i\in I$ and
$x\in\bigcap_{n\in\mathbb{N}}C_{n}$ such that $y=f_{i}(x).$ Then $y\in
f_{i}(C_{n})$ for all $n\in\mathbb{N},$ so
$y\in\bigcap_{n\in\mathbb{N}}\bigcup_{i\in
I}f_{i}(C_{n})=\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}(C_{n}).$
Conversely, let $y\in\bigcap_{n\in\mathbb{N}}\bigcup_{i\in I}f_{i}(C_{n}).$
Then for all $n\in\mathbb{N}$ there exist $i_{n}\in I$ and $x_{n}\in C_{n}$
such that $y=f_{i_{n}}(x_{n}).$ Note that since the sequence
$(C_{n})_{n\in\mathbb{N}}$ is decreasing, we have that $y\in
f_{i_{n+1}}(C_{n+1})\subseteq f_{i_{n+1}}(C_{n}),$ so that $y\in
f_{i_{n+1}}(C_{n})\cap f_{i_{n}}(C_{n}),$ so $i_{n+1}=i_{n}$ for all
$n\in\mathbb{N}$ since $(f_{i})_{i\in I}$ is non-overlapping. Thus, there
exists $i_{\ast}\in I$ such that $y\in f_{i_{\ast}}(C_{n})$ for all
$n\in\mathbb{N}$ and write $y=f_{i_{\ast}}(x_{n}),$ where $x_{n}\in C_{n}$ as
before. It follows that $(x_{n})_{n\in\mathbb{N}}\subseteq
f_{i_{\ast}}^{-1}(y).$ Since this fibre is finite, it follows that we may find
$(x_{n_{k}})_{k\in\mathbb{N}}\subseteq(x_{n})_{n\in\mathbb{N}}$ a subsequence
and $x_{\ast}\in f_{i_{\ast}}^{-1}(y)$ such that $x_{n_{k}}=x_{\ast}$ for all
$k\in\mathbb{N}.$ Since $(C_{n})_{n\in\mathbb{N}}$ is decreasing and
$x_{\ast}=x_{n_{k}}\in C_{n_{k}}$ for all $k\in\mathbb{N},$ it follows that
$x_{\ast}\in\bigcap_{n\in\mathbb{N}}C_{n}.$ Since $x_{\ast}\in
f_{i_{\ast}}^{-1}(y),$ we deduce that $y\in\bigcup_{i\in
I}f_{i}(\bigcap_{n\in\mathbb{N}}C_{n})=F_{\mathcal{S}}(\bigcap_{n\in\mathbb{N}}C_{n}),$
which concludes the proof that $F_{\mathcal{S}}$ is $\supseteq-$continuous.
Thus, the conditions of the Tarski-Kantorovitch fixed-point principle are
satisfied and the first part of the theorem follows from a direct application
of this principle.
If $A$ is a fixed point of $F_{\mathcal{S}},$ then $A=F_{\mathcal{S}}(A),$ so
$A=F_{\mathcal{S}}^{n}(A)$ for all $n\in\mathbb{N}.$ Hence,
$A=\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(A)\subseteq\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X),$
so that $\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)$ is indeed the
greatest fixed point of $F_{\mathcal{S}}.$ The last part of the theorem is
trivial. ∎

######  Remark 3.2.

Consider $X\mathrel{\mathop{\mathchar 58\relax}}=[0,1),$ $(f_{m})_{m\geq
2}\subseteq X^{X},$ $f_{m}(x)\mathrel{\mathop{\mathchar
58\relax}}=\\{x+\frac{1}{m}\\},$ where $\\{x\\}$ symbolises the fractional
part of $x$ and $(C_{n})_{n\geq 3},C_{n}\mathrel{\mathop{\mathchar
58\relax}}=[0,\frac{1}{n}]\cup\br[1-\frac{1}{n},1).$ Obviously, the fibres of
each $f_{m}$ are finite, but the system is not non-overlapping. Clearly,
$\bigcap_{n\geq 3}C_{n}=\\{0\\},$ so $\bigcup_{m\geq 2}f_{m}(\bigcap_{n\geq
3}C_{n})=\\{\frac{1}{2},\frac{1}{3},\dots\\}.$ Also note that $0\in
f_{n}(C_{n})$ for all $n\geq 3.$ It follows that $0\in\bigcup_{m\geq
2}f_{m}(C_{n})$ for all $n\geq 3,$ so $0\in\bigcap_{n\geq 3}\bigcup_{m\geq
2}f_{m}(C_{n})\setminus\bigcup_{m\geq 2}f_{m}(\bigcap_{n\geq 3}C_{n}).$ What
this simple example tells us is that we actually need to assume that the IIFS
considered in the statement of the previous theorem is non-overlapping,
otherwise the Hutchinson-Barnsley operator need not be continuous with respect
to $\supseteq.$

##  4\. The Hutchinson-Barnsley operator on $(\mathcal{F}(X),\supseteq)$

In what follows $X$ will denote a Hausdorff topological space and
$(\mathcal{F}(X),\supseteq)$ is the poset of nonempty closed parts of $X$
ordered by $\supseteq.$ In order to apply the Tarski-Kantorovitch fixed-point
principle, we need to have that each countable chain in
$(\mathcal{F}(X),\supseteq)$ admits a supremum. As shown in Proposition $4$
from [8], this assumption restricts our attention to countably compact spaces.
In fact we will be looking at countably compact sequential spaces $X$ and
establish results regarding the operators $F_{\mathcal{S}}$ and
$G_{\mathcal{S}}$ in this setting. Note that in such a space, given a
decreasing sequence $(C_{n})_{n\in\mathbb{N}}\subseteq\mathcal{F}(X),$ its
supremum is simply $\bigcap_{n\in\mathbb{N}}C_{n}.$

######  Remark 4.1.

As $X$ is a countably compact sequential space, Theorem 2.1 assures us that a
function $f\mathrel{\mathop{\mathchar 58\relax}}X\xrightarrow{}X$ is
continuous if and only if $f(A)$ is closed for each $A\in\mathcal{F}(X)$ and
all fibres of $f$ are closed.

The main result of this section is the following:

######  Theorem 4.1.

Let $X$ be a countably compact sequential space and
$\mathcal{S}=(X,(f_{i})_{i\in I})$ a locally finite non-overlapping IIFS,
where each $f_{i}$ is continuous. Then
$F_{\mathcal{S}}(\mathcal{F}(X))\subseteq\mathcal{F}(X),$
$\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)$ is nonempty and closed and it
is the greatest fixed point of $F_{\mathcal{S}}.$ Moreover, if $X$ is
metrizable, then the sequence
$(F_{\mathcal{S}}^{n}(X))_{n\in\mathbb{N}}\subseteq\mathcal{F}(X)$ converges
to $\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)$ with respect to the
Hausdorff-Pompeiu metric.

###### Proof.

First we prove that we can indeed consider the restriction
$F_{\mathcal{S}}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{F}(X)\xrightarrow{}\mathcal{F}(X).$ Thus, let
$A\in\mathcal{F}(X).$ We shall prove that $F_{\mathcal{S}}(A)=\bigcup_{i\in
I}f_{i}(A)=\bigcup_{i\in I}{}\mkern
3.0mu\overline{\mkern-3.0muf_{i}(A)}={}\mkern
3.0mu\overline{\mkern-3.0mu\bigcup_{i\in I}f_{i}(A)}={}\mkern
3.0mu\overline{\mkern-3.0muF_{\mathcal{S}}(A)}.$ The direct inclusion is
trivial by definition, so we only prove the converse. It suffices to show that
$F_{\mathcal{S}}(A)$ is sequentially closed.
Indeed, let $y\in{}\mkern 3.0mu\overline{\mkern-3.0mu\bigcup_{i\in
I}f_{i}(A)}$ and $(y_{n})_{n\in\mathbb{N}}\subseteq\bigcup_{i\in I}f_{i}(A)$
such that $y_{n}\to y.$ Let $V_{y}$ be the neighbourhood of $y$ provided by
the local-finiteness of the IIFS, i.e. $\\#\\{i\in I\mathrel{\mathop{\mathchar
58\relax}}V_{y}\cap f_{i}(X)\neq\emptyset\\}<\infty.$ Then $V_{y}$ intersects
only finitely many of the sets $(f_{i}(A))_{i\in I}.$ Since $y_{n}\to y,$ we
may assume that $(y_{n})_{n\in\mathbb{N}}\subseteq V_{y}.$ Define $i_{n}\in I$
to be the subscript such that $y_{n}\in f_{i_{n}}(A)$ (it is well defined
since this IIFS is non-overlapping). It follows that
$\\#\\{i_{n}\mathrel{\mathop{\mathchar 58\relax}}n\in\mathbb{N}\\}<\infty,$ so
we may find a subsequence
$(y_{n_{k}})_{k\in\mathbb{N}}\subseteq(y_{n})_{n\in\mathbb{N}}$ such that
$i_{n_{k}}=i_{n_{1}}$ and $y_{n_{k}}\in f_{i_{n_{1}}}(A)$ for all
$k\in\mathbb{N}.$ Since $X$ is Hausdorff, we deduce that $y_{n_{k}}\to y,$ so
that $y\in{}\mkern
3.0mu\overline{\mkern-3.0muf_{i_{n_{1}}}(A)}\subseteq\bigcup_{i\in I}{}\mkern
3.0mu\overline{\mkern-3.0muf_{i}(A)}=\bigcup_{i\in
I}f_{i}(A)=F_{\mathcal{S}}(A),$ proving that $F_{\mathcal{S}}(A)$ is indeed
closed.
$F_{\mathcal{S}}$ is clearly increasing and the continuity of this operator
with respect to $\supseteq$ is shown in the same way as in Theorem 3.1.
It is trivial that $F_{\mathcal{S}}(X)\subseteq X.$ Hence, all the conditions
stated in the Tarski-Kantorovitch fixed-point principle are satisfied and the
first part of the theorem follows directly from this.
For the last part of the theorem, note that if $X$ is metrizable, the sequence
$(F_{\mathcal{S}}^{n}(X))_{n\in\mathbb{N}}$ is $\supseteq-$increasing, so it
converges to
$\sup_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)=\br\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)$
with respect to the Hausdorff-Pompeiu metric (see [4]). ∎

In the proof of the last theorem, we also obtained a result about the other
Hutchinson-Barnley operator, $G_{\mathcal{S}}.$

######  Corollary 4.1.

Let $X$ be countably compact and sequential space,
$\mathcal{S}=(X,(f_{i})_{i\in I})$ a locally finite non-overlapping IIFS. Then
$F_{\mathcal{S}}(A)=\bigcup_{i\in I}f_{i}(A)=\bigcup_{i\in I}{}\mkern
3.0mu\overline{\mkern-3.0muf_{i}(A)}={}\mkern
3.0mu\overline{\mkern-3.0mu\bigcup_{i\in I}f_{i}(A)}=G_{\mathcal{S}}(A)$ for
all $A\in\mathcal{F}(X).$

######  Remark 4.2.

Let $X=[0,1]$ (which is compact and sequential) and
$(f_{m})_{m\in\mathbb{N}}\subseteq X^{X}$ given by
$f_{m}(x)\mathrel{\mathop{\mathchar 58\relax}}=\frac{x+1}{2^{2m-1}}$ for all
$x\in X$ and $m\in\mathbb{N}.$ Obviously, the image of $f_{m}$ is the closed
interval $[\frac{1}{2^{2m-1}},\frac{1}{2^{2m-2}}]$ and $f_{m}$ is continuous
for any $m\in\mathbb{N}.$ It clearly follows that the IIFS
$\mathcal{S}=(X,(f_{m})_{m\in\mathbb{N}})$ is non-overlapping, but not locally
finite (because it is not locally finite at $0$). It is also clear that
$0\in{}\mkern
3.0mu\overline{\mkern-3.0mu\bigcup_{m\in\mathbb{N}}f_{m}(X)}\setminus(\bigcup_{m\in\mathbb{N}}f_{m}(X)),$
so in this case it is not true that
$F_{\mathcal{S}}(\mathcal{F}(X))\subseteq\mathcal{F}(X).$ This example shows
us that we cannot drop the condition that the IIFS considered in Theorem 4.1
is locally finite, because in that case we could have that
$F_{\mathcal{S}}(\mathcal{F}(X))\not\subseteq\mathcal{F}(X)$ and we wouldn’t
be able to apply the Tarski-Kantorovitch fixed-point principle.
Also note that there exist locally finite non-overlapping IIFS’s. Indeed, for
a nonempty set $I$ consider the IIFS $\mathcal{S}=(\Lambda(I),(F_{i})_{i\in
I}).$ This is clearly non-overlapping. Moreover, if $\omega\in\Lambda(I)$ is
arbitrary, consider the open set $U_{\omega}\mathrel{\mathop{\mathchar
58\relax}}=\\{\eta\in\Lambda(I)\mathrel{\mathop{\mathchar
58\relax}}d_{\Lambda}(\omega,\eta)<\frac{1}{3}\\}.$ If $\eta\in\Lambda(I)$ and
$\eta_{1}\neq\omega_{1},$ then $d_{\Lambda}(\omega,\eta)\geq\frac{1}{3},$ so
$\eta\not\in U_{\omega}.$ It follows that $U_{\omega}$ only intersects
$\Lambda_{\omega_{1}}=F_{\omega_{1}}(\Lambda(I)),$ so this IIFS is also
locally finite.

######  Remark 4.3.

Finally, note that we can extend Theorem 4.1 and Corollary 4.1 on the poset
$(\mathcal{B}(X),\supseteq)$ if $X$ is metrizable, the IIFS considered is also
bounded and there exists $B\in\mathcal{B}(X)$ such that
$F_{\mathcal{S}}(B)\subseteq B$. Indeed, note that in this case
$F_{\mathcal{S}}(\mathcal{B}(X))\subseteq\mathcal{B}(X)$ since the IIFS is
bounded and Theorem 4.1 clearly shows us that
$F_{\mathcal{S}}(\mathcal{F}(X))\subseteq\mathcal{F}(X),$ so we may apply the
Tarski-Kantorovitch fixed-point principle to the poset
$(\mathcal{B}(X),\supseteq)$ and $F_{\mathcal{S}}.$ Note that in the case that
such a $B$ exists, then $\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(B)$ is
nonempty, closed and bounded and it is the greatest fixed point of
$F_{\mathcal{S}}$ contained in $B.$

##  5\. The Hutchinson-Barnsley operator on $(\mathcal{K}(X),\supseteq)$

Henceforth $X$ will be a Hausdorff topological space and
$(\mathcal{K}(X),\supseteq)$ will denote the poset of nonempty compact subsets
of $X$ ordered by $\supseteq.$ Note that in this case every countable chain
admits a supremum and if $(C_{n})_{n\in\mathbb{N}}\subseteq\mathcal{K}(X)$ is
a decreasing sequence, then its supremum in this poset is simply
$\bigcap_{n\in\mathbb{N}}C_{n}.$

######  Remark 5.1.

Note that we may assume that $X$ is compact. Indeed, let
$\mathcal{S}=(X,(f_{i})_{i\in I})$ be an IIFS and
$F_{\mathcal{S}}(A)\mathrel{\mathop{\mathchar 58\relax}}=\bigcup_{i\in
I}f_{i}(A)$ for all $A\subseteq X$ just as before. In order to apply the
Tarski-Kantorovitch fixed-point principle to $(\mathcal{K}(X),\supseteq)$ and
$F_{\mathcal{S}},$ we would need the existence of a nonempty compact subset
$B\subseteq X$ such that $F_{\mathcal{S}}(B)\subseteq B.$ Then we may simply
consider the restricted IIFS
$\mathcal{S}\restriction_{B}\mathrel{\mathop{\mathchar
58\relax}}=(B,(f_{i}\restriction_{B})_{i\in I})$ and establish the desired
result in the poset $(\mathcal{K}(B),\supseteq).$

The main result of this section is the following:

######  Theorem 5.1.

Let $X$ be a compact space and $\mathcal{S}=(X,(f_{i})_{i\in I})$ a locally
finite non-overlapping IIFS, where $f_{i}$ is continuous for all $i\in I.$
Then $F_{\mathcal{S}}(\mathcal{K}(X))\subseteq\mathcal{K}(X),$
$\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)$ is nonempty and compact and
it is the greatest fixed point of $F_{\mathcal{S}}.$ Moreover, if $X$ is
metrizable, then the sequence
$(F_{\mathcal{S}}^{n}(X))_{n\in\mathbb{N}}\subseteq\mathcal{K}(X)$ converges
to $\bigcap_{n\in\mathbb{N}}F_{\mathcal{S}}^{n}(X)$ with respect to the
Hausdorff-Pompeiu metric.

###### Proof.

Note that all we need to prove is that
$F_{\mathcal{S}}(\mathcal{K}(X))\subseteq\mathcal{K}(X),$ as the continuity of
$F_{\mathcal{S}}$ with respect to $\supseteq$ follows in the same way as in
Theorem 3.1 and we clearly have that $F_{\mathcal{S}}(X)\subseteq X$ (and $X$
is compact), so we may apply the Tarski-Kantorovitch fixed point principle to
establish the first part of the theorem. Also the last part of the theorem can
be proven in the same way as in Theorem 4.1.
To show that $F_{\mathcal{S}}(\mathcal{K}(X))\subseteq\mathcal{K}(X),$ note
that all compact sets are closed in Hausdorff topological spaces, so
$F_{\mathcal{S}}(\mathcal{K}(X))\subseteq
F_{\mathcal{S}}(\mathcal{F}(X))\subseteq\mathcal{F}(X).$ But since closed
subsets of compact spaces are compact, we deduce that indeed
$F_{\mathcal{S}}(\mathcal{K}(X))\subseteq\mathcal{K}(X).$ ∎

######  Corollary 5.1.

Let $X$ be an arbitrary topological space and $\mathcal{S}=(X,(f_{i})_{i\in
I})$ a locally finite non-overlapping IIFS, where $f_{i}$ is continuous for
all $i\in I.$ The following assertions are equivalent:

  1. a)

there exists $A\in\mathcal{K}(X)$ such that $F_{\mathcal{S}}(A)=A;$

  2. b)

there exists $A\in\mathcal{K}(X)$ such that $F_{\mathcal{S}}(A)\subseteq A.$

###### Proof.

Obviously, $a)\implies b).$ The converse follows from applying Theorem 5.1 to
the restricted IIFS $\mathcal{S}\restriction_{A}$ described in Remark 5.1. ∎

A direct application of Corollary 5.1 (thus a direct application of Theorem
5.1) is the next result, which establishes the existence of a fixed point of
the Hutchinson-Barnsley operator associated to a locally finite non-
overlapping IIFS of contractions on a bounded Heine-Borel metric space.

######  Corollary 5.2.

Let $(X,d)$ be a bounded Heine-Borel metric space and
$\mathcal{S}=(X,(f_{i})_{i\in I})$ a locally finite non-overlapping IIFS of
contractions, where the contractive constant of $f_{i}$ is $h_{i}\in(0,1).$
Then there exists a nonempty compact subset $A\subseteq X$ such that
$F_{\mathcal{S}}(A)=A.$

###### Proof.

The proof is the same as the proof of Corollary 2 from [8] with the remark
that in this case, we have that $M\mathrel{\mathop{\mathchar
58\relax}}=\sup_{i\in I}d(e_{1},e_{i})<\infty,$ where $e_{i}$ is the fixed
point of $f_{i}$ for each $i\in I$ and $h\mathrel{\mathop{\mathchar
58\relax}}=\sup_{i\in I}h_{i}<1$ by the definition of an IIFS of contractions.
∎

##  6\. Remarks regarding the canonical projection
$\pi\mathrel{\mathop{\mathchar
58\relax}}\Lambda(I)\xrightarrow{}A(\mathcal{S})$ for an IIFS of contractions

Throughout this section, $(X,d)$ is a complete metric space and
$\mathcal{S}=(X,(f_{i})_{i\in I})$ is an IIFS of contractions on $X.$ As in
Definition 2.9, we will denote $c\mathrel{\mathop{\mathchar
58\relax}}=\sup_{i\in I}lip(f_{i})<1.$ The attractor of $\mathcal{S}$ will be
denoted by $A=A(\mathcal{S}).$ By $\Lambda(I)$ we mean the shift space
associated to this IIFS (as in Definition 2.11) and
$\pi\mathrel{\mathop{\mathchar
58\relax}}\Lambda(I)\xrightarrow{}A(\mathcal{S})$ is the canonical projection
from the shift space to the attractor of $\mathcal{S}.$ Note that each metric
space is sequential.

######  Proposition 6.1.

With the notations above, if $c\leq\frac{1}{3},$ then $\pi$ is a contraction
and $lip(\pi)\leq 3\delta(A).$

###### Proof.

Indeed, let $\alpha,\beta\in\Lambda(I),$ $\alpha\neq\beta$ and write
$\alpha=\alpha_{1}\alpha_{2}\dots\alpha_{n}\alpha_{n+1}\dots,$
$\beta=\beta_{1}\beta_{2}\dots\beta_{n}\beta_{n+1}\dots.$ Define
$m\mathrel{\mathop{\mathchar 58\relax}}=\max\\{i\geq
0\mathrel{\mathop{\mathchar 58\relax}}\alpha_{i}=\beta_{i}\\},$ where we
define $\alpha_{0}=\beta_{0}\mathrel{\mathop{\mathchar 58\relax}}=\lambda.$
Then $\alpha_{j}=\beta_{j}$ for all $0\leq j\leq m$ and
$\alpha_{m+1}\neq\beta_{m+1}.$ It follows from the definition of $d_{\Lambda}$
that $\frac{1}{3^{m+1}}\leq d_{\Lambda}(\alpha,\beta)\leq\sum_{j\geq
m+1}\frac{1}{3^{j}}=\frac{1}{2}\frac{1}{3^{m}}.$ Moreover, note that
$a_{\alpha},a_{\beta}\in{}\mkern
3.0mu\overline{\mkern-3.0muA_{[\alpha]_{m}}}={}\mkern
3.0mu\overline{\mkern-3.0muA_{[\beta]_{m}}},$ so
$d(\pi(\alpha),\pi(\beta))=d(a_{\alpha},a_{\beta})\leq\delta({}\mkern
3.0mu\overline{\mkern-3.0muA_{[\alpha]_{m}}})\leq c^{m}\delta(A)$ (by part
$a)$ of Theorem $2.3$). Thus, $d(\pi(\alpha),\pi(\beta))\leq
c^{m}\delta(A)\leq\frac{1}{3^{m}}\delta(A)=\frac{1}{3^{m+1}}3\delta(A)\leq
3\delta(A)d_{\Lambda}(\alpha,\beta).$ Since the inequality is also valid when
$\alpha=\beta,$ the conclusion follows. ∎

######  Proposition 6.2.

If $X$ is countably compact and $\mathcal{S}$ is also locally finite and non-
overlapping, then the canonical projection $\pi\mathrel{\mathop{\mathchar
58\relax}}\Lambda(I)\xrightarrow{}A$ is surjective.

###### Proof.

It follows directly from Remark $4.3$, Theorem $4.1$, Corollary $4.1$, the
definition of the attractor of this IIFS and Proposition $5.1$ from [10]
(stating that $\pi$ is onto if and only if $A=\bigcup_{i\in I}f_{i}(A)$). ∎

######  Remark 6.1.

Note that if the IIFS considered has the property that $f_{\omega}(B)\cap
f_{\gamma}(B)=\emptyset$ for all $B\in\mathcal{B}(X)$ and
$\omega,\gamma\in\Lambda^{\ast}(I),$ $\omega\neq\gamma$ (we shall say in this
case that the IIFS is strongly non-overlapping) and $X$ and $\mathcal{S}$
satisfy the conditions in the last proposition, then $\pi$ is also injective.
Indeed, let $\omega,\gamma\in\Lambda(I),$ $\omega\neq\gamma$ and let
$m\in\mathbb{N}$ be such that $\omega_{m}\neq\gamma_{m}.$ Since $\pi$ is
surjective, Proposition $5.1$ from [10] tells us that
$f_{\alpha}(A)=A_{\alpha}=\bigcup_{\omega\in\Lambda(I)}\\{a_{\alpha\omega}\\}$
for any $\alpha\in\Lambda^{\ast}(I).$ Then $[\omega]_{m}\neq[\gamma]_{m},$ so
$f_{[\omega]_{m}}(A)\cap f_{[\gamma]_{m}}(A)=A_{[\omega]_{m}}\cap
A_{[\gamma]_{m}}=\emptyset.$ But $a_{\omega}\in A_{[\omega]_{m}}$ and
$a_{\gamma}\in A_{[\gamma]_{m}},$ so it follows that
$\pi(\omega)=a_{\omega}\neq a_{\gamma}=\pi(\gamma),$ i.e. $\pi$ is injective.

The last remark proves the following:

######  Proposition 6.3.

If $X$ is countably compact and $\mathcal{S}$ is also locally finite and
strongly non-overlapping, then the canonical projection
$\pi\mathrel{\mathop{\mathchar 58\relax}}\Lambda(I)\xrightarrow{}A$ is
bijective.

Finally, we will give sufficient conditions for the canonical projection to be
a homeomorphism and give a few corollaries.

######  Theorem 6.1.

Let $(X,d)$ be a complete metric space and $\mathcal{S}=(X,(f_{i})_{i\in I})$
an IFS of bi-Lipschitz contractions with attractor
$A=A_{\mathcal{S}}\in\mathcal{B}(X)$ admitting a seed space such that:

  1. a)

the coding map $\pi\mathrel{\mathop{\mathchar
58\relax}}I^{\omega}\xrightarrow[]{}A_{\mathcal{S}}$ is continuous and
bijective (in particular, this implies that $\mathcal{S}$ satisfies (SSC)- the
strong separation condition);

  2. b)

if $c_{ij}\mathrel{\mathop{\mathchar 58\relax}}=\inf_{x,y\in
A}d(f_{i}(x),f_{j}(y))>0$ (from (SSC)), we ask that
$c\mathrel{\mathop{\mathchar 58\relax}}=\inf_{i,j\in I}c_{ij}>0.$

Then $\pi\mathrel{\mathop{\mathchar 58\relax}}I^{\omega}\xrightarrow[]{}A$ is
a homeomorphism.

###### Proof.

All we need to show is that the inverse of $\pi$ is continuous, i.e.
$\pi^{-1}\mathrel{\mathop{\mathchar 58\relax}}A\xrightarrow[]{}I^{\omega}$ is
continuous. Let $l,L\in(0,1)$ such that $ld(x,y)\leq d(f_{i}(x),f_{i}(y))\leq
Ld(x,y)$ for all $i\in I$ and $x,y\in X.$
Let us fix $\varepsilon>0$ and define
$\delta_{\varepsilon}\mathrel{\mathop{\mathchar 58\relax}}=c\cdot
l^{-\log_{3}\varepsilon}.$ For $\alpha\in I^{\omega},$ we want to show that
$\pi^{-1}(A\cap B_{X}(a_{\alpha},\delta_{\varepsilon}))\subseteq
B_{I}(\alpha,\varepsilon).$ We define $n(\cdot,\cdot)$ in the following way:
$n(\alpha,\beta)\mathrel{\mathop{\mathchar 58\relax}}=\sup\\{n\geq
0\mathrel{\mathop{\mathchar 58\relax}}[\alpha]_{n}=[\beta]_{n}\\}$ for all
$\alpha,\beta\in I^{\omega}.$ Let us fix $\alpha,\beta\in I^{\omega},$
$\alpha\neq\beta$ and $n>n(\alpha,\beta)=\mathrel{\mathop{\mathchar
58\relax}}p.$ Then we have that
$d(f_{[\alpha]_{n}}(x),f_{[\beta]_{n}}(y))=d(f_{[\alpha]_{p}}(f_{\alpha[p,n]}(x)),f_{[\beta]_{p}}(f_{\beta[p,n]}(y)))\geq
l^{p}d(f_{\alpha_{p+1}}(u),f_{\beta_{p+1}}(v)),$ where $u$ and $v$ are some
elements in the attractor of $\mathcal{S}.$ Then by hypothesis we get
$d(f_{[\alpha]_{n}}(x),f_{[\beta]_{n}}(y))\geq
l^{p}c_{\alpha_{p+1}\beta_{p+1}}\geq l^{p}\cdot c>0.$ Keeping in mind the
statement of $c)$ of Theorem $2.3,$ we deduce that if
$d(a_{\alpha},a_{\beta})<\delta_{\varepsilon},$ then we must have that
$l^{p}\cdot c<\delta_{\varepsilon}=c\cdot l^{-\log_{3}\varepsilon}.$
Therefore, we infer that $p>-\log_{3}\varepsilon.$ Consequently, we have that
$d_{I}(\alpha,\beta)<\frac{1}{3^{n(\alpha,\beta)}}=\frac{1}{3^{p}}<3^{\log_{3}\varepsilon}=\varepsilon.$
Hence the desired inclusion: $\pi^{-1}(A\cap
B_{X}(a_{\alpha},\delta_{\varepsilon}))\subseteq B_{I}(\alpha,\varepsilon).$ ∎

######  Remark 6.2.

  1. i)

Note that the $\delta_{\varepsilon}$ we defined in the proof of the previous
theorem does not depend on $\alpha\in I^{\omega},$ so $\pi^{-1}$ is actually
uniformly continuous;

  2. ii)

Recall that in a metric space, a set is compact if and only if it is complete
and totally bounded;

  3. iii)

Note that if $\\#I<\infty,$ then the second assumption is superfluous since it
is always true. We want to explain why the last theorem is not necessarily
very restrictive. One of the main points of the theorem is that the system
considered consists in bi-Lipschitz function, which we have seen that is
pivotal point of the proof. A large class of interest in the theory of
iterated function systems is that of self-similar systems, i.e. systems of
similarities. Obviously, every similarity is in particular a bi-Lipschitz
function, so the class of systems considered is larger than that of self-
similar systems. The second important assumption is that the canonical
projection is continuous and bijective. If $I$ is finite, then the only
condition here is that the system satisfies (SSC), which is not a big ask. If
$I$ is infinite, then we also ask that this projection is surjective. Once
again, a sufficiently large class of systems satisfy this condition. Finally,
we asked that $\inf_{i,j\in I}c_{ij}>0.$ We are not entirely sure how much
this reduces the class of functions considered when $I$ is infinite. However,
having gained some insight from the proof of the last theorem, we actually
deduce a lesser condition which allows us to conclude that the inverse of the
coding map is continuous. More exactly, we want the following condition to
hold: given $\alpha\in I^{\omega},$ the number
$c_{\alpha}\mathrel{\mathop{\mathchar 58\relax}}=\inf_{n\in\mathbb{N},j\in
I}c_{\alpha_{n}j}$ is strictly positive. In this case we lose the uniform
continuity of $\pi^{-1},$ but what matters is that $\pi^{-1}$ is still
continuous;

  4. iv)

Note that $I^{\omega}$ is compact if and only if $I$ is finite. Indeed, since
$I^{\omega}$ is a metric space, it is easier to prove that $I^{\omega}$ is
sequentially compact if and only if $I$ is finite, which is fairly easy to
see.

######  Corollary 6.1.

If $\pi\mathrel{\mathop{\mathchar
58\relax}}I^{\omega}\xrightarrow[]{}A_{\mathcal{S}}$ is a homeomorphism, then
the attractor of $\mathcal{S}$ is totally disconnected.

###### Proof.

This follows immediately from the fact that $I^{\omega}$ is totally
disconnected in the topology induced by $d_{I}.$ ∎

######  Corollary 6.2.

All finite iterated function systems of bi-Lipschitz functions satisfying
(SSC) have the property that their attractor is homeomorphic to their
associated shift space.

###### Proof.

This follows immediately from the comments made in the last remark and the
last theorem. ∎

######  Corollary 6.3.

Let $\mathcal{S}$ be an IIFS of bi-Lipschitz functions satisfying (SSC) and
whose coding map is surjective. Assume that the attractor of $\mathcal{S}$ is
compact. Then $\pi$ cannot be a homeomorphism. In particular, neither
condition $b),$ nor the condition stated in the previous remark holds.

######  Corollary 6.4.

If $\mathcal{S}$ is an IIFS of bi-Lipschitz functions satisfying the
conditions of the last theorem, then the attractor of $\mathcal{S}$ is not
totally bounded.

###### Proof.

Obviously, it would be true that $A$ is homeomorphic to the shift space of
$\mathcal{S}.$ But $I^{\omega}$ is not compact. Therefore, neither is the
attractor of $\mathcal{S}.$ However, $A$ is closed in a complete metric space,
so it is also complete. Since it is not compact, we deduce that it is not
totally bounded. ∎

## References

  * [1] A. Baranga, The contraction principle as a particular case of Kleene’s fixed point theorem, Discrete Math. 98 (1998), 75-79.
  * [2] M. F. Barnsley, Fractals Everywhere (Academic Press, Boston, 1993).
  * [3] J. Dugundji and A. Granas, Fixed Point Theory (Polish Scientific Publishers, Warszawa, 1982).
  * [4] G. A. Edgar, Measure, Topology and Fractal Geometry (Springer-Verlag, New York, 1990).
  * [5] R. Engelking, General Topology (Polish Scientific Publishers, Warszawa, 1977).
  * [6] K. J. Falconer, Fractal Geometry, Mathematical Foundations and Applications (Wiley, Chichester, 1990).
  * [7] J. Jachymski, Some consequences of the Tarski-Kantorovitch ordering theorem in metric fixed point theory, Quaestiones Math. 21 (1998), 89-99.
  * [8] J. Jachymski, L. Gajek and P. Pokarowski, The Tarski–Kantorovitch prinicple and the theory of iterated function systems, Bulletin of the Australian Mathematical Society 20, 61(2), 247-261.
  * [9] R. Miculescu and A. Mihail, Lipscomb’s space $\omega^{A}$ is the attractor of an infinite IFS containing affine transformations of $l^{2}(A)$, Proc. Amer. Math. Soc. 136 (2008), 587-592.
  * [10] R. Miculescu and A. Mihail, The shift space for an infinite iterated function system, Math. Rep. (Bucur.) 61 (2009), 21-31.
  * [11] R. Miculescu and L. Ioana, Some connections between the attractors of an IIFS $\mathcal{S}$ and the attractors of the sub-IFSs of $\mathcal{S}$, Fixed Point Theory Appl. 2012, 141 (2012)
  * [12] R. Miculescu and A. Mihail, Remetrization results for possible infinite self-similar systems, Topol. Methods. Nonlinear Analysis. 47 (2016), 333-345.
  * [13] R. Miculescu and S. Urziceanu, The canonical projection associated with certain possibly infinite generalized iterated function systems as a fixed point, J. Fixed Point Theory Appl. 20, 141 (2018)
  * [14] N. A. Secelean, Măsură și fractali (Ed. Univ. ”Lucian Blaga”, Sibiu, 2002).