A PROXIMAL BUNDLE VARIANT WITH OPTIMAL ITERATION-COMPLEXITY FOR A LARGE RANGE OF PROX STEPSIZES.

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, in both 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, iterationcomplexity results for RPB to obtain iterates satisfying practical termination criteria, rather than near optimal solutions, are also derived. [ABSTRACT FROM AUTHOR]