A new framework to relax composite functions in nonlinear programs
A new framework to relax composite functions in nonlinear programs
复制标题
DOI：
10.1007/s10107-020-01541-x
复制
发表时间：
2020-07
影响因子：
2.7
通讯作者：
Taotao He;Mohit Tawarmalani
中科院分区：
文献类型：
--
作者：
Taotao He;Mohit Tawarmalani
在本文中，我们为复合函数设计了新的松弛，通过利用内部函数结构，改进了普遍的可分解松弛，而无需引入额外的变量。我们使用任意的欠估计器和高估计器对内部函数进行外部近似，然后在多面体上凸化外部函数，该多胞体对内部函数及其估计器之间的排序关系进行建模，并利用内部函数以及估计器上的绑定信息。我们证明存在一个子集 QofP，其组合结构要简单得多，因此通过快速组合算法，外函数 overPi 的图的分离问题多项式等价于其图 overQ 的分离问题。我们的研究专门考虑两个内部函数的乘积，每个内部函数都有一个非平凡的低估量。对于相应的多胞形P，我们证明除了四个麦考密克不等式之外，还有八个有效的不等式，这提高了可因式松弛。最后，我们表明我们的结果可以推广到外部函数向量的同时凸化。
In this paper, we devise new relaxations for composite functions, which improve the prevalent factorable relaxations, without introducing additional variables, by exploiting the inner-function structure. We outer-approximate inner-functions using arbitrary under- and over-estimators and then convexify the outer-function over a polytopeP, which models the ordering relationships between the inner-functions and their estimators and utilizes bound information on the inner-functions as well as on the estimators. We show that there is a subsetQofP, with significantly simpler combinatorial structure, such that the separation problem of the graph of the outer-function overPis polynomially equivalent, via a fast combinatorial algorithm, to that of its graph overQ. We specialize our study to consider the product of two inner-functions with one non-trivial underestimator for each inner-function. For the corresponding polytopeP, we show that there are eight valid inequalities besides the four McCormick inequalities, which improve the factorable relaxation. Finally, we show that our results generalize to simultaneous convexification of a vector of outer-functions.