Solving Certain Nonconvex Quadratic Minimization Problems by Ranking the Extreme Points

Certain types of quadratic programs with linear constraints have the property that an extreme point of the convex set of feasible solutions is an optimal solution. This paper presents a procedure for solving these problems, it involves determining a related linear program having the same constraints, the extreme-point-ranking approach of Murty is then applied to this linear program to obtain an optimum solution to the quadratic program.