DEPARTAMENTO DE MATEMÁTICA – CFM / UFSC

Próximo Colóquio

26 de Novembro de 2021, 14:00h

Prof. Dr. Luiz-Rafael Santos (UFSC-Blumenau)

Infeasibility and error bound imply finite convergence of alternating projections

Abstract: In this work we combine 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. Moreover, the farther the target sets lie from each
other, 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.

Link do Youtube para o Colóquio: