  


A Trust Region Algorithm with a WorstCase Iteration Complexity of ${\cal O}(\epsilon^{3/2})$ for Nonconvex Optimization
Frank E. Curtis (frank.e.curtisgmail.com) Abstract: We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any $\bar\epsilon \in (0,\infty)$, the algorithm requires at most $\mathcal{O}(\epsilon^{3/2})$ iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any $\epsilon \in (0,\bar\epsilon]$. This improves upon the $\mathcal{O}(\epsilon^{2})$ bound known to hold for some other trust region algorithms and matches the $\mathcal{O}(\epsilon^{3/2})$ bound for the recently proposed Adaptive Regularisation framework using Cubics, also known as the arc algorithm. Our algorithm, entitled trace, follows a trust region framework, but employs modified step acceptance criteria and a novel trust region update mechanism that allow the algorithm to achieve such a worstcase global complexity bound. Importantly, we prove that our algorithm also attains global and fast local convergence guarantees under similar assumptions as for other trust region algorithms. We also prove a worstcase upper bound on the number of iterations, function evaluations, and derivative evaluations that the algorithm requires to obtain an approximate secondorder stationary point. Keywords: unconstrained optimization, nonlinear optimization, nonconvex optimization, trust region methods, global convergence, local convergence, worstcase iteration complexity, worstcase evaluation complexity Category 1: Nonlinear Optimization Category 2: Nonlinear Optimization (Unconstrained Optimization ) Citation: F. E. Curtis, D. P. Robinson, and M. Samadi. A Trust Region Algorithm with a WorstCase Iteration Complexity of $O(\epsilon^{3/2})$ for Nonconvex Optimization. Mathematical Programming, DOI: 10.1007/s1010701610262, 2016. Download: Entry Submitted: 10/21/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  