带有二次约束的一般二次规划问题的松弛分枝定界方法

Relaxed Branch and Bound Method for General QuadraticProgramming Problems with Quadratic Constraints

考虑带有二次约束的一般二次规划问题的求解 ,当约束条件为非凸二次函数时 ,对原问题中的某个二次约束进行凸二次松弛 ,或在原问题的约束条件中增加一个球约束 ,使得原问题的可行域包含在松弛二次规划问题的可行域内 .采用椭球剖分策略剖分可行域为小的椭球 ,用投影次梯度算法解松弛二次规划问题的拉格朗日对偶问题 ,从而获得原问题的一个下界 .原问题最优值的一个上界可从迭代过程中的可行点得到 ,并在迭代过程中得到调整 .该算法或在原问题最优值的上下界相同时终止 ,得到原问题的整体最优解 ;或产生一无限序列 。

The solution of general quadratic programming problems with quadratic constraints is concerned. When all the quadratic constraints are not convex, a strategy is proposed either to relax one of the quadratic constraints into a convex quadratic constraint or to add a ball constraint in the original problem. The feasible region of the original problem is included in the feasible region of the relaxed quadratic programming problem. A projection subgradient algorithm for the Lagrangian dual problem of the relaxed quadratic problem is employed to general lower bounds of the optimal value for the original problem. An upper bound of the optimal value of the original problem is obtained and adjusted from the generated feasible points in the iteration process. The proposed algorithm either terminates after finite iteration when the upper and lower bounds of the optimal value are equal, or generates an infinite sequence and any convergent subsequence of the sequence gives a global solution of the problem.