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

An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal 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
$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

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Amestoy, P., Dollar, H.S., Reid, J.K., Scott, J.A.: An approximate minimum degree algorithm for matrices with dense rows. Technical Report RAL-TR-2007-020, Rutherford Appleton Laboratory (2007)

  2. Bauer, I., Bock, H.G., Körkel, S., Schlöder, J.P.: Numerical methods for initial value problems and derivative generation for DAE models with application to optimum experimental design of chemical processes. Sci. Comput. Chem. Eng. II(2), 282–289 (1999)

    Google Scholar 

  3. Bauer, I., Bock, H.G., Schlöder, J.P.: DAESOL—a BDF-code for the numerical solution of differential algebraic equations. Preprint, IWR der Universität Heidelberg, SFB 359 (1999)

  4. Bischof, C., Khademi, P., Mauer, A., Carle, A.: ADIFOR 2.0: automatic differentiation of fortran 77 programs. IEEE Comput. Sci. Eng. 3(3), 18–32 (1996)

    Article  Google Scholar 

  5. Bisschop, J., Meeraus, A.: Matrix augmentation and partitioning in the updating of the basis inverse. Math. Program. 13(1), 241–254 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bock, H.G.: Randwertproblemmethoden zur Parameteridentifizierung in Systemen nichtlinearer Differentialgleichungen, volume 183 of Bonner Mathematische Schriften. Universität Bonn, Bonn (1987)

    Google Scholar 

  7. Bock, H.G., Plitt, K.J.: A multiple shooting algorithm for direct solution of optimal control problems. In: Proceedings of the 9th IFAC World Congress, pages 242–247, Budapest, 1984. Pergamon Press. Available at http://www.iwr.uni-heidelberg.de/groups/agbock/FILES/Bock1984.pdf

  8. Bryson, A.E.: Applied Optimal Control: Optimization, Estimation and Control. CRC Press, Boca Raton (1975)

    Google Scholar 

  9. Byrd, R.H., Khalfan, H.F., Schnabel, R.B.: Analysis of a symmetric rank-one trust region method. SIAM J. Optim. 6(4), 1025–1039 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  10. Conn, A.R., Gould, N.I.M., Toint, PhL: Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comput. 50(182), 399–430 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  11. Conn, A.R., Gould, N.I.M., Toint, PhL: Convergence of quasi-Newton matrices generated by the symmetric rank one update. Math. Program. 50(1–3), 177–195 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  12. Conn, A.R., Gould, N.I.M., Toint, PhL: LANCELOT: A Fortran Package for Large-scale Nonlinear Optimization (Release A). Volume 17 of Springer Series in Computational Mathematics. Springer, Heidelberg (1992)

    Book  MATH  Google Scholar 

  13. Contreras, M., Tapia, R.A.: Sizing the BFGS and DFP updates: numerical study. J. Optim. Theory Appl. 78(1), 93–108 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  14. Cuthrell, J.E., Biegler, L.T.: Simultaneous optimization and solution methods for batch reactor control profiles. Comput. Chem. Eng. 13(1), 49–62 (1989)

    Article  Google Scholar 

  15. Diehl, M., Bock, H.G., Kostina, E.: An approximation technique for robust nonlinear optimization. Math. Program. 107, 213–230 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  16. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  17. Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization software with COPS 3.0. Argonne National Laboratory Technical Report ANL/MCS-TM-273 (2004)

  18. Duff, I.S.: MA57—a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30(2), 118–144 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  19. Ferreau, H.J., Bock, H.G., Diehl, M.: An online active set strategy to overcome the limitations of explicit MPC. Int. J. Robust Nonlinear Control 18(8), 816–830 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  20. Ferreau, H.J., Kirches, C., Potschka, A., Bock, H.G., Diehl, M.: qpOASES 3.0: a parametric active-set algorithm for quadratic programming. Math. Program. Comput. 6(4), 327–363 (2014)

  21. Fletcher, R.: Stable reduced hessian updates for indefinite quadratic programming. Math. Program. 87(2), 251–264 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  22. Forbes, J.: Model structure and adjustable parameter selection for operations optimizations. PhD thesis, McMaster University, Hamilton, Canada (1994)

  23. Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: A Schur-complement method for sparse quadratic programming. Technical report, Stanford Univ., CA (USA). Systems Optimization Lab. (1987)

  24. Gill, P.E., Wong, E.: Methods for convex and general quadratic programming. Technical report, University of California at San Diego (2013)

  25. Gould, N.I.M., Toint, PhL: An iterative working-set method for large-scale nonconvex quadratic programming. Appl. Numer. Math. 43(1), 109–128 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  26. Griewank, A., Toint, PhL: Local convergence analysis for partitioned quasi-Newton updates. Numerische Mathematik 39(3), 429–448 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  27. Griewank, A., Toint, PhL: Partitioned variable metric updates for large structured optimization problems. Numerische Mathematik 39(1), 119–137 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  28. Janka, D.: Optimum experimental design and multiple shooting. Diplomarbeit, Universität Heidelberg, Heidelberg (2010)

    Google Scholar 

  29. Janka, D.: Sequential quadratic programming with indefinite Hessian approximations for nonlinear optimum experimental design for parameter estimation in differential-algebraic equations. PhD thesis, Ruprecht-Karls-Universität Heidelberg, 2015. Available at http://archiv.ub.uni-heidelberg.de/volltextserver/19170/

  30. Khalfan, H.F., Byrd, R.H., Schnabel, R.B.: A theoretical and experimental study of the symmetric rank-one update. SIAM J. Optim. 3(1), 1–24 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  31. Körkel, S.: Numerische Methoden für Optimale Versuchsplanungsprobleme bei nichtlinearen DAE-Modellen. PhD thesis, Universität Heidelberg (2002)

  32. Körkel, S., Potschka, A., Bock, H.G., Sager, S.: A multiple shooting formulation for optimum experimental design. (2008). (submitted to Mathematical Programming, under review)

  33. Leineweber, D.B., Bauer, I., Schäfer, A.A.S., Bock, H.G., Schlöder, J.P.: An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization (parts I and II). Comput. Chem. Eng. 27, 157–174 (2003)

    Article  Google Scholar 

  34. Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, Berlin (2006). ISBN 0-387-30303-0 (hardcover)

  35. Oren, S.S., Luenberger, D.G.: Self-scaling variable metric (SSVM) algorithms part i: criteria and sufficient conditions for scaling a class of algorithms. Manag. Sci. 20(5), 845–862 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  36. Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1(1), 15–22 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  37. Plitt, K.J.: Ein superlinear konvergentes Mehrzielverfahren zur direkten Berechnung beschränkter optimaler Steuerungen. Diplomarbeit. Rheinische Friedrich-Wilhelms-Universität Bonn, Bonn (1981)

    Google Scholar 

  38. Powell, M.J.D.: The convergence of variable metric methods for non-linearly constrained optimization calculations. Nonlinear Program. 3, 27–63 (1978)

  39. Pukelsheim, F.: Optimal Design of Experiments. Classics in Applied Mathematics 50. SIAM (2006). ISBN 978-0-898716-04-7

  40. Sager, S.: On the Integration of Optimization Approaches for Mixed-Integer Nonlinear Optimal Control. Universität Heidelberg, August (2011). Habilitationsschrift

  41. Sager, S.: Sampling decisions in optimum experimental design in the light of Pontryagin’s maximum principle. SIAM J. Control Optim. 51(4), 3181–3207 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  42. Sager, S., Bock, H.G., Diehl, M., Reinelt, G., Schlöder, J.P.: Numerical methods for optimal control with binary control functions applied to a Lotka–Volterra type fishing problem. In: Seeger, A. (ed.) Recent Advances in Optimization, Volume 563 of Lectures Notes in Economics and Mathematical Systems, pp. 269–289. Springer, Heidelberg (2009). ISBN 978-3-5402-8257-0

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

    Article  MathSciNet  MATH  Google Scholar 

  44. Vassiliadis, V.S., Sargent, R.W.H., Pantelides, C.C.: Solution of a class of multistage dynamic optimization problems. Parts 1. and 2. Indus. Eng. Chem. Res. 10(33), 2111–2133 (1994)

    Article  Google Scholar 

  45. Wächter, A., Biegler, L.T.: Line search filter methods for nonlinear programming: motivation and global convergence. SIAM J. Optim. 16(1), 1–31 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  46. Wächter, A., Biegler, L.T.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors thank two anonymous referees and an anonymous technical editor for their constructive and helpful comments.

