(456d) Differentiable McCormick Relaxations for Global Optimization

Several deterministic methods for nonconvex optimization require lower bounding information that is typically obtained by minimizing convex underestimators of the objective function on appropriate subdomains. McCormick's relaxation scheme [1] is an established, efficient method for generating and computing appropriate convex underestimators of factorable functions, and was recently generalized and improved by Tsoukalas and Mitsos [2]. However, both McCormick's original scheme and the variant in [2] can produce underestimators that are nonsmooth, particularly when the relaxed functions employ products of nontrivial terms. This nonsmoothness necessitates the use of nonsmooth optimization solvers to evaluate lower bounds; such solvers exhibit poorer convergence properties and performance than their smooth counterparts.

This presentation describes conditions under which Tsoukalas and Mitsos's relaxation scheme is guaranteed to produce continuously differentiable relaxations, and shows how these conditions may be satisfied for any factorable function by modifying the treatment of products and other multivariate intrinsic functions. The result is a continuously differentiable variant of McCormick's relaxations that retain the various computational benefits of the established schemes: the new relaxations may be generated and evaluated automatically, cheaply, and accurately, and converge rapidly to the relaxed function as the considered domain is reduced in size. Gradients may be evaluated using standard automatic differentiation techniques, removing the need for dedicated subgradient propagation methods. The new relaxations remain differentiable even if the relaxed function is nonsmooth. Moreover, since the relaxations are generated in closed form, they may be employed in established methods for generating convex underestimators for implicit functions and the solutions of parametric ordinary differential equations.

This presentation focuses on the construction of the differentiable relaxations themselves; a case study in optimization of an offshore LNG production employing these relaxations is the topic of a separate presentation. An implementation in C++ based on the library MC++ [3] is described.

References:

[1]: G.P. McCormick, Computability of global solutions to factorable nonconvex programs: Part I - Convex underestimating problems. Math. Program., 10 (1976), pp. 147-175.

[2]: A. Tsoukalas and A. Mitsos, Multivariate McCormick relaxations. J. Glob. Optim., 59 (2014), pp. 633-662.

[3]: B. Chachuat, MC++: A toolkit for bounding factorable functions, https://projects.coin-or.org/MCpp