Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity
Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity
复制标题
DOI：
10.1007/s10107-009-0337-y
复制
发表时间：
2011-12-01
影响因子：
2.7
通讯作者：
Toint, Philippe L.
中科院分区：
文献类型：
--
作者：
Cartis, Coralia;Gould, Nicholas I. M.;Toint, Philippe L.
使用 Cubics (ARC) 的自适应正则化框架在 Cartis、Gould 和 Toint（第一部分，数学程序，doi:10.1007/s10107-009-0286-5, 2009）中被提出用于无约束优化并进行了分析，同时概括了 Griewank 未发表的方法（技术报告 NA/12, 1981, DAMTP, 大学） Cambridge），Nesterov 和 Polyak 的算法（Math Program 108(1):177-205, 2006）以及 Weiser、Deuflhard 和 Erdmann 的提议（OptimMethods Softw 22(3):413-431, 2007）。在这篇配套论文中，我们通过提供 ARC 和二阶变体的最坏情况全局迭代复杂性界限来进一步分析，以实现近似一阶和后者二阶迭代的关键性。特别是，二阶 ARC 算法最多需要 O(epsilon(-3/2)) 次迭代，或者等效地，函数和梯度评估，以将目标的梯度范数驱动到低于所需精度 epsilon 和 O(epsilon(-3)) 次迭代，从而在子空间中达到近似非负曲率。这些边界的阶数与 Nesterov 和 Polyak 的算法 3.3 证明的阶数相匹配，算法 3.3 在每次迭代中全局最小化三次模型。我们的方法更通用，因为它只允许近似求解三次模型，并且可以采用近似 Hessian 矩阵。
An Adaptive Regularisation framework using Cubics (ARC) was proposed for unconstrained optimization and analysed in Cartis, Gould and Toint (Part I, Math Program, doi:10.1007/s10107-009-0286-5, 2009), generalizing at the same time an unpublished method due to Griewank (Technical Report NA/12, 1981, DAMTP, University of Cambridge), an algorithm by Nesterov and Polyak (Math Program 108(1):177-205, 2006) and a proposal by Weiser, Deuflhard and Erdmann (Optim Methods Softw 22(3):413-431, 2007). In this companion paper, we further the analysis by providing worst-case global iteration complexity bounds for ARC and a second-order variant to achieve approximate first-order, and for the latter second-order, criticality of the iterates. In particular, the second-order ARC algorithm requires at most O(epsilon(-3/2)) iterations, or equivalently, function- and gradient-evaluations, to drive the norm of the gradient of the objective below the desired accuracy epsilon and O(epsilon(-3)) iterations, to reach approximate nonnegative curvature in a subspace. The orders of these bounds match those proved for Algorithm 3.3 of Nesterov and Polyak which minimizes the cubic model globally on each iteration. Our approach is more general in that it allows the cubic model to be solved only approximately and may employ approximate Hessians.