Abstract
We use some results from polarity theory to recast several geometric properties of Conjugate Gradient-based methods, for the solution of nonsingular symmetric linear systems. This approach allows us to pursue three main theoretical objectives. First, we can provide a novel geometric perspective on the generation of conjugate directions, in the context of positive definite systems. Second, we can extend the above geometric perspective to treat the generation of conjugate directions for handling indefinite linear systems. Third, by exploiting the geometric insight suggested by polarity theory, we can easily study the possible degeneracy (pivot breakdown) of Conjugate Gradient-based methods on indefinite linear systems. In particular, we prove that the degeneracy of the standard Conjugate Gradient on nonsingular indefinite linear systems can occur only once in the execution of the Conjugate Gradient.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Hestenes, M., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409–435 (1952)
Stoer, J.: Solution of large linear systems of equations by conjugate gradient type methods. In: Bachem, A., Grötschel, M., Korte, B. (eds.) Mathematical Programming. The State of the Art, pp. 540–565. Springer, Berlin (1983)
Nazareth, L.: A relationship between the BFGS and conjugate gradient algorithms and its implications for new algorithms. SIAM J. Numer. Anal. 16, 794–800 (1979)
Hestenes, M.: Conjugate direction methods in optimization. Springer, New York (1980)
Fasano, G.: Conjugate gradient (CG)-type method for the solution of Newton’s equation within optimization frameworks. Optim. Methods Softw. 19, 267–290 (2004)
Fasano, G.: Planar-conjugate gradient algorithm for large scale unconstrained optimization, part 2: application. J. Optim. Theory Appl. 125, 543–558 (2005)
Luenberger, D.: Hyperbolic pairs in the method of conjugate gradients. SIAM J. Appl. Math. 17, 1263–1267 (1969)
Lakshmikantham, V., Trigiante, D.: Theory of Difference Equations: Numerical Methods and Applications. Marcel Dekker Inc, New York (2002)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2000)
Nash, S.: A survey of truncated-Newton methods. J. Comput. Appl. Math. 124, 45–59 (2000)
Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400–408 (1982)
Grippo, L., Lampariello, F., Lucidi, S.: A truncated Newton method with nonmonotone line search for unconstrained optimization. J. Optim. Theory Appl. 60, 401–419 (1989)
Fasano, G., Roma, M.: Iterative computation of negative curvature directions in large scale optimization. Comput. Optim. Appl. 38, 81–104 (2007)
Gould, N.I.M., Lucidi, S., Roma, M., Toint, PhL: Exploiting negative curvature directions in linesearch methods for unconstrained optimization. Optim. Methods Softw. 14, 75–98 (2000)
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.: A framework of conjugate direction methods for symmetric linear systems in optimization. J. Optim. Theory Appl. 164, 883–914 (2015)
Gratton, S., Sartenaer, A., Tshimanga, J.: On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides. SIAM J. Optim. 21, 912–935 (2011)
Fasano, G., Roma, M.: Preconditioning Newton–Krylov methods in non-convex large scale optimization. Comput. Optim. Appl. 56, 253–290 (2013)
Beltrametti, M.C., Carletti, E., Gallarati, D., Monti Bragadin, G.: Lectures on Curves. European Mathematical Society, Surfaces and Projective Varieties: A Classical View of Algebraic Geometry (2009)
Casey, J.: A Treatise on the Analytical Geometry of the Point, Line, Circle and Conic Sections. Dublin University Press, Dublin (1885)
Schreirer, O., Sperner, E.: Projective Geometry of n Dimensions. Chelsea Publishing Company, New York (1961)
Seidenberg, A.: Lectures in Projective Geometry. Dover Publications Inc, Mineola (2005)
Akivis, M.A., Goldberg, V.V.: Differential Geometry of Varieties with Degenerate Gauss Maps. Springer, New York (2004)
Higham, N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (1996)
Greenbaum, A.: Iterative Methods for Solving Linear Systems. SIAM, Philadelphia (1997)
Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its performance. Math. Program. Ser. A 108, 177–205 (2006)
Acknowledgements
The authors are indebted with the Editorial Board and the reviewers, for their constructive and valuable comments. The work of G. Fasano is partially supported by the Italian Flagship Project RITMARE, coordinated by the Italian National Research Council (CNR) and funded by the Italian Ministry of Education, within the National Research Program 2012–2016.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Jérôme Bolte.
Rights and permissions
About this article
Cite this article
Fasano, G., Pesenti, R. Conjugate Direction Methods and Polarity for Quadratic Hypersurfaces. J Optim Theory Appl 175, 764–794 (2017). https://doi.org/10.1007/s10957-017-1180-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-017-1180-6
Keywords
- Polarity in homogeneous coordinates
- Quadratic hypersurfaces
- Conjugate Gradient method
- Indefinite linear systems