求不定二次规划问题全局解的新的分支定界算法  

New branch-and-bound algorithm for indefinite quadratic programming problems

作　　者：黎健玲[1] 王鹏[1] 马林[1] 李杰[1] 

机构地区：[1]广西大学数学与信息科学学院,广西南宁530004

出　　处：《广西大学学报（自然科学版）》2009年第4期561-564,共4页Journal of Guangxi University（Natural Science Edition）

基　　金：国家自然科学基金资助项目(10771040);广西科学基金资助项目(0728006);广西大学科研基金资助项目(X081016);广西研究生教育创新计划项目(2008105930701M066)

摘　　要：提出了求解不定二次规划问题一个新的分支定界算法。利用D.C.分解和正定阵的Cholesky分解把问题转化为可分离形式,并导出Lagrangian对偶界,给出基于Lagrangian对偶界和矩形对分的分支定界算法,同时给出初步数值实验结果。In this paper a new algorithm for finding a global solution of indefinite quadratic programming is proposed. The problem is first refermulated as a separable form by D.C. decomposition and Cholesky factorization. And then the Lagrangian dual bound is derived. A new branch-and-bound algorithm based on the Lagrangian dual bounds and rectangular bisection is presented. Finally, preliminary numerical results are reported.

关 键 词：不定二次规划 分支定界 D.C.分解 凸松弛 Lagrangian对偶界 

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