Strong Evaluation Complexity of An Inexact Trust-Region Algorithm for Arbitrary-Order Unconstrained Nonconvex Optimization

Abstract

A trust-region algorithm using inexact function and derivatives values is introduced for solving unconstrained smooth optimization problems. This algorithm uses high-order Taylor models and allows the search of strong approximate minimizers of arbitrary order. The evaluation complexity of finding a $q$-th approximate minimizer using this algorithm is then shown, under standard conditions, to be $\mathcal{O}\left({\min }_{j\in \{1,\dots ,q\}}{\epsilon }_j^{-(q+1)}\right)$ where the ${\epsilon }_j$ are the order-dependent requested accuracy thresholds. Remarkably, this order is identical to that of classical trust-region methods using exact information.