Optimization Online


A Factorization with Update Procedures for a KKT Matrix Arising in Direct Optimal Control

Christian Kirches (christian.kirches***at***iwr.uni-heidelberg.de)
Hans Georg Bock (bock***at***iwr.uni-heidelberg.de)
Johannes P. Schlöder (schloeder***at***iwr.uni-heidelberg.de)
Sebastian Sager (sebastian.sager***at***iwr.uni-heidelberg.de)

Abstract: 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.

Keywords: optimal control, active set methods, matrix updates

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Nonlinear Optimization (Systems governed by Differential Equations Optimization )

Citation: Accepted for publication. To appear in Mathematical Programming Computation, vol. 3, no. 4, 2011. DOI 10.1007/s12532-011-0030-z


Entry Submitted: 11/11/2009
Entry Accepted: 11/11/2009
Entry Last Modified: 08/03/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society