二次约束二次规划问题的二元均值松弛定界算法  

Relaxation and bounding algorithm based on binary mean inequality for quadratically constrained quadratic programming problems

作　　者：田福平 高岳林 孙滢 TIAN Fuping;GAO Yuelin;SUN Ying(School of Mathematics and Information Science,North Minzu University,Yinchuan 750021,China;School of Mathematics,Hefei University of Technology,Hefei 230601,China;Ningxia Collaborative Innovation Center for Scientific Computing and Intelligent Information Processing,Yinchuan 750021,China)

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

出　　处：《合肥工业大学学报（自然科学版）》2021年第1期137-144,共8页Journal of Hefei University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(11961001);宁夏高等教育一流学科建设基金资助项目(NXYLXK2017B09);北方民族大学研究生创新资助项目(YCX19124)

摘　　要：二次约束二次规划(quadratically constrained quadratic programming,QQP)问题目标函数和约束条件均是非凸的,是一类NP难问题,目前还没有通用的全局收敛准则,从而使得求该问题的全局最优解面临着严峻挑战。文章通过引入辅助乘积变量,将QQP问题等价地转化为带有乘积等式约束的非线性规划(nonlinear programming,NLP)问题;进而在NLP问题中利用二元均值不等式结合函数的性质松弛乘积等式约束后,产生QQP问题的带有辅助变量的松弛线性规划(relaxation linear programming,RLP)问题,由此确定QQP问题的全局最优值的下界,利用超矩形基于线性函数的缩减策略,以增强子超矩形的紧致删除能力;最后给出了该算法的收敛性分析,数值实验结果表明所提出的算法是可行且有效的。The objective function and constraints of quadratically constrained quadratic programming(QQP)are non-convex.It is a class of NP-hard problems.Up to now,there is no general global convergence criterion for solving general QQP,and it brings great challenges.In this paper,by introducing the auxiliary product variable,the QQP problem is equivalently transformed into the nonlinear programming(NLP)problem with product equality constraints.After using the binary mean inequality and the property of the function to relax the product equality constraint in the NLP problem,the relaxation linear programming(RLP)problem with auxiliary variables of the QQP problem is generated to determine the lower bound of the global optimal value of the QQP problem.The hyperrectangle based linear function reduction strategy is used to enhance the compact deletion ability of the subhyperrectangle.Finally,the convergence analysis of the algorithm is given,and the numerical experimental results show that the proposed algorithm is feasible and effective.

关 键 词：全局优化 二次约束二次规划(QQP) 分支定界方法 松弛技术 二元均值不等式 

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