解带有二次约束二次规划的一个整体优化方法(英文)

A Globally Optimal Method of Quadratic Programs with Quadratic Constraints

在本文中,我们提出了一种解带有二次约束二次规划问题（QP）的新算法.这种方法是基于单纯形分枝定界技术,其中包括极小极大问题和线性规划问题作为子问题.利用拉格朗日松弛和投影次梯度方法来确定问题（QP）最优值的下界.在问题（QP）的可行域是n维的条件下,如果这个算法有限步后终止,得到的点必是问题（QP）的整体最优解;否则,该算法产生的点的序列{vk}的每一个聚点也必是问题（QP）的整体最优解.

In this paper we present a new algorithm for solving quadratic programming problem (QP) with quadratic constraints. The method is based on a simplicity branch-and-bound scheme involving mainly max-min subproblems and linear programming subproblems. The lower bound of the optimal value of the problem (QP) is determined by Lagrangian slack and projection subgradient method. Under the assumption that the feasible region of the problem (QP) is n dimension, if the algorithm is terminated after finite step, the point obtained must be a global optimal solution of the problem, else each accumulation point of sequence {vk} which the algorithm produces must be a global optimization solution of the problem (QP).