摘要
本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果.
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.
出处
《运筹学学报》
CSCD
北大核心
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.
关键词
运筹学
全局优化
不定二次规划
分枝定界方法
凸松弛
拉格朗日松弛
Operations research, global optimization, indefinite quadratic programming, branch-and-bound method, convex relaxation, Lagrangian relaxation
