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

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.

Citation

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

Article

Download

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