Concise complexity analyses for trust region methods

DOI10.1007/S11590-018-1286-2zbMATH Open1412.90139arXiv1802.07843OpenAlexW2962881194MaRDI QIDQ1634776FDOQ1634776

Authors: Frank E. Curtis, Zachary Lubberts, Daniel P. Robinson 

Publication date: 18 December 2018

Published in: Optimization Letters (Search for Journal in Brave)

Abstract: Concise complexity analyses are presented for simple trust region algorithms for solving unconstrained optimization problems. In contrast to a traditional trust region algorithm, the algorithms considered in this paper require certain control over the choice of trust region radius after any successful iteration. The analyses highlight the essential algorithm components required to obtain certain complexity bounds. In addition, a new update strategy for the trust region radius is proposed that offers a second-order complexity bound.

Full work available at URL: https://arxiv.org/abs/1802.07843

Recommendations

• Convergence analysis of adaptive trust region methods
• scientific article; zbMATH DE number 1131709
• On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization
• Recent advances in trust region algorithms
• Complexity and global rates of trust-region methods based on probabilistic models

zbMATH Keywords

nonconvex optimizationglobal convergencenonlinear optimizationunconstrained optimizationtrust region methodsworst-case iteration complexityworst-case evaluation complexity

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Cites Work

• Title not available (Why is that?)
• Trust Region Methods
• Nonlinear stepsize control, trust regions and regularizations for unconstrained optimization
• Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
• On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization
• Nonlinear stepsize control algorithms: complexity bounds for first- and second-order optimality
• A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization

Cited In (13)

• Title not available (Why is that?)
• Analysis of inexact trust-region SQP algorithms
• Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
• Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
• Regional complexity analysis of algorithms for nonconvex smooth optimization
• Complexity and global rates of trust-region methods based on probabilistic models
• Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization
• Title not available (Why is that?)
• Convergence and evaluation-complexity analysis of a regularized tensor-Newton method for solving nonlinear least-squares problems
• The effect of smooth parametrizations on nonconvex optimization landscapes
• Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy
• An active set trust-region method for bound-constrained optimization
• A proximal quasi-Newton trust-region method for nonsmooth regularized optimization

This page was built for publication: Concise complexity analyses for trust region methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1634776)