Linear convergence of the generalized PPA and several splitting methods for the composite inclusion problem

2015/08/21 by Li Shen, Shen, Li, Shaohua Pan +1
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC) #Optimization and Variational Analysis

paper · pdf · doi:10.48550/arxiv.1508.05156

openalex publication_date 2015/08/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For the inclusion problem involving two maximal monotone operators, under the metric subregularity of the composite operator, we derive the linear convergence of the generalized proximal point algorithm and several splitting algorithms, which include the over-relaxed forward-backward splitting algorithm, the generalized Douglas-Rachford splitting algorithm and Davis' three-operator splitting algorithm. To the best of our knowledge, this linear convergence condition is weaker than the existing ones that almost all require the strong monotonicity of the composite operator. Withal, we give some sufficient conditions to ensure the metric subregularity of the composite operator. At last, the preliminary numerical performances on some toy examples support the theoretical results.

Citations

• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Algorithms for Finding Global Minimizers of Image Segmentation and Denoising Models
• Monotone Operators and the Proximal Point Algorithm
• Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications
• Nonlinear total variation based noise removal algorithms
• On the Optimal Linear Convergence Rate of a Generalized Proximal Point Algorithm
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• Convergence rate analysis of the forward-Douglas-Rachford splitting\n scheme

Related

• Projective splitting with backward, half-forward and proximal-Newton steps
• A new splitting method for solving composite monotone inclusions involving parallel-sum operators
• A splitting algorithm for system of composite monotone inclusions
• Almost-Surely Convergent Randomly Activated Monotone Operator Splitting Methods
• Split-Douglas-Rachford algorithm for composite monotone inclusions and Split-ADMM