Optimization Online


Tight Global Linear Convergence Rate Bounds for Operator Splitting Methods

Goran Banjac (goran.banjac***at***eng.ox.ac.uk)
Paul J. Goulart (paul.goulart***at***eng.ox.ac.uk)

Abstract: In this paper we establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding strong convexity and smoothness of the constituent functions in the optimization problem. However, there are several examples in the literature showing that linear convergence is possible even when these properties do not hold. We provide a unifying analysis method for establishing linear convergence based on linear regularity and show that many existing results are special cases of our approach. Moreover, we propose a novel linearly convergent splitting method for linear programming.

Keywords: Global linear convergence, operator splitting methods, composite convex optimization, linear regularity, averaged operator, error bound, Friedrichs angle, linear programming

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )


Download: [PDF]

Entry Submitted: 03/10/2016
Entry Accepted: 03/10/2016
Entry Last Modified: 07/19/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society