2024, issue 3, p. 12-24
Received 21.04.2024; Revised 20.05.2024; Accepted 10.09.2024
Published 24.09.2024; First Online 30.09.2024
https://doi.org/10.34229/2707-451X.24.3.2
A Combined Quasi-Newton-Type Method Using 4th-Order Directional Derivatives for Solving Degenerate Problems of Unconstrained Optimization
Viktor
Zadachyn 
Simon Kuznets Kharkiv National University of Economics, Ukraine
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Methods of unconstrained optimization play a significant role in machine learning [1–6]. When solving practical problems in machine learning, such as tuning nonlinear regression models, the extremum point of the chosen optimality criterion is often degenerate, which significantly complicates its search. Therefore, degenerate problems are the most challenging in optimization. Known numerical methods for solving the general unconstrained optimization problem, up to the second order, have very low convergence rates when solving degenerate problems [7, 8]. This is explained by the fact that for a significant improvement in convergence rate in this case, it is necessary to use higher-order derivatives in the method than the second order [10].
The purpose of the paper is to develop an efficient quasi-Newton method for solving degenerate unconstrained optimization problems, the idea of which (unlike regularization) involves dividing the entire space into the sum of two orthogonal subspaces. This idea was introduced in [23]. The space division at each iteration of the method is based on the spectral decomposition of the matrix approximating the Hessian of the objective function using the BFGS formula [3]. Each subspace exhibits its own behavior of the objective function, and therefore, an appropriate minimization method is applied on it.
Results. A combined quasi-Newton method is presented for solving degenerate unconstrained optimization problems, based on orthogonal decomposition of the Hessian approximation matrix and division of the entire space into the sum of two orthogonal subspaces. On one subspace (the kernel of the Hessian approximation matrix), a method is applied where derivatives in the direction of the 4th order are computed, while on the orthogonal complement to it, a quasi-Newtonian method is applied. A separate one-dimensional search is applied on each of these subspaces to determine the step multiplier in the respective direction.
The effectiveness of the presented combined method is confirmed by numerical experiments conducted on widely accepted test functions for unconstrained optimization problems. The proposed method allows obtaining fairly accurate solutions to test tasks in case of degeneracy of the minimum point with significantly lower computational costs for gradient calculations compared to optimization procedures of well-known mathematical packages.
Conclusions. The idea of dividing the entire space into the sum of two (or possibly more) orthogonal subspaces when solving complex optimization problems is quite promising in terms of applying a combination of different numerical methods on separate subspaces.
In the future, it is planned to conduct theoretical research on the convergence rate of the presented combined method in solving degenerate unconstrained optimization problems.
Keywords: unconstrained optimization, quasi-Newton methods, degenerate minimum point, spectral matrix decomposition, Machine Learning.
Cite as: Zadachyn V. A Combined Quasi-Newton-Type Method Using 4th-Order Directional Derivatives for Solving Degenerate Problems of Unconstrained Optimization. Cybernetics and Computer Technologies. 2024. 3. P. 12–24. https://doi.org/10.34229/2707-451X.24.3.2
References
1. Ring W. Optimization methods on Riemannian manifolds and their application to shape space. SIAM Journal on Optimization. 2012. 22 (2). P. 596–627. https://doi.org/10.1137/11082885X
2. Maratos N.G. Some results on the Sign recurrent neural network for unconstrained minimization. Neurocomputing. 2017. 287. P. 1–21. https://doi.org/10.1016/j.neucom.2017.09.036
3. Tirer T., Bruna J. Extended Unconstrained Features Model for Exploring Deep Neural Collapse. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research. 2012. 162: 21478–21505. Available from https://proceedings.mlr.press/v162/tirer22a.html
4. Wang Z., Li P., Li X., Pham H. A Modified Three-Term Type CD Conjugate Gradient Algorithm for Unconstrained Optimization Problems. Mathematical Problems in Engineering. 2020. P. 1–14. (Machine Learning and its Applications in Image Restoration) https://doi.org/10.1155/2020/4381515
5. Berahas A.S., Jahani M., Richtárik P., Takáč M. Quasi-Newton methods for machine learning: forget the past, just sample. Optimization Methods and Software. 2022. 37 (5). P. 1668–1704. https://doi.org/10.1080/10556788.2021.1977806
6. Kingma D.P., Ba J. Adam: A Method for Stochastic Optimization. 2014. https://arxiv.org/abs/1412.6980
7. Avriel M. Nonlinear Programming: Analysis and Methods. Dover Publishing. 2003.
8. Nocedal J., Wright S.J. Numerical Optimization. New York: Springer. 2006.
9. Liu D.C., Nocedal J. On the Limited Memory Method for Large Scale Optimization. Mathematical Programming. 1989. 45 (3). P. 503–528. https://doi.org/10.1007/BF01589116
10. Birgin E.G., Gardenghi J.L., Martínez J.M., Santos S.A. On the use of third-order models with fourth-order regularization for unconstrained optimization. Optimization Letters. 2020. 14. P. 815–838. https://doi.org/10.1007/s11590-019-01395-z
11. Li D.H., Fukushima M., Qi L., Yamashita N. Regularized newton methods for convex minimization problems with singular solutions. Comput. Optim. Appl. 2004. 28. P. 131–147. https://doi.org/10.1023/B:COAP.0000026881.96694.32
12. Shen C., Chen X., Liang Y. A regularized Newton method for degenerate unconstrained optimization problems. Optimization Letters. 2012. 6. P. 1913–1933. https://doi.org/10.1007/s11590-011-0386-z
13. Graspa T. N. A modified Newton direction for unconstrained optimization. Optimization. 2014. 63 (7). P. 983–1004. https://doi.org/10.1080/02331934.2012.696115
14. Taheri S., Mammadov M., Seifollahi S. Globally convergent algorithms for solving unconstrained optimization problems. Optimization. 2015. 64 (2). P. 249–263. https://doi.org/10.1080/02331934.2012.745529
15. Li X., Wang B., Hu W. A modified nonmonotone BFGS algorithm for unconstrained optimization. Journal of Inequalities and Applications. 2017. 183. https://doi.org/10.1186/s13660-017-1453-5
16. Ghazali K., Sulaiman J., Dasril Y., Gabda D. Newton-SOR Iteration for Solving Large-Scale Unconstrained Optimization Problems with an Arrowhead Hessian Matrices. Journal of Physics: Conference Series. 2019. 1358 (1). P. 1–10. https://doi.org/10.1088/1742-6596/1358/1/012054
17. Niri T.D., Hosseini M.M., Heydari M. An efficient improvement of the Newton method for solving nonconvex optimization problems. Computational Methods for Differential Equations. 2019. 7 (1). P. 69–85.
18. Wang H., Qin M. A Regularized Newton Method with Correction for Unconstrained Nonconvex Optimization. Journal of Mathematics Research. 2015. 13 (2). P. 7–17. https://doi.org/10.5539/jmr.v7n2p7
19. Li Q. A Modified Fletcher-Reeves-Type Method for Nonsmooth Convex Minimization. Stat., Optim. Inf. Comput. 2014. 2. P. 200–210. https://doi.org/10.19139/soic.v2i3.64
20. Andrei N. A new accelerated diagonal quasi-Newton updating method with scaled forward finite differences directional derivative for unconstrained optimization. Optimization. 2021. 70 (2). P. 345–360. https://doi.org/10.1080/02331934.2020.1712391
21. Cartis C., Gould N.I.M., Toint Ph.L. A concise second-order complexity analysis for unconstrained optimization using high-order regularized models. Optimization Methods and Software. 2020. 35 (2). P. 243–256. https://doi.org/10.1080/10556788.2019.1678033
22. Yang Y. A robust BFGS algorithm for unconstrained nonlinear optimization problems. Optimization. 2024. 73 (3). P. 851–873. https://doi.org/10.1080/02331934.2022.2124869
23. Zadachyn V. M. Combined method for solving degenerate problems of unconditional optimization. Information processing systems. 2020. 1 (160). P. 52–58. (in Ukrainian) https://doi.org/10.30748/soi.2020.160.06
24. Zadachyn V.M. Higher-order Optimality Conditions for Degenerate Unconstrained Optimization Problems. Journal of Optimization, Differential Equations and Their Application. 2022. 30 (1). P. 88–97. https://doi.org/10.15421/142204
25. Zadachyn V.M. On the rate of convergence of the gradient method with a degenerate minimum. USSR Cybernetics (ISSN 0023-1274). 1989. 1. P. 99–101. (in Russian)
26. Andrei N. Collection of 75 Unconstrained Optimization Test Functions. Research Institute for Informatics, Technical Report. 2018. 6. P. 1–9.
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)