Catching-Up Algorithm for Moreau’s Sweeping Processes

1 Preliminaries

This chapter introduces the mathematical preliminaries needed for the development of the catching-up algorithm with approximate projections.

1.1 Basic Definitions

Throughout this work, \(H\) denotes a real Hilbert space with norm \(\| \cdot \| \) induced by an inner product \(\langle \cdot , \cdot \rangle \).

Definition 1.1 Distance function
#

For a set \(S \subset H\), the distance function is defined as

\[ d_S(x) := \inf _{z \in S} \| x - z\| \]

for all \(x \in H\).

1.2 Support and Enlargements

Definition 1.2 Support function
#

For a set \(S \subset H\), the support function at \(x \in H\) is defined as

\[ \sigma (x, S) := \sup _{z \in S} \langle x, z \rangle \]
Definition 1.3 \(\rho \)-enlargement
#

Given \(\rho \in ]0, +\infty ]\), the \(\rho \)-enlargement of \(S\) is defined as

\[ U_{\rho }(S) = \{ x \in H : d_S(x) {\lt} \rho \} . \]
Definition 1.4 \(\gamma \rho \)-inner enlargement
#

Given \(\rho \in ]0, +\infty ]\) and positive \(\gamma {\lt} 1\), the \(\gamma \rho \)-inner enlargement of \(S\) is defined as

\[ U_{\rho }^{\gamma }(S) := \{ x \in H : d_S(x) {\lt} \gamma \rho \} . \]
Definition 1.5 Excess
#

The excess of \(A\) over \(B\) is defined by

\[ e(A, B) := \sup _{x \in A} d_B(x). \]
Definition 1.6 Hausdorff distance
#

The Hausdorff distance is defined as

\[ d_H(A, B) := \max \{ e(A, B), e(B, A)\} . \]

1.3 Normal Cones

Definition 1.7 Clarke tangent cone
#

A vector \(h \in H\) belongs to the Clarke tangent cone \(T(S; x)\) when for every sequence \((x_n)\) in \(S\) converging to \(x\) and every sequence of positive numbers \((t_n)\) converging to \(0\), there exists a sequence \((h_n)\) converging to \(h\) such that \(x_n + t_n h_n \in S\) for all \(n \in \mathbb {N}\).

Definition 1.8 Clarke normal cone
#

The Clarke normal cone to \(S\) at \(x \in S\) is defined as

\[ N(S; x) := \{ v \in H : \langle v, h \rangle \le 0 \text{ for all } h \in T(S; x) \} \]

where \(T(S; x)\) is the Clarke tangent cone.

Definition 1.9 Clarke subdifferential

Let \(f : H \to \mathbb {R} \cup \{ +\infty \} \) and \(x \in \operatorname {dom} f\). The Clarke subdifferential of \(f\) at \(x\) is

\[ \partial f(x) := \{ v \in H : (v,-1) \in N(\operatorname {epi} f; (x,f(x))) \} . \]

When \(f\) is finite and locally Lipschitz around \(x\), it is characterized by

\[ \partial f(x)=\{ v\in H:\langle v,h\rangle \le f^{\circ }(x;h)\ \text{for all }h\in H\} , \]

where \(f^{\circ }(x;\cdot )\) is the generalized directional derivative, and \(f^{\circ }(x;\cdot )\) is the support function of \(\partial f(x)\).

Definition 1.10 Proximal subdifferential
#

Let \(f : H \to \mathbb {R} \cup \{ +\infty \} \) be lower semicontinuous and \(x \in \text{dom } f\). An element \(\zeta \) belongs to the proximal subdifferential of \(f\) at \(x\), denoted \(\partial _P f(x)\), if there exist \(\sigma , \eta \geq 0\) such that

\[ f(y) \ge f(x) + \langle \zeta , y - x \rangle - \sigma \| y - x\| ^2 \]

for all \(y \in \mathbb {B}(x; \eta )\).

Definition 1.11 Proximal normal cone
#

Let \(S \subset H\) be a closed set and \(x \in S\). A vector \(\zeta \) belongs to the proximal normal cone to \(S\) at \(x\) if there exist \(\sigma \ge 0\) and \(\eta {\gt} 0\) such that

\[ \langle \zeta , y - x \rangle \le \sigma \| y-x\| ^2 \]

for all \(y \in S\) with \(\| y-x\| {\lt} \eta \).

Lemma 1.12 Projection formula for the proximal subdifferential of the distance

Let \(S \subset H\) be a closed set, \(x \in H\), and \(z \in S\) such that \(d_S(x)=\| x-z\| \). Then

\[ x-z \in d_S(x)\, \partial _P d_S(z). \]

1.4 Approximate Projections

Definition 1.13 Approximate projection
#

Let \(S \subset H\) be a closed set, \(\varepsilon {\gt} 0\) and \(x \in H\). We define the set of \(\varepsilon \)-approximate projections as

\[ \text{proj}_S^\varepsilon (x) := \left\{ z \in S : \| x - z\| ^2 {\lt} d_S^2(x) + \varepsilon \right\} \]
Lemma 1.14

Let \(S \subset H\), \(x \in S\), and \(\varepsilon {\gt} 0\). Then

\[ x \in \text{proj}_S^\varepsilon (x). \]
Lemma 1.15 Monotonicity with respect to the tolerance

If \(0 {\lt} \varepsilon _1 \le \varepsilon _2\), then

\[ \text{proj}_S^{\varepsilon _1}(x) \subset \text{proj}_S^{\varepsilon _2}(x). \]
Lemma 1.16 Nonemptiness of approximate projections
#

If \(x \in S\) and \(\varepsilon {\gt} 0\), then \(\text{proj}_S^\varepsilon (x)\) is nonempty.