Infeasibility and error bound imply finite convergence of alternating projections
| Autor: | Luiz-Rafael Santos, Roger Behling, Yunier Bello-Cruz |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
021103 operations research
Finite convergence 010102 general mathematics 0211 other engineering and technologies Regular polygon 02 engineering and technology 01 natural sciences 47N10 49M27 65K05 90C25 Theoretical Computer Science Optimization and Control (math.OC) FOS: Mathematics Applied mathematics Order (group theory) 0101 mathematics Mathematics - Optimization and Control Software Mathematics |
| Popis: | This paper combines two ingredients in order to get a rather surprising result on one of the most studied, elegant and powerful tools for solving convex feasibility problems, the method of alternating projections (MAP). Going back to names such as Kaczmarz and von Neumann, MAP has the ability to track a pair of points realizing minimum distance between two given closed convex sets. Unfortunately, MAP may suffer from arbitrarily slow convergence, and sublinear rates are essentially only surpassed in the presence of some Lipschitzian error bound, which is our first ingredient. The second one is a seemingly unfavorable and unexpected condition, namely, infeasibility. For two non-intersecting closed convex sets satisfying an error bound, we establish finite convergence of MAP. In particular, MAP converges in finitely many steps when applied to a polyhedron and a hyperplane in the case in which they have empty intersection. Moreover, the farther the target sets lie from each other, the fewer are the iterations needed by MAP for finding a best approximation pair. Insightful examples and further theoretical and algorithmic discussions accompany our results, including the investigation of finite termination of other projection methods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|