Branch-and-Lift Algorithm for Deterministic Global Optimization in Nonlinear Optimal Control
Branch-and-Lift Algorithm for Deterministic Global Optimization in Nonlinear Optimal Control
复制标题
DOI：
10.1007/s10957-013-0426-1
复制
发表时间：
2013-09
影响因子：
1.9
通讯作者：
B. Houska;B. Chachuat
中科院分区：
文献类型：
--
作者：
B. Houska;B. Chachuat
本文提出了一种分支提升算法，用于求解光滑非线性动力学、潜在非凸目标和约束函数保证全局最优的最优控制问题。该算法以一种通用的空间分支定界算法为基础，采用直接顺序法。引入了一种新的操作，称为提升，它通过Gram-Schmidt正交化过程来改进控制参数化，同时消除不可行或可证明不包含任何全局最优的控制子区域。给出了控制参数化误差在状态空间中的图像随着参数化阶数的增加呈指数收缩的条件，从而使提升操作高效。同时，提出了一种基于椭球体微积分的计算方法来满足这些条件。通过数值算例说明了支举法的实际应用。
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.