A clique algorithm for standard quadratic programming

A standard Quadratic Programming problem (StQP) consists in minimizing a (nonconvex) quadratic form over the standard simplex. For solving a SLQP we present an exact and a heuristic algorithm, that are based on new theoretical results for quadratic and convex optimization problems. With these results a StQP is reduced to a constrained nonlinear minimum weight clique problern in an associated graph. Such a Clique problem, which does not seem to have been Studied before, is then solved with all exact and a heuristic algorithm. Some computational experience shows that Our algorithms are able to solve StQP problems of at least one order of magnitude larger than those reported in the literature. (c) 2007 Elsevier B.V. All rights reserved.