NONCONVEX NOTIONS OF REGULARITY AND CONVERGENCE OF FUNDAMENTAL ALGORITHMS FOR FEASIBILITY PROBLEMS

作者：Hesse, Robert^*; Luke, D. Russell

来源：SIAM Journal on Optimization, 2013, 23(4): 2397-2419.

DOI：10.1137/120902653

• averaged alternating reflections
• convex set
• constraint qualification
• Douglas-Rachford
• linear convergence
• method of alternating projections
• nonconvex set
• normal cone
• projection operator
• reflection operator
• metric regularity
• strong regularity
• linear regularity
• superregularity
• firmly nonexpansive
• nonexpansive
• quasi nonexpansive
• Fejer monotone

We consider projection algorithms for solving (nonconvex) feasibility problems in Euclidean spaces. Of special interest are the method of alternating projections (AP) and the Douglas-Rachford algorithm (DR). In the case of convex feasibility, firm nonexpansiveness of projection mappings is a global property that yields global convergence of AP and for consistent problems DR. A notion of local subfirm nonexpansiveness with respect to the intersection is introduced for consistent feasibility problems. This, together with a coercivity condition that relates to the regularity of the collection of sets at points in the intersection, yields local linear convergence of AP for a wide class of nonconvex problems and even local linear convergence of nonconvex instances of the DR algorithm.

• 出版日期2013