非精确牛顿法在自适应三次正则化牛顿方法中的应用
Application of Inexact Newton Method in Adaptive Third-Order Regularized Newton Method
摘要: 本文基于自适应三次正则化牛顿方法提出了非精确牛顿法自适应三次正则化牛顿方法，并且通过数值实验验证了该方法的单调性和收敛性。本文给出了3种算法。本文使用不同的非精确求解器来求解子优化问题，并且通过数值实验对比了在不同绝对截断误差和不同相对截断误差下非精确求解与精确求解的收敛情况。数值实验结果表明，在绝对截断误差过大时，会导致算法收敛速度变慢，随着绝对截断误差的减少算法的收敛速度逐渐加快。相对截断误差过大时也会出现收敛速度较慢的情况。此外，不同的非精确求解器在数值实验中在算法1上表现差异不大，但在算法2和算法3中却差异较为明显。
Abstract: In this paper, based on the adaptive cubic regularized Newton method, an inexact adaptive cubic regularized Newton method is proposed, and the monotonicity and convergence of the method are verified by numerical experiments. Three algorithms are given in this paper. In this paper, different imprecise solvers are used to solve sub-optimization problems, and the convergence of imprecise solutions and exact solutions under different absolute and relative truncation errors is compared by numerical experiments. The numerical results show that when the absolute truncation error is too large, the convergence rate of the algorithm will slow down, and the convergence rate of the algorithm will gradually accelerate with the reduction of the absolute truncation error. When the relative truncation error is too large, the convergence speed will be slow. In addition, different imprecise solvers show little difference in algorithm 1 in numerical experiments, but the difference is obvious in algorithm 2 and algorithm 3.
文章引用：张林, 何清龙, 张海芳. 非精确牛顿法在自适应三次正则化牛顿方法中的应用[J]. 运筹与模糊学, 2023, 13(6): 6441-6449. https://doi.org/10.12677/ORF.2023.136634

参考文献

[1] Bottou, L., Curtis, F.E., and Nocedal, J. (2018) Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60, 223-311. [Google Scholar] [CrossRef] 
[2] Gower, R.M., Loizou, N., Qian, X., Sail-anbayev, A., Shulgin, E., and Richtárik, P. (2019) SGD: General Analysis and Improved Rates. Proceedings of the 36th International Conference on Machine Learning, Volume 97, Long Beach, 9-15 June 2019, 5200-5209.
[3] Mishchenko, K., Khaled, A. and Richtárik, P. (2020) Random Reshuffling: Simple Analysis with Vast Improvements. Advances in Neural Information Processing Systems, 33, 17309-17320.
[4] Levenberg, K. (1944) A Method for the Solution of Certain Problems in Least Squares. Quarterly of Applied Mathematics, 2,164-168. [Google Scholar] [CrossRef] 
[5] Marquardt, D. (1963) An Algorithm for Least-Squares Estimation of Nonlinear Parameters. SIAM Journal on Applied Mathematics, 11, 431-441. [Google Scholar] [CrossRef] 
[6] Grippo, L., Lampariello, F. and Luclidi, S. (1986) A Nonmonotone Line Search Technique for Newton’s Method. SIAM Journal on Numerical Analysis, 23, 707-716. [Google Scholar] [CrossRef] 
[7] Conn, A.B., Gould, N.I.M. and Toint, P.L. (2000) Trust Region Methods. SIAM, Philadelphia. [Google Scholar] [CrossRef] 
[8] Carmon, Y. and Duchi, J.C. (2016) Gradient Descent Effi-ciently Finds the Cubic-Regularized Non-Convex Newton Step. arXiv: 1803.09357.
[9] Richtárik, P. and Doikov, N. (2018) Randomized Block Cubic Newton Method. arXiv Preprint: 1802.04084.
[10] Song, C. and Liu, J. (2019) Inexact Proximal Cubic Regularized Newton Methods for Convex Optimization. arXiv Preprint: 1902.02388.
[11] Xu, P., Roosta-Khorasani, F. and Mahoney, M.W. (2017) Newton-Type Methods for Non-Convex Optimization under Inexact Hessian Information. arXiv: 1708.07164.
[12] Kohler, J.M. and Lucchi, A. (2017) Sub-Sampled Cubic Regularization for Non-Convex Optimization. Proceedings of the 34th International Conference on Machine Learning (ICML), Volume 70, Naha, 16-18 April 2019, 1895-1904.
[13] Wang, Z., Zhou, Y., Liang, Y. and Lan, G. (2019) Sample Complexity of Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), Volume 33, Sydney, 6-11 August 2017, 1440-1462.
[14] Mishchenko, K. (2023) Regularized Newton Method with Global O(1/k2) Convergence. arXiv: 2112.02089.
[15] Wright, S.J. (1999) Numerical Optimization. Springer Science & Business Media, Berlin.

为你推荐