Optimization Online


Efficient and cheap bounds for (standard) quadratic optimization

I.M. Bomze (immanuel.bomze***at***univie.ac.at)
M. Locatelli (locatell***at***di.unito.it)
F. Tardella (fabio.tardella***at***uniroma1.it)

Abstract: A standard quadratic optimization problem (StQP) consists in minimizing a quadratic form over a simplex. A number of problems can be transformed into a StQP, including the general quadratic problem over a polytope and the maximum clique problem in a graph. In this paper we present several 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.

Keywords: standard quadratic optimization, Semidefinite programming, quadratic programming, max clique, resource allocation

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Global Optimization (Applications )


Download: [PDF]

Entry Submitted: 07/13/2005
Entry Accepted: 07/13/2005
Entry Last Modified: 07/13/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society