[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A combined SQP–IPM algorithm for solving large-scale nonlinear optimization problems

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We consider a combined IPM–SQP method to solve smooth nonlinear optimization problems, which may possess a large number of variables and a sparse Jacobian matrix of the constraints. Basically, the algorithm is a sequential quadratic programming (SQP) method, where the quadratic programming subproblem is solved by a primal-dual interior point method (IPM). A special feature of the algorithm is that the quadratic programming subproblem does not need to become exactly solved. To solve large optimization problems, either a limited-memory BFGS update to approximate the Hessian of the Lagrangian function is applied or the user specifies the Hessian by himself. Numerical results are presented for the 306 small and dense Hock-Schittkowski problems, for 13 large semi-linear elliptic control problems after a suitable discretization, and for 35 examples of the CUTEr test problem collection with more than 5000 variables.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide. Society for industrial and applied mathematics, Philadelphia (1999)

    Book  Google Scholar 

  2. Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1995)

    Article  MathSciNet  Google Scholar 

  3. Byrd, R.H., Gilbert, J.C., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Math. Progr. 89, 149–185 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  4. Cafieri, S., D’Apuzzo, M., De Simone, V., di Serafino, D.: On the iterative solution of KKT systems in potential reduction software for large scale quadratic problems. Comput. Optim. Appl. 38, 27–45 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chen, L., Goldfarb, D.: An interior-point piecewise linear penalty method for nonlinear programming. Math. Progr. 10, 1–50 (2009)

    MathSciNet  Google Scholar 

  6. Curtis, F.E., Nocedal, J.: Flexible penalty functions for nonlinear constrained optimization. J. Numer. Anal. 28, 335–351 (2008)

    MathSciNet  Google Scholar 

  7. D’Apuzzo, M., De Simone, V., di Serafino, D.: On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods. Comput. Optim. Appl. 45(2), 283–310 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  8. Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large-scale optimization. Math. Progr. 45, 503–528 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  9. Fletcher, R.: Practical methods of optimization. Wiley, Chichester (1987)

    MATH  Google Scholar 

  10. Gill, P.E., Murray, W., Wright, M.: Practical optimization. Academic Press, London (1982)

    Google Scholar 

  11. Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218, 587–601 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  12. Gould, N.I.M., Toint, Ph.L.: SQP methods for large-scale nonlinear programming. In: Proceedings of the 19th IFIP TC7 Conference on System Modelling and Optimization: Methods, Theory and Applications, pp 149–178 (1999)

  13. Gould, N.I.M., Orban, D., Toint, Ph.L.: General CUTEr documentation, CERFACS Technical Report TR/PA/02/13 (2005)

  14. Griva, I., Shanno, D.F., Vanderbei, R.J., Benson, H.Y.: Global convergence of a primal-dual interior-point method for nonlinear programming. Algorithmic Oper. Res. 3, 12–19 (2008)

    MATH  MathSciNet  Google Scholar 

  15. Hock, W., Schittkowski, K.: A comparative performance evaluation of 27 nonlinear programming codes. Computing 30, 335–358 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  16. 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  MathSciNet  Google Scholar 

  17. 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  MathSciNet  Google Scholar 

  18. Nocedal, J., Wächter, A., Waltz, R.A.: Adaptive barrier strategies for nonlinear interior methods. SIAM J. Optim. 19, 1674–1693 (2009)

    Article  MATH  Google Scholar 

  19. Sachsenberg, B., Schittkowski, K.: NLPIP: a Fortran implementation of an SQP interior point method for solving large-scale nonlinear optimization problems—user’s guide. Department of Computer Science, University of Bayreuth, Report (2014)

  20. Schenk, O., Gärtner, K.: On fast factorizing pivoting methods for symmetric indefinite systems. Electron. Trans. Numer. Anal. 23, 158–179 (2006)

    MATH  MathSciNet  Google Scholar 

  21. Schittkowski, K.: On the convergence of a sequential quadratic programming method with an augmented Lagrangian search direction. Optimization 14, 197–216 (1983)

    MATH  MathSciNet  Google Scholar 

  22. Schittkowski, K.: NLPQL: a Fortran subroutine solving constrained nonlinear rogramming problems. Annals of Operations Research 5, 485–500 (1986)

  23. Schittkowski, K.: More test examples for nonlinear programming, lecture notes in economics and mathematical systems, vol. 182. Springer

  24. Schittkowski, K.: NLPQLP: a Fortran implementation of a sequential quadratic programming algorithm with distributed and non-monotone line Search—user’s guide, version 3.0, Report, Department of Computer Science, University of Bayreuth (2009)

  25. Sun, W.Y., Yuan, Y.: Optimization theory and methods: nonlinear programming. Springer, New York (2006)

    Google Scholar 

  26. Vanderbei, R.J.: LOQO: An interior point code for quadratic programming. Optim. Methods Softw. 11, 451–484 (1999)

    Article  MathSciNet  Google Scholar 

  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. Math. Program. 107, 391–408 (2006)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Bayreuth, 95440, Bayreuth, Germany

    Björn Sachsenberg & Klaus Schittkowski

Authors
  1. Björn Sachsenberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Klaus Schittkowski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Klaus Schittkowski.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sachsenberg, B., Schittkowski, K. A combined SQP–IPM algorithm for solving large-scale nonlinear optimization problems. Optim Lett 9, 1271–1282 (2015). https://doi.org/10.1007/s11590-015-0863-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-015-0863-x

Keywords

Search

Navigation