Skip to main content
SpringerLink
Log in

A robust implementation of a sequential quadratic programming algorithm with successive error restoration

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

Abstract

We consider sequential quadratic programming methods for solving constrained nonlinear programming problems. It is generally believed that these methods are sensitive to the accuracy by which partial derivatives are provided. One reason is that differences of gradients of the Lagrangian function are used for updating a quasi-Newton matrix, e.g., by the BFGS formula. The purpose of this paper is to show by numerical experimentation that the method can be stabilized substantially. The algorithm applies non-monotone line search and internal and external restarts in case of errors due to inaccurate derivatives while computing the search direction. Even in case of large random errors leading to partial derivatives with at most one correct digit, termination subject to an accuracy of 10−7 can be achieved in 90% of 306 problems of a standard test suite. On the other hand, the original version with monotone line search and without restarts solves only 30% of these problems under the same test environment. In addition, we show how initial and periodic scaled restarts improve the efficiency in situations with slow convergence.

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. Armijo L.: Minimization of functions having Lipschitz continuous first partial derivatives. Pac. J. Math. 16, 1–3 (1966)

    MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  3. Bongartz I., Conn A.R., Gould N., Toint Ph.: CUTE: Constrained and unconstrained testing environment. Trans. Math. Softw. 21(1), 123–160 (1995)

    Article  MATH  Google Scholar 

  4. Dai Y.H.: On the nonmonotone line search. J. Optim. Theory Appl. 112(2), 315–330 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  5. Dai Y.H., Schittkowski K.: A sequential quadratic programming algorithm with non-monotone line search. Pac. J. Optim. 4, 335–351 (2008)

    MATH  MathSciNet  Google Scholar 

  6. Gill P.E., Leonard M.W.: Limited-memory reduced-Hessian methods for unconstrained optimization. SIAM J. Optim. 14, 380–401 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Goldfarb D., Idnani A.: A numerically stable method for solving strictly convex quadratic programs. Math. Program. 27, 1–33 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  8. Grippo L., Lampariello F., Lucidi S.: A nonmonotone line search technique for Newtons’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  9. Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer (1981)

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

    Article  MATH  MathSciNet  Google Scholar 

  11. Maurer H., Mittelmann H.: 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 

  12. Maurer H., Mittelmann H.: 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 

  13. Nocedal J.: Updating quasi-Newton matrices with limited storage. Math. Comput. 35, 773–782 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  14. Powell, M.J.D.: A fast algorithm for nonlinearly constraint optimization calculations. In: Watson, G.A. Numerical Analysis, Lecture Notes in Mathematics, vol. 630, Springer (1978)

  15. Powell M.J.D.: The convergence of variable metric methods for nonlinearly constrained optimization calculations. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds) Nonlinear Programming 3, Academic Press, New York (1978)

    Google Scholar 

  16. Rockafellar T.: Augmented Lagrangian multiplier functions and duality in nonconvex programming. SIAM J. Control 12, 268–285 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  17. Sachsenberg, B.: NLPIP: A Forrtan implementation of an SQP Interior Point algorithm for solving large scale nonlinear optimization problems: user’s guide, Report, Department of Computer Science, University of Bayreuth (2010)

  18. Schittkowski, K.: Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, vol. 183. Springer (1980)

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

    Article  MATH  MathSciNet  Google Scholar 

  20. Schittkowski K.: NLPQL: A Fortran subroutine solving constrained nonlinear programming problems. Ann Oper Res 5, 485–500 (1985/1986)

    MathSciNet  Google Scholar 

  21. Schittkowski K.: More Test Examples for Nonlinear Programming. Lecture Notes in Economics and Mathematical Systems, vol. 182. Springer, Berlin (1987)

    Google Scholar 

  22. Schittkowski K.: Solving nonlinear least squares problems by a general purpose SQP-method. In: Hoffmann, K.-H., Hiriart-Urruty, J.-B., Lemarechal, C., Zowe, J. (eds) Trends in Mathematical Optimization. International Series of Numerical Mathematics, vol. 84, pp. 295–309. Birkhäuser, Basel (1988)

    Google Scholar 

  23. Schittkowski K.: Numerical Data Fitting in Dynamical Systems. Kluwer Academic Publishers, Dordrecht (2002)

    MATH  Google Scholar 

  24. Schittkowski, K.: QL: A Fortran code for convex quadratic programming—user’s guide, Report, Department of Mathematics, University of Bayreuth (2003)

  25. Schittkowski K.: An active set strategy for solving optimization problems with up to 200,000,000 nonlinear constraints. Appl. Numer. Math. 59, 2999–3007 (2008)

    Article  MathSciNet  Google Scholar 

  26. Schittkowski, K.: An updated set of 306 test problems for nonlinear programming with validated optimal solutions: user’s guide, Report, Department of Computer Science, University of Bayreuth (2008)

  27. 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)

  28. Schittkowski K., Zillober C., Zotemantel R.: Numerical comparison of nonlinear programming algorithms for structural optimization. Struct. Optim. 7(1), 1–28 (1994)

    Article  Google Scholar 

  29. Spellucci P.: DONLP2 users guide, Technical University at Darmstadt, Department of Mathematics, Darmstadt, Germany

  30. Stoer J.: Foundations of recursive quadratic programming methods for solving nonlinear programs. In: Schittkowski, K. (eds) Computational Mathematical Programming, NATO ASI Series. Series F. Computer and Systems Sciences. vol. 15, Springer, Berlin (1985)

    Google Scholar 

  31. Toint P.L.: An assessment of nonmontone line search techniques for unconstrained optimization. SIAM J. Sci. Comput. 17, 725–739 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  32. Toint P.L.: A nonmonotone trust-region algorithm for nonlinear optimization subject to convex constraints. Math. Program. 77, 69–94 (1997)

    MATH  MathSciNet  Google Scholar 

  33. Wolfe P.: Convergence conditions for ascent methods. SIAM Rev. 11, 226–235 (1969)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    K. Schittkowski

Authors
  1. K. Schittkowski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to K. Schittkowski.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Schittkowski, K. A robust implementation of a sequential quadratic programming algorithm with successive error restoration. Optim Lett 5, 283–296 (2011). https://doi.org/10.1007/s11590-010-0207-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-010-0207-9

Keywords

Search

Navigation