期刊
JOURNAL OF COMPLEXITY
卷 28, 期 1, 页码 93-108出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jco.2011.06.001
关键词
Evaluation complexity; Worst-case analysis; Nonconvex optimization; Second-order optimality conditions
资金
- EPSRC [EP/E053351/1]
- Royal Society [14265]
- EPSRC [EP/I013067/1, EP/E053351/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/E053351/1, EP/I013067/1] Funding Source: researchfish
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 0(epsilon(-3)) iterations may have to be performed for finding an iterate which is within E 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. (C) 2011 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据