An efficient algorithm for globally minimizing sum of quadratic ratios problem with nonconvex quadratic constraints

摘要

In this paper a new branch and bound algorithm based on the rectangular partition and the Lagrangian relaxation for solving sum of quadratic ratios problem with nonconvex quadratic constraints (QSRP) is proposed. Firstly, the problem QSRP is converted into an equivalent sum of linear ratios problem with quadratic constraints (LSRP). Then, the bounding procedure is investigated by minimizing the restricted Lagrangian function of LSRP with a given estimate of the Lagrange multipliers. Minimizing a linear relaxation of the restricted Lagrangian overcomes the difficulty that the restricted Lagrangian is often nonconvex and facilitates the use of Lagrangian duality within a global optimization framework. In the algorithm, the interval Newton method is used to facilitate convergence in the neighborhood of the global solution. The proposed algorithm is convergent to the global minimum through the successive refinement of the solutions of a series of linear programming problems. Finally, numerical experiments are reported to show the efficiency of our algorithm.