Some iterative methods for the solution of a symmetric indefinite KKT system | Computational Optimization and Applications Skip to main content
Springer Nature Link
Log in

Some iterative methods for the solution of a symmetric indefinite KKT system

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

This paper is concerned with the numerical solution of a Karush–Kuhn–Tucker system. Such symmetric indefinite system arises when we solve a nonlinear programming problem by an Interior-Point (IP) approach. In this framework, we discuss the effectiveness of two inner iterative solvers: the method of multipliers and the preconditioned conjugate gradient method. We discuss the implementation details of these algorithms in an IP scheme and we report the results of a numerical comparison on a set of large scale test-problems arising from the discretization of elliptic control problems.

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

Access this article

Log in via an institution

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.

Institutional subscriptions

Similar content being viewed by others

References

  1. Altman, A., Gondzio, J.: Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optim. Methods Softw. 11–12, 275–302 (1999)

    Article  Google Scholar 

  2. Bergamaschi, L., Gondzio, J., Zilli, G.: Preconditioning indefinite systems in interior point methods for optimization. Comput. Optim. Appl. 28(2), 149–171 (2004)

    Article  MATH  Google Scholar 

  3. Bonettini, S., Galligani, E., Ruggiero, V.: An inexact Newton method combined with Hestenes multipliers’ scheme for the solution of Karush–Kuhn–Tucker systems. Appl. Math. Comput. 168, 651–676 (2005)

    Article  MATH  Google Scholar 

  4. Bunch, J.R., Parlett, B.N.: Direct methods for solving symmetric indefinite systems of linear equations. SIAM J. Numer. Anal. 8, 639–655 (1971)

    Article  Google Scholar 

  5. Byrd, R.H., Hribar, M.E., Nocedal, J.: An interior point algorithm for large scale nonlinear programming. SIAM J. Optim. 9(4), 877–900 (1999)

    Article  MATH  Google Scholar 

  6. D’Apuzzo, M., Marino, M.: Parallel computational issues of an interior-point method for solving large bound constrained quadratic programming problems. Parallel Comput. 29, 467–483 (2003)

    Article  Google Scholar 

  7. Durazzi, C., Ruggiero, V.: A Newton inexact interior-point method for large scale nonlinear optimization problems. Ann. Univ. Ferrara Sez. VII Sc. Matem. IL, 333–357 (2003)

    Google Scholar 

  8. Durazzi, C., Ruggiero, V.: Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems. Numer. Linear Algebra Appl. 10, 673–688 (2003)

    Article  MATH  Google Scholar 

  9. Durazzi, C., Ruggiero, V., Zanghirati, G.: Parallel interior-point method for linear and quadratic programs with special structure. J. Optim. Theory Appl. 110, 289–313 (2001)

    Article  MATH  Google Scholar 

  10. El-Bakry, A.S., Tapia, R.A., Tsuchiya, T., Zhang, Y.: On the formulation and theory of Newton interior-point method for nonlinear programming. J. Optim. Theory Appl. 89, 507–541 (1996)

    Article  MATH  Google Scholar 

  11. Gould, N.I.M.: On practical conditions for the existence and uniqueness of solutions to the general equality quadratic programming problem. Math. Program. 32, 90–99 (1985)

    Article  MATH  Google Scholar 

  12. Harwell Subroutine Library: A catalogue of subroutines (HSL 2000). AEA Technology. Harwell, Oxfordshire, England (2002)

  13. Hestenes, M.R.: Optimization Theory. The Finite-Dimensional Case. Wiley, New York (1975)

    MATH  Google Scholar 

  14. Liu, J.W., Ng, E.G., Peyton, B.W.: On finding supernodes for sparse matrix computations. SIAM J. Matrix Anal. Appl. 14, 242–252 (1993)

    Article  MATH  Google Scholar 

  15. Luenberger, D.G.: Linear and Nonlinear Programming 2nd edn. Addison-Wesley, Reading (1984)

    MATH  Google Scholar 

  16. Lukšan, L., Matonoha, C., Vlček, J.: Interior-Point method for nonlinear nonconvex optimization. Numer. Linear Algebra Appl. 11, 431–453 (2004)

    Article  Google Scholar 

  17. Lukšan, L., Vlček, J.: Indefinitely preconditioned Inexact Newton method for large sparse equality constrained non-linear programming problems. Numer. Linear Algebra Appl. 5, 219–247 (1998)

    Article  Google Scholar 

  18. Maurer, H., Mittelmann, H.D.: Optimization techniques for solving elliptic control problems with control and state constraints: part 1. Boundary control. Comput. Optim. Appl. 16, 29–55 (2000)

    Article  MATH  Google Scholar 

  19. Maurer, H., Mittelmann, H.D.: Optimization techniques for solving elliptic control problems with control and state constraints: part 2. Distributed control. Comput. Optim. Appl. 18, 141–160 (2001)

    Article  MATH  Google Scholar 

  20. Mittelmann, H.D.: Private communication (2004)

  21. Mittelmann, H.D., Maurer, H.: Solving elliptic control problems with interior-point and SQP methods: control and state constraint. J. Comput. Appl. Math. 120, 175–195 (2000)

    Article  MATH  Google Scholar 

  22. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999)

    MATH  Google Scholar 

  23. Saad, Y.: Iterative Methods for Sparse Linear System. PSW, Boston (1996)

    Google Scholar 

  24. Saunders, M., Tomlin, J.A.: Solving regularized linear programs using barrier methods and KKT systems. Technical report SOL 96-4, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, CA 94305 (December 1996)

  25. Vanderbei, R.J.: Symmetric quasidefinite matrices. SIAM J. Optim. 5, 100–113 (1999)

    Article  Google Scholar 

  26. Vanderbei, R.J., Shanno, D.F.: An interior-point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13, 231–252 (1999)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Matematica Pura ed Applicata, Università di Modena e Reggio Emilia, via Campi 213/b, 41100, Modena, Italy

    Silvia Bonettini

  2. Dipartimento di Matematica, Università di Ferrara, via Machiavelli 35, 44100, Ferrara, Italy

    Valeria Ruggiero

Authors
  1. Silvia Bonettini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Valeria Ruggiero
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Silvia Bonettini.

Additional information

This research was supported by the Italian Ministry for Education, University and Research (MIUR), FIRB Project RBAU01JYPN.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bonettini, S., Ruggiero, V. Some iterative methods for the solution of a symmetric indefinite KKT system. Comput Optim Appl 38, 3–25 (2007). https://doi.org/10.1007/s10589-007-9039-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-007-9039-7

Keywords

Search

Navigation