Convergence rates with inexact non-expansive operators

• 成果类型: Article
• 署名作者: Liang, Jingwei; Fadili, Jalal; Peyre, Gabriel
• 署名单位: Universite de Caen Normandie; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Universite Paris-Dauphine; Universite PSL; Universite Paris-Dauphine
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0964-4
• 发表日期: 2016
• 页码: 403-434
• 关键词: proximal point algorithm; monotone inclusions; convex minimization; WEAK-CONVERGENCE; extragradient; REGULARITY; SUM

摘要

In this paper, we present a convergence rate analysis for the inexact Krasnosel'skiAaEuroMann iteration built from non-expansive operators. The presented results include two main parts: we first establish the global pointwise and ergodic iteration-complexity bounds; then, under a metric sub-regularity assumption, we establish a local linear convergence for the distance of the iterates to the set of fixed points. The obtained results can be applied to analyze the convergence rate of various monotone operator splitting methods in the literature, including the Forward-Backward splitting, the Generalized Forward-Backward, the Douglas-Rachford splitting, alternating direction method of multipliers and Primal-Dual splitting methods. For these methods, we also develop easily verifiable termination criteria for finding an approximate solution, which can be seen as a generalization of the termination criterion for the classical gradient descent method. We finally develop a parallel analysis for the non-stationary Krasnosel'skiAaEuroMann iteration.