Optimization Online


Level methods uniformly optimal for composite and structured nonsmooth convex optimization

Guanghui Lan (glan***at***ise.ufl.edu)

Abstract: The main goal of this paper is to develop uniformly optimal first-order methods for large-scale convex programming (CP). By uniform optimality we mean that the first-order methods themselves do not require the input of any problem parameters, but can still achieve the best possible iteration complexity bounds. To this end, we provide a substantial generalization of the accelerated level method by Lan \cite{Lan10-2} and demonstrate that it can uniformly achieve the optimal iteration complexity for solving a class of generalized composite CP problems, which covers a wide range of CP problems, including the nonsmooth, weakly smooth, smooth, minmax, composite and regularized problems etc. Then, we present two variants of this level method for solving a class of structured CP problems with a bilinear saddle point structure due to Nesterov~\cite{Nest05-1}. We show that one of these variants can achieve the ${\cal O} (1/\epsilon)$ iteration complexity without requiring the input of any problem parameters. We illustrate the significant advantages of these level methods over some existing first-order methods for solving certain important classes of semidefinite programming (SDP) and two-stage stochastic programming (SP) problems.

Keywords: Convex Programming, Complexity, Level methods, Optimal methods, Semidefinite programming, Stochastic programming

Category 1: Convex and Nonsmooth Optimization

Category 2: Stochastic Programming

Category 3: Linear, Cone and Semidefinite Programming

Citation: Technical Report, Department of Industrial and Systems Engineering, University of Florida, April 2011.

Download: [PDF]

Entry Submitted: 04/19/2011
Entry Accepted: 04/19/2011
Entry Last Modified: 04/21/2011

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