(342c) Modified Mccormick Relaxation Rules for Handling Infeasibility in Relaxation-Based Iterative Domain Reduction Methods

McCormick’s relaxation technique is widely used for constructing lower bounding problems in global optimization. Specifically, this technique computes convex and concave relaxations of closed-form algebraic expressions and does so by recursively applying a set of rules for computing relaxations of elementary operations, such as the sum or product of two functions, based on relaxations of the operands. In this talk, we will discuss an extension of McCormick’s rules that provides meaningful results when the relaxations of the operands are improper in the sense that the convex relaxation lies above the concave relaxation on some or all of the domain. While such relaxations may seem nonsensical, they can be meaningful in some contexts. For example, in reduced-space global optimization, convex and concave relaxations of one set of (dependent) variables must be computed with respect to another set of (independent) variables. In this context, some iterative domain reduction methods under development in our research group can cause these relaxations to cross, indicating that the values of the independent variables at which they cross are infeasible. This gives rise to a new kind of relaxations that are only required to underestimate/overestimate a function on its feasible set. The ability to propagate such relaxations through further operations would enable relaxations of the objective function and constraints that can be considerably tighter than conventional relaxations, which at best underestimate/overestimate on the interval hull of the feasible set. Our preliminary experiments with global dynamic optimization problems indicate that this improvement can be substantial.

Unfortunately, relaxations of this type are not propagated properly using the standard definitions of McCormick’s rules. Specifically, if the convex and concave relaxations of an operand to some elementary operation cross at some points in their domain, then the standard McCormick rules can produce results that are nonconvex. To address this problem, we present modified rules for binary addition, binary multiplication, and composition with elementary univariate functions that (i) preserve the desired upper and lower bounding properties at any point in the domain where the input relaxations are properly ordered, and (ii) maintain convexity and concavity of the output relaxations for any convex and concave inputs, regardless of their bounding properties. These results are similar to the methods developed in [1] for constraint propagation using McCormick relaxations. However, infeasible points in the relaxation domain were handled in [1] by assigning the relaxations the value NaN at such points. In contrast, our new method assigns finite real values at all points in the domain while preserving convexity and concavity, which is critical for using such relaxations within numerical solvers (e.g., local optimization codes used to solve lower bounding problems or ODE solvers used to construct relaxations for global dynamic optimization). Therefore, these new rules are an important step for enabling the use of iterative relaxation refinement algorithms for effective domain reduction. Finally, we will present preliminary results showing significant improvements in relaxation quality for reduced space global optimization problems using refinement algorithms enabled by our new McCormick rules.

References

[1] Achim Wechsung, Joseph K. Scott, Harry A.J. Watson, and Paul I. Barton. Reverse propagation of McCormick relaxations. Journal of Global Optimization, 63(1):1–36, September 2015.