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

Résultats de recherche: Contribution à un journal/une revueArticle

3 Downloads (Pure)

Résumé

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(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| 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(epsilon)|+epsilon^{-2}) is also presented.
langue originaleAnglais
Nombre de pages19
journalMathematical Programming
Volumeto appear
étatAccepté/sous presse - 2 janv. 2020

Empreinte digitale

Derivatives
Evaluation
Adaptive algorithms
Nonconvex Minimization
Inexact Methods
Derivative
Nonsmooth Optimization
Optimal Bound
Nonconvex Optimization
Nonconvex Problems
Stationary point
Regularization
Composite materials
Composite
First-order
Generalise

Citer ceci

@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(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| 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(epsilon)|+epsilon^{-2}) is also presented.",
keywords = "evaluation complexity, nonsmooth problems, nonconvex optimization, inexact evaluations, composite functions",
author = "Serge Gratton and Ehouarn Simon and Philippe Toint",
year = "2020",
month = "1",
day = "2",
language = "English",
volume = "to appear",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",

}

An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity. / Gratton, Serge; Simon, Ehouarn; Toint, Philippe.

Dans: Mathematical Programming, Vol to appear, 02.01.2020.

Résultats de recherche: Contribution à un journal/une revueArticle

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

PY - 2020/1/2

Y1 - 2020/1/2

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(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| 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(epsilon)|+epsilon^{-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(epsilon)| epsilon^{-2}) evaluations of the problem's functions and their derivatives for finding an $\epsilon$-approximate first-order stationary point. This complexity bound therefore generalizes that provided by [Bellavia, Gurioli, Morini and Toint, 2018] for inexact methods for smooth nonconvex problems, and is within a factor |log(epsilon)| 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(epsilon)|+epsilon^{-2}) is also presented.

KW - evaluation complexity

KW - nonsmooth problems

KW - nonconvex optimization

KW - inexact evaluations

KW - composite functions

M3 - Article

VL - to appear

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -