New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability

• 成果类型: Article
• 署名作者: Bomze, Immanuel M.; Locatelli, Marco; Tardella, Fabio
• 署名单位: Sapienza University Rome; University of Vienna; University of Turin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0138-0
• 发表日期: 2008
• 页码: 31-64
• 关键词: stability number; semidefinite; POLYNOMIALS; graph

摘要

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 Lovasz's theta function bound for the maximum size of a clique in a graph.