Complexity and global rates of trust-region methods based on probabilistic models

Serge Gratton, Clement W. Royer, Luís N. Vicente, Zaikun Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)


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- A nd 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.

Original languageEnglish
Pages (from-to)1579-1597
Number of pages19
JournalIMA Journal of Numerical Analysis
Issue number3
Publication statusPublished - 17 Jul 2018


  • probabilistic models
  • trust-region methods
  • worst-case complexity

ASJC Scopus subject areas

  • Mathematics(all)
  • Computational Mathematics
  • Applied Mathematics

Cite this