- Level methods uniformly optimal for composite and structured nonsmooth convex optimization Guanghui Lan (glanise.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/2011Entry Accepted: 04/19/2011Entry Last Modified: 04/21/2011Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.