Unconstrained formulation of standard quadratic optimization problems

Authors

  • Immanuel M Bomze Dept. of Statistics and Decision Support Systems, University of Vienna,
  • Luigi Grippo Dipartimento Informatica e Sistemistica "Antonio Ruberti"
  • Laura Palagi Dipartimento Informatica e Sistemistica "Antonio Ruberti"

Keywords:

standard quadratic optimization, maximum clique, exact penalization

Abstract

A standard quadratic optimization problem (StQP) consists of nding the largest or smallest value of a (possibly indenite) 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 dierent approaches. We test our method on clique problems from the DIMACS challenge.

Downloads

How to Cite

Bomze, I. M., Grippo, L., & Palagi, L. (2010). Unconstrained formulation of standard quadratic optimization problems. Department of Computer and System Sciences Antonio Ruberti Technical Reports, 2(12), 16. Retrieved from https://rosa.uniroma1.it/rosa00/index.php/dis_technical_reports/article/view/8902