一种新的二次约束二次规划问题的分支定界算法  

A New Branch and Bound Algorithm for Quadratically Constrained Quadratic Programming Problem

作　　者：黄小利 高岳林 谢金宵 谷剑峰 HUANG Xiaoli;GAO Yuelin;XIE Jinxiao;GU Jianfeng(School of Mathematics and Information Science,North Minzu University,Yinchuan 750021,China;Ningxia Scienti c Computing and Intelligent Information Processing Co-Innovation Center,Yinchuan 750021,China)

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

出　　处：《应用数学》2021年第1期240-252,共13页Mathematica Applicata

基　　金：国家自然科学基金项目(11161001,61561001);宁夏高等教育一流学科建设基金(NXYLXK2017B09);北方民族大学研究生创新项目(YCX20103);北方民族大学重大专项(ZDZX201901)。

摘　　要：本文为了获得二次约束二次规划(QCQP)问题的全局最优解,提出一种新的参数化线性松弛分支定界算法.该算法利用参数化线性松弛技术,得到(QCQP)的全局最小值的下界,并利用区域缩减技术以最大限度地删除不可行区域,加快该算法的收敛速度.数值实验表明,本文提出的算法是有效并且可行的.In this paper,in order to obtain globally optimal solution of the quadratically constrained quadratic programming problem(QCQP),a new parametric linearized relaxation branch and bound algorithm is proposed.Our algorithm utilize the parametric linearized relaxation technique to get the lower bound of the global minimum value of(QCQP),using the region-reduction-technique to delete the infeasible region as much as possible in which can accelerate the convergence speed of the algorithm.The numerical experiments show that the proposed algorithm is effective and feasible.

关 键 词：二次约束二次规划 全局优化 分支定界 参数化线性松弛 区域缩减 

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