Source-linked AI summary
Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
Robert Hesse, D. Russell Luke
TL;DR
The paper addresses convergence analysis for MAP and Douglas–Rachford in nonconvex feasibility problems, where classical firm nonexpansiveness is unavailable. It introduces relaxed local operator regularity based on (ε, δ)-regularity and combines it with coercivity and intersection regularity to obtain convergence results. The framework yields local linear convergence for MAP and establishes sharper necessity conditions for Douglas–Rachford iterates in relevant settings.
Problem
Classical firm nonexpansiveness gives global convex convergence, but nonconvex feasibility requires a relaxed local framework for projection-based algorithms.
Method
The paper develops (S, ε)-firm nonexpansiveness from set regularity and combines operator estimates with coercivity and regularity of fixed-point intersections.
Results
The framework yields local linear convergence of MAP under broad nonconvex conditions and shows that strong regularity is necessary for linear convergence of Douglas–Rachford iterates to affine-subspace intersections.
Takeaways & Limitations
The analysis extends projection-method convergence theory beyond convex sets while distinguishing the stronger conditions required for Douglas–Rachford iterates than for MAP.
Takeaways & Limitations
The convergence-radius estimates are conservative, and the modulus of linear regularity does not recover optimal Douglas–Rachford convergence results.
Abstract
from arXiv · showhide
We consider projection algorithms for solving (nonconvex) feasibility problems in Euclidean spaces. Of special interest are the Method of Alternating Projections (MAP) and the Douglas-Rachford or Averaged Alternating Reflection Algorithm (AAR). In the case of convex feasibility, firm nonexpansiveness of projection mappings is a global property that yields global convergence of MAP and for consistent problems AAR. Based on (ε, δ)-regularity of sets developed by Bauschke, Luke, Phan and Wang in 2012, a relaxed local version of firm nonexpansiveness with respect to the intersection is introduced for consistent feasibility problems. Together with a coercivity condition that relates to the regularity of the intersection, this yields local linear convergence of MAP for a wide class of nonconvex problems,
1 Introduction
The paper develops a framework for analyzing MAP and Douglas–Rachford iterations when projection mappings depart quantitatively from firm nonexpansiveness, extending convergence analysis to nonconvex feasibility problems. Its examples contrast their convergence behavior across geometric settings, while the classical convex theory supplies the starting point.
- Contribution: The framework generalizes fixed-point analysis to operators that violate firm nonexpansiveness in a quantifiable way.It is applied to MAP and Douglas–Rachford algorithms.
- Algorithms: The paper introduces MAP and Douglas–Rachford as Picard iterations of their associated projection and reflection operators.The Douglas–Rachford operator averages the identity with a composition of reflectors.
- Examples: MAP and Douglas–Rachford converge linearly for two intersecting lines in R2.This example illustrates the basic favorable behavior of both methods.
- Examples: For two lines in R3, MAP retains the first example’s convergence behavior, whereas Douglas–Rachford has fixed points outside the intersection.Starting points in the sum of the lines reduce to the R2 case.
- Examples: For a line and a ball intersecting at one point, MAP converges without a linear rate and Douglas–Rachford has fixed points outside the intersection.The paper also discusses a cross and subspace example where both methods converge globally despite nonconvexity.
- Background: The paper extends projection-method analysis from convex to nonconvex sets, where projectors may be set-valued.For closed convex sets, projectors are single-valued and firmly nonexpansive, while reflectors are nonexpansive.
2 (S, ε)-firm nonexpansiveness
The paper relaxes firm nonexpansiveness relative to a target set and connects this property to weak regularity conditions for nonconvex sets. These relationships provide the operator estimates used in subsequent convergence analysis.
- Relaxed operator regularity: The paper introduces (S, ε)-firm nonexpansiveness as a relaxed firm-nonexpansiveness property for possibly set-valued mappings.When ε = 0, the corresponding notions become S-firm nonexpansiveness or S-nonexpansiveness.
- Operator calculus: The relaxed property is linked to 1/2-averaged companion mappings and is preserved under convex combinations with the maximum constituent ε.This extends the framework to combinations of operators.
- Set regularity: (ε, δ)-subregularity and (ε, δ)-regularity provide localized set conditions used to derive relaxed firm nonexpansiveness of projectors and reflectors.The projector onto an (ε, δ)-subregular set is shown to satisfy a corresponding relaxed firm-nonexpansiveness property.
- Set regularity: (ε, δ)-regularity is weaker than Clarke regularity and therefore weaker than super-regularity.The paper explicitly notes that (ε, δ)-regularity does not imply Clarke regularity.
- Examples: A pathological example shows that subregularity can hold even when regularity and Clarke regularity fail at the same point.The example is (0, ∞)-subregular at the origin but not (ε, δ)-regular there for ε < 1.
- Douglas–Rachford: The framework characterizes how Douglas–Rachford violates firm nonexpansiveness on neighborhoods of subregular sets.For convex sets, the usual firm-nonexpansiveness result is recovered.
3 Linear Convergence of Iterated (S, ε)-firmly nonexpansive Operators
The paper develops localized regularity and coercivity conditions for analyzing fixed-point iterations beyond firm nonexpansiveness. These conditions yield local linear convergence results for MAP and Douglas-Rachford, while strong regularity is necessary for Douglas-Rachford iterates to converge linearly to the intersection.
- Regularity framework: The framework extends fixed-point analysis to operators that violate firm nonexpansiveness in a quantifiable way.It connects set regularity with the degree of violation of firm nonexpansiveness for projection-based mappings.
- Regularity framework: Local linear regularity links the distances to individual sets with the distance to their intersection and generalizes key regularity concepts through localization.Strong regularity implies local linear regularity, but is more restrictive.
- Method of Alternating Projections: For MAP, local linear regularity supplies a coercivity condition that yields a linear distance decrease under suitable regularity of the nonconvex set.The stated estimate is d(x_{2n+2}, S) ≤ (1 − γ^2 + ε̃)d(x_{2n}, S).
- Douglas-Rachford: For Douglas-Rachford with an affine subspace and a super-regular set, strong linear regularity gives local linear convergence, while (ε, δ)-regularity yields convergence in a special case.The paper summarizes these results through Theorem 42 and the preceding special-case lemma.
- Douglas-Rachford: For affine subspaces, strong regularity is necessary for Douglas-Rachford iterates to converge linearly to the intersection, unlike MAP where the same conditions are sufficient but not necessary.The subspace characterization is A⊥ ∩ B⊥ = {0}; under this condition, convergence holds for every starting point with linear rate.
- Douglas-Rachford: A Friedrichs angle below 1 alone does not guarantee Douglas-Rachford convergence to the intersection from every starting point.The paper gives an example where the angle matches a convergent case but iterates outside a specified subspace do not converge to the intersection.
4 Concluding Remarks
The paper identifies unresolved limitations in its Douglas–Rachford convergence analysis and outlines extensions to broader fixed-point mappings. It also notes that the current linear-regularity approach may not yield optimal rates.
- The linear-regularity modulus does not recover optimal convergence results for Douglas–Rachford, possibly because of the proof technique.The authors leave the question of a quantitative primal angle between sets open.
- The paper leaves a fuller investigation of Douglas–Rachford shadows and angles between sets at the intersection in the nonconvex setting to future work.
- Extending the analysis to fixed-point mappings built from functions, set-valued mappings, proximal operators, and reflectors is identified as future work.The authors relate local linear regularity to strong metric subregularity, but showing metric subregularity of the mappings remains difficult.