An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

Serge Gratton; Ehouarn Simon; Philippe Toint

doi:10.1007/s10107-020-01466-5

An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

Serge Gratton, Ehouarn Simon, Philippe Toint

Namur Institute for Complex Systems

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

26 Downloads (Pure)

Abstract

An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(ϵ)|ϵ-2) evaluations of the problem’s functions and their derivatives for finding an ϵ-approximate first-order stationary point. This complexity bound therefore generalizes that provided by Bellavia et al. (Theoretical study of an adaptive cubic regularization method with dynamic inexact Hessian information. arXiv:1808.06239, 2018) for inexact methods for smooth nonconvex problems, and is within a factor | log (ϵ) | of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(| log (ϵ) | + ϵ ^{- 2}) is also presented.

Original language	English
Pages (from-to)	1-24
Number of pages	19
Journal	Mathematical Programming
Volume	187
Issue number	1-2
DOIs	https://doi.org/10.1007/s10107-020-01466-5
Publication status	Published - 21 Jan 2020

Keywords

evaluation complexity
nonsmooth problems
nonconvex optimization
inexact evaluations
composite functions
Evaluation complexity
Nonconvex optimization
Composite functions
Nonsmooth problems
Inexact evaluations

Access to Document

10.1007/s10107-020-01466-5

2020_GrattonToint_articleAccepted author manuscript, 234 KB

Cite this

@article{d59b8e03b88447b1a189a2d42aacf1a8,

title = "An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity",

abstract = "An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(ϵ)|ϵ-2) evaluations of the problem{\textquoteright}s functions and their derivatives for finding an ϵ-approximate first-order stationary point. This complexity bound therefore generalizes that provided by Bellavia et al. (Theoretical study of an adaptive cubic regularization method with dynamic inexact Hessian information. arXiv:1808.06239, 2018) for inexact methods for smooth nonconvex problems, and is within a factor | log (ϵ) | of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(| log (ϵ) | + ϵ - 2) is also presented. ",

keywords = "evaluation complexity, nonsmooth problems, nonconvex optimization, inexact evaluations, composite functions, Evaluation complexity, Nonconvex optimization, Composite functions, Nonsmooth problems, Inexact evaluations",

author = "Serge Gratton and Ehouarn Simon and Philippe Toint",

note = "Funding Information: Ph. L. Toint: Partially supported by ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02. Funding Information: Funding was provided by Agence Nationale de Recherche (FR) (Grant No. ANR-11-LABX-0040-CIMI). Acknowledgements Publisher Copyright: {\textcopyright} 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society. Copyright: Copyright 2020 Elsevier B.V., All rights reserved. Funding Information: The third author is grateful to the ENSEEIHT (INP, Toulouse) for providing a friendly research environment for the duration of this research project. Funding Information: Funding was provided by Agence Nationale de Recherche (FR) (Grant No. ANR-11-LABX-0040-CIMI). Publisher Copyright: {\textcopyright} 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.",

year = "2020",

month = jan,

day = "21",

doi = "10.1007/s10107-020-01466-5",

language = "English",

volume = "187",

pages = "1--24",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-2",

}

TY - JOUR

T1 - An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

AU - Gratton, Serge

AU - Simon, Ehouarn

AU - Toint, Philippe

N1 - Funding Information: Ph. L. Toint: Partially supported by ANR-11-LABX-0040-CIMI within the program ANR-11-IDEX-0002-02. Funding Information: Funding was provided by Agence Nationale de Recherche (FR) (Grant No. ANR-11-LABX-0040-CIMI). Acknowledgements Publisher Copyright: © 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society. Copyright: Copyright 2020 Elsevier B.V., All rights reserved. Funding Information: The third author is grateful to the ENSEEIHT (INP, Toulouse) for providing a friendly research environment for the duration of this research project. Funding Information: Funding was provided by Agence Nationale de Recherche (FR) (Grant No. ANR-11-LABX-0040-CIMI). Publisher Copyright: © 2020, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2020/1/21

Y1 - 2020/1/21

N2 - An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(ϵ)|ϵ-2) evaluations of the problem’s functions and their derivatives for finding an ϵ-approximate first-order stationary point. This complexity bound therefore generalizes that provided by Bellavia et al. (Theoretical study of an adaptive cubic regularization method with dynamic inexact Hessian information. arXiv:1808.06239, 2018) for inexact methods for smooth nonconvex problems, and is within a factor | log (ϵ) | of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(| log (ϵ) | + ϵ - 2) is also presented.

AB - An adaptive regularization algorithm using inexact function and derivatives evaluations is proposed for the solution of composite nonsmooth nonconvex optimization. It is shown that this algorithm needs at most O(|log(ϵ)|ϵ-2) evaluations of the problem’s functions and their derivatives for finding an ϵ-approximate first-order stationary point. This complexity bound therefore generalizes that provided by Bellavia et al. (Theoretical study of an adaptive cubic regularization method with dynamic inexact Hessian information. arXiv:1808.06239, 2018) for inexact methods for smooth nonconvex problems, and is within a factor | log (ϵ) | of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithm with worst-case complexity O(| log (ϵ) | + ϵ - 2) is also presented.

KW - evaluation complexity

KW - nonsmooth problems

KW - nonconvex optimization

KW - inexact evaluations

KW - composite functions

KW - Evaluation complexity

KW - Nonconvex optimization

KW - Composite functions

KW - Nonsmooth problems

KW - Inexact evaluations

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

U2 - 10.1007/s10107-020-01466-5

DO - 10.1007/s10107-020-01466-5

M3 - Article

VL - 187

SP - 1

EP - 24

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -

An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Evaluation complexity of algorithms for nonconvex optimization

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

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Complexity in nonlinear optimization

Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

5th Conference on Numerical Analysis and Optimization

Cite this

An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Research output

Evaluation complexity of algorithms for nonconvex optimization

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

Adaptive regularization algorithms with inexact evaluations for nonconvex optimization

Projects

Complexity in nonlinear optimization

Activities

Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

5th Conference on Numerical Analysis and Optimization

Cite this