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

• 成果类型: Article
• 署名作者: Gratton, S.; Simon, E.; Toint, Ph L.
• 署名单位: Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP); Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National Polytechnique de Toulouse; University of Namur
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01466-5
• 发表日期: 2021
• 页码: 1-24
• 关键词: Optimization; shrinkage; composite

摘要

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(similar to)| similar to-2) evaluations of the problem's functions and their derivatives for finding an similar to-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(similar to)| of the optimal bound known for smooth and nonsmooth nonconvex minimization with exact evaluations. A practically more restrictive variant of the algorithmwithworst-case complexity O(| log(similar to)|+ similar to-2) is also presented.