3 Prox-Regular Case
This chapter establishes convergence of the catching-up algorithm for uniformly prox-regular moving sets.
3.1 Uniformly Prox-Regular Sets
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 \(\rho \in ]0, +\infty ]\). The following assertions are equivalent:
\(S\) is \(\rho \)-uniformly prox-regular
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}\)
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 \]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). \]
This is the constant-radius specialization of the equivalences proved by Colombo–Thibault for variable radius \(\rho (\cdot )\) (their Theorem 3).
(1) \(\Rightarrow \) (2). If \(S\) is \(\rho \)-uniformly prox-regular, then Theorem 3(f) with \(\rho (\cdot )\equiv \rho \) yields: for each \(\gamma \in (0,1)\), the projection is single-valued on \(U_\rho ^\gamma (S)\) and
Hence (2) holds.
(2) \(\Rightarrow \) (1). Take \(x\in S\), \(v\in N^P(S;x)\) with \(\| v\| \le 1\), and \(t\in (0,\rho )\). To prove \(\rho \)-prox-regularity it is enough to show
Choose \(t{\lt}t'{\lt}\rho \) and set \(\gamma =t'/\rho \in (0,1)\). Then
so \(x+tv\in U_\rho ^\gamma (S)\) and \(\text{proj}_S(x+tv)\) is well-defined by (2). Using the projection/resolvent identification for the proximal normal cone from Theorem 3 (constant-radius case), one gets \(\text{proj}_S(x+tv)=x\). Therefore \(x\in \text{Proj}_S(x+tv)\), i.e. \(S\) is \(\rho \)-uniformly prox-regular. so \(x+tv\in U_\rho ^\gamma (S)\) and \(\text{proj}_S(x+tv)\) is well-defined by (2). Using the projection/resolvent identification for the proximal normal cone from Theorem 3 (constant-radius case), one gets \(\text{proj}_S(x+tv)=x\). Therefore \(x\in \text{Proj}_S(x+tv)\), i.e. \(S\) is \(\rho \)-uniformly prox-regular.
(1) \(\Leftrightarrow \) (3). In Theorem 3, prox-regularity is equivalent to the hypomonotonicity inequality for proximal normals. For constant radius, that inequality becomes exactly
which is (3).
(2) \(\Rightarrow \) (4). Fix \(\gamma \in (0,1)\) and \(x\in U_\rho ^\gamma (S)\), and write \(p=\text{proj}_S(x)\). By (2), \(\text{proj}_S\) is Lipschitz on the tube, which yields \(C^{1,1}\) regularity of \(x\mapsto \frac12 d_S(x)^2\) there, with modulus controlled by \((1-\gamma )^{-1}\). Translating this estimate to \(d_S\) via proximal subgradients gives Fix \(\gamma \in (0,1)\) and \(x\in U_\rho ^\gamma (S)\), and write \(p=\text{proj}_S(x)\). By (2), \(\text{proj}_S\) is Lipschitz on the tube, which yields \(C^{1,1}\) regularity of \(x\mapsto \frac12 d_S(x)^2\) there, with modulus controlled by \((1-\gamma )^{-1}\). Translating this estimate to \(d_S\) via proximal subgradients gives
equivalent to (4).
(4) \(\Rightarrow \) (3). The semiconvexity-type estimate in (4) implies a near-monotonicity inequality for \(\partial _P d_S\). Passing to the limit along proximal normal rays approaching \(S\) recovers the hypomonotonicity inequality for \(N^P(S;\cdot )\) in (3).
Combining the implications,
so all four statements are equivalent.
Convex sets are \(\rho \)-uniformly prox-regular for any \(\rho {\gt} 0\). This class also includes nonconvex bodies with \(C^2\) boundary.
3.2 Properties of Approximate Projections for Prox-Regular Sets
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)\).
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.
3.3 Convergence Result
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.