(78g) Novel Relaxations for Global Optimization

Fueled by applications across science and engineering, general-purpose deterministic global optimization algorithms have been developed for nonconvex nonlinear programs (NLPs) and mixed-integer nonlinear programs (MINLPs) over the past two decades. By building upon results from convex analysis, combinatorial optimization, and convex programming, these algorithms have already had a transformative impact in many areas, including engineering design, operations research, computer science, and computational biology. Yet, there exist vast classes of important applications that these algorithms are unable to address at the moment.

We address the problem that lies at the heart of spatial branch-and-bound algorithms, i.e., the construction of sharp relaxations. Current global optimization algorithms iteratively decompose nonconvex functions, through the introduction of variables and constraints for intermediate functional expressions, until the intermediate expressions can be outer-approximated by a convex feasible set. While it is easy to automate, this factorable programming technique often leads to weak relaxations. We propose novel relaxations that are obtained by generating convex and concave envelopes of nonconvex functions while minimizing, or even entirely eliminating, the steps of this factorable decomposition.

Explicit algebraic expressions for convex/concave envelopes are, in general, very difficult to obtain and are currently known only for simple univariate functions, bilinear, trilinear, fractional, and edge-concave functions. We present explicit formulas for convex envelopes of over 60% of the nonconvex functions that arise in several widely used collections of global optimization test problems. Extensive computational results with the new relaxations will be presented.