凸约束非凸二次规划问题的分枝定界方法

针对凸约束非凸二次规划问题,给出了一个分枝定界方法。首先,我们构造一个多胞体包含可行域,然后根据凸集上非凸二次规划问题的整体最优解在可行域边界达到的性质,对锥所包含的可行域的边界构造一个包含它的超矩形体,并对这个超矩形体构造一个外接球。我们通过求解球约束非凸二次规划问题的整体最优解来确定下界,并把锥的棱与可行域的边界交点的目标函数值的最小值作为上界,把锥剖分技术与外逼近方法结合起来寻找原问题的整体最优解。最后,我们对这个方法进行收敛性分析。

A branch-and-bound method of non-convex quadratic programming problem with convex constraints

In this paper,a branch-and-bound method is proposed for non-convex quadratic programming problems with convex constrains.First,we construct a polyhedron containing the feasible field.Then,based on the property of which the global optimal solution of non-convex quadratic programming problems with convex constraints,we obtained the bound of the feasible field,a rectangle which contains the bound of the feasible field is constructed over a cone,and a circum-sphere is constructed over the rectangle.We determine a lower bound of the original problem over a cone by solving non-convex quadratic programming problem with ball constrains,considering the minimum of the objective function values of the intersection points of the cone edge and the bound of the feasible field as an upper bound of the original problem over a cone,and combining cone dissection with out-approximate method in order to find the global optimal solution of the original problem.Finally,the convergence of the algorithm is analyzed.