Abstract
In this paper, we consider the issue of computing negative curvature directions, for nonconvex functions, within Newton–Krylov methods for large scale unconstrained optimization. This issue has been widely investigated in the literature, and different approaches have been proposed. We focus on the well known SYMMBK method proposed for solving large scale symmetric possibly indefinite linear systems [3, 5, 7, 20], and show how to exploit it to yield an effective negative curvature direction. The distinguishing feature of our proposal is that the computation of such negative curvature direction is iteratively carried out, without storing no more than a couple of additional vectors. The results of a preliminary numerical experience are reported showing the reliability of the novel approach we propose.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Avelino, C.P., Moguerza, J.M., Olivares, A., Prieto, F.J.: Combining and scaling descent and negative curvature directions. Math. Program. 128, 285–319 (2011)
Bray, A.J., Dean, D.S.: Statistics of critical points of Gaussian fields on large-dimensional spaces. Phys. Rev. Lett. 98(15), 150201 (2007)
Bunch, J., Kaufman, L.: Some stable methods for calculating inertia and solving symmetric linear equations. Math. Comput. 31, 163–179 (1977)
Caliciotti, A., Fasano, G., Potra, F., Roma, M.: Issues on the use of a modified Bunch and Kaufman decomposition for large scale Newton’s equation. Comput. Optim. Appl. 77, 627–651 (2020)
Chandra, R.: Conjugate gradient methods for partial differential equations. Ph.D. thesis, Yale University, New Haven (1978). Research report 129
Choromanska, A., Henaff, M., Mathieu, M., Arous, G.B., LeCun, Y.: The loss surfaces of multilayer networks. In: Artificial Intelligence and Statistics, pp. 192–204. PMLR (2015)
Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods. In: MPS-SIAM Series on Optimization, Philadelphia, PA (2000)
Curtis, F.E., Robinson, D.P.: Exploiting negative curvature in deterministic and stochastic optimization. Math. Program. 176, 69–94 (2019)
Dauphin, Y.N., Pascanu, R., Gulcehre, C., Cho, K., Ganguli, S., Bengio, Y.: Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. Adv. Neural Inf. Process. Syst. 27 (2014)
Dembo, R., Eisenstat, S., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400–408 (1982)
Dembo, R., Steihaug, T.: Truncated-Newton algorithms for large-scale unconstrained optimization. Math. Program. 26, 190–212 (1983)
Fasano, G.: Planar-conjugate gradient algorithm for large-scale unconstrained optimization, part 1: theory. J. Optim. Theory Appl. 125, 523–541 (2005)
Fasano, G.: Planar-conjugate gradient algorithm for large-scale unconstrained optimization, part 2: application. J. Optim. Theory Appl. 125, 543–558 (2005)
Fasano, G., Lucidi, S.: A nonmonotone truncated Newton–Krylov method exploiting negative curvature directions, for large scale unconstrained optimization. Optim. Lett. 3, 521–535 (2009)
Fasano, G., Piermarini, C., Roma, M.: Bridging the gap between trust-region methods (TRMs) and linesearch based methods (LBMs) for nonlinear programming: quadratic sub-problems. Department of Management, Università Ca’Foscari Venezia Working Paper (8) (2022)
Fasano, G., Roma, M.: Iterative computation of negative curvature directions in large scale optimization. Comput. Optim. Appl. 38, 81–104 (2007)
Ferris, M., Lucidi, S., Roma, M.: Nonmonotone curvilinear linesearch methods for unconstrained optimization. Comput. Optim. Appl. 6, 117–136 (1996)
Gould, N.I.M., Lucidi, S., Roma, M., Toint, P.L.: Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optim. Methods Softw. 14, 75–98 (2000)
Gould, N.I.M., Orban, D., Toint, P.L.: CUTEst: a constrained and unconstrained testing environment with safe threads. Comput. Optim. Appl. 60, 545–557 (2015)
HSL 2013: a collection of Fortran codes for large scale scientific computation. http://www.hsl.rl.ac.uk/
Lucidi, S., Rochetich, F., Roma, M.: Curvilinear stabilization techniques for truncated Newton methods in large scale unconstrained optimization. SIAM J. Optim. 8, 916–939 (1998)
McCormick, G.: A modification of Armijo’s step-size rule for negative curvature. Math. Program. 13, 111–115 (1977)
Moré, J., Sorensen, D.: On the use of directions of negative curvature in a modified Newton method. Math. Program. 16, 1–20 (1979)
Nash, S.: A survey of truncated-Newton methods. J. Comput. Appl. Math. 124, 45–59 (2000)
Olivares, A., Moguerza, J.M., Prieto, F.J.: Nonconvex optimization using negative curvature within a modified linesearch. Eur. J. Oper. Res. 189, 706–722 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Fasano, G., Piermarini, C., Roma, M. (2024). On the Use of the SYMMBK Algorithm for Computing Negative Curvature Directions Within Newton–Krylov Methods. In: Bruglieri, M., Festa, P., Macrina, G., Pisacane, O. (eds) Optimization in Green Sustainability and Ecological Transition. ODS 2023. AIRO Springer Series, vol 12. Springer, Cham. https://doi.org/10.1007/978-3-031-47686-0_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-47686-0_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-47685-3
Online ISBN: 978-3-031-47686-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)