Optimization Online


Fast Bundle-Level Type Methods for unconstrained and ball-constrained convex optimization

Yunmei Chen(yun***at***math.ufl.edu)
Guanghui Lan(glan***at***ise.ufl.edu)
Yuyuan Ouyang(ouyang***at***ufl.edu)
Wei Zhang(weizhang657***at***ufl.edu)

Abstract: It has been shown in \cite{Lan13-1} 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.

Keywords: convex programming, first-order, optimal method, bundle-level type method, total variation, image reconstruction

Category 1: Convex and Nonsmooth Optimization

Citation: Technical Report, Department of Industrial and Systems Engineering & Department Mathematics, University of Florida, December, 2014.

Download: [PDF]

Entry Submitted: 12/05/2014
Entry Accepted: 12/05/2014
Entry Last Modified: 12/05/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society