D. Janka and C. Kirches were supported by DFG Graduate School 220 (Heidelberg Graduate School of Mathematical and Computational Methods for the Sciences) funded by the German Excellence Initiative. D. Janka was supported by BASF SE within the junior research group experimental design. C. Kirches and S. Sager were supported by the German Federal Ministry of Education and Research program “Mathematics for Innovations in Industry and Service 2013–2016”, Grant No. 05M2013-GOSSIP. Financial support by the European Union within the 7th Framework Programme under Grant Agreement No 611909 is gratefully acknowledged. A. Wächter was supported in part by the National Science Foundation Grant DMS-1216920. Parts of this work were carried out during an appointment of D. Janka to Northwestern University.

Author information

Authors and Affiliations

  1. Interdisciplinary Center for Scientific Computing (IWR), Heidelberg University, Im Neuenheimer Feld 368, 69120, Heidelberg, Germany

    Dennis Janka & Christian Kirches

  2. Institute for Mathematical Optimization, Otto-von-Guericke-University Magdeburg, 39106, Magdeburg, Germany

    Sebastian Sager

  3. Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 60208, USA

    Andreas Wächter

Authors
  1. Dennis Janka
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christian Kirches
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sebastian Sager
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Andreas Wächter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dennis Janka.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Janka, D., Kirches, C., Sager, S. et al. An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix. Math. Prog. Comp. 8, 435–459 (2016). https://doi.org/10.1007/s12532-016-0101-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-016-0101-2

Keywords

Mathematics Subject Classification

Search

Navigation