×

A factorization with update procedures for a KKT matrix arising in direct optimal control. (English) Zbl 1276.90046

Summary: Quadratic programs obtained for optimal control problems of dynamic or discrete-time processes usually involve highly block structured Hessian and constraints matrices, to be exploited by efficient numerical methods. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite factorization codes. For active set methods, however, conventional dense matrix techniques suffer from the need to update base matrices in every active set iteration, thereby loosing the sparsity structure after a few updates. This contribution presents a new factorization of a KKT matrix arising in active set methods for optimal control. It fully respects the block structure without any fill-in. For this factorization, matrix updates are derived for all cases of active set changes. This allows for the design of a highly efficient block structured active set method for optimal control and model predictive control problems with long horizons or many control parameters.

MSC:

90C20 Quadratic programming
90C30 Nonlinear programming
93B40 Computational methods in systems theory (MSC2010)
15A23 Factorization of matrices
65F05 Direct numerical methods for linear systems and matrix inversion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albersmeyer, J., Bock, H.: Efficient sensitivity generation for large scale dynamic systems. Technical report, SPP 1253 Preprints, University of Erlangen (2009)
[2] 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, 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia (1999) · Zbl 0934.65030
[3] Bartlett R., Biegler L.: QPSchur: a dual, active set, Schur complement method for large-scale and structured convex quadratic programming algorithm. Optim. Eng. 7, 5–32 (2006) · Zbl 1167.90615
[4] Bartlett, R., Wächter, A., Biegler, L.: Active set vs. interior point strategies for model predictive control. In: Proceedings of the American Control Conference, Chicago, IL, pp. 4229–4233 (2000)
[5] Benzi M., Golub G., Liesen J.: Numerical solution of saddle-point problems. Acta Numerica 14, 1–137 (2005) · Zbl 1115.65034
[6] Best M.: An algorithm for the solution of the parametric quadratic programming problem. In: Fischer, H., Riedmüller, B., Schäffler, S. (eds.) Applied Mathematics and Parallel Computing–Festschrift for Klaus Ritter, Chap. 3, pp. 57–76. Physica-Verlag, Heidelberg (1996) · Zbl 0906.65064
[7] Bock, H., Plitt, K.: A multiple shooting algorithm for direct solution of optimal control problems. In: Proceedings of the 9th IFAC World Congress, pp. 242–247. Pergamon Press, Budapest (1984)
[8] Bock H., Diehl M., Kostina E., Schlöder J.: Constrained optimal feedback control for DAE. In: Biegler, L., Ghattas, O., Heinkenschloss, M., Keyes, D., van Bloemen Waanders, B. (eds.) Real-Time PDE-Constrained Optimization, Chap. 1, pp. 3–24. SIAM, Philadelphia (2007) · Zbl 1248.93071
[9] Davis T.: Algorithm 832: UMFPACK–an unsymmetric-pattern multifrontal method with a column pre-ordering strategy. ACM Trans. Math. Softw. 30, 196–199 (2004) · Zbl 1072.65037
[10] Davis T., Hager W.: Multiple-rank modifications of a sparse Cholesky factorization. SIAM J. Matrix Anal. Appl. 22(4), 997–1013 (2000) · Zbl 1049.65021
[11] Diehl M., Bock H., Schlöder J., Findeisen R., Nagy Z., Allgöwer F.: Real-time optimization and nonlinear model predictive control of processes governed by differential-algebraic equations. J. Proc. Contr. 12(4), 577–585 (2002)
[12] Diehl M., Kuehl P., Bock H., Schlöder J.: Schnelle Algorithmen für die Zustands- und Parameterschätzung auf bewegten Horizonten. Automatisierungstechnik 54(12), 602–613 (2006)
[13] Duff I.: MA57–a code for the solution of sparse symmetric definite and indefinite systems. ACM Trans. Math. Softw. 30(2), 118–144 (2004) · Zbl 1070.65525
[14] Duff I., Reid J.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Softw. 9(3), 302–325 (1983) · Zbl 0515.65022
[15] Eldersveld S., Saunders M.: A block-LU update for large scale linear programming. SIAM J. Matrix Anal. Appl. 13, 191–201 (1992) · Zbl 0753.65050
[16] Ferreau H., Bock H., Diehl M.: An online active set strategy to overcome the limitations of explicit MPC. Int. J. Robust Nonlinear Control 18(8), 816–830 (2008) · Zbl 1284.93100
[17] Fletcher R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987) · Zbl 0905.65002
[18] Fletcher, R.: Resolving degeneracy in quadratic programming. Numerical Analysis Report NA/135, University of Dundee, Dundee, Scotland (1991) · Zbl 0796.90042
[19] Fletcher, R.: Approximation Theory and Optimization. Dense Factors of Sparse Matrices, pp. 145–166. Tributes to M.J.D. Powell. Cambridge University Press (1997) · Zbl 1031.65043
[20] Fletcher, R.: Numerical Analysis 1997. Block Triangular Orderings and Factors for Sparse Matrices in LP, pp. 91–110. Pitman Research Notes in Mathematics, vol. 380. Longman, Harlow (1998) · Zbl 0903.65022
[21] Gerdts M.: Solving mixed-integer optimal control problems by Branch&Bound: a case study from automobile test-driving with gear shift. Optimal Control Appl. Methods 26, 1–18 (2005)
[22] Gertz E., Wright S.: Object-oriented software for quadratic programming. ACM Trans. Math. Softw. 29, 58–81 (2003) · Zbl 1068.90586
[23] Gill P., Golub G., Murray W., Saunders M.A.: Methods for modifying matrix factorizations. Math. Comput. 28(126), 505–535 (1974) · Zbl 0289.65021
[24] Gill P., Murray W., Saunders M., Wright M.: Sparse matrix methods in optimization. SIAM J. Sci. Stat. Comput. 5(3), 562–589 (1984) · Zbl 0559.65042
[25] Gill P., Murray W., Saunders M., Wright M.: A practical anti-cycling procedure for linearly constrained optimization. Math. Program. 45(1–3), 437–474 (1989) · Zbl 0688.90038
[26] Gill P., Murray W., Saunders M., Wright M.: Inertia-controlling methods for general quadratic programming. SIAM Rev. 33(1), 1–36 (1991) · Zbl 0734.90062
[27] Gill, P., Murray, W., Saunders, M.: User’s Guide For QPOPT 1.0: A Fortran Package for Quadratic Programming (1995)
[28] Golub G., van Loan C.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[29] Hall J., McKinnon K.: The simplest examples where the simplex method cycles and conditions where the EXPAND method fails to prevent cycling. Math. Program. Ser. A & B 100(1), 133–150 (2004) · Zbl 1146.90473
[30] Han S.: Superlinearly convergent variable-metric algorithms for general nonlinear programming problems. Math. Program. 11, 263–282 (1976) · Zbl 0364.90097
[31] Haseltine E., Rawlings J.: Critical evaluation of extended Kalman filtering and moving-horizon estimation. Ind. Eng. Chem. Res. 44, 2451–2460 (2005)
[32] Huynh, H.: A large-scale quadratic programming solver based on block-LU updates of the KKT system. PhD thesis, Stanford University (2008)
[33] Kirches C., Sager S., Bock H., Schlöder J.: Time-optimal control of automobile test drives with gear shifts. Optimal Control Appl. Methods 31(2), 137–153 (2010) · Zbl 1204.49033
[34] Kirches C., Bock H., Schlöder J., Sager S.: Block structured quadratic programming for the direct multiple shooting method for optimal control. Optim. Methods Softw. 26(2), 239–257 (2011) · Zbl 1226.90139
[35] Leineweber D., Bauer I., Schäfer A., Bock H., Schlöder J.: 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)
[36] Nocedal J., Wright S.: Numerical Optimization, 2nd edn. Springer, Berlin, Heidelberg, New York (2006) · Zbl 1104.65059
[37] Powell M.: Algorithms for nonlinear constraints that use Lagrangian functions. Math. Program. 14(3), 224–248 (1978) · Zbl 0383.90092
[38] Powell, M.: ZQPCVX: a Fortran subroutine for convex quadratic programming. Technical report, Department of Applied Mathematics and Theoretical Physics, Cambridge University (1983)
[39] Schmid C., Biegler L.: Quadratic programming methods for tailored reduced Hessian SQP. Comput. Chem. Eng. 18(9), 817–832 (1994)
[40] Steinbach, M.: Fast recursive SQP methods for large-scale optimal control problems. PhD thesis, Ruprecht-Karls-Universität Heidelberg (1995) · Zbl 0826.49026
[41] Vanderbei R.: LOQO: an interior point code for quadratic programming. Optim. Methods Softw. 11(1–4), 451–484 (1999) · Zbl 0973.90518
[42] Wächter A., Biegler L.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25–57 (2006) · Zbl 1134.90542
[43] Wirsching, L., Albersmeyer, J., Kühl, P., Diehl, M., Bock, H.: An adjoint-based numerical method for fast nonlinear model predictive control. In: Chung, M., Misra, P. (eds.) Proceedings of the 17th IFAC World Congress, Seoul, Korea, July 6–11, 2008. IFAC-PapersOnLine, vol. 17, pp. 1934–1939 (2008)
[44] Wright, S.: Applying new optimization algorithms to model predictive control. In: Fifth International Conference on Chemical Process Control–CPC V, pp. 147–155. CACHE Publications (1997)
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.