Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

• 成果类型: Article
• 署名作者: Birgin, E. G.; Gardenghi, J. L.; Martinez, J. M.; Santos, S. A.; Toint, Ph. L.
• 署名单位: Universidade de Sao Paulo; Universidade Estadual de Campinas; University of Namur; University of Namur
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1065-8
• 发表日期: 2017
• 页码: 359-368
• 关键词: cubic regularization; global performance; algorithm

摘要

The worst-case evaluation complexity for smooth (possibly nonconvex) unconstrained optimization is considered. It is shown that, if one is willing to use derivatives of the objective function up to order p (for p >= 1) and to assume Lipschitz continuity of the p-th derivative, then an epsilon-approximate first-order critical point can be computed in at most O(epsilon -((p+1)/p)) evaluations of the problem's objective function and its derivatives. This generalizes and subsumes results known for p = 1 and p = 2.