摘要
针对凸约束非凸二次规划问题,给出了一个分枝定界方法。首先,我们构造一个多胞体包含可行域,然后根据凸集上非凸二次规划问题的整体最优解在可行域边界达到的性质,对锥所包含的可行域的边界构造一个包含它的超矩形体,并对这个超矩形体构造一个外接球。我们通过求解球约束非凸二次规划问题的整体最优解来确定下界,并把锥的棱与可行域的边界交点的目标函数值的最小值作为上界,把锥剖分技术与外逼近方法结合起来寻找原问题的整体最优解。最后,我们对这个方法进行收敛性分析。
In this paper, a branch -and -bound method is p 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.
出处
《沈阳航空工业学院学报》
2007年第3期89-92,共4页
Journal of Shenyang Institute of Aeronautical Engineering
关键词
非凸二次规划
分枝定界方法
锥剖分
整体优化
凸约束
球约束
Non - convex quadratic program
Branch - and - bound method
Cone dissection
Global optimization
Convex constrains
Ball constraints
