Nos partenaires



Accueil du site > Français > Evénements > Séminaires



L’IRIT étant localisé sur plusieurs sites, ses séminaires sont organisés et ont lieu soit à l’Université Toulouse 3 Paul Sabatier (UT3), l’Université Toulouse 1 Capitole (UT1), l’INP-ENSEEIHT ou l’Université Toulouse 2 Jean Jaurès (UT2J).


SPOT Seminar : Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization

Philippe TOINT - Université de Namur (Belgique)

Lundi 11 Mars 2019, 14h00 - 15h00
INP-ENSEEIHT, Salle des thèses
Version PDF :


We present a review of the results obtained during the last year on the worst-case complexity of minimization algorithm for nonconvex problems using potentially high-degree models. In the smooth (Lipschitz or Hölder) case, global complexity bound will be presented that are valid for any model's degree and any order of optimality, thereby generalizing all known results for first- and second-order methods. The bound states that 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. Moreover, these results are shown to be sharp. We will also show how to extend these optimal-complexity results to the case where the problem's objective function and derivatives are computed inexactly, yielding a bound of O(|log(epsilon)|epsilon^{(p+1)/(p-q+1)}) approximate evaluations. Co-authored with C. Cartis, N. Gould, S. Bellavia, G. Gurioli, B. Morini