Skip to main content
SpringerLink
Log in

On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming

  • Published:
Mathematical Programming Submit manuscript

Abstract.

We present a primal-dual interior-point algorithm with a filter line-search method for nonlinear programming. Local and global convergence properties of this method were analyzed in previous work. Here we provide a comprehensive description of the algorithm, including the feasibility restoration phase for the filter method, second-order corrections, and inertia correction of the KKT matrix. Heuristics are also considered that allow faster performance. This method has been implemented in the IPOPT code, which we demonstrate in a detailed numerical study based on 954 problems from the CUTEr test set. An evaluation is made of several line-search options, and a comparison is provided with two state-of-the-art interior-point codes for nonlinear programming.

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. Benson, H. Y., Shanno, D. F., Vanderbei, R. J.: Interior-point methods for nonconvex nonlinear programming: Filter methods and merit functions. Computational Optimization and Applications, 23 (2), 257–272 (2002)

    Article  MathSciNet  Google Scholar 

  2. Byrd, R. H., Gilbert, J. Ch., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Mathematical Programming, 89, 149–185 (2000)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  4. Byrd, R. H., Liu, G., Nocedal, J.: On the local behavior of an interior point method for nonlinear programming. In: Griffiths, D. F., Higham, D. J. (eds), Numerical Analysis 1997, pages 37–56. Addison–Wesley Longman, Reading, MA, USA, 1997

  5. Chamberlain, R. M., Lemarechal, C., Pedersen, H. C., Powell, M. J. D.: The watchdog technique for forcing convergence in algorithms for constrained optimization. Mathematical Programming Study, 16, 1–17 (1982)

    MATH  MathSciNet  Google Scholar 

  6. Conn, A. R., Gould, N. I. M., Toint, Ph. L.: LANCELOT: a Fortran package for large-scale nonlinear optimization (Release A). Number 17 in Springer Series in Computational Mathematics. Springer Verlag, Heidelberg, Berlin, New York, 1992

  7. Conn, A. R., Gould, N. I. M., Toint, Ph. L.: Trust-Region Methods. SIAM, Philadelphia, PA, USA, 2000

  8. Conn, A. R., Gould, N.I.M., Orban, D., Toint, Ph. L.: A primal-dual trust-region algorithm for non-convex nonlinear programming. Mathematical Programming, 87 (2), 215–249 (2000)

    Article  MathSciNet  Google Scholar 

  9. Dolan, E. D., Moré, J. J.: Benchmarking optimization software with performance profiles. Mathematical Programming, 91 (2), 201–213 (2002)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  11. Fiacco, A. V., McCormick, G. P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley, New York, USA, 1968 Reprinted by SIAM Publications, 1990.

  12. Fletcher, R.: Practical Methods of Optimization. John Wiley and Sons, New York, USA, second edition, 1987

  13. Fletcher, R., Gould, N. I. M., Leyffer, S., Toint, Ph. L., Wächter, A.: Global convergence of a trust-region SQP-filter algorithms for general nonlinear programming. SIAM Journal on Optimization, 13 (3), 635–659 (2002)

    Article  MathSciNet  Google Scholar 

  14. Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Mathematical Programming, 91 (2), 239–269 (2002)

    Article  MathSciNet  Google Scholar 

  15. Fletcher, R., Leyffer, S., Toint, Ph. L.: On the global convergence of a filter-SQP algorithm. SIAM Journal on Optimization, 13 (1), 44–59 (2002)

    Article  MathSciNet  Google Scholar 

  16. Forsgren, A., Gill, P. E., Wright, M. H.: Interior methods for nonlinear optimization. SIAM Review, 44 (4), 525–597 (2002)

    Article  MathSciNet  Google Scholar 

  17. Gould, N. I. M., Orban, D., Sartenaer, A., Toint, Ph. L.: Superlinear convergence of primal-dual interior point algorithms for nonlinear programming. SIAM Journal on Optimization, 11 (4), 974–1002 (2001)

    Article  Google Scholar 

  18. Gould, N. I. M., Orban, D., Toint, Ph. L.: CUTEr (and SifDec), a constrained and unconstrained testing environment, revisited. Technical Report TR/PA/01/04, CERFACS, Toulouse, France, 2001

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

  20. Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York, NY, USA, 1999

  21. Tits, A. L., Wächter, A., Bakhtiari, S., Urban, T. J., Lawrence, C. T.: A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties. SIAM Journal on Optimization, 14 (1), 173–199 (2003)

    Article  MathSciNet  Google Scholar 

  22. Ulbrich, M., Ulbrich, S., Vicente, L. N.: A globally convergent primal-dual interior-point filter method for nonlinear programming. Mathematical Programming, 100 (2), 379–410 (2004)

    Article  MathSciNet  Google Scholar 

  23. Vanderbei, R. J., Shanno, D. F.: An interior-point algorithm for nonconvex nonlinear programming. Computational Optimization and Applications, 13, 231–252 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  24. Wächter, A.: An Interior Point Algorithm for Large-Scale Nonlinear Optimization with Applications in Process Engineering. PhD thesis, Carnegie Mellon University, Pittsburgh, PA, USA, January 2002

  25. Wächter, A., Biegler, L. T.: Failure of global convergence for a class of interior point methods for nonlinear programming. Mathematical Programming, 88 (2), 565–574 (2000)

    Article  MathSciNet  Google Scholar 

  26. Wächter, A., Biegler, L. T.: Line search filter methods for nonlinear programming: Motivation and global convergence. Technical Report RC 23036, IBM T.J. Watson Research Center, Yorktown Heights, USA, 2001; revised 2004. To appear in SIAM Journal on Optimization.

  27. Waltz, R. A., Morales, J. L., Nocedal, J., Orban, D.: An interior algorithm for nonlinear optimization that combines line search and trust region steps. Technical Report OTC 6/2003, Optimization Technology Center, Northwestern University, Evanston, IL, USA. To appear in Mathematical Programming A

  28. Waltz, R. A., Nocedal, J.: KNITRO user's manual. Technical Report OTC 2003/05, Optimization Technology Center, Northwestern University, Evanston, IL, USA, April 2003

  29. Yamashita, H.: A globally convergent primal-dual interior-point method for constrained optimization. Optimization Methods and Software, 10, 443–469 (1998)

    MATH  MathSciNet  Google Scholar 

  30. Yamashita, H., Yabe, H., Tanabe, T.: A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization. Technical report, Mathematical System Institute, Inc., Tokyo, Japan, July 1997. Revised July 1998

Download references

Author information

Authors and Affiliations

  1. IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY, 10598, USA

    Andreas Wächter

  2. Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, USA

    Lorenz T. Biegler

Authors
  1. Andreas Wächter
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lorenz T. Biegler
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Wächter.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wächter, A., Biegler, L. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106, 25–57 (2006). https://doi.org/10.1007/s10107-004-0559-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-004-0559-y

Keywords

Mathematical Subject Classification (2000):

Search

Navigation