The Impact of Noise on Evaluation Complexity: The Deterministic Trust-Region Case

Stefania Bellavia; Gianmarco Gurioli; Benedetta Morini; Philippe TOINT

doi:10.1007/s10957-022-02153-5

The Impact of Noise on Evaluation Complexity: The Deterministic Trust-Region Case

Stefania Bellavia, Gianmarco Gurioli, Benedetta Morini, Philippe TOINT

Namur Institute for Complex Systems

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Résumé

Intrinsic noise in objective function and derivatives evaluations may cause
premature termination of optimization algorithms. Evaluation complexity bounds
taking this situation into account are presented in the framework of a
deterministic trust-region method. The results show that the presence of
intrinsic noise may dominate these bounds, in contrast with what is known for
methods in which the inexactness in function and derivatives' evaluations is
fully controllable. Moreover, the new analysis provides estimates of the
optimality level achievable, should noise cause early termination. It finally
sheds some light on the impact of inexact computer arithmetic on evaluation
complexity.

langue originale	Anglais
Pages (de - à)	700-729
Nombre de pages	30
journal	Journal of Optimization Theory and Applications
Volume	196
Numéro de publication	2
Les DOIs	https://doi.org/10.1007/s10957-022-02153-5
Etat de la publication	Publié - févr. 2023

Financement

INdAM-GNCS partially supported the first, second and third authors under Progetti di Ricerca 2019 and 2020. The fourth author was partially supported by INdAM through a GNCS grant and by Università degli Studi di Firenze through Fondi di Internazionalizzazione.

Accès au document

10.1007/s10957-022-02153-5

Autres fichiers et liens

Lien vers la publication sur Scopus

7 Citations
3 Article
2 Papier de travail
1 Livre
1 Article dans les actes d'une conférence/un colloque
Afficher plus d’informations
- 1 Préprint

Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is o(eps^{-2}) rather than O(eps^{-2})
Gratton, S., Sim, C. & Toint, P., 20 août 2024, Arxiv.
Résultats de recherche: Papier de travail

File
An optimally fast objective-function-free minimization algorithm using random subspaces
Bellavia, S., Gratton, S., Morini, B. & TOINT, P., 25 oct. 2023, Arxiv, 23 p.
Résultats de recherche: Papier de travail › Préprint

File
Evaluation complexity of algorithms for nonconvex optimization
Cartis, C., Gould, N. I. M. & TOINT, P., juil. 2022, SIAM. 600 p. (SIAM-MOS Series on Optimization)
Résultats de recherche: Livre/Rapport/Revue › Livre

2 Actif

Complexity in nonlinear optimization
Toint, P. (Co-investigateur), Gould, N. I. M. (Co-investigateur) & Cartis, C. (Co-investigateur)
1/11/08 → …
Projet: Recherche
ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire
Sartenaer, A. (Co-investigateur) & Toint, P. (Co-investigateur)
1/01/87 → …
Projet: Axe de recherche

2 Visite à une institution académique externe

DIEF, University of Florence
Toint, P. (Chercheur visiteur)
24 sept. 2023 → 26 oct. 2023
Activité: Visite d'une organisation externe › Visite à une institution académique externe
DIEF, University of Florence
Toint, P. (Chercheur visiteur)
20 sept. 2021 → 20 oct. 2021
Activité: Visite d'une organisation externe › Visite à une institution académique externe

Contient cette citation

@article{08d1a4af16074e30a873ac34d47f3c8c,

title = "The Impact of Noise on Evaluation Complexity: The Deterministic Trust-Region Case",

abstract = "Intrinsic noise in objective function and derivatives evaluations may causepremature termination of optimization algorithms. Evaluation complexity boundstaking this situation into account are presented in the framework of adeterministic trust-region method. The results show that the presence ofintrinsic noise may dominate these bounds, in contrast with what is known formethods in which the inexactness in function and derivatives' evaluations isfully controllable. Moreover, the new analysis provides estimates of theoptimality level achievable, should noise cause early termination. It finallysheds some light on the impact of inexact computer arithmetic on evaluationcomplexity.",

keywords = "Noise, evaluation complexity, trust-region methods, inexact functions and derivatives",

author = "Stefania Bellavia and Gianmarco Gurioli and Benedetta Morini and Philippe TOINT",

note = "Funding Information: INdAM-GNCS partially supported the first, second and third authors under Progetti di Ricerca 2019 and 2020. The fourth author was partially supported by INdAM through a GNCS grant and by Universit{\`a} degli Studi di Firenze through Fondi di Internazionalizzazione. Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = feb,

doi = "10.1007/s10957-022-02153-5",

language = "English",

volume = "196",

pages = "700--729",

journal = "Journal of Optimization Theory and Applications",

issn = "0022-3239",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - The Impact of Noise on Evaluation Complexity

T2 - The Deterministic Trust-Region Case

AU - Bellavia, Stefania

AU - Gurioli, Gianmarco

AU - Morini, Benedetta

AU - TOINT, Philippe

N1 - Funding Information: INdAM-GNCS partially supported the first, second and third authors under Progetti di Ricerca 2019 and 2020. The fourth author was partially supported by INdAM through a GNCS grant and by Università degli Studi di Firenze through Fondi di Internazionalizzazione. Publisher Copyright: © 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2023/2

Y1 - 2023/2

N2 - Intrinsic noise in objective function and derivatives evaluations may causepremature termination of optimization algorithms. Evaluation complexity boundstaking this situation into account are presented in the framework of adeterministic trust-region method. The results show that the presence ofintrinsic noise may dominate these bounds, in contrast with what is known formethods in which the inexactness in function and derivatives' evaluations isfully controllable. Moreover, the new analysis provides estimates of theoptimality level achievable, should noise cause early termination. It finallysheds some light on the impact of inexact computer arithmetic on evaluationcomplexity.

AB - Intrinsic noise in objective function and derivatives evaluations may causepremature termination of optimization algorithms. Evaluation complexity boundstaking this situation into account are presented in the framework of adeterministic trust-region method. The results show that the presence ofintrinsic noise may dominate these bounds, in contrast with what is known formethods in which the inexactness in function and derivatives' evaluations isfully controllable. Moreover, the new analysis provides estimates of theoptimality level achievable, should noise cause early termination. It finallysheds some light on the impact of inexact computer arithmetic on evaluationcomplexity.

KW - Noise, evaluation complexity, trust-region methods, inexact functions and derivatives

UR - http://www.scopus.com/inward/record.url?scp=85145939534&partnerID=8YFLogxK

U2 - 10.1007/s10957-022-02153-5

DO - 10.1007/s10957-022-02153-5

M3 - Article

AN - SCOPUS:85145939534

SN - 0022-3239

VL - 196

SP - 700

EP - 729

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

IS - 2

ER -

The Impact of Noise on Evaluation Complexity: The Deterministic Trust-Region Case

Résumé

Financement

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Refining asymptotic complexity bounds for nonconvex optimization methods, including why steepest descent is o(eps^{-2}) rather than O(eps^{-2})

An optimally fast objective-function-free minimization algorithm using random subspaces

Evaluation complexity of algorithms for nonconvex optimization

Projets

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Algorithmes avancés en optimisation non-linéaire

Activités

DIEF, University of Florence

DIEF, University of Florence

Contient cette citation