کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4608946 | 1338392 | 2012 | 16 صفحه PDF | دانلود رایگان |
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)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.
► Worst-case evaluation bounds for finding unconstrained local minimizers are shown.
► Cubic regularization and trust-region techniques are analysed in this respect.
► Only one-dimensional global minimization is required in the respective subproblems.
► The bounds are sharp for cubic regularization and in some cases, for trust region.
► Cubic regularization’s complexity is always as good or better than trust region’s.
Journal: Journal of Complexity - Volume 28, Issue 1, February 2012, Pages 93–108