A generalized proximal point a lgorithm and its convergence rate

Etienne Corman, Xiaoming YUAN*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

41 Citations (Scopus)

Abstract

We propose a generalized proximal point algorithm (PPA) in the generic setting of finding a root of a maximal monotone operator. In addition to the classical PPA, a number of benchmark operator splitting methods in the PDE and optimization literatures can be retrieved by this generalized PPA scheme. We establish the convergence rate of this generalized PPA scheme under different conditions, including estimating its worst-case convergence rate measured by the iteration complexity under mild assumptions and deriving its linear convergence rate under certain stronger conditions. Throughout our discussion, we pay particular attention to the special case where the operator is the sum of two maximal monotone operators and specify our theoretical results in the generic setting to this special case. Our result turns out to be a general and unified study on the convergence rate of a number of existing methods and subsumes some existing results in the literature.

Original languageEnglish
Pages (from-to)1614-1638
Number of pages25
JournalSIAM Journal on Optimization
Volume24
Issue number4
DOIs
Publication statusPublished - 2014

Scopus Subject Areas

  • Software
  • Theoretical Computer Science

User-Defined Keywords

  • Convergence rate
  • Convex optimization
  • Operator splitting methods
  • Proximal point algorithm

Fingerprint

Dive into the research topics of 'A generalized proximal point a lgorithm and its convergence rate'. Together they form a unique fingerprint.

Cite this