Global Optimization Algorithm For Nonconvex Quadratic Optimization Problems

Quadratic programming problem is extensively used in economies of scale, fixed charges, finance, planning and scheduling, engineering design and so on. Due to the quadratic programming problem is abstracted from practical problem, generally speaking, it is non-convex problem. The characteristic of multiextremum of the nonconvex problem make it difficult to solve. In this paper, the methods are given for two types of nonconvex quadratic programming problems with linear constraints or quadratic constraints. More details as follows.The first chapter briefly introduces research background and research status, and concisely introduces our work in this paper.In the second chapter, a branch and reduce algorithm based on (DCA)(D.C.algorithm) for the nonconvex quadratic programming problem with linear constraint is given. First, by means of equivalent conversion to the prime problem, a separable optimization problem is obtained. Second, by region segmentation, determination of the upper bound and the lower bound and reducing box, the global optimum solution of the problem can be found, besides, initial upper bound of the problem is provided by (DCA). Last, numerical experiments indicate that the algorithm is feasible.In the third chapter, a branch and reduce algorithm based on the D.M.(difference of monotonic functions)function for the nonconvex quadratic programming problem with linear constraint is proposed. First, a optimization problem which the objective function is single argument and the constraints are D.M.function is obtained by means of equivalent conversion to the prime problem. Second, with the help of bounding process and prun-ing operations, the global optimum solution of the problem can be got. Last, numerical experiments indicate the feasibility of the algorithm.In the fourth chapter, a new algorithm for the nonconvex quadratic programming problem with quadratic constraint is presented. First, by introducing a new variable, an equivalent monotonic optimization problem which the objective function is single argument is obtained. Second, a convex programming problem is obtained by using of exponential transformation and relaxation approximate to the optimization problem after conversion, and the convex programming problem is easily to solve, thus we can get the approximate global optimum solution of the problem. Last, numerical experimental results show the feasibility and effectiveness of the algorithm.