Conjugate Direction Methods and Polarity for Quadratic Hypersurfaces | Journal of Optimization Theory and Applications Skip to main content
Log in

Conjugate Direction Methods and Polarity for Quadratic Hypersurfaces

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

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.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

References

  1. Hestenes, M., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand. 49, 409–435 (1952)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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)

    Chapter  Google Scholar 

  3. 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)

    Article  MathSciNet  MATH  Google Scholar 

  4. Hestenes, M.: Conjugate direction methods in optimization. Springer, New York (1980)

    Book  MATH  Google Scholar 

  5. Fasano, G.: Conjugate gradient (CG)-type method for the solution of Newton’s equation within optimization frameworks. Optim. Methods Softw. 19, 267–290 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fasano, G.: Planar-conjugate gradient algorithm for large scale unconstrained optimization, part 2: application. J. Optim. Theory Appl. 125, 543–558 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Luenberger, D.: Hyperbolic pairs in the method of conjugate gradients. SIAM J. Appl. Math. 17, 1263–1267 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  8. Lakshmikantham, V., Trigiante, D.: Theory of Difference Equations: Numerical Methods and Applications. Marcel Dekker Inc, New York (2002)

    Book  MATH  Google Scholar 

  9. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (2000)

    MATH  Google Scholar 

  10. Nash, S.: A survey of truncated-Newton methods. J. Comput. Appl. Math. 124, 45–59 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  11. Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400–408 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  12. 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)

    Article  MathSciNet  MATH  Google Scholar 

  13. Fasano, G., Roma, M.: Iterative computation of negative curvature directions in large scale optimization. Comput. Optim. Appl. 38, 81–104 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  14. 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)

    Article  MathSciNet  MATH  Google Scholar 

  15. 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)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fasano, G.: A framework of conjugate direction methods for symmetric linear systems in optimization. J. Optim. Theory Appl. 164, 883–914 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  17. 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)

    Article  MathSciNet  MATH  Google Scholar 

  18. Fasano, G., Roma, M.: Preconditioning Newton–Krylov methods in non-convex large scale optimization. Comput. Optim. Appl. 56, 253–290 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  19. 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)

  20. Casey, J.: A Treatise on the Analytical Geometry of the Point, Line, Circle and Conic Sections. Dublin University Press, Dublin (1885)

    MATH  Google Scholar 

  21. Schreirer, O., Sperner, E.: Projective Geometry of n Dimensions. Chelsea Publishing Company, New York (1961)

    Google Scholar 

  22. Seidenberg, A.: Lectures in Projective Geometry. Dover Publications Inc, Mineola (2005)

    MATH  Google Scholar 

  23. Akivis, M.A., Goldberg, V.V.: Differential Geometry of Varieties with Degenerate Gauss Maps. Springer, New York (2004)

    Book  MATH  Google Scholar 

  24. Higham, N.J.: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia (1996)

    MATH  Google Scholar 

  25. Greenbaum, A.: Iterative Methods for Solving Linear Systems. SIAM, Philadelphia (1997)

    Book  MATH  Google Scholar 

  26. Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its performance. Math. Program. Ser. A 108, 177–205 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to Giovanni Fasano.

Additional information

Communicated by Jérôme Bolte.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-017-1180-6

Keywords

Mathematics Subject Classification

Navigation