Unconstrained formulation of standard quadratic optimization problems

Unconstrained formulation of standard quadratic optimization problems

0.00 Avg rating0 Votes
Article ID: iaor20123776
Volume: 20
Issue: 1
Start Page Number: 35
End Page Number: 51
Publication Date: Apr 2012
Journal: TOP
Authors: , ,
Keywords: graphs, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.