A convergent relaxation of the Douglas-Rachford algorithm

Area of Science:

• Optimization Theory
• Numerical Analysis
• Convex Analysis

Background:

• Structured optimization problems are prevalent in various scientific domains.
• Existing algorithms like backward-backward and Douglas-Rachford (DR) have limitations.
• Non-convex feasibility problems, including inconsistent ones, require efficient solution methods.

Purpose of the Study:

• To propose a generalized algorithm for structured optimization problems.
• To analyze the convergence properties of the proposed algorithm.
• To investigate its application to non-convex feasibility problems and compare its performance.

Main Methods:

• Development of a novel iterative algorithm for structured optimization.
• Characterization of fixed point sets for the associated operator.
• Establishment of convergence criteria based on general fixed-point iterations.
• Analysis of local linear convergence for non-convex feasibility problems under regularity assumptions.

Main Results:

• The proposed algorithm encompasses backward-backward and Douglas-Rachford algorithms as special cases.
• New convergence criteria are established for general fixed-point iterations.
• Local linear convergence is proven for non-convex feasibility problems with mild regularity conditions.
• Refined linear convergence criteria for the Douglas-Rachford algorithm are presented.
• New criteria for linear and sublinear convergence are derived for feasibility problems involving affine sets.
• Demonstrated improved numerical performance compared to the RAAR algorithm for sparse feasibility problems.

Conclusions:

• The proposed algorithm offers a unified framework for solving structured optimization problems.
• It provides enhanced convergence analysis, particularly for non-convex and inconsistent feasibility problems.
• The algorithm shows promising numerical performance, outperforming existing methods in specific applications.