A note on the worst-case complexity of nonlinear stepsize control methods for convex smooth unconstrained optimization

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 $\mathcal{O}\left({ϵ}^{-1}\right)$ 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.

Keywords:

• Nonlinear stepsize control algorithms
• worst-case complexity
• convex smooth unconstrained optimization

AMS CLASSIFICATIONS:

• 90C25
• 90C30
• 65K05
• 49M37

Disclosure statement

No potential conflict of interest was reported by the author.

Additional information

Funding

The support for the author was provided by FCT (Fundação para a Ciência e a Tecnologia) under the scholarship SFRH/BPD/89903/2012 and by the Center for Mathematics of the University of Coimbra – UID/MAT/00324/2013, funded by the Portuguese Government through FCT/MEC and co-funded by the European Regional Development Fund through the Partnership Agreement PT2020, until March 2019. Also, from 1 April 2019 by national funds through FCT under the scope of projects PTDC/MAT-APL/28400/2017 and UIDB/MAT/00297/2020 (Centro de Matemática e Aplicações).