Seminar @Dipartimento di Ingegneria Industriale
Room 108 – Plesso didattico Morgagni

Philippe Toint (University of Namur)

Complexity of nonconvex optimization

Abstract.
We present a review of results on the worst-case complexity of minimization algorithms for nonconvex problems using potentially high-degree models.
Global complexity bound are presented that are valid for any model’s degree and any order of optimality, thereby generalizing known results for first- and second-order methods. An adaptive regularization algorithm using derivatives up to degree p will produce an epsilon-approximate q-th order minimizer in at most O(epsilon^( -(p+1)/(p−q+1) ) evaluations. We will also extend these results to the case of inexact objective function and derivatives with an application to subsampling algorithms for machine learning.