带有二次约束的一般二次规划问题的松弛分枝定界方法
考虑带有二次约束的一般二次规划问题的求解,当约束条件为非凸二次函数时,对原问题中的某个二次约束进行凸二次松弛,或在原问题的约束条件中增加一个球约束,使得原问题的可行域包含在松弛二次规划问题的可行域内.采用椭球剖分策略剖分可行域为小的椭球,用投影次梯度算法解松弛二次规划问题的拉格朗日对偶问题,从而获得原问题的一个下界.原问题最优值的一个上界可从迭代过程中的可行点得到,并在迭代过程中得到调整.该算法或在原问题最优值的上下界相同时终止,得到原问题的整体最优解;或产生一无限序列,其任一聚点都是原问题的整体最优解.
作 者: 高岳林 徐成贤 作者单位: 西安交通大学理学院,710049,西安 刊 名: 西安交通大学学报 ISTIC EI PKU 英文刊名: JOURNAL OF XI'AN JIAOTONG UNIVERSITY 年,卷(期): 2002 36(8) 分类号: O212.2 关键词: 整体优化 分枝定界方法 拉格朗日对偶 投影次梯度方法