Ivo Nowak
A Global Optimality Criterion for Nonconvex Quadratic Programming over a Simplex
Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976)

MSC:

90C20 Quadratic programming

90C30 Nonlinear programming

90C06 Large-scale problems

65K05 Mathematical programming, See also {90Cxx}

Abstract: 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.
Keywords: global optimality criterion, nonconvex quadratic programming, semidefinite programming