(398e) Convex Relaxation of Multivariate Compositions

McCormick relaxations [1] provide the framework for the computation of convex relaxations of composite functions. McCormick's relaxations are clearly a very important tool, but they have the limitation of only allowing univariate composition. Although most functions can be decomposed in a way that only univariate functions are used as building blocks, this often results in weak relaxations.

We propose a reformulation of McCormick's composition theorem, which while equivalent to the original, suggests a straight forward generalization to multi-variate outer functions. In addition to extending the framework, the multi-variate McCormick relaxation is a useful tool for the proof of relaxations: by direct application to the product, division and minimum/maximum of two functions, we obtain improved relaxations when comparing with uni-variate McCormick.

Furthermore, we generalize the theory for the computation of subgradients [2] to the multi-variate case, envisioning practical methods that utilize the framework. Finally, our approach suggests that an algorithm operating directly on recursively obtained McCormick relaxations, can be seen as a decomposition method for the auxiliary variable method (AVM) [3,4]. This interpretation suggests hybrid methods, which can eliminate the disadvantage of the potentially weaker relaxations due to repeated terms in McCormick's framework with minimal increase to the dimension of the optimization space.

[1] G. P. McCormick. “Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems.” Mathematical Programming, 10(1):147–175, 1976.

[2] A. Mitsos, B. Chachuat, and P. I. Barton. “McCormick-based relaxations of algorithms”. SIAM Journal on Optimization, 20(2):573–601, 2009.

[3] E. Smith and C.C. Pantelides. “Global optimisation of nonconvex minlps.” Computers & Chemical Engineering, 21:791–796, 1997.

[4] E. Smith and C. C. Pantelides. “A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex minlps.” Computers & Chemical Engineering, 23(4-5):457–478, 1999.