New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
复制标题
DOI：
10.1007/s10107-007-0138-0
复制
发表时间：
2008-05
影响因子：
2.7
通讯作者：
I. Bomze;M. Locatelli;F. Tardella
中科院分区：
文献类型：
--
作者：
I. Bomze;M. Locatelli;F. Tardella
标准的二次优化问题（StQP）包括最小化单纯形上的二次形式。其中的问题，可以转化为一个StQP是一般的二次问题的多面体，和最大团的问题，在一个图。在本文中，我们提出了几个新的多项式时间范围StQP从非常简单和便宜的更复杂和紧凑的结构。在大多数界限的概念和分析中使用的主要工具是半定规划和将目标函数分解为两个二次函数的和，每个二次函数都很容易最小化。我们提供了一个完整的图表的优势，不可比性，或等价关系之间的界限，在这方面和以前的作品。特别是，我们表明，我们的一个新的界限支配所有其他的。此外，这种界限的特殊化支配着Schrijver对图中团的最大大小的Lovász θ函数界限的改进。
A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. Among the problems which can be transformed into a StQP are the general quadratic problem over a polytope, and the maximum clique problem in a graph. In this paper we present several new polynomial-time bounds for StQP ranging from very simple and cheap ones to more complex and tight constructions. The main tools employed in the conception and analysis of most bounds are Semidefinite Programming and decomposition of the objective function into a sum of two quadratic functions, each of which is easy to minimize. We provide a complete diagram of the dominance, incomparability, or equivalence relations among the bounds proposed in this and in previous works. In particular, we show that one of our new bounds dominates all the others. Furthermore, a specialization of such bound dominates Schrijver’s improvement of Lovász’sθfunction bound for the maximum size of a clique in a graph.