  This paper presents a proximal bundle variant, namely, the relaxed proximal
bundle (RPB) method, for solving convex nonsmooth composite optimization
problems. Like other proximal bundle variants, RPB solves a sequence of prox
bundle subproblems whose objective functions are regularized composite
cutting-plane models. Moreover, RPB uses a novel condition to decide whether to
perform a serious or null iteration which does not necessarily yield a function
value decrease. Optimal iteration-complexity bounds for RPB are established for
a large range of prox stepsizes, both in the convex and strongly convex
settings. To the best of our knowledge, this is the first time that a proximal
bundle variant is shown to be optimal for a large range of prox stepsizes.
Finally, iteration-complexity results for RPB to obtain iterates satisfying
practical termination criteria, rather than near optimal solutions, are also
derived.
