Branch-and-Lift Algorithm for Deterministic Global Optimization in Nonlinear Optimal Control
File(s)JOTA-D-12-00631R4.pdf (950.64 KB)
Accepted version
Author(s)
Houska, B
Chachuat, B
Type
Journal Article
Abstract
This paper presents a branch-and-lift algorithm for solving optimal control problems with smooth nonlinear dynamics and potentially nonconvex objective and constraint functionals to guaranteed global optimality. This algorithm features a direct sequential method and builds upon a generic, spatial branch-and-bound algorithm. A new operation, called lifting, is introduced, which refines the control parameterization via a Gram-Schmidt orthogonalization process, while simultaneously eliminating control subregions that are either infeasible or that provably cannot contain any global optima. Conditions are given under which the image of the control parameterization error in the state space contracts exponentially as the parameterization order is increased, thereby making the lifting operation efficient. A computational technique based on ellipsoidal calculus is also developed that satisfies these conditions. The practical applicability of branch-and-lift is illustrated in a numerical example. © 2013 Springer Science+Business Media New York.
Date Issued
2014-07-01
Date Acceptance
2013-09-06
Citation
Journal of Optimization Theory and Applications, 2014, 162 (1), pp.208-248
ISSN
0022-3239
Start Page
208
End Page
248
Journal / Book Title
Journal of Optimization Theory and Applications
Volume
162
Issue
1
Copyright Statement
The final publication is available at Springer via http://link.springer.com/article/10.1007%2Fs10957-013-0426-1
Publication Status
Published
Date Publish Online
2013-09-21