求不定二次规划全局解的一个新算法(英文)  

A New Algorithm for Finding Global Solution of Indefinite Quadratic Programming Problems

作　　者：黎健玲[1] 孙小玲[2] 

机构地区：[1]广西大学数学与信息科学学院,南宁530004 [2]复旦大学管理学院,上海200433

出　　处：《运筹学学报》2008年第3期75-82,共8页Operations Research Transactions

基　　金：National Natural Science Foundation of China under grants 70671064,10771040;Guangxi Science Foundation(No. 0726006,0640001);the Scientific Research Foundation of Guangxi University(No.X081016)of China.

摘　　要：本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果.In this paper we propose a new algorithm for finding a global solution of indefinite quadratic programming problems. We first derive three lower bounding techniques： linear approximation, convex relaxation and Lagrangian relaxation. We prove that the Lagrangian dual bound is identical to the lower bound obtained by convex relaxation. A branch-and-bound algorithm based on the Lagrangian lower bounds and rectangular bisection is then presented with preliminary computational results.

关 键 词：运筹学 全局优化 不定二次规划 分枝定界方法 凸松弛 拉格朗日松弛 

分 类 号：O224[理学—运筹学与控制论] O221.2[理学—数学]