OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

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

Gratton, Serge and Simon, Ehouarn and Toint, Philippe An algorithm for the minimization of nonsmooth and nonconvex functions using inexact evaluations and its worst-case complexity. (2020) Mathematical Programming, Series A. 1-23. ISSN 0025-5610

[img]
Preview
(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
459kB

Official URL: https://doi.org/10.1007/s10107-020-01466-5

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(ϵ)|ϵ−2) evaluations of the problem’s functions and their derivatives for finding an ϵ-approximate first-order stationary point. This complexity bound therefore generalizes that provided by Bellavia et al. (Theoretical study of an adaptive cubic regularization method with dynamic inexact Hessian information. arXiv:1808.06239, 2018) for inexact methods for smooth nonconvex problems, and is within a factor |log(ϵ)| 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(ϵ)|+ϵ−2) is also presented.

Item Type:Article
Additional Information:Thanks to Springer editor. The original PDF can be found at Mathematical Programming (ISSNs 0025-5610 ; 1436-4646) website : https://link.springer.com/article/10.1007/s10107-020-01466-5
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > Université de Namur - UNamur (BELGIQUE)
Laboratory name:
Funders:
ANR : Agence Nationale de la Recherche (France) - CIMI : Centre International de Mathématiques et d'Informatique de Toulouse (France)
Statistics:download
Deposited On:16 Sep 2020 14:48

Repository Staff Only: item control page