×

Inexact Newton-type optimization with iterated sensitivities. (English) Zbl 1381.49028

Summary: This paper presents and analyzes an Inexact Newton-type optimization method based on Iterated Sensitivities (INIS). A particular class of NonLinear Programming (NLP) problems is considered, where a subset of the variables is defined by nonlinear equality constraints. The proposed algorithm considers any problem-specific approximation for the Jacobian of these constraints. Unlike other inexact Newton methods, the INIS-type optimization algorithm is shown to preserve the local convergence properties and the asymptotic contraction rate of the Newton-type scheme for the feasibility problem yielded by the same Jacobian approximation. The INIS approach results in a computational cost which can be made close to that of the standard inexact Newton implementation. In addition, an Adjoint-Free (AF-INIS) variant of the approach is presented which, under certain conditions, becomes considerably easier to implement than the adjoint based scheme. The applicability of these results is motivated specifically for dynamic optimization problems. In addition, the numerical performance of a corresponding open-source implementation is illustrated.

MSC:

49M15 Newton-type methods
90C30 Nonlinear programming
65M70 Spectral, collocation and related methods for initial value and initial-boundary value problems involving PDEs
49M20 Numerical methods of relaxation type
49M37 Numerical methods based on nonlinear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Albersmeyer and M. Diehl, {\it The lifted Newton method and its application in optimization}, SIAM J. Optim., 20 (2010), pp. 1655-1684. · Zbl 1198.90396
[2] J. Betts, {\it Practical Methods for Optimal Control and Estimation Using Nonlinear Programming}, 2nd ed., SIAM, Philadelphia, 2010. · Zbl 1189.49001
[3] T. A. Bickart, {\it An efficient solution process for implicit Runge-Kutta methods}, SIAM J. Numer. Anal., 14 (1977), pp. 1022-1027. · Zbl 0368.65037
[4] L. Biegler, O. Ghattas, M. Heinkenschloss, and B. van Bloemen Waanders, eds., {\it Large-Scale PDE-Constrained Optimization}, Lect. Notes Comput. Sci. Eng. 30, Springer-Verlag, Berlin, 2003. · Zbl 1021.00015
[5] L. T. Biegler, {\it Nonlinear Programming}, MOS-SIAM Ser. Optim., SIAM, Philadelphia, 2010. · Zbl 1207.90004
[6] H. Bock, {\it Randwertproblemmethoden zur Parameteridentifizierung in Systemen nichtlinearer Differentialgleichungen}, Bonner Math. Schrift. 183, Universität Bonn, Bonn, 1987. · Zbl 0622.65064
[7] H. Bock, W. Egartner, W. Kappis, and V. Schulz, {\it Practical shape optimization for turbine and compressor blades by the use of PRSQP methods}, Optim. Eng., 3 (2002), pp. 395-414. · Zbl 1079.90623
[8] H. G. Bock, {\it Recent Advances in Parameter Identification Techniques for ODE}, in Numerical Treatment of Inverse Problems in Differential and Integral Equations, Birkhäuser, Basel, 1983, pp. 95-121.
[9] H. G. Bock, M. Diehl, E. A. Kostina, and J. P. Schlöder, {\it Constrained optimal feedback control of systems governed by large differential algebraic equations}, in Real-Time and Online PDE-Constrained Optimization, SIAM, Philadelphia, 2007, pp. 3-22. · Zbl 1248.93071
[10] H. G. Bock and K. J. Plitt, {\it A multiple shooting algorithm for direct solution of optimal control problems}, in Proceedings of the IFAC World Congress, Pergamon Press, Oxford, 1984, pp. 242-247.
[11] P. T. Boggs and J. W. Tolle, {\it Sequential quadratic programming}, Acta Num., 4 (1995), pp. 1-51. · Zbl 0828.65060
[12] J. Butcher, {\it On the implementation of implicit Runge-Kutta methods}, BIT Numer. Math., 16 (1976), pp. 237-240. · Zbl 0336.65037
[13] G. Cooper and R. Vignesvaran, {\it Some schemes for the implementation of implicit Runge-Kutta methods}, J. Comput. Appl. Math., 45 (1993), pp. 213-225. · Zbl 0783.65064
[14] F. E. Curtis, T. C. Johnson, D. P. Robinson, and A. Wächter, {\it An inexact sequential quadratic optimization algorithm for nonlinear optimization}, SIAM J. Optim., 24 (2014), pp. 1041-1074. · Zbl 1311.90184
[15] F. E. Curtis, J. Nocedal, and A. Wächter, {\it A matrix-free algorithm for equality constrained optimization problems with rank-deficient Jacobians}, SIAM J. Optim., 20 (2009), pp. 1224-1249. · Zbl 1195.49035
[16] R. Dembo, S. Eisenstat, and T. Steihaug, {\it Inexact Newton methods}, SIAM J. Numer. Anal., 19 (1982), pp. 400-408. · Zbl 0478.65030
[17] J. E. Dennis, {\it On Newton-like methods}, Numer. Math., 11 (1968), pp. 324-330. · Zbl 0165.17303
[18] J. E. Dennis and J. J. Moré, {\it Quasi-Newton methods, motivation and theory}, SIAM Rev., 19 (1977), pp. 46-89. · Zbl 0356.65041
[19] P. Deuflhard, {\it Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms}, Springer Ser. Comput. Math. 35, Springer-Verlag, Berlin, 2011. · Zbl 1226.65043
[20] M. Diehl, {\it Lecture Notes on Numerical Optimization}, (2016).
[21] M. Diehl, H. G. Bock, J. Schlöder, R. Findeisen, Z. Nagy, and F. Allgöwer, {\it Real-time optimization and nonlinear model predictive control of processes governed by differential-algebraic equations}, J. Process Control, 12 (2002), pp. 577-585.
[22] M. Diehl, A. Walther, H. G. Bock, and E. Kostina, {\it An adjoint-based SQP algorithm with quasi-Newton Jacobian updates for inequality constrained optimization}, Optim. Methods Softw., 25 (2010), pp. 531-552. · Zbl 1197.49034
[23] H. J. Ferreau, C. Kirches, A. Potschka, H. G. Bock, and M. Diehl, {\it qpOASES: A parametric active-set algorithm for quadratic programming}, Math. Program. Comput., 6 (2014), pp. 327-363. · Zbl 1302.90146
[24] J. V. Frasch, S. Sager, and M. Diehl, {\it A parallel quadratic programming method for dynamic optimization problems}, Math. Program. Comput., 7 (2015), pp. 289-329. · Zbl 1321.90094
[25] G. Frison, H. B. Sorensen, B. Dammann, and J. B. Jørgensen, {\it High-performance small-scale solvers for linear model predictive control}, in Proceedings of the European Control Conference (ECC), June 2014, European Control Association, pp. 128-133.
[26] S. González-Pinto, J. I. Montijano, and L. Rández, {\it Iterative schemes for three-stage implicit Runge-Kutta methods}, Appl. Numer. Math., 17 (1995), pp. 363-382. · Zbl 0885.65086
[27] S. González-Pinto, S. Pérez-Rodríguez, and J. I. Montijano, {\it Implementation of high-order implicit Runge-Kutta methods}, Comput. Math. Appl., 41 (2001), pp. 1009-1024. · Zbl 0985.65086
[28] A. Griewank, {\it Evaluating derivatives, principles and techniques of algorithmic differentiation}, Front. Appl. Math. 19, SIAM, Philadelphia, 2000. · Zbl 0958.65028
[29] A. Griewank and A. Walther, {\it On constrained optimization by adjoint based quasi-Newton methods}, Optim. Methods Softw., 17 (2002), pp. 869-889. · Zbl 1065.90077
[30] M. Heinkenschloss and L. Vicente, {\it Analysis of inexact trust-region SQP algorithms}, SIAM J. Optim., 12 (2001), pp. 283-302. · Zbl 1035.90104
[31] B. Houska and M. Diehl, {\it A quadratically convergent inexact SQP method for optimal control of differential algebraic equations}, Optim. Control Appl. Methods, 34 (2013), pp. 396-414. · Zbl 1292.90223
[32] B. Houska, H. J. Ferreau, and M. Diehl, {\it ACADO toolkit – An open source framework for automatic control and dynamic optimization}, Optimal Control Appl. Methods, 32 (2011), pp. 298-312. · Zbl 1218.49002
[33] B. Houska, H. J. Ferreau, and M. Diehl, {\it An auto-generated real-time iteration algorithm for nonlinear MPC in the microsecond range}, Automatica, 47 (2011), pp. 2279-2285. · Zbl 1227.65054
[34] H. Jaeger and E. Sachs, {\it Global convergence of inexact reduced SQP methods}, Optim. Methods Softw., 7 (1997), pp. 83-110. · Zbl 0886.49025
[35] T. C. Johnson, C. Kirches, and A. Wächter, {\it An active-set method for quadratic programming based on sequential hot-starts}, SIAM J. Optim., 25 (2015), pp. 967-994. · Zbl 1327.90003
[36] F. Leibfritz and E. W. Sachs, {\it Inexact SQP interior point methods and large scale optimal control problems}, SIAM J. Control Optim., 38 (2006), pp. 272-293. · Zbl 0946.65047
[37] J. Nocedal and S. J. Wright, {\it Numerical Optimization}, 2nd ed., Springer Ser. Oper. Res. Financ. Eng., Springer-Verlag, Berlin, 2006. · Zbl 1104.65059
[38] A. Potschka, {\it Handling Path Constraints in a Direct Multiple Shooting Method for Optimal Control Problems}, Diplomarbeit, University of Heidelberg, Heidelberg, 2006.
[39] A. Potschka, {\it A Direct Method for the Numerical Solution of Optimization Problems with Time-Periodic PDE Constraints}, Ph.D. thesis, University of Heidelberg, Heidelberg, 2011. · Zbl 1237.65062
[40] A. Potschka, H. Bock, S. Engell, A. Küpper, and J. Schlöder, {\it Optimization of Periodic Adsorption Processes: The Newton-Picard Inexact SQP Method}, Preprint of DFG Priority Programme 1253: Optimization with Partial Differential Equations, SPP1253-01-01, 2008.
[41] R. Quirynen, {\it Numerical Simulation Methods for Embedded Optimization}, Ph.D. thesis, KU Leuven and University of Freiburg, 2017. · Zbl 1356.65158
[42] R. Quirynen, S. Gros, and M. Diehl, {\it Inexact Newton based lifted implicit integrators for fast nonlinear MPC}, in Proceedings of the IFAC Conference on Nonlinear Model Predictive Control (NMPC), 2015, International Federation of Automatic Control, pp. 32-38.
[43] R. Quirynen, S. Gros, and M. Diehl, {\it Lifted implicit integrators for direct optimal control}, in Proceedings of the IEEE Conference on Decision and Control (CDC), IEEE, Piscataway, NJ, 2015, pp. 3212-3217.
[44] R. Quirynen, S. Gros, B. Houska, and M. Diehl, {\it Lifted collocation integrators for direct optimal control in ACADO toolkit}, Math. Program. Comput., 9 (2017), pp. 527-571. · Zbl 1387.65057
[45] R. Quirynen, B. Houska, and M. Diehl, {\it Efficient symmetric Hessian propagation for direct optimal control}, J. Process Control, 50 (2017), pp. 19-28.
[46] S. Robinson, {\it Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear programming algorithms}, Math. Program., 7 (1974), pp. 1-16. · Zbl 0294.90078
[47] A. Walther and L. Biegler, {\it Numerical experiments with an inexact Jacobian trust-region algorithm}, Comput. Optim. Appl., 48 (2011), pp. 255-271. · Zbl 1219.90166
[48] A. Walther, S. R. R. Vetukuri, and L. T. Biegler, {\it A first-order convergence analysis of trust-region methods with inexact Jacobians and inequality constraints}, Optim. Methods Softw., 27 (2012), pp. 373-389. · Zbl 1242.90244
[49] L. Wirsching, H. G. Bock, and M. Diehl, {\it Fast NMPC of a chain of masses connected by springs}, in Proceedings of the IEEE International Conference on Control Applications, Munich, IEEE, Piscataway, NJ, 2006, pp. 591-596.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.