Email this article 
On the Redundancy of Hessian Non-Singularity for Linear Convergence Rate of the Newton Method Applied to the Minimization of Convex Functions
- Authors: Evtushenko Y.G.1,2, Tretyakov A.A.1,3
-
Affiliations:
- Information Science and Control Federal Research Center, Russian Academy of Sciences
- Moscow Institute of Physics and Technology
- Siedlce University
- Issue: Vol 64, No 4 (2024)
- Pages: 637-643
- Section: Optimal control
- URL: https://journals.rcsi.science/0044-4669/article/view/269968
- DOI: https://doi.org/10.31857/S0044466924040045
- EDN: https://elibrary.ru/ZKJRII
- ID: 269968
Cite item
Open Access
Access granted
Abstract
A new property of convex functions that makes it possible to achieve the linear rate of convergence of the Newton method during the minimization process is established. Namely, it is proved that, even in the case of singularity of the Hessian at the solution, the Newtonian system is solvable in the vicinity of the minimizer; i.e., the gradient of the objective function belongs to the image of the matrix of second derivatives and, therefore, analogs of the Newton method may be used.
Keywords
Full Text
About the authors
Yu. G. Evtushenko
Information Science and Control Federal Research Center, Russian Academy of Sciences; Moscow Institute of Physics and Technology
Author for correspondence.
Email: yuri-evtushenko@yandex.ru
Russian Federation, Moscow; Dolgoprudny
A. A. Tretyakov
Information Science and Control Federal Research Center, Russian Academy of Sciences; Siedlce University
Email: prof.tretyakov@gmail.com
Russian Federation, Moscow; Siedlce, Poland
References
- Бомадио Б., Лебедев К. А. Метод Ньютона для нахождения экстремумов сильно выпуклых функций // Международный научно-исследовательский журнал. 2015. Выпуск 6—2 (37). С. 11—14.
- Заботин В. И., Черняев Ю. А. Метод Ньютона для задачи минимизации выпуклой дважды гладкой функции на предвыпуклом множестве //Ж. вычисл. матем. и матем. физ. 2018. Т. 58. № 3. С. 340—345. doi: 10.7868/S0044466918030031.
- Budzko D., Cordero A., Torregrosa J. R. Modification of Newton’s Method to extend the convergence domain // SeMA Journal. 2014. Т. 66. № 1. С. 43—53. doi: 10.1007/s40324-014-0020-y.
- Nesterov Y. Accelerating the cubic regularization of Newton’s method on convex problems //Mathematical Programming. 2008. Т. 112. № 1. С. 159—181. doi: 10.1007/s10107—006—0089-x.
- Polyak B., Tremba A. New versions of Newton method: step-size choice, convergence domain and under-determined equations //Optimization Methods and Software. 2019. С. 1272—1303. doi: 10.1080/10556788.2019.1669154.
- Nesterov Y., Polyak B. T. Cubic regularization of Newton method and its global performance //Mathematical Programming. 2006. Т. 108. № 1. С. 177—205.
- Поляк Б. Т. Градиентные методы минимизации функционалов //Ж. вычисл. матем. и матем. физ. 1963. Т. 3. № 4. С. 643—653.
- Поляк Б. Т. Метод Ньютона и его роль в оптимизации и вычислительной математике //Труды Института системного анализа Российской академии наук. 2006. Т. 28. С. 44—62.
- Colding T. H., Minicozzi W. P. Lojasiewicz inequalities and applications //arXiv:1402.5087. 2014.
- Lojasiewicz S. Division d’une distribution par une fonction analytique de variables reelles //C. R. Acad. Sci. 1958. Т. 246. № 5. С. 683—686.
Supplementary files
