Dependencies

A sequence \((\varepsilon _k)\) is admissible if \(\varepsilon _k {\gt} 0\) for every \(k\).

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

A set \(S \subset H\) is boundedly compact if \(S \cap r\mathbb {B}\) is compact for all \(r {\gt} 0\).

Given a time discretization \(\{ t_k^n\} _{k=0}^n\) of \([0,T]\) and a sequence \((\varepsilon _k^n)\) of positive numbers, the catching-up algorithm with errors defines a piecewise linear function \(x^n: [0,T] \to H\) with nodes

for all \(k \in \{ 0, \ldots , n-1\} \), with \(x_0^n = x_0\).

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)\).

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}\).

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

for all \(x \in H\).

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

A family \((S(t))_{t\in I}\) of closed sets is called equi-uniformly subsmooth if for all \(\varepsilon {\gt} 0\), there exists \(\delta {\gt} 0\) such that for all \(t \in I\), the subsmoothness inequality holds uniformly.

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

The Hausdorff distance is defined as

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

Let \(S \subset H\) be a closed set and \(\rho \in (0, +\infty ]\). The set \(S\) is called \(\rho \)-uniformly prox-regular if for all \(x \in S\) and \(\zeta \in N^P(S; x)\) one has

for all \(x' \in S\).

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 \(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. We say that \(S\) is subsmooth at \(x_0 \in S\) if for every \(\varepsilon {\gt} 0\) there exists \(\delta {\gt} 0\) such that

whenever \(x_1, x_2 \in B[x_0, \delta ] \cap S\) and \(\xi _i \in N(S; x_i) \cap \mathbb {B}\) for \(i \in \{ 1,2\} \).

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

Given a Hilbert space \(H\) and a family of closed moving sets \((C(t))_{t\in [0,T]}\), Moreau’s sweeping process is the differential inclusion

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.

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

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

If \(x \in S\) and \((\varepsilon _k)\) is admissible, then for every \(k\):

Let \(\mathcal{C} = \{ C_n\} _{n\in \mathbb {N}} \cup \{ C\} \) be a family of nonempty, closed, and equi-uniformly subsmooth sets. Under appropriate convergence assumptions, certain stability properties hold for the subdifferentials of distance functions.

Let \(S \subset H\) be \(\rho \)-uniformly prox-regular. If \((x_n) \to x \in U_\rho (S)\) and \(z_n \in \text{proj}_S^{\varepsilon _n}(x_n)\) with \(\varepsilon _n \to 0\), then \(z_n \to \text{proj}_S(x)\).

Let \(S \subset H\) be a closed set and \(\rho \in ]0, +\infty ]\). The following assertions are equivalent:

1. \(S\) is \(\rho \)-uniformly prox-regular

2. For any \(\gamma \in (0,1)\), the projection map \(\text{proj}_S\) is well-defined on \(U_\rho ^\gamma (S)\) and Lipschitz continuous with constant \((1-\gamma )^{-1}\)

3. For any \(x_i \in S\), \(v_i \in N^P(S; x_i)\) with \(i = 1, 2\):

   \[ \langle v_1 - v_2, x_1 - x_2 \rangle \ge -\frac{1}{2\rho } (\| v_1\| + \| v_2\| ) \| x_1 - x_2\| ^2 \]

4. For all \(\gamma \in ]0,1[\), for all \(x \in U_\rho ^\gamma (S)\), for all \(x' \in H\), and for all \(\xi \in \partial _P d_S(x)\),

   \[ \langle \xi , x' - x \rangle \le \frac{1}{2\rho (1-\gamma )^2}\| x' - x\| ^2 + d_S(x') - d_S(x). \]

For suitable \(\gamma \) and \(\varepsilon \), approximate projections on prox-regular sets satisfy a quasi-Lipschitz property relating the distance between projections to the distance between original points.

Under suitable assumptions on the moving set \(C\) and the error sequence \((\varepsilon _k^n)\), the sequence \((x^n)\) of functions generated by the catching-up algorithm satisfies certain boundedness and convergence properties.

Let \(C \subset H\) be a boundedly compact closed set. Under appropriate assumptions on the error sequence, the catching-up algorithm with approximate projections converges to a solution of the sweeping process with fixed set \(C\).

Let \((C(t))_{t\in [0,T]}\) be a family of uniformly prox-regular sets. Under appropriate assumptions on the discretization and error sequence, the sequence \((x^n)\) generated by the catching-up algorithm converges to the unique solution of the sweeping process.

For boundedly compact subsmooth moving sets, the catching-up algorithm with approximate projections converges to a solution of the sweeping process.