Fast Bundle-Level Type Methods for Unconstrained and Ball-Constrained Convex Optimization

摘要: It has been shown in (14) that the accelerated prox-level (APL) method and its variant, uniform smoothing level (USL) method, have optimal iteration complexity for solving black-box structured convex programming problems without requiring input of any smoothness information. However, these algorithms require assumption on boundedness feasible set their eciency relies solutions two involved subproblems. These hindered applicability large-scale unconstrained optimization problems. In this paper, we rst present a generic algorithmic framework to extend uniformly methods Moreover, introduce new variants methods, i.e., fast APL (FAPL) USL (FUSL) large scale respectively. Both FAPL FUSL enjoy same as USL, while number subproblems each is reduced from one. an exact solve only subproblem algorithms. As result, proposed improved performance practice signicantly terms both computational time solution quality. Our numerical results some least square total variation based image reconstruction great advantages bundle-level type over APL, other state-of-the-art rst-order methods.