A note on the worst-case complexity of nonlinear stepsize control methods for convex smooth unconstrained optimization. (3rd June 2022)

• Record Type: Journal Article
• Authors: Garmanjani, R.
• Is Part Of: Optimization. Volume 71:Number 6(2022)
• Page Start: 1709
• Page End: 1719
• Publication Date: 2022-06-03
• Subjects: Nonlinear stepsize control algorithms -- worst-case complexity -- convex smooth unconstrained optimization; 90C25 -- 90C30 -- 65K05 -- 49M37; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1830088
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: In this paper, we analyse the worst-case complexity of nonlinear stepsize control (NSC) algorithms for solving convex smooth unconstrained optimization problems. We show that, to drive the norm of the gradient below some given positive ε, such methods take at most O ( ϵ − 1 ) iterations, which shows that the complexity bound for these methods is in parity with that of gradient descent methods for the same class of problems. As NSC algorithm is a generalization of several methods such as trust-region and adaptive cubic with regularization methods, such bound holds automatically for these methods as well.