Abstract
| Original language | English |
|---|---|
| Number of pages | 19 |
| Journal | Mathematical Programming |
| Volume | to appear |
| Publication status | Accepted/In press - 2 Jan 2020 |
Fingerprint
Keywords
- evaluation complexity
- nonsmooth problems
- nonconvex optimization
- inexact evaluations
- composite functions
Cite this
}
An algorithm for the minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity. / Gratton, Serge; Simon, Ehouarn; Toint, Philippe.
In: Mathematical Programming, Vol. to appear, 02.01.2020.Research output: Contribution to journal › 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 -