### Abstract

Original language | English |
---|---|

Publisher | Arxiv |

Number of pages | 19 |

Volume | 1902.10406 |

Publication status | Published - Feb 2019 |

### Fingerprint

### Keywords

- evaluation complexity
- nonsmooth problems
- nonconvex optimization
- inexact evaluations
- composite functions

### Cite this

}

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

Research output: Working paper

TY - UNPB

T1 - Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

AU - Gratton, Serge

AU - Simon, Ehouarn

AU - Toint, Philippe

PY - 2019/2

Y1 - 2019/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 - Working paper

VL - 1902.10406

BT - Minimization of nonsmooth nonconvex functions using inexact evaluations and its worst-case complexity

PB - Arxiv

ER -