Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/96502
Title: | Circumcentering reflection methods for nonconvex feasibility problems | Authors: | Dizon, ND Hogan, JA Lindstrom, SB |
Issue Date: | Sep-2022 | Source: | Set-valued and variational analysis, Sept. 2022, v. 30, no. 3, p. 943-973 | Abstract: | Recently, circumcentering reflection method (CRM) has been introduced for solving the feasibility problem of finding a point in the intersection of closed constraint sets. It is closely related with Douglas–Rachford method (DR). We prove local convergence of CRM in the same prototypical settings of most theoretical analysis of regular nonconvex DR, whose consideration is made natural by the geometry of the phase retrieval problem. For the purpose, we show that CRM is related to the method of subgradient projections. For many cases when DR is known to converge to a feasible point, we establish that CRM locally provides a better convergence rate. As a root finder, we show that CRM has local convergence whenever Newton–Raphson method does, has quadratic rate whenever Newton–Raphson method does, and exhibits superlinear convergence in many cases when Newton–Raphson method fails to converge at all. We also obtain explicit regions of convergence. As an interesting aside, we demonstrate local convergence of CRM to feasible points in cases when DR converges to fixed points that are not feasible. We demonstrate an extension in higher dimensions, and use it to obtain convergence rate guarantees for sphere and subspace feasibility problems. Armed with these guarantees, we experimentally discover that CRM is highly sensitive to compounding numerical error that may cause it to achieve worse rates than those guaranteed by theory. We then introduce a numerical modification that enables CRM to achieve the theoretically guaranteed rates. Any future works that study CRM for product space formulations of feasibility problems should take note of this sensitivity and account for it in numerical implementations. | Keywords: | Circumcentering Douglas–Rachford Feasibility Iterative methods Projection methods Reflection methods |
Publisher: | Springer | Journal: | Set-valued and variational analysis | ISSN: | 1877-0533 | EISSN: | 1877-0541 | DOI: | 10.1007/s11228-021-00626-9 | Rights: | © The Author(s) 2022. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/. The following publication Dizon, N.D., Hogan, J.A. & Lindstrom, S.B. Circumcentering Reflection Methods for Nonconvex Feasibility Problems. Set-Valued Var. Anal 30, 943–973 (2022) is available at https://doi.org/10.1007/s11228-021-00626-9 |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dizon_Circumcentering_Reflection_Methods.pdf | 1.22 MB | Adobe PDF | View/Open |
Page views
49
Last Week
3
3
Last month
Citations as of Oct 13, 2024
Downloads
27
Citations as of Oct 13, 2024
SCOPUSTM
Citations
6
Citations as of Oct 17, 2024
WEB OF SCIENCETM
Citations
5
Citations as of Oct 17, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.