A global optimization algorithm using linear relaxation

Various local optimization approaches have been developed for solving the non-convex quadratically constrained quadratic programs (QP). But up to now, less work has been devoted to solving global optimization of (QP) problem due to the inherent difficulty. This paper considers the global minimum of (QP) that arise in various practice problems. By utilizing the inherent property of the quadratic function an approximations a linear relaxation of (QP) is then obtained. Thus initial (QP) is reduced to a sequence of linear programming problems through the successive refinement of a linear relaxation of feasible region of the objective function. The proposed algorithm is convergent to the global minimum of (QP) by means of the subsequent solutions of a series of linear programming problems. Test results indicate that the proposed algorithm is extremely robust and can be used successfully to solve the global minimum of (QP) on a microcomputer.