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

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	700-729
Number of pages	30
Journal	Journal of Optimization Theory and Applications
Volume	196
Issue number	2
DOIs	https://doi.org/10.1007/s10957-022-02153-5
Publication status	Published - Feb 2023

Keywords

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

Access to Document

10.1007/s10957-022-02153-5

Cite this

@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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

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

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

DIEF, University of Florence

DIEF, University of Florence

Cite this

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Research output

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

Projects

Complexity in nonlinear optimization

ADALGOPT: ADALGOPT - Advanced algorithms in nonlinear optimization

Activities

DIEF, University of Florence

DIEF, University of Florence

Cite this