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

2020/11/02 by Coralia Cartis, Nicholas I. M. Gould, Cartis, C. +3 · 1 citation
Computer Science · Engineering · Mathematics · #65Y20 #90C30 #90C60 #Advanced Optimization Algorithms Research #F.2.1 #FOS: Mathematics #G.1.6 #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2011.00854

openalex publication_date 2020/11/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 O(min_j∈\1,…,q\ε_j^-(q+1)) where the ε_j are the order-dependent requested accuracy thresholds. Remarkably, this order is identical to that of classical trust-region methods using exact information.

Cited by

• A Homogeneous Tensor Framework for High-Order Trust-Region and Spherical Polynomial Optimization

Related

• Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
• Concise Complexity Analyses for Trust-Region Methods
• Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization
• Complexity of a Class of First-Order Objective-Function-Free\n Optimization Algorithms
• Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques