### 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

*Mathematical Programming*,

*to appear*.

}

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

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 -