Worst Case Complexity Bounds for Linesearch-Type Derivative-Free Algorithms
Journal of Optimization Theory and Applications · 2024-10 · 203 (1) · 419-454
DOI: 10.1007/s10957-024-02519-x ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Optimization Theory and Applications, online erschienen am 04.10.2024. Verfasst von Andrea Brilli und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 18 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Università degli Studi di Roma La Sapienza.
Abstract (Originalsprache)
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.
Förderung
- Università degli Studi di Roma La Sapienza
Zitieren
APA
Brilli, A., Kimiaei, M., Liuzzi, G., & Lucidi, S. (2024). Worst Case Complexity Bounds for Linesearch-Type Derivative-Free Algorithms. Journal of Optimization Theory and Applications, 203(1), 419-454. https://doi.org/10.1007/s10957-024-02519-x
Vancouver
Brilli A, Kimiaei M, Liuzzi G, Lucidi S. Worst Case Complexity Bounds for Linesearch-Type Derivative-Free Algorithms. Journal of Optimization Theory and Applications. 2024;203(1):419-454. doi:10.1007/s10957-024-02519-x
BibTeX
@article{Brilli2024,
author = {Brilli, Andrea and Kimiaei, Morteza and Liuzzi, Giampaolo and Lucidi, Stefano},
title = {Worst Case Complexity Bounds for Linesearch-Type Derivative-Free Algorithms},
journal = {Journal of Optimization Theory and Applications},
year = {2024},
volume = {203},
number = {1},
pages = {419--454},
doi = {10.1007/s10957-024-02519-x}
}
EUVIMED