(10f) Improving the Tightness of State Relaxations for Global Dynamic Optimization through Refinement with Invariants

This talk will introduce the technique of using invariants to tighten the relaxations of solutions of parametric ODEs in dynamic models. Tight state relaxations in such dynamic settings ensure high efficiency in using branch-and-bound (B&B) to solve dynamic optimization (DO) problems to global optimality. Efficient solution of global dynamic optimization (GDO) problems is crucial in many applications, ranging from optimal control of batch reactions to aircraft trajectory tracking with rigorous safety guarantees. In terms of both computational time and relaxation tightness, relaxation preserving dynamics (RPD) [4] is one of the current state-of-the-art methods for computing state relaxations for GDO. It applies McCormick’s relaxation rules to relax the ODE right-hand side functions over a pre-computed interval enclosure of the possible ODE solutions. These relaxations are then used to form a relaxed system of ODEs that can be solved numerically to obtain relaxations of the original ODE solutions (i.e., state relaxations). Unfortunately, RPD produces weak relaxations in many cases. For the similar problem of computing constant upper and lower bounds on the possible ODE solutions (i.e., state bounds), it has been shown that much tighter enclosures can be obtained by using invariants relating the state variables whenever such invariants are available (e.g., conservation of mass or other reaction invariants). Specifically, such relations are used to continuously refine the computed bounds as they are propagated forward in time using various iterative methods [3, 5]. In contrast, no methods have yet been developed that can exploit invariants for tightening state relaxations. Thus, the ability to achieve tight state relaxations for GDO is still limited.

The analogy to state-bounding methods suggests that improved state relaxations might be achieved by (i) developing an iterative algorithm for refining pairs of convex/concave relaxations based on invariants, and (ii) embedding this algorithm within the RPD method such that the state relaxations are refined at each point in time before being propagated forward. However, due to technical details of RPD, this approach runs into considerable problems. Specifically, the combination of iterative relaxation refinement with RPD can (and often does) lead to intermediate variables where the convex underestimator lies above the concave overestimator on parts of the decision space. All further computations with these objects, known as ‘empty’ McCormick objects, are undefined using standard McCormick relaxation rules. This causes RPD to terminate unsuccessfully, or, if ignored, can lead to nonconvex state relaxations. Hence, the use of invariants to obtain tighter state relaxations has remained an unaddressed challenge.

In the 2020 AIChE meeting, we presented extended McCormick relaxation rules that are well defined for empty objects and preserve the desired convexity/concavity properties [2]. In the 2021 meeting, we presented an improved version of the RPD method (without invariants) that uses these rules to avoid some computationally undesirable details of the RPD method [1]. In this talk, we further utilize the extended McCormick rules to enable the use of invariant-based state relaxation refinement seamlessly within the RPD method. We then present preliminary results showing that state relaxations can indeed be made significantly tighter using this technique. Future work will apply these improved relaxations within B&B to maximize its efficiency in solving GDO problems.

References

[1] AIChE: An Improved Implementation of the RPD Method for Computing Convex Relaxations for Global Dynamic Optimization (2021)

[2] AIChE: Modified McCormick Relaxation Rules for Handling Infeasibility in Relaxation-Based Iterative Domain Reduction Methods (2020)

[3] Scott, J.K., Barton, P.I.: Bounds on the reachable sets of nonlinear control systems. Automatica 49(1), 93–100 (2013). DOI https://doi.org/10.1016/j.automatica.2012.09.020

[4] Scott, J.K., Barton, P.I.: Improved relaxations for the parametric solutions of odes using differential inequalities. Journal of Global Optimization 57, 143–176 (2013). DOI 10.1007/s10898-012-9909-0

[5] Shen, K.J., Scott, J.K.: Rapid and accurate reachability analysis for nonlinear dynamic systems by exploiting model redundancy. Computers and Chemical Engineering 106, 596–608 (2017). DOI 10.1016/j.compchemeng.2017.08.001