摘要
在本文中,我们提出了一种解带有二次约束二次规划问题（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).
出处
《运筹学学报》
CSCD
北大核心
2002年第2期53-60,共8页
Operations Research Transactions
基金
This work is supported by NNSF of China 19971065.
关键词
二次约束二次规划
分枝定界
整体优化
拉格朗日松驰
拉格朗日对偶
投影次梯度方法
Branch-and-bound, Global optimization, Lagrangian slack, Lagrangian duality, Projection subgradient method, Quadratically constrained quadratic programs.
