Finitely convergent deterministic and stochastic iterative methods for solving convex feasibility problems

• 成果类型: Article
• 署名作者: Kolobov, Victor I.; Reich, Simeon; Zalas, Rafal
• 署名单位: Technion Israel Institute of Technology; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01628-z
• 发表日期: 2022
• 页码: 1163-1183
• 关键词: douglas-rachford algorithm

摘要

We propose finitely convergent methods for solving convex feasibility problems defined over a possibly infinite pool of constraints. Following other works in this area, we assume that the interior of the solution set is nonempty and that certain overrelaxation parameters form a divergent series. We combine our methods with a very general class of deterministic control sequences where, roughly speaking, we require that sooner or later we encounter a violated constraint if one exists. This requirement is satisfied, in particular, by the cyclic, repetitive and remotest set controls. Moreover, it is almost surely satisfied for random controls.