Ivo Nowak
Some Heuristics and Test Problems 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 compare two methods for estimating a global minimizer of an indefinite quadratic form over a simplex. The first method is based on the enumeration of local minimizers of a so-called control polytope. The second method is based on an approximation of the convex envelope using semidefinite programming. In order to test the algorithms a method for generating random test problems is presented where the optimal solution is known and the number of binding constraints is prescribed. Moreover, it is investigated if some modifications of the objective function influence the performance of the algorithms. Numerical experiments are reported.
Keywords: global optimization, nonconvex quadratic programming, heuristics, Bezier methods, test problems