Convergence Analysis of Some Methods for Minimizing a Nonsmooth Convex Function

Abstract

In this paper, we analyze a class of methods for minimizing a proper lower semicontinuous extended-valued convex function . Instead of the original objective function f , we employ a convex approximation f k + 1 at the k th iteration. Some global convergence rate estimates are obtained. We illustrate our approach by proposing (i) a new family of proximal point algorithms which possesses the global convergence rate estimate even it the iteration points are calculated approximately, where are the proximal parameters, and (ii) a variant proximal bundle method. Applications to stochastic programs are discussed.