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

Research output: Contribution to journalArticle

### 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.
Original language English 19 Mathematical Programming to appear Accepted/In press - 2 Jan 2020

### Fingerprint

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

### Keywords

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

### Cite this

@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",

}

In: Mathematical Programming, Vol. to appear, 02.01.2020.

Research output: Contribution to journalArticle

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 -