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.

New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability / I., Bomze; Locatelli, Marco; F., Tardella. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - Vol. 115:(2008), pp. 31-64. [10.1007/s10107-007-0138-0]

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

LOCATELLI, Marco;
2008-01-01

Abstract

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.
2008
New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability / I., Bomze; Locatelli, Marco; F., Tardella. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - Vol. 115:(2008), pp. 31-64. [10.1007/s10107-007-0138-0]
File in questo prodotto:
File Dimensione Formato  
MathSciNet2403752.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Creative commons
Dimensione 50.04 kB
Formato Adobe PDF
50.04 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
MP_stqp.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 389.02 kB
Formato Adobe PDF
389.02 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2292497
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 49
  • ???jsp.display-item.citation.isi??? 48
social impact