Abstract: In this paper，by using a technique for reducing the duality gap，a new branch and bound algorithm is developed for quadratic programming global minimization.The major improvement of the new algorithm is that the algorithm uses Lagrangian duality to obtain lower bounds.In the last，two different algorithms（namely，the proposed algorithm，the traditional branch and bound algorithm）have been implemented for same construction problems and random instances.Computation results indicate that the proposed algorithm can solve large-scale nonconvex quadratic problems.

摘要： 针对求解多面集上二次函数的全局近似最优解问题，利用逐步缩小对偶间隙的处理办法，提出了一个新型分枝定界算法。新算法的主要改进之处是利用了Lagrange 对偶性获取下界。最后,用构造和随机产生的问题实例,对提出的新算法和传统的分枝定界算法做了初步的数值比较实验。计算实验表明算法对求解中大规模非凸二次规划问题的有效性。