A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes

DOI10.1137/20M1327513zbMATH Open1532.90075arXiv2003.11457MaRDI QIDQ6337413

Renato D. C. Monteiro, Jiaming Liang

Publication date: 25 March 2020

Abstract: 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.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)

This page was built for publication: A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes