Journal of Convex Analysis 19 (2012), No. 4, 1167--1192
Copyright Heldermann Verlag 2012
Inexact and Accelerated Proximal Point Algorithms
DIBRIS, Università di Genova, Via Opera Pia 13, 16145 Genova, Italy
Istituto Italiano di Tecnologia, Via Morego 30, 16163 Genova, Italy
We present inexact accelerated proximal point algorithms for minimizing a proper lower semicontinuous and convex function. We carry on a convergence analysis under different types of errors in the evaluation of the proximity operator, and we provide corresponding convergence rates for the objective function values. The proof relies on a generalization of the strategy proposed by O. Güler ["New proximal point algorithms for convex minimization", SIAM J. Optimization 2(4) (1992) 649--664] for generating estimate sequences according to the definition of Nesterov, and is based on the concept of ε-subdifferential. We show that the convergence rate of the exact accelerated algorithm 1/k2 can be recovered by constraining the errors to be of a certain type.
Keywords: Accelerated proximal point algorithms, global convergence rates, approximation criteria.
MSC: 90C25, 49D37, 65K10
[ Fulltext-pdf (203 KB)] for subscribers only.