Tightening state relaxations for global dynamic optimization using dynamic cuts

The ability to compute tight convex and concave relaxations of the parametric solutions of ordinary differential equations (i.e., state relaxations) is essential for efficiently solving global dynamic optimization (GDO) problems using spatial branch-and-bound (B&B). The use of cutting planes derived through various techniques is often critical for obtaining tight relaxations for conventional nonlinear programs (NLPs), but has not previously been proposed for GDO (without prior approximation as an NLP). This paper considers the use of dynamic cuts to tighten state relaxations. We present new theoretical results that enable the use of refinements based on dynamic cuts within an existing state-of-the-art state relaxation method, resulting in substantially tighter relaxations. We then develop a specific numerical implementation of this theory for the case of affine cuts. Numerical experiments on two examples show that using dynamic cuts can lead to much tighter relaxations with a moderate increase in computational cost. The results show good potential for the improved accuracy to outweigh the increased cost when implemented in B&B solvers for GDO. Such an implementation, however, requires further work to develop a method for evaluating subgradients of the proposed relaxations, which is not addressed herein.