Inexact and accelerated proximal point algorithms

We present inexact accelerated proximal point algorithms for minimizing a proper lower semicon- tinuous 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 in [O. Güler. New proximal point algorithms for convex minimization. SIAM J. on Optimization, 2(4):649–664, 1992] for generating estimate sequences according to the definition of Nesterov, and is based on the concept of $\epsilon$-subdifferential. We show that the convergence rate of the exact accelerated algorithm $1/k^2$ can be recovered by constraining the errors to be of a certain type.

Article

Download

View PDF