Optimization Online


Convergence Rates with Inexact Nonexpansive Operators

Jingwei Liang (jingwei.liang***at***ensicaen.fr)
Jalal Fadili (jalal.Fadili***at***ensicaen.fr)
Gabriel Peyré (gabriel.Peyre***at***ceremade.dauphine.fr)

Abstract: In this paper, we present a convergence rate analysis for the inexact Krasnosel'ski{\u{\i}}-Mann iteration built from nonexpansive operators. Our results include two main parts: we first establish global pointwise and ergodic iteration-complexity bounds, and then, under a metric subregularity assumption, we establish local linear convergence for the distance of the iterates to the set of fixed points. The obtained iteration-complexity result can be applied to analyze the convergence rate of various monotone operator splitting methods in the literature, including the Forward-Backward, the Generalized Forward-Backward, Douglas-Rachford, ADMM and Primal-Dual splitting (PDS) methods. For these methods, we also develop easily verifiable termination criteria for finding an approximate solution, which can be seen as generalization of the termination criterion for the classical gradient descent method. We finally develop a parallel analysis for the non-stationary iteration. The usefulness of our results is illustrated by applying them to a large class of composite convex optimization problems of the form $f + \sum_{i=1}^n h_i$, where $f$'s gradient is Lipschitz-continuous and the $h_i$'s are simple (\ie~whose proximity operator is easily computable). Experiments on some inverse problems in signal and image processing problems are shown.

Keywords: Monotone inclusion, Nonexpansive operator, Convergence rates, Operator splitting, Convex optimization, Inverse problems.

Category 1: Convex and Nonsmooth Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: GREYC CNRS UMR 6072, ENSICAEN, 6, Bd du Maréchal Juin, 14050 Caen Cedex, France, 04/2014

Download: [PDF]

Entry Submitted: 04/18/2014
Entry Accepted: 04/18/2014
Entry Last Modified: 06/11/2014

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