On the impact of running intersection inequalities for globally solving polynomial optimization problems
On the impact of running intersection inequalities for globally solving polynomial optimization problems
复制标题
关于运行交集不等式对全局求解多项式优化问题的影响
DOI：
10.1007/s12532-019-00169-z
复制
发表时间：
2019
影响因子：
6.3
通讯作者：
Sahinidis, Nikolaos V.
中科院分区：
文献类型：
--
作者：
Del Pia, Alberto;Khajavirad, Aida;Sahinidis, Nikolaos V.
我们考虑全局优化的非凸问题，其可因式分解的重新包含一个集合的形式的多线性方程，其中E表示一组子集的基数至少有两个地面集。重要的特殊情况包括多线性和多项式优化问题。多线性多面体是满足上述多线性方程组的二元点集的凸船体。最近德尔皮亚和Khajavirad介绍了运行交叉不等式，家庭的面定义不等式的多线性多面体。在本文中，我们解决这类不等式的分离问题。我们首先证明了分离花不等式，运行的交集不等式的一个子类，是NP-困难的。随后，对于固定度的多线性多面体，我们设计了一个有效的多项式时间算法分离运行的交集不等式，并嵌入建议的切割平面生成计划在每个节点的分支和减少全球solverBARON。为了评估所提出的方法的有效性，我们考虑两个测试集：随机生成的多线性和多项式优化问题的程度三，四，和计算机视觉实例从图像恢复问题的结果表明，运行相交切割显着提高性能的BARON和导致平均CPU时间减少50%的随机测试集和63%的图像恢复测试集。
We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations of the form,, whereEdenotes a set of subsets of cardinality at least two of a ground set. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary pointszsatisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facet-defining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solverBARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance ofBARONand lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set.
登录
查看更多内容
DOI：
--
发表时间：
2010
期刊：
ArXiv
影响因子：
--
作者：
Mohit Tawarmalani
通讯作者：
Mohit Tawarmalani
影响因子：
2.7
作者：
Anthony, Martin;Boros, Endre;Gruber, Aritanan
通讯作者：
Gruber, Aritanan
影响因子：
2.7
作者：
Mohit Tawarmalani;Jean;Chuanhui Xiong
通讯作者：
Chuanhui Xiong
影响因子：
3.1
作者：
C. Buchheim;G. Rinaldi
通讯作者：
G. Rinaldi
具有正域或负域的三线性单项式：凸包络线和凹包络线的面
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
C. A. Meyer;C. Floudas
通讯作者：
C. Floudas