Optimization Online


The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

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

Abstract: This paper considers a general class of iterative optimization algorithms, referred to as linear-optimization-based convex programming (LCP) methods, for solving large-scale convex programming (CP) problems. The LCP methods, covering the classic conditional gradient (CG) method (a.k.a., Frank-Wolfe method) as a special case, can only solve a linear optimization subproblem at each iteration. In this paper, we first establish a series of new lower complexity bounds for the LCP methods to solve different classes of CP problems, including smooth, nonsmooth and certain saddle-point problems. We then formally establish the theoretical optimality or nearly optimality, in the large-scale case, for the CG method and its variants to solve different classes of CP problems. We also introduce several new optimal LCP methods, obtained by properly modifying Nesterov's accelerated gradient method, and demonstrate their possible advantages over the classic CG for solving certain classes of CP problems.

Keywords: convex programming, complexity, conditional gradient method, Frank-Wolfe method, Nesterov's method

Category 1: Convex and Nonsmooth Optimization

Citation: Technical Report, Department of Industrial and Systems Engineering, University of Florida, May 2013.

Download: [PDF]

Entry Submitted: 05/31/2013
Entry Accepted: 05/31/2013
Entry Last Modified: 09/21/2013

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