Optimization Online


Block Structured Quadratic Programming for the Direct Multiple Shooting Method for 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: In this contribution we address the efficient solution of optimal control problems of dynamic processes with many controls. Such problems arise, e.g., from the outer convexification of integer control decisions. We treat this optimal control problem class using the direct multiple shooting method to discretize the optimal control problem. The resulting nonlinear problems are solved using sequential quadratic programming methods. We review the classical condensing algorithm that preprocesses the large but sparse quadratic programs to obtain small but dense ones. We show that this approach leaves room for improvement when applied in conjunction with outer convexification. To this end, we present a new complementary condensing algorithm for quadratic programs with many controls. This algorithm is based on a hybrid null--space range--space approach to exploit the block sparse structure of the quadratic programs that is due to direct multiple shooting. An assessment of the theoretical run time complexity reveals significant advantages of the proposed algorithm. We give a detailed account on the required number of floating point operations, depending on the process dimensions. Finally we demonstrate the merit of the new complementary condensing approach by comparing the behavior of both methods for a vehicle control problem in which the integer gear decision is convexified.

Keywords: Quadratic Programming, Mixed--Integer Optimal Control, Direct Multiple Shooting

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

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

Citation: Optimization Methods and Software, 26(2), pp. 239-257, April 2011 URL: http://www.informaworld.com/smpp/content~db=all~content=a919763304~frm=titlelink


Entry Submitted: 09/11/2009
Entry Accepted: 09/11/2009
Entry Last Modified: 02/22/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 Programming Society