Complexity and global rates of trust-region methods based on probabilistic models. (18th August 2017)

• Record Type: Journal Article
• Authors: Gratton, Serge; Royer, Clément W; Vicente, Luís N; Zhang, Zaikun
• Is Part Of: IMA journal of numerical analysis. Volume 38:Number 3(2018)
• Page Start: 1579
• Page End: 1597
• Publication Date: 2017-08-18
• Subjects: trust-region methods -- worst-case complexity -- probabilistic models; Numerical analysis -- Periodicals; 519.405
• DOI: 10.1093/imanum/drx043
• Languages: English
• ISSNs: 0272-4979

Abstract

Abstract: Trust-region algorithms have been proved to globally converge with probability 1 when the accuracy of the trust-region models is imposed with a certain probability conditioning on the iteration history. In this article, we study the complexity of such methods, providing global rates and worst-case complexity bounds on the number of iterations (with overwhelmingly high probability), for both first- and second-order measures of optimality. Such results are essentially the same as the ones known for trust-region methods based on deterministic models. The derivation of the global rates and worst-case complexity bounds follows closely from a study of direct search methods based on the companion notion of probabilistic descent.