Optimization Online


Underestimate Sequences via Quadratic Averaging

Chenxin Ma (chm514***at***lehigh.edu)
Naga Venkata C. Gudapati (nag415***at***lehigh.edu)
Majid Jahani (maj316***at***lehigh.edu)
Rachael Tappenden (rachael.tappenden***at***canterbury.ac.nz)
Martin Takac (Takac.MT***at***gmail.com)

Abstract: In this work we introduce the concept of an Underestimate Sequence (UES), which is a natural extension of Nesterovís estimate sequence. Our definition of a UES utilizes three sequences, one of which is a lower bound (or under-estimator) of the objective function. The question of how to construct an appropriate sequence of lower bounds is also addressed, and we present lower bounds for strongly convex smooth functions and for strongly convex composite functions, which adhere to the UES framework. Further, we propose several first order methods for minimizing strongly convex functions in both the smooth and composite cases. The algorithms, based on efficiently updating lower bounds on the objective functions, have natural stopping conditions, which provides the user with a certificate of optimality. Convergence of all algorithms is guaranteed through the UES framework, and we show that all presented algorithms converge linearly, with the accelerated variants enjoying the optimal linear rate of convergence.

Keywords: Underestimate Sequence; Estimate Sequence; Quadratic Averaging; Lower bounds; Strongly convex; Smooth minimization; Composite minimization; Accelerated Algorithms

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )


Download: [PDF]

Entry Submitted: 10/10/2017
Entry Accepted: 10/10/2017
Entry Last Modified: 10/11/2017

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