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 \).
For a set \(S \subset H\), the distance function is defined as
for all \(x \in H\).
1.2 Support and Enlargements
For a set \(S \subset H\), the support function at \(x \in H\) is defined as
Given \(\rho \in ]0, +\infty ]\), the \(\rho \)-enlargement of \(S\) is defined as
Given \(\rho \in ]0, +\infty ]\) and positive \(\gamma {\lt} 1\), the \(\gamma \rho \)-inner enlargement of \(S\) is defined as
The excess of \(A\) over \(B\) is defined by
The Hausdorff distance is defined as
1.3 Normal Cones
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}\).
The Clarke normal cone to \(S\) at \(x \in S\) is defined as
where \(T(S; x)\) is the Clarke tangent cone.
Let \(f : H \to \mathbb {R} \cup \{ +\infty \} \) and \(x \in \operatorname {dom} f\). The Clarke subdifferential of \(f\) at \(x\) is
When \(f\) is finite and locally Lipschitz around \(x\), it is characterized by
where \(f^{\circ }(x;\cdot )\) is the generalized directional derivative, and \(f^{\circ }(x;\cdot )\) is the support function of \(\partial f(x)\).
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
for all \(y \in \mathbb {B}(x; \eta )\).
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
for all \(y \in S\) with \(\| y-x\| {\lt} \eta \).
Let \(S \subset H\) be a closed set, \(x \in H\), and \(z \in S\) such that \(d_S(x)=\| x-z\| \). Then
1.4 Approximate Projections
Let \(S \subset H\) be a closed set, \(\varepsilon {\gt} 0\) and \(x \in H\). We define the set of \(\varepsilon \)-approximate projections as
Let \(S \subset H\), \(x \in S\), and \(\varepsilon {\gt} 0\). Then
If \(0 {\lt} \varepsilon _1 \le \varepsilon _2\), then
If \(x \in S\) and \(\varepsilon {\gt} 0\), then \(\text{proj}_S^\varepsilon (x)\) is nonempty.