Multivariate McCormick relaxations
Multivariate McCormick relaxations
复制标题
DOI：
10.1007/s10898-014-0176-0
复制
发表时间：
2014-04
影响因子：
1.8
通讯作者：
A. Tsoukalas;A. Mitsos
中科院分区：
文献类型：
--
作者：
A. Tsoukalas;A. Mitsos
McCormick（数学进展10(1):147-175,1976）通过函数积规则和单变量函数的组合形式，提供了可因式函数的凸/凹松弛的框架。本文将复合定理推广到允许多元外函数，并给出了子梯度的传播理论。推广将麦考密克松弛法解释为辅助变量法的分解方法。除了扩展了框架外，新结果还为证明特定函数的松弛性提供了一个工具。此外，一个直接的结果是两个函数乘积的松弛得到改善，至少和麦考密克的结果一样紧，而且常常更紧。该结果也允许函数的多线性积的直接松弛。此外，将组合结果应用于改进的最小/最大值凸低估器和电流松弛通常较弱的两个函数的划分。这些情况可以扩展到允许组合各种已经提出松弛的函数。
McCormick (Math Prog 10(1):147–175, 1976) provides the framework for convex/concave relaxations of factorable functions, via rules for the product of functions and compositions of the form, whereis a univariate function. Herein, the composition theorem is generalized to allow multivariate outer functions, and theory for the propagation of subgradients is presented. The generalization interprets the McCormick relaxation approach as a decomposition method for the auxiliary variable method. In addition to extending the framework, the new result provides a tool for the proof of relaxations of specific functions. Moreover, a direct consequence is an improved relaxation for the product of two functions, at least as tight as McCormick’s result, and often tighter. The result also allows the direct relaxation of multilinear products of functions. Furthermore, the composition result is applied to obtain improved convex underestimators for the minimum/maximum and the division of two functions for which current relaxations are often weak. These cases can be extended to allow composition of a variety of functions for which relaxations have been proposed.