Local linear convergence analysis of Primal–Dual splitting methods

DOI10.1080/02331934.2018.1426584zbMATH Open1400.90246arXiv1705.01926OpenAlexW2964137109MaRDI QIDQ5745166FDOQ5745166

Gabriel Peyré, Jingwei Liang, Jalal Fadili

Publication date: 5 June 2018

Published in: Optimization (Search for Journal in Brave)

Abstract: In this paper, we study the local linear convergence properties of a versatile class of Primal-Dual splitting methods for minimizing composite non-smooth convex optimization problems. Under the assumption that the non-smooth components of the problem are partly smooth relative to smooth manifolds, we present a unified local convergence analysis framework for these methods. More precisely, in our framework we first show that (i) the sequences generated by Primal-Dual splitting methods identify a pair of primal and dual smooth manifolds in a finite number of iterations, and then (ii) enter a local linear convergence regime, which is characterized based on the structure of the underlying active smooth manifolds. We also show how our results for Primal-Dual splitting can be specialized to cover existing ones on Forward-Backward splitting and Douglas-Rachford splitting/ADMM (alternating direction methods of multipliers). Moreover, based on these obtained local convergence analysis result, several practical acceleration techniques are discussed. To exemplify the usefulness of the obtained result, we consider several concrete numerical experiments arising from fields including signal/image processing, inverse problems and machine learning, etc. The demonstration not only verifies the local linear convergence behaviour of Primal-Dual splitting methods, but also the insights on how to accelerate them in practice.

Full work available at URL: https://arxiv.org/abs/1705.01926

zbMATH Keywords

forward-backward splittingprimal-dual splittinglocal linear convergenceDouglas-Rachford/ADMM partial smoothness

Mathematics Subject Classification ID

Convex programming (90C25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• Variational Analysis
• Convex analysis and monotone operator theory in Hilbert spaces
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science
• Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
• Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs
• Proximité et dualité dans un espace hilbertien
• A splitting algorithm for dual monotone inclusions involving cocoercive operators
• On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems
• Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
• A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality
• A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms
• Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
• A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
• Variable metric forward–backward splitting with applications to monotone inclusions in duality
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration
• An Extrinsic Look at the Riemannian Hessian
• Newton methods for nonsmooth convex minimization: connections among \(\mathcal U\)-Lagrangian, Riemannian Newton and SQP methods
• Identifiable Surfaces in Constrained Optimization
• Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
• Active Sets, Nonsmoothness, and Sensitivity
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Convergence rates with inexact non-expansive operators
• Activity Identification and Local Linear Convergence of Douglas–Rachford/ADMM under Partial Smoothness
• NON-STRICTLY CONVEX MINIMIZATION OVER THE FIXED POINT SET OF AN ASYMPTOTICALLY SHRINKING NONEXPANSIVE MAPPING
• Linear convergence of iterative soft-thresholding
• Compositions and convex combinations of averaged nonexpansive operators
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Convergence Rate Analysis of Primal-Dual Splitting Schemes
• Activity Identification and Local Linear Convergence of Forward--Backward-type Methods
• The degrees of freedom of partly smooth regularizers
• Local Linear Convergence of ISTA and FISTA on the LASSO Problem
• Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
• Local linear convergence of a primal-dual algorithm for the augmented convex models

Cited In (15)

• Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems
• A Peaceman-Rachford splitting method with monotone plus skew-symmetric splitting for nonlinear saddle point problems
• Smooth over-parameterized solvers for non-smooth structured optimization
• Linear convergence rates for variants of the alternating direction method of multipliers in smooth cases
• On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
• Local linear convergence of an ADMM-type splitting framework for equality constrained optimization
• An Implementation Of The Dual Local Decomposition Method
• Faster first-order primal-dual methods for linear programming using restarts and sharpness
• Active‐Set Newton Methods and Partial Smoothness
• Local convergence analysis of a primal-dual method for bound-constrained optimization without SOSC
• Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
• Convergence Rate Analysis of Primal-Dual Splitting Schemes
• Inexact proximal \(\epsilon\)-subgradient methods for composite convex optimization problems
• Partial Smoothness and Constant Rank
• Convergence rates of forward-Douglas-Rachford splitting method

This page was built for publication: Local linear convergence analysis of Primal–Dual splitting methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5745166)