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- 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 language | English |
---|---|
Pages (from-to) | 1579-1597 |
Number of pages | 19 |
Journal | IMA Journal of Numerical Analysis |
Volume | 38 |
Issue number | 3 |
DOIs | |
Publication status | Published - 17 Jul 2018 |
Keywords
- probabilistic models
- trust-region methods
- worst-case complexity
ASJC Scopus subject areas
- Mathematics(all)
- Computational Mathematics
- Applied Mathematics