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

A Branch and Contract Algorithm for Nonconvex Quadratic Programs

基于非凸二次约束二次规划问题(QP)的松弛线性规划问题提出一种区域收缩策略以排除(QP)的可行域中不存在全局解的部分,然后结合区域收缩策略和分支定界方法针对问题(QP)给出收缩分支定界方法,数值计算表明算法是有效可行的。

A range contract strategy is proposed based upon a linear relaxation program of the nonconvex quadratically-constrained quadratic program（QP） to delete the subregions not containing the optimal solutions of（QP）.Then combining branch-and-bound scheme and the range contract strategy,a branch and contract algorithm is given for the problem（QP）.Finally numerical computation is given to illustrate the feasibility and efficiency of the proposed algorithm.