Résumé
| langue originale | Anglais |
|---|---|
| Nombre de pages | 19 |
| journal | Mathematical Programming |
| Volume | to appear |
| état | Accepté/sous presse - 2 janv. 2020 |
Empreinte digitale
Citer ceci
}
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 revue › Article
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 -