运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2008年
3期
75-82
,共8页
运筹学%全局优化%不定二次规划%分枝定界方法%凸松弛%拉格朗日松弛
運籌學%全跼優化%不定二次規劃%分枝定界方法%凸鬆弛%拉格朗日鬆弛
운주학%전국우화%불정이차규화%분지정계방법%철송이%랍격랑일송이
Operations research%global optimization%indefinite quadratic programming%branch-and-bound method%convex relaxation%Lagrangian relaxation
本文提出了一个求不定二次规划问题全局最优解的新算法.首先,给出了三种计算下界的方法:线性逼近法、凸松弛法和拉格朗日松弛法;并且证明了拉格朗日对偶界与通过凸松弛得到的下界是相等的;然后建立了基于拉格朗日对偶界和矩形两分法的分枝定界算法,并给出了初步的数值试验结果.
本文提齣瞭一箇求不定二次規劃問題全跼最優解的新算法.首先,給齣瞭三種計算下界的方法:線性逼近法、凸鬆弛法和拉格朗日鬆弛法;併且證明瞭拉格朗日對偶界與通過凸鬆弛得到的下界是相等的;然後建立瞭基于拉格朗日對偶界和矩形兩分法的分枝定界算法,併給齣瞭初步的數值試驗結果.
본문제출료일개구불정이차규화문제전국최우해적신산법.수선,급출료삼충계산하계적방법:선성핍근법、철송이법화랍격랑일송이법;병차증명료랍격랑일대우계여통과철송이득도적하계시상등적;연후건립료기우랍격랑일대우계화구형량분법적분지정계산법,병급출료초보적수치시험결과.
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.
