On High-Order Multilevel Optimization Strategies

Abstract

We propose a new family of multilevel methods for unconstrained minimization. The resulting strategies are multilevel extensions of high-order optimization methods based on q-th order Taylor models (with q>=1) that have been recently proposed in the literature. The use of high-order models, while decreasing the worst-case complexity bound, makes these methods computationally more expensive. Hence, to counteract this effect, we propose a multilevel strategy that exploits a hierarchy of problems of decreasing dimension, still approximating the original one, to reduce the global cost of the step computation. A theoretical analysis of the family of methods is proposed. Specifically, local and global convergence results are proved and a worst-case complexity bound to reach first-order stationary points is also derived. A multilevel version of the well-known adaptive regularization by cubics (corresponding to q= 2 in our setting) has been implemented, as well as a multilevel third-order method (q= 3). Numerical experiments clearly highlight the relevance of the new multilevel approaches leading to considerable computational savings compared to their one-level counterparts.