Trilinear Monomials with Positive or Negative Domains: Facets of the Convex and Concave Envelopes
Trilinear Monomials with Positive or Negative Domains: Facets of the Convex and Concave Envelopes
复制标题
具有正域或负域的三线性单项式：凸包络线和凹包络线的面
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
C. Floudas
中科院分区：
文献类型：
--
作者：
C. A. Meyer;C. Floudas
非凸函数凸包络的近似在确定性全局优化算法中起着核心作用，并且这些算法的效率很大程度上受到这些近似的紧密性的影响。 McCormick (1976)、AlKhayyal 和 Falk (1983) 已经展示了如何在矩形域上构造各个双线性项的凸包络。 Rikun (1997) 证明矩形域上的多线性单项式的凸包是多面体。高阶多重线性项的凸包络近似基于这种双线性构造的递归使用。然而，只有在非常特殊的情况下，这些近似才会产生凸包络本身。本文推导了定义三线性单项式的凸包络线和凹包络线的面的显式表达式，每个变量具有正或负有界域。
Approximations of the convex envelope of nonconvex functions play a central role in deterministic global optimization algorithms and the efficiency of these algorithms is highly infuenced by the tightness of these approximations. McCormick (1976), and AlKhayyal and Falk (1983) have shown how to construct the convex envelope of individual bilinear terms over a rectangular domain. Rikun (1997) has shown that the convex hull of multilinear monomials over a rectangular domain is polyhedral. Approximations of the convex envelope for higher order multilinear terms have been based on the recursive use of this bilinear construction. Only under very special circumstances, however, do these approximations yield the convex envelope itself. Explicit expressions defining the facets of the convex and concave envelopes for trilinear monomials, with positive or negative bounded domains for each variable, are derived in this paper.