一种求解二次约束二次规划问题的自适应全局优化算法  

An adaptive global optimization algorithm for solving quadratically constrained quadratic programming problems

作　　者：黄小利 高岳林 张博[1] 刘霞 HUANG Xiaoli;GAO Yuelin;ZHANG Bo;LIU Xia(School of Mathematics and Statistics,Ningxia University,Yinchuan 750021,Ningxia,China;Ningxia Province Cooperative Innovation Center of Scientific Computing and Intelligent Information Processing,North Minzu University,Yinchuan 750021,Ningxia,China)

机构地区：[1]宁夏大学数学统计学院,宁夏银川750021 [2]北方民族大学宁夏科学计算与智能信息处理协同创新中心,宁夏银川750021

出　　处：《运筹学学报》2022年第2期83-100,共18页Operations Research Transactions

基　　金：国家自然科学基金(No.11961001);宁夏高等教育一流学科建设基金(No.NXYLXK2017B09);北方民族大学重大专项(No.ZDZX201901)。

摘　　要：为了更好地解决二次约束二次规划问题(QCQP),本文基于分支定界算法框架提出了自适应线性松弛技术,在理论上证明了这种新的定界技术对于解决(QCQP)是可观的。文中分支操作采用条件二分法便于对矩形进行有效剖分;通过缩减技术删除不包含全局最优解的部分区域,以加快算法的收敛速度。最后,通过数值结果表明提出的算法是有效可行的。In order to better solve the quadratically constrained quadratic programming problem(QCQP),an adaptive linearized relaxation technique based on the framework of the branch and bound algorithm is proposed in this paper,which theoretically proved that this new delimitation technique is considerable for solving(QCQP).The branch operation in this paper adopts the conditional dichotomy to facilitate effective division of the rectangle;the reduction technique is used to delete some regions that do not contain the global optimal solution to speed up the convergence of the algorithm.Finally,the numerical results show that the proposed algorithm in this paper is effective and feasible.

关 键 词：二次约束二次规划 全局优化 分支定界 自适应线性松弛技术 条件二分法 

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