On the Optimal Linear Convergence Rate of a Generalized Proximal Point Algorithm

Min Tao, Xiaoming YUAN*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

The proximal point algorithm (PPA) has been well studied in the literature. In particular, its linear convergence rate has been studied by Rockafellar in 1976 under certain condition. We consider a generalized PPA in the generic setting of finding a zero point of a maximal monotone operator, and show that the condition proposed by Rockafellar can also sufficiently ensure the linear convergence rate for this generalized PPA. Indeed we show that these linear convergence rates are optimal. Both the exact and inexact versions of this generalized PPA are discussed. The motivation of considering this generalized PPA is that it includes as special cases the relaxed versions of some splitting methods that are originated from PPA. Thus, linear convergence results of this generalized PPA can be used to better understand the convergence of some widely used algorithms in the literature. We focus on the particular convex minimization context and specify Rockafellar’s condition to see how to ensure the linear convergence rate for some efficient numerical schemes, including the classical augmented Lagrangian method proposed by Hensen and Powell in 1969 and its relaxed version, the original alternating direction method of multipliers (ADMM) by Glowinski and Marrocco in 1975 and its relaxed version (i.e., the generalized ADMM by Eckstein and Bertsekas in 1992). Some refined conditions weaker than existing ones are proposed in these particular contexts.

Original languageEnglish
Pages (from-to)826-850
Number of pages25
JournalJournal of Scientific Computing
Volume74
Issue number2
DOIs
Publication statusPublished - 1 Feb 2018

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Engineering(all)
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Alternating direction method of multipliers
  • Augmented Lagrangian method
  • Convex programming
  • Linear convergence rate
  • Proximal point algorithm

Fingerprint

Dive into the research topics of 'On the Optimal Linear Convergence Rate of a Generalized Proximal Point Algorithm'. Together they form a unique fingerprint.

Cite this