Optimization Online


Branch-and-Lift Algorithm for Deterministic Global Optimization in Nonlinear Optimal Control

Boris Houska (b.houska***at***imperial.ac.uk)
Benoit Chachuat (b.chachuat***at***imperial.ac.uk)

Abstract: This paper presents a branch-and-lift algorithm for solving optimal control problems with smooth nonlinear dynamics and nonconvex objective and constraint functionals to guaranteed global optimality. This algorithm features a direct sequential method and builds upon a 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. This paper also contributes the development of an ellipsoidal set-propagation technique for bounding the effect of control parameterization on the response of a dynamic system. Conditions are given under which these ellipsoidal bounds contract exponentially when refining the control parameterization, thereby making the lifting operation efficient. The advantages of the proposed method are illustrated through numerical examples.

Keywords: Optimal Control; Dynamic Optimization; Dynamic Systems; Deterministic Global Optimization; Spatial Branch-and-Bound; Ellipsoidal Calculus

Category 1: Global Optimization (Theory )

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

Citation: Centre for Process systems Engineering, Imperial College London, August 2012

Download: [PDF]

Entry Submitted: 09/03/2012
Entry Accepted: 09/03/2012
Entry Last Modified: 07/23/2013

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