Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results
Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results
复制标题
DOI：
10.1007/s10107-009-0286-5
复制
发表时间：
2011-04-01
影响因子：
2.7
通讯作者：
Toint, Philippe L.
中科院分区：
文献类型：
--
作者：
Cartis, Coralia;Gould, Nicholas I. M.;Toint, Philippe L.
提出了一种基于立方体的无约束优化自适应正则化算法（ARC），同时推广了Griewank （Technical Report NA/12, 1981， DAMTP, University of Cambridge）提出的一种未发表的方法、Nesterov和Polyak（数学程序108(1):177- 205,2006）提出的一种算法和Weiser等人（Optim Methods software 22(3):413-431, 2007）的一种算法。在我们的方法的每次迭代中，目标函数的局部三次正则化的近似全局最小值被确定，这确保了目标的显著改进，只要目标的Hessian是局部Lipschitz连续的。新方法使用了局部Lipschitz常数的自适应估计和对全局模型最小值的逼近，即使对于大规模问题也保持计算可行性。通过我们的ARC方法，我们证明了Nesterov和Polyak得到的优秀的全局和局部收敛性质是保留的，并且有时可以推广到更广泛的一类问题。基于CUTEr集的小规模测试问题的初步数值实验表明，与基本的信任域实现相比，ARC算法具有令人鼓舞的性能。
An Adaptive Regularisation algorithm using Cubics (ARC) is proposed for unconstrained optimization, 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 et al. (Optim Methods Softw 22(3):413-431, 2007). At each iteration of our approach, an approximate global minimizer of a local cubic regularisation of the objective function is determined, and this ensures a significant improvement in the objective so long as the Hessian of the objective is locally Lipschitz continuous. The new method uses an adaptive estimation of the local Lipschitz constant and approximations to the global model-minimizer which remain computationally-viable even for large-scale problems. We show that the excellent global and local convergence properties obtained by Nesterov and Polyak are retained, and sometimes extended to a wider class of problems, by our ARC approach. Preliminary numerical experiments with small-scale test problems from the CUTEr set show encouraging performance of the ARC algorithm when compared to a basic trust-region implementation.