Quadratic programs obtained for optimal control problems of dynamic or discrete--time processes usually involve highly block structured Hessian and constraints matrices. Efficient numerical methods for the solution of such QPs have to respect and exploit this block structure. 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. Preprocessing steps for the block structured QP data, such as provided by the condensing algorithm, have been successfully used in the past to ameliorate this situation. These approaches leave room for improvement if applied to control problems with longer horizons or with many control parameters. 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.
Citation
Accepted for publication. To appear in Mathematical Programming Computation, vol. 3, no. 4, 2011. DOI 10.1007/s12532-011-0030-z