Q-quadratic convergence of the centralized circumcentered-reflection method under a relative interior condition

Abstract

The centralized circumcentered-reflection method (\cCRM) of Behling, Bello-Cruz, Iusem, and Santos~\cite{Behling:2024} is known to converge superlinearly for the feasibility problem $\mathrm{find}z\in X\cap Y$ under a ${\mathcal{C}}^1$ smoothness assumption on the boundaries of $X$ and $Y$. We sharpen this to a quantitative rate: when the boundaries are ${\mathcal{C}}^2$ near the limit point $\bar{z}$, \cCRM\ converges Q-quadratically, with an asymptotic constant \( 2\max(κ_X,κ_Y)/ω\) governed by the boundary curvatures $\hat{I}{º}_X,\hat{I}{º}_Y$ at $\bar{z}$ and the local error-bound modulus $\ddot{I}‰$. The estimate matches Newton-type second-order behavior even though \cCRM\ uses only projections and circumcenters, and numerical experiments on equality-constrained and spectral feasibility problems exhibit the predicted quadratic rate, with \cCRM\ reaching machine precision in a handful of steps where alternating projections and Douglas--Rachford take many. The argument is local and does not require $X\cap Y$ to have nonempty interior in $\re^n$: it suffices that the sets share an affine hull $L=\aff(X)=\aff(Y)$ and meet with nonempty relative interior, which is the natural setting for equality-constrained and spectral feasibility problems, where the classical full-dimensional hypothesis necessarily fails. A ${\mathcal{C}}^1$ version of the argument recovers and extends the superlinear rate of~\cite{Behling:2024} to this lower-dimensional regime. The case $\aff(X)\neq\aff(Y)$ is identified as open.

15 pages