Skip to main content
SpringerLink
Log in

Planar Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization, Part 1: Theory

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

Abstract

In this paper, we present a new conjugate gradient (CG) based algorithm in the class of planar conjugate gradient methods. These methods aim at solving systems of linear equations whose coefficient matrix is indefinite and nonsingular. This is the case where the application of the standard CG algorithm by Hestenes and Stiefel (Ref. 1) may fail, due to a possible division by zero. We give a complete proof of global convergence for a new planar method endowed with a general structure; furthermore, we describe some important features of our planar algorithm, which will be used within the optimization framework of the companion paper (Part 2, Ref. 2). Here, preliminary numerical results are reported.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. R. Hestenes E. Stiefel (1952) ArticleTitle Methods of Conjugate Gradients for Solving Linear Systems Journal of Research of the National Bureau of Standards 49 409–436

    Google Scholar 

  2. G. Fasano (2005) ArticleTitle Planar-Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization, Part 2: Application Journal of Optimization Theory and Applications 125 543–558

    Google Scholar 

  3. R. W. Freund G. H. Golub N. M. Nachtigal (1992) ArticleTitle Iterative Solution of Linear Systems Acta Numerica 1 57–100

    Google Scholar 

  4. J. R. Bunch B. N. Parlett (1971) ArticleTitle Direct Methods for Solving Symmetric Indefinite Systems of Linear Equations SIAM Journal on Numerical Analysis 8 639–655 Occurrence Handle10.1137/0708060

    Article  Google Scholar 

  5. Y. Saad H.A. Vorst ParticleVan Der (2000) ArticleTitle Iterative Solution of Linear Systems in the 20th Century Journal on Computational and Applied Mathematics 123 1–33 Occurrence Handle10.1016/S0377-0427(00)00412-X

    Article  Google Scholar 

  6. G. H. Golub H. A. Vorst ParticleVan Der (1997) Closer to the Solution: Iterative Linear Solvers I. S. Duff G. A. Watson (Eds) The State of the Art in Numerical Analysis Clarendon Press Oxford, UK 63–92

    Google Scholar 

  7. G. L. G. Sleijpen H. A. Vorst ParticleVan Der J. Modersitzki (2000) ArticleTitle Differences in the Effects of Rounding Errors in Krylov Solvers for Symmetric Indefinite Linar Systems SIAM Journal on Matrix Analysis and Applications 3 726–751 Occurrence Handle10.1137/S0895479897323087

    Article  Google Scholar 

  8. H. A. Vorst ParticleVan Der T. F. Chan (1997) Linear System Solvers: Sparse-Iterative Methods D. E. Keyes A. Samed V. Venkatakrishnan (Eds) Parellel Numerical Algorithms, ICASE/LaRC Interdisciplinary Series in Science and Engineering. Kluwer Academic Publishers Dordrecht Holland 91–118

    Google Scholar 

  9. G. L. G. Sleijpen H. A. Vorst ParticleVan Der (1983) Krylov Subspace Methods for Large Linear Systems of Equations Department of Mathematics University of Utrecht

    Google Scholar 

  10. J. M. Ortega W. C. Rheinboldt (1970) Iterative Solution of Nonlinear Equations in Several Variables Academic Press New York, NY

    Google Scholar 

  11. S. G. Nash (1999) ArticleTitle A Survey of Truncated Newton Methods Journal of Computational and Applied Mathematics 124 45–59 Occurrence Handle10.1016/S0377-0427(00)00426-X

    Article  Google Scholar 

  12. J. J. More’ D. C. Sorensen (1979) ArticleTitle On the Use of Directions of Negative Curvature in a Modified Newton Method Mathematical Programming 16 1–20 Occurrence Handle10.1007/BF01582091

    Article  Google Scholar 

  13. G. P. McCormick (1977) ArticleTitle A Modification of Armijo’s Stepsize Rule for Negative Curvature Mathematical Programming 13 111–115 Occurrence Handle10.1007/BF01584328

    Article  Google Scholar 

  14. D. P. Bertsekas (1995) Nonlinear Programming Athena Scientific Belmont Massachusetts

    Google Scholar 

  15. I. Bongartz A. R. Conn N. Gould P. L. Toint (1995) ArticleTitle CUTE: Constrained and Unconstrained Test Environment ACM Transactions on Mathematical Software 21 123–160 Occurrence Handle10.1145/200979.201043

    Article  Google Scholar 

  16. R. Fletcher C. M. Reeves (1964) ArticleTitle Function Minimization by Conjugate Gradients Computer Journal 7 49–154

    Google Scholar 

  17. E. Polak G. Ribiere (1969) ArticleTitle Note sur la Convergence de Methodes de Directions Conjugées Revue Francaise d’Informatique et de Recherche Operationelle 16 35–43

    Google Scholar 

  18. R. Fletcher (1975) Conjugate Gradient Methods for Indefinite Systems G. A. Watson (Eds) Proceedings of the Dundee Biennal Conference on Numerical Analysis Springer Berlin, Germany 73–89

    Google Scholar 

  19. C. C. Paigee M. A. Saunders (1975) ArticleTitle Solution of Sparse Indefinite Systems of Linear Equations SIAM Journal on Numerical Analysis 12 617–629 Occurrence Handle10.1137/0712047

    Article  Google Scholar 

  20. J. K. Cullum R. A. Willoughby (1985) Lanczos Algorithm for Large Symmetric Eigenvalue Computations Birkhauser Boston, Massachusetts

    Google Scholar 

  21. P. C. Hansen (1998) Rank-Deficit and Discrete Ill-Posed Problems SIAM Philadelphia Pennsylvania

    Google Scholar 

  22. M. R. Hestenes (1980) Conjugate Direction Models in Optimization Springer Verlag New York, NY

    Google Scholar 

  23. D. G. Luenberger (1969) ArticleTitle Hyperbolic Pairs in the Method of Conjugate Gradients SIAM Journal on Applied Mathematics 17 1263–1267 Occurrence Handle10.1137/0117118

    Article  Google Scholar 

  24. G. Fasano (2001) Use of Conjugate Directions Inside Newton-Type Algorithms for Large-Scale Unconstrained Optimization Italy Rome

    Google Scholar 

  25. Y. F. Hu C. Storey (1991) ArticleTitle Efficient Generalized Conjugate Gradient Algorithms, Part 2: Implementation Journal of Optimization Theory and Applications 69 139–152 Occurrence Handle10.1007/BF00940465

    Article  Google Scholar 

  26. Y. Liu C. Storey (1991) ArticleTitle Efficient Generalized Conjugate Gradient Algorithms, Part 1: Theory Journal of Optimization Theory and Applications 69 129–137 Occurrence Handle10.1007/BF00940464

    Article  Google Scholar 

  27. L. C. W. Dixon P. G. Ducksbury P. Singh (1985) A New Three-Term Conjugate Gradient Method Numerical Optimization Centre, Hatfield Polytechnic Hatfield, Hertfordshire, England

    Google Scholar 

  28. A. Miele J. W. Cantrell (1969) ArticleTitle Study on a Memory Gradient Method for the Minimization of Functions Journal of Optimization Theory and Applications 3 459–470 Occurrence Handle10.1007/BF00929359

    Article  Google Scholar 

  29. G. Fasano (2004) Planar-Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization, Part 1: Theory Istituto Nazionale per Studi ed Esperienze di Architettura (INSEAN) Rome, Italy

    Google Scholar 

  30. A. Greenbaum (1997) Iterative Methods for Solving Linear Systems SIAM Philadelphia Pennsylvania.

    Google Scholar 

  31. N. I. M. Gould S. Lucidi M. Roma P. L. Toint (2000) ArticleTitle Exploiting Negative Curvature Directions in Line Search Methods for Unconstrained Optimization Optimization Methods and Software 14 75–98

    Google Scholar 

  32. S. Lucidi M. Roma (1997) ArticleTitle Numerical Experiences with Truncated Newton Methods in Large Scale Unconstrained Optimization Computational Optimization and Applications 7 71–87 Occurrence Handle10.1023/A:1008619812615

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Postdoctoral Fellow, Department of Computer Science and Systems A. Ruberti, University of Rome-La Sapienza, Rome, Italy

    G. Fasano

Authors
  1. G. Fasano
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported by MIUR, FIRB Research Program on Large-Scale Nonlinear Optimization, Rome, Italy

The author acknowledges Luigi Grippo and Stefano Lucidi, who contributed considerably to the elaboration of this paper. The exchange of experiences with Massimo Roma was a constant help in the investigation. The author expresses his gratitude to the Associate Editor and the referees for suggestions and corrections.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fasano, G. Planar Conjugate Gradient Algorithm for Large-Scale Unconstrained Optimization, Part 1: Theory. J Optim Theory Appl 125, 523–541 (2005). https://doi.org/10.1007/s10957-005-2087-1

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-005-2087-1

Keywords

Search

Navigation