2019/02/27 by Serge Gratton, Gratton, S., Ehouarn Simon +3
Engineering · Mathematics · #49K10 #49M37 #65K05 #68T05 #68W40 #Advanced Optimization Algorithms Research #F.1.3 #F.2.1 #FOS: Mathematics #G.1.6 #I.2.6 #Numerical methods in inverse problems #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1902.10406
openalex publication_date 2019/02/27 · openalex created_date 2019/05/03 · openalex updated_date 2026/07/28
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, Gurioli, Morini and Toint, 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.