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.
A clique algorithm for standard quadratic programming / Andrea, Scozzari; Tardella, Fabio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 156:13(2008), pp. 2439-2448. (Intervento presentato al convegno 5th International Conference on Graphs and Optimization tenutosi a Leukerbad, SWITZERLAND nel AUG, 2006) [10.1016/j.dam.2007.09.020].
A clique algorithm for standard quadratic programming
TARDELLA, Fabio
2008
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
