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.
Citation
Technical Report, Department of Industrial and Systems Engineering, University of Florida, April 2011.