Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Inexact constraint preconditioners for linear systems arising in interior point methods

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

An Erratum to this article was published on 13 November 2009

Abstract

Issues of indefinite preconditioning of reduced Newton systems arising in optimization with interior point methods are addressed in this paper. Constraint preconditioners have shown much promise in this context. However, there are situations in which an unfavorable sparsity pattern of Jacobian matrix may adversely affect the preconditioner and make its inverse representation unacceptably dense hence too expensive to be used in practice. A remedy to such situations is proposed in this paper. An approximate constraint preconditioner is considered in which sparse approximation of the Jacobian is used instead of the complete matrix. Spectral analysis of the preconditioned matrix is performed and bounds on its non-unit eigenvalues are provided. Preliminary computational results are encouraging.

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
$34.99 /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 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. Andersen, E.D., Gondzio, J., Mészáros, C., Xu, X.: Implementation of interior point methods for large scale linear programming. In: Terlaky, T. (ed.), Interior Point Methods in Mathematical Programming, pp. 189–252. Kluwer Academic, Dordrecht (1996)

    Google Scholar 

  2. Benzi, M., Golub, G., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  3. Benzi, M., Simoncini, V.: On the eigenvalues of a class of saddle point matrices. Numer. Math. 103 173–196 (2006)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  5. Coleman, T., Verma, A.: A preconditioned conjugate gradient approach to linear equality constrained minimization. Comput. Optim. Appl. 20, 61–72 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  6. Dollar, H., Wathen, A.: Approximate factorization constraint preconditioners for saddle-point matrices. SIAM J. Sci. Comput. 27, 1555–1572 (2005)

    Article  MathSciNet  Google Scholar 

  7. Freund, R.W., Nachtigal, N.M.: Software for simplified Lanczos and QMR algorithms. Appl. Numer. Math. 19, 319–341 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  8. Gondzio, J.: HOPDM (version 2.12)—a fast LP solver based on a primal–dual interior point method. Eur. J. Oper. Res. 85, 221–225 (1995)

    Article  MATH  Google Scholar 

  9. Gould, N.I.M., Hribar, M.E., Nocedal, J.: On the solution of equality constrained quadratic problems arising in optimization. SIAM J. Sci. Comput. 23, 1375–1394 (2001)

    Article  MathSciNet  Google Scholar 

  10. Keller, C., Gould, N.I.M., Wathen, A.J.: Constraint preconditioning for indefinite linear systems. SIAM J. Matrix Anal. Appl. 21, 1300–1317 (2000)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  12. Wright, S.J.: Primal–Dual Interior-Point Methods. SIAM, Philadelphia (1997)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Methods and Models for Scientific Applications, University of Padua, Padua, Italy

    Luca Bergamaschi & Giovanni Zilli

  2. School of Mathematics, University of Edinburgh, Edinburgh, Scotland, UK

    Jacek Gondzio

  3. Department of Pure and Applied Mathematics, University of Padua, Padua, Italy

    Manolo Venturin

Authors
  1. Luca Bergamaschi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jacek Gondzio
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Manolo Venturin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Giovanni Zilli
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luca Bergamaschi.

Additional information

An erratum to this article can be found online at http://dx.doi.org/10.1007/s10589-009-9298-6.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bergamaschi, L., Gondzio, J., Venturin, M. et al. Inexact constraint preconditioners for linear systems arising in interior point methods. Comput Optim Appl 36, 137–147 (2007). https://doi.org/10.1007/s10589-006-9001-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-006-9001-0

Keywords

Search

Navigation