Convergence analysis of some methods for minimizing a nonsmooth convex function

In this paper, we analyze a class of methods for minimizing a proper lower semicontinuous extended-valued convex function f: R-fraktur signn→R-fraktur sign ∪ {∞}. Instead of the original objective function f, we employ a convex approximation fk+1at the kth 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 f(Xk)-minx∈R-fraktur signnf(x) = O(1/(∑k+1j=0√λj)2)even if the iteration points are calculated approximately, where {λk}∞k=0 are the proximal parameters, and (ii) a variant proximal bundle method. Applications to stochastic programs are discussed.