(227d) An Improved Implementation of the Rpd Method for Computing Convex Relaxations for Global Dynamic Optimization

This talk will present a new modification of an existing method for computing relaxations of the solutions of parametric ODEs based on the theory of relaxation preserving dynamics (RPD). Such relaxations are essential for solving dynamic optimization problems to guaranteed global optimality, which has important applications in optimal control, parameter estimation, batch process design, and more. In the basic RPD approach, McCormick’s relaxation technique is used to compute relaxations of 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). Although a variety of methods have been proposed for computing state relaxations, we focus on the RPD method because it remains among the state-of-the-art methods in terms of both computational efficiency and relaxation tightness.

Unfortunately, the existing implementation of RPD has a significant drawback. Owing to some technical details of RPD theory, and the interaction of these details with technical requirements of McCormick’s relaxation technique, existing RPD implementations must solve a relaxed system of ODEs that is discontinuous (i.e., a hybrid system). This is numerically undesirable because it adds computational cost and because event detection can be sensitive to numerical errors, making the method potentially too unreliable for use in branch-and-bound codes. More seriously, this hybrid system implementation makes it impossible to compute valid sensitivities using any known theory. This is critical because sensitivities are needed to effectively minimize the constructed relaxations, or (more often) to construct affine relaxations that are cheaper to solve. Thus, it is highly desirable to develop an alternative implementation of RPD that avoids the need to solve a hybrid system.

Careful examination of the RPD method shows that, if the hybrid switching conditions are removed, then intermediate calculations during the solution of the relaxed ODEs may require computations with `empty’ McCormick objects. By `empty’ McCormick objects, we refer to relaxations of intermediate variables where the convex underestimator lies above the concave overestimator (representing a kind of infeasibility). This is problematic because McCormick’s relaxation rules are not defined in this case, and straightforward extensions of them will lead to nonconvex results. In this talk, we present extended definitions of McCormick’s rules that produce identical results as the original rules for nonempty input McCormick objects, but are also well-defined and guarantee certain convexity properties when empty input McCormick objects are used in their computation. These new rules are then used to develop a new implementation of RPD that no longer requires a hybrid system. The resulting implementation is simpler, more efficient, more numerically stable, and allows sensitivities to be computed straightforwardly, all of which make these relaxations much more desirable for use in global dynamic optimization algorithms. Moreover, this same theory can be leveraged to enable refinements based on invariants and dynamic cuts, which can lead to much tighter relaxations.