CS seminar - Youssef Diouane - A line-search algorithm inspired by the adaptive cubic regularization framework

CS seminar series presents

A line-search algorithm inspired by the adaptive cubic regularization framework, with a worst-case complexity O(\epsilon^{-3/2})

by Youssef Diouane, Associate Professor at Institut Supérieur de l’Aéronautique et de l’Espace (ISAE-SUPAERO)

Thursday, June 8 at 14:00 in 205


We consider solving unconstrained optimization problems by means of two popular globalization techniques: trust-region (TR) algorithms and adaptive regularized framework using cubics (ARC). Both techniques require the solution of a so-called “subproblem' in which a trial step is computed by solving an optimization problem involving an approximation of the objective function, called “the model". The latter is supposed to be adequate in a neighborhood of the current iterate. In this work, we address an important practical question related with the choice of the norm for defining the neighborhood. Given a symmetric positive definite matrix M that satisfies a specific secant equation, we propose the use of the M-scaled norm -- defined by ‖x‖M=xTMx‾‾‾‾‾‾√ for all x∈ℝn -- in both TR and ARC techniques. We show that the use of this norm induces remarkable relations between the trial step of both methods that can be used to obtain efficient practical algorithms. Using the M-scaled norm we propose a possible way to derive line-search algorithms enjoying the same worst case complexity as the ARC algorithms. The good potential of the proposed algorithms is illustrated on a set of numerical experiments.