Unconstrained formulation of standard quadratic optimization problems

Immanuel M. Bomze ^[1] ; Luigi Grippo ^[2] ; Laura Palagi ^[2]
1. [1] University of Vienna
  
  University of Vienna
  
  Innere Stadt, Austria
2. [2] Università di Roma La Sapienza, Italia
Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 20, Nº. 1, 2012, págs. 35-51
Idioma: inglés
Enlaces
- Texto completo (pdf)
Resumen
- A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. We propose unconstrained reformulations of StQPs, by using different approaches. We test our method on clique problems from the DIMACS challenge.