×

zbMATH — the first resource for mathematics

Polarity and conjugacy for quadratic hypersurfaces: a unified framework with recent advances. (English) Zbl 1454.90086
Summary: We aim at completing the analysis in [the authors, J. Optim. Theory Appl. 175, No. 3, 764–794 (2017; Zbl 1387.90240)] for quadratic hypersurfaces, where the geometric viewpoint suggested by the Polarity theory is considered, in order to recast basic properties of the Conjugate Gradient (CG) method [M. R. Hestenes and E. Stiefel, J. Res. Natl. Bur. Stand. 49, 409–436 (1952; Zbl 0048.09901)]. Here, the focus is on possibly exploiting theoretical advances on nonconvex quadratic hypersurfaces, in order to address guidelines for efficient optimization methods converging to second order stationary points, in large scale settings. We first recall some results from [the authors, loc. cit.], in order to fully analyze the relationship between the CG and the Polarity theory. Then, we specifically address, from a different perspective, the geometric insight of the pivot breakdown, which might occur when solving a nonsingular indefinite Newton’s equation applying the CG. Furthermore, we fully exploit some novel theoretical advances of the Polarity theory on nonconvex quadratic hypersurfaces not considered in [the authors, loc. cit.]. Finally, we show that our approach describes a general framework, which also encompasses a class of CG-based methods, namely Planar CG-based methods. The framework we consider intends to emphasize a bridge between the geometry behind stationary points of nonconvex quadratic hypersurfaces and their efficient computation using Krylov-subspace methods.

MSC:
90C30 Nonlinear programming
90C52 Methods of reduced gradient type
65K05 Numerical mathematical programming methods
03H05 Nonstandard models in mathematics
65F05 Direct numerical methods for linear systems and matrix inversion
14P10 Semialgebraic sets and related spaces
14N05 Projective techniques in algebraic geometry
Software:
tn
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hestenes, M.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand., 49, 409-435 (1952) · Zbl 0048.09901
[2] Beltrametti, M.; Carletti, E.; Gallarati, D.; Monti Bragadin, G., Lectures on Curves, Surfaces and Projective Varieties - A Classical View of Algebraic Geometry (2009), European Mathematical Society · Zbl 1180.14001
[3] Casey, J., A Treatise on the Analytical Geometry of the Point, Line, Circle and Conic Sections (1885), Dublin University Press · JFM 17.0672.02
[4] Schreirer, O.; Sperner, E., Projective Geometry of \(n\) Dimensions (1961), Chelsea Publishing Company: Chelsea Publishing Company NY
[5] Fasano, G.; Pesenti, R., Conjugate direction methods and polarity for quadratic hypersurfaces, J. Optim. Theory Appl., 175, 3, 764-794 (2017) · Zbl 1387.90240
[6] Fasano, G., Conjugate Gradient (CG)-type method for the solution of Newton’s equation within optimization frameworks, Optim. Methods Softw., 19, 267-290 (2004) · Zbl 1141.90541
[7] Fasano, G., Planar-conjugate gradient algorithm for large scale unconstrained optimization, Part 1: Theory, J. Optim. Theory Appl., 125, 523-541 (2005) · Zbl 1079.90162
[8] Fasano, G., Planar-conjugate gradient algorithm for large scale unconstrained optimization, Part 2: Application, J. Optim. Theory Appl., 125, 543-558 (2005) · Zbl 1079.90163
[9] Curtis, F.; Robinson, D., Exploiting negative curvature in deterministic and stochastic optimization, Math. Program., 176, 69-94 (2019) · Zbl 1417.49036
[10] Jin, C.; Ge, R.; Netrapalli, P.; Kakade, S. M.; Jordan, M. I., How to escape saddle points efficiently, (Proceedings of the 34th International Conference on Machine Learning - Vol. 70, ICML’17 (2017), JMLR.org), 1724-1732
[11] Moré, J.; Sorensen, D., On the use of directions of negative curvature in a modified Newton method, Math. Program., 16, 1-20 (1979) · Zbl 0394.90093
[12] Fasano, G.; Roma, M., Iterative computation of negative curvature directions in large scale optimization, Comput. Optim. Appl., 38, 81-104 (2007) · Zbl 1171.90549
[13] De Leone, R.; Fasano, G.; Sergeyev, Y. D., Planar methods and grossone for the conjugate gradient breakdown in nonlinear programming, Comput. Optim. Appl., 71, 73-93 (2018) · Zbl 06946577
[14] Spong, M. W.; Hutchinson, S.; Vidyasagar, M., Robot Modeling and Control (2020), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. Hoboken, NJ
[15] Foley, J.; van Dam, A.; Feiner, S.; Hughes, J., Computer Graphics. Principles and Practice (1990), Addison-Wesley Publishing Company
[16] Dembo, R.; Eisenstat, S.; Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19, 400-408 (1982) · Zbl 0478.65030
[17] Nash, S., A survey of truncated-Newton methods, J. Comput. Appl. Math., 124, 45-59 (2000) · Zbl 0969.65054
[18] Caliciotti, A.; Fasano, G.; Nash, S.; Roma, M., An adaptive truncation criterion, for linesearch-based truncated Newton methods in large scale nonconvex optimization, Oper. Res. Lett., 46, 7-12 (2018) · Zbl 07064413
[19] Hestenes, M., Conjugate Direction Methods in Optimization (1980), Springer Verlag: Springer Verlag New York, Heidelberg, Berlin · Zbl 0439.49001
[20] Luenberger, D., Hyperbolic pairs in the method of conjugate gradients, SIAM J. Appl. Math., 17, 1263-1267 (1969) · Zbl 0187.09704
[21] Paige, C.; Saunders, M., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025
[22] Chandra, R., Conjugate Gradient Methods for Partial Differential EquationsResearch Report 129 (1978), Yale University: Yale University New Haven, (Ph.D. thesis)
[23] Bunch, J.; Kaufman, L., Some stable methods for calculating inertia and solving symmetric linear equations, Math. Comp., 31, 163-179 (1977) · Zbl 0355.65023
[24] Greenbaum, A., Iterative Methods for Solving Linear Systems (1997), SIAM: SIAM Philadelphia, PA · Zbl 0883.65022
[25] De Leone, R.; Egidi, N.; Fatone, L., The use of grossone in elastic net regularization and sparse support vector machines, Soft Comput. (2020)
[26] De Leone, R.; Fasano, G.; Roma, M.; Sergeyev, Y. D., Iterative grossone-based computation of negative curvature directions in large-scale optimization, J. Optim. Theory Appl., 186, 554-589 (2020) · Zbl 1450.90009
[27] Sergeyev, Y. D., Numerical infinities and infinitesimals: Methodology, applications, and repercussions on two Hilbert problems, EMS Surv. Math. Sci., 4, 2, 219-320 (2017) · Zbl 1390.03048
[28] Sergeyev, Y. D., Higher order numerical differentiation on the infinity computer, Optim. Lett., 5, 4, 575-585 (2011) · Zbl 1230.65028
[29] Sergeyev, Y. D., Independence of the grossone-based infinity methodology from non-standard analysis and comments upon logical fallacies in some texts asserting the opposite, Found. Sci., 24, 153-170 (2019) · Zbl 1428.03076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.