Skip to main content
SpringerLink
Log in

Conjugate gradient algorithms in the solution of optimization problems for nonlinear elliptic partial differential equations

Konjugierte Gradienten-Algorithmen in der Lösung von Optimierungsproblemen für nichtlineare elliptische partielle Randwertprobleme

  • Published:
Computing Aims and scope Submit manuscript

Abstract

Several variants of the conjugate gradient algorithm are discussed with emphasis on determining the parameters without performing line searches and on using splitting techniques to accelerate convergence. The splittings used here are related to the nonlinear SSOR algorithm. The behavior of the methods is illustrated on a discretization of a nonlinear elliptic partial differential boundary value problem, the minimal surface equation. A conjugate gradient algorithm with splittings is also developed for constrained minimization with upper and lower bounds on the variables, and the method is applied to the obstacle problem for the minimal surface equation.

Zusammenfassung

Wir besprechen mehrere Varianten des konjugierten Gradienten-Algorithmus unter Hervorhebung der Parameterbestimmung ohne Minimierung entlang von Linien und der Konvergenzbeschleunigung durch Zerlegung. Die hier verwendeten Zerlegungen sind dem nichtlinearen SSOR-Algorithmus verwandt. Das Verhalten der Methoden wird illustriert an der Diskretisierung eines nichtlinearen elliptischen partiellen Randwertproblems, nämlich der Minimalflächen-Gleichung. Wir entwickeln auch einen konjugierten Gradienten-Algorithmus mit Zerlegungen für Minimierung mit von oben und unten beschränkten Variabeln; ferner zeigen wir eine Anwendung der Methode auf das Hindernisproblem bei der Minimalflächen-Gleichung.

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. Axelsson, O.: Solution of linear systems of equations: iterative methods. Sparse Matrix Techniques (Lecture Notes Vol. 572), pp. 1–11. Berlin-Heidelberg-New York: Springer 1977.

    Google Scholar 

  2. Bartels, R., Daniel, J. W.: A conjugate gradient approach to nonlinear elliptic voundary value problems in irregular regions. Proc. Conf. on Numerical Solution of Differential Equations (Lecture Notes, Vol. 363), pp. 1–11. Berlin-Heidelberg-New York: Springer 1974.

    Google Scholar 

  3. Bertsekas, D.: Partial conjugate gradient methods for a class of optimal control problems. IEEE Trans. Automat. ControlAC-19, 209–217 (1974).

    Google Scholar 

  4. Broyden, C. G.: Quasi-Newton methods, in: Numerical methods for unconstrained optimization (Murray, W., ed.), pp. 87–106. New York: Academic Press 1972.

    Google Scholar 

  5. Cohen, A. I.: Rate of convergence of several conjugate gradient algorithms. SIAM J. Numer. Anal.9, 248–259 (1972).

    Google Scholar 

  6. Concus, P.: Numerical solution of the minimal surface equation. Math. Comp.21, 340–350 (1967).

    Google Scholar 

  7. Concus, P.: Numerical solution of the minimal surface equation by block nonlinear successive overrelaxation. Information Processing 68, Proc. IFIP Congress 1968, pp. 153–158. Amsterdam: North-Holland 1969.

    Google Scholar 

  8. Concus, P., Golub, G. H., O'Leary, D. P.: A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, in: Sparse matrix computations (Bunch, J. R., Rose, D. J., eds.), pp. 309–332. New York: Academic Press 1976.

    Google Scholar 

  9. Concus, P., Golub, G. H., O'Leary, D. P.: Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method. Computing19, 321–339 (1978).

    Google Scholar 

  10. Daniel, J. W.: The conjugate gradient method for linear and nonlinear operator equations. Ph. D. Thesis, Stanford University, and SIAM J. Numer Anal.4, 10–26 (1967).

    Google Scholar 

  11. Dixon, L. C. W.: Conjugate gradient algorithms: quadratic termination without linear searches. J. Inst. Maths. Applics.15, 9–18 (1975).

    Google Scholar 

  12. Douglas, Jesse: A method of numerical solution of the problem of Plateau. Ann. Math.29, 180–187 (1928).

    Google Scholar 

  13. Douglas, J., jr., Dupont, T.: Preconditional conjugate gradient iteration applied to Galerkin methods for a mildly nonlinear Dirichlet problem, in: Sparse matrix computations (Bunch, J. R., Rose, D. J., eds.), pp. 333–349. New York: Academic Press 1976.

    Google Scholar 

  14. Eckhardt, U.: On an optimization problem related to minimal surfaces with obstacles. Technical Report, Jülich (1975).

  15. Ehrlich, L. W.: On some experience using matrix splitting and conjugate gradient (abstract). SIAM Review18, 801 (1976).

    Google Scholar 

  16. Fletcher, R., Reeves, C. M.: Function minimization by conjugate gradients. Computer J.7, 149–154 (1964).

    Google Scholar 

  17. Goldfarb, D.: A conjugate gradient method for nonlinear programming. Princeton University Press, Thesis, 1966.

  18. Greenspan, D.: On approximating extremals of functionals part 1. ICC Bull.4, 99–120 (1965).

    Google Scholar 

  19. Hayes, L., Young, D. M., Schleicher, E.: The use of the accelerated SSOR method to solve large linear systems (abstract). SIAM Review18, 808 (1976).

    Google Scholar 

  20. Hestenes, M. R.: The conjugate gradient method for solving linear systems. Proc. Symp. in Appl. Math.6, 83–102 (1956).

    Google Scholar 

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

    Google Scholar 

  22. Klessig, R., Polak, E.: Efficient implementation of the Polak-Ribiere conjugate gradient algorithm. SIAM J. Control10, 524–549 (1972).

    Google Scholar 

  23. Lenard, M. L.: Convergence conditions for restarted conjugate gradient methods with inaccurate line searches. Math. Prog.10, 32–51 (1976).

    Google Scholar 

  24. McCormick, G. P., Ritter, K.: Alternative proofs of the convergence properties of the conjugate gradient method. J. Opt. Th. Applic.13, 497–518 (1974).

    Google Scholar 

  25. Meijerink, J. A., van der Vorst, H. A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comp.31, 148–162 (1977).

    Google Scholar 

  26. Nazareth, L.: A conjugate direction algorithm without line searches. J. Opt. Th. Applic.23, 373–388 (1977).

    Google Scholar 

  27. O'Leary, D. P.: A generalized conjugate gradient algorithm for solving a class of quadratic programming problems. Report STAN-CS-77-638, Stanford University (1977).

  28. Ortega, J. M., Rheinboldt, W. C.: Iterative Solution of Nonlinear Equations in Several Variables. New York: Academic Press 1970.

    Google Scholar 

  29. Polak, E., Ribiere, G.: Note sur la convergence de méthodes de directions conjugées. Rev. Française Informat. Recherche Operationnelle16-R1, 35–43 (1969).

    Google Scholar 

  30. Polyak, B. T.: Conjugate gradient method in extremal problems. USSR Comput. Math. and Math. Phys.9, 809–821 (1969).

    Google Scholar 

  31. Powell, M. J. D.: Restart procedures for the conjugate gradient method. Math. Prog.12, 241–254 (1977).

    Google Scholar 

  32. Reid, J. K.: On the method of conjugate gradients for the solution of large sparse systems of linear equations, in: Large sparse sets of linear equations (Reid, J. K., ed.), pp. 231–254. New York: Academic Press 1971.

    Google Scholar 

  33. Schecter, S.: Relaxation methods for convex problems. SIAM J. Numer. Anal.5, 601–612 (1968).

    Google Scholar 

  34. Wang, H. H.: The application of the symmetric SOR and the symmetric SIP methods for the numerical solution of the neutron diffusion equation. Report G 320-3358, IBM Palo Alto Scientific Center (1977).

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of Maryland, 20742, College Park, MD, USA

    Dianne P. O'Leary

Authors
  1. Dianne P. O'Leary
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported by the National Science Foundation under Grant MCS 76-06595 at the University of Michigan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

O'Leary, D.P. Conjugate gradient algorithms in the solution of optimization problems for nonlinear elliptic partial differential equations. Computing 22, 59–77 (1979). https://doi.org/10.1007/BF02246559

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02246559

Keywords

Search

Navigation