Abstract:
We review the available results on the evaluation complexity of algorithms using Lipschitz-continuous Hessians for the approximate solution of nonlinear and potentially nonconvex optimization problems. Here, evaluation complexity is a bound on the largest number of problem functions (objective, constraints) and derivatives evaluations that are needed before an approximate first-order critical point of the problem is guaranteed to be found. We start by considering the unconstrained case and examine classical methods (such as Newton’s method) and the more recent ARC2 method, which we show is optimal under reasonable assumptions. We then turn to constrained problems and analyze the case of convex constraints first, showing that a suitable adaptation ARC2CC of the ARC2 approach also possesses remarkable complexity properties. We finally extend the results obtained in simpler settings to the general equality and inequality constrained nonlinear optimization problem by constructing a suitable ARC2GC algorithm whose evaluation complexity also exhibits the same remarkable properties.
Biography:
Philippe L. Toint (born 1952) received its degree in Mathematics in the University of Namur (Belgium) in 1974 and his Ph.D. in 1978 under the guidance of Prof M.J.D. Powell. He was appointed as lecturer at the University of Namur in 1979 were he became associate professor in 1987 and full-professor in 1993. Since 1979, he has been the co-director of the Numerical Analysis Unit and director of the Transportation Research Group in this department. He was in charge of the University Computer Services from 1998 to 2000 and director of the Department of Mathematics from 2006 to 2009. He currently serves as Vice-rector for Research and IT for the university. His research interests include numerical optimization, numerical analysis and transportation research. He has published four books and more than 280 papers and technical reports. Elected as SIAM Fellow (2009), he was also awarded the Beale-Orchard-Hayes Prize (1994, with Conn and Gould)) and the Lagrange Prize in Continuous Optimization (2006, with Fletcher and Leyffer). He is the past Chairman (2010-2013) of the Mathematical Programming Society, the international scientific body gathering most researchers in mathematical optimization world-wide. Married and father of two girls, he is a keen music and poetry lover as well as an enthusiast scuba-diver.