论文标题
不可行和错误约束意味着交替预测的有限收敛性
Infeasibility and error bound imply finite convergence of alternating projections
论文作者
论文摘要
本文结合了两种成分，以便对解决凸的可行性问题的研究，最优雅和强大的工具之一，即交替投影的方法（MAP）。回到Kaczmarz和Von Neumann等名称，MAP具有跟踪一对点的能力，以实现两个给定的闭合凸组之间的最小距离。不幸的是，MAP可能会遭受任意缓慢的收敛性，并且在某些Lipschitzian误差结合的情况下，均方根率基本上才超过，这是我们的第一种成分。第二个是看似不利且出乎意料的状况，即不可行。对于满足误差绑定的两个非交流闭合凸集集，我们建立了MAP的有限收敛性。特别是，在具有空的交叉点的情况下，将MAP应用于多面体和超平面时有限的许多步骤收敛。此外，目标集彼此之间越远，MAP所需的迭代越越少，可以找到最佳的近似对。我们的结果伴随着有见地的例子以及进一步的理论和算法讨论，包括研究其他投影方法的有限终止。
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.
