Worst Case Complexity Bounds for Linesearch-Type Derivative-Free Algorithms

Andrea Brilli (), Morteza Kimiaei (), Giampaolo Liuzzi () and Stefano Lucidi ()
Additional contact information
Andrea Brilli: Sapienza University of Rome
Morteza Kimiaei: Universität Wien
Giampaolo Liuzzi: Sapienza University of Rome
Stefano Lucidi: Sapienza University of Rome

Journal of Optimization Theory and Applications, 2024, vol. 203, issue 1, No 17, 419-454

Abstract: Abstract This paper is devoted to the analysis of worst case complexity bounds for linesearch-type derivative-free algorithms for the minimization of general non-convex smooth functions. We consider a derivative-free algorithm based on a linesearch extrapolation technique. First we prove that it enjoys the same complexity properties which have been proved for pattern and direct search algorithms, namely that the number of iterations and of function evaluations required to drive the norm of the gradient of the objective function below a given threshold $$\epsilon $$ ϵ for the first time is $${{\mathcal {O}}}(\epsilon ^{-2})$$ O ( ϵ - 2 ) in the worst case. This is the first contribution proving worst-case complexity properties for derivative-free linesearch-type algorithms. Then we show that the lineasearch approach used by the described algorithm allows us to guarantee the further property that the number of iterations such that the norm of the gradient is bigger than $$\epsilon $$ ϵ is $$\mathcal{O}(\epsilon ^{-2})$$ O ( ϵ - 2 ) in the worst case.

Keywords: Derivative-free optimization; Unconstrained optimization; Line search; Worst case complexity; 90C30; 90C56 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-024-02519-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:203:y:2024:i:1:d:10.1007_s10957-024-02519-x

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-024-02519-x

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().