(288h) Branch-and-Lift Algorithm for Deterministic Global Optimization in Nonlinear Optimal Control

Finding globally optimal solutions to nonlinear optimal control problems is a practically relevant, but challenging task. Although nonlinear optimal control methods and tools based on local optimization are satisfactory for many practical purposes, they can get trapped into local optima, possibly suboptimal by a large margin. Such situations can occur in the field of control of chemical and biochemical processes, as these processes can present complex and highly nonlinear behavior leading for instance to steady-state multiplicity. For such problems, it is often unclear how to initialize a local solver in order to find a control input leading to the best possible performance. Moreover, there are important classes of problems for which obtaining a certificate of global optimality is paramount, for instance in the field of robust or scenario-integrated optimization [1].

Existing global optimal control algorithms based on dynamic programming have run-times that scale exponentially with the number of differential states [2]. Global optimization algorithms based on direct methods, on the other hand, present worst-case run-times that scale exponentially with the number of optimization variables in the discretized NLP problem approximating the solution of the original optimal control problem [3-6]. Moreover, a priori parameterization of the control functions in direct methods does not allow control over the accuracy of a given parameterization, and therefore this approach is not suitable for rigorous search of globally optimal solutions in optimal control problems.

We present 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 spatial branch-and-bound algorithm in order to eliminate control subregions that are either infeasible or that provably cannot contain any global optima. A new operation, called lifting, is introduced, which enables systematic branching in the infinite-dimensional space of control functions by refining the control parameterization via a Gram-Schmidt orthogonalization process. We discuss conditions 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, and we present a computational technique based on ellipsoidal calculus that satisfies these conditions. We also analyze the convergence properties of the branch-and-lift algorithm. Finally, we illustrate the practical applicability of branch-and-lift with numerical examples.

References:

1. A. Mitsos, B. Chachuat, P.I. Barton, Towards global bilevel dynamic optimization, Journal of Global Optimization, 45:63-93, 2009.
2. L. Grune, and W. Semmler, Using dynamic programming with adaptive grid scheme to solve nonlinear dynamic models in economics, Computing in Economics and Finance, 99, 2002.
3. W.R. Esposito, and C.A. Floudas, Deterministic global optimization in nonlinear optimal control problems, Journal of Global Optimization, 17:97-126, 2000.
4. B. Chachuat, A.B. Singer, and P.I. Barton, Global methods for dynamic optimization and mixed-integer dynamic optimization, Industrial & Engineering Chemistry Research, 45(25):8373-8392, 2006.
5. Y. Lin, and M.A. Stadtherr, Deterministic global optimization of nonlinear dynamic systems, AIChE Journal, 53:866-875, 2007.
6. A.M. Sahlodin, Global Optimization of Dynamic Process Systems using Complete Search Methods, Ph.D. Thesis, McMaster University, December 2012.