Global minimization algorithms for concave quadratic programming problems

In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by Dür, Horst & Locatelli and Hirart-Urruty & Ledyav, we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.