EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Andrea Brilli, Morteza Kimiaei, Giampaolo Liuzzi, Stefano Lucidi

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →