A global optimality criterion for nonconvex quadratic programming over a simplex

In this paper we propose a global optimality criterion for globally minimizing a quadratic form over the standard simplex, which in addition provides a sharp lower bound for the optimal value. The approach is based on the solution of a semidefinite program (SDP) and a convex quadratic program (QP). Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the computational time for checking the global optimality criterion and for computing the lower bound is reasonable. Numerical experiments on random test examples up to 30 variables indicate that the optimality criterion verifies a global solution in almost all instances. (orig.)Available from TIB Hannover: RR 6329(98-18) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman