Quadratic reformulations of nonlinear binary optimization problems
Quadratic reformulations of nonlinear binary optimization problems
复制标题
DOI：
10.1007/s10107-016-1032-4
复制
发表时间：
2017-03-01
影响因子：
2.7
通讯作者：
Gruber, Aritanan
中科院分区：
文献类型：
--
作者：
Anthony, Martin;Boros, Endre;Gruber, Aritanan
大量的非线性无约束二元优化问题在广泛的应用中出现。当目标函数是二次多项式时，一些精确的或启发式的技术被证明非常成功地解决了许多这样的问题。然而，对于更高度的情况，没有类似的有效方法可用。由于高阶目标在某些应用领域变得越来越重要，例如计算机视觉，因此最近开发了各种技术，以通过引入额外的辅助变量来增加变量的数量，从而将一般情况简化为二次型情况。在本文中，我们对这些二次化方法进行了系统的研究。我们为一般目标函数、有界函数和有限类的二次化提供了在最坏情况下所需的辅助变量数量的严格下界和上界。我们的上界是建设性的，因此产生了新的二次化过程。最后，我们完全刻画了负单项式的所有“极小”二次化。
Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables by introducing additional auxiliary variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all "minimal" quadratizations of negative monomials.