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