解非凸二次规划的分支定界缩减方法

An efficient branch-and-bound reduced algorithm for solving a class of non-convex quadratic programming

目的研究带有二次约束的非凸二次规划问题。方法采用二级松弛技术、超矩形缩减与剪支技术。结果与结论提出了确定该类问题全局最优值的分支定界缩减算法,并证明了算法是收敛的,并用数值算例验证了算法的可行性与有效性。

Purpose-To study a class of non-convex quadratic programming problem with quadrat- ic constraints. Methods-Two-level relaxation technique and a rectangular reduction-cut strategy are used to solve the aforesaid problem. Conclusion and Results-The convergence of the new algorithm is proved in addition to presenting a new braneh-and-bound reduced algorithm for determining the global optimal value. The feasibility and effectiveness of this algorithm are verified by numerical examples.