On high-order multilevel optimization strategies

We propose a new family of multilevel methods for unconstrained minimization. The resulting strategies are multilevel extensions of high-order optimization methods based on qth-order Taylor models (with q \geq 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.