Complexity bounds for second-order optimality in unconstrained optimization |
| |
Authors: | C Cartis NIM Gould |
| |
Institution: | a School of Mathematics, University of Edinburgh, The King’s Buildings, Edinburgh, EH9 3JZ, Scotland, UKb Computational Science and Engineering Department, Rutherford Appleton Laboratory, Chilton, Oxfordshire, OX11 0QX, England, UKc Namur Center for Complex Systems (naXys), FUNDP—University of Namur, 61, rue de Bruxelles, B-5000 Namur, Belgium |
| |
Abstract: | This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) 15] and Cartis et al. (2010) 3] show that at most O(?−3) iterations may have to be performed for finding an iterate which is within ? of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm, which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods. |
| |
Keywords: | Evaluation complexity Worst-case analysis Nonconvex optimization Second-order optimality conditions |
本文献已被 ScienceDirect 等数据库收录! |
|