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

田福平, 高岳林,2, 孙 滢

(1.北方民族大学 数学与信息科学学院,宁夏 银川 750021; 2.合肥工业大学 数学学院,安徽 合肥 230601; 3.宁夏科学计算与智能信息处理协同创新中心,宁夏 银川 750021)

本文主要考虑的二次约束二次规划((quadratically constrained quadratic programming,QQP)问题形式如下:

其中:Qs=(qsij)n×n为实对称矩阵;cs∈Rn;ds∈R,s=0,1,2,…,N;i,j=1,2,…,n;A∈Rm×n;b∈R。QQP问题的可行域记为F,假设F是非空有界闭集。

一般二次约束二次规划问题是非线性规划(nonlinear programming,NLP)问题,它在很多领域都有广泛的应用,如无线通信、网络、雷达、信号处理等[1-2]。当QQP问题中的Q0,Q1,Q2,…,Qs均为半正定矩阵时,可以利用文献[3]中的二阶锥规划方法对其进行求解;另一方面,一些特殊的非凸QQP问题可以等价地转化为凸问题[4-6]。但是,一般二次约束二次规划问题通常是NP难问题,因此很难求到此类问题的全局最优解。

学者们提出了各种各样的用于求解非凸二次规划问题的分支定界算法[7-8]。同时,也有一些可以用来求解非凸QQP问题全局最优解的求解器,如SCIP、GloMIQO、Ipopt、ANTIGONE、BARON、COUENNE等。这些算法和求解器已经在某些类型的问题上有了十分良好的性能,如BARON、SCIP、COUENNE求解器对于求解具有稀疏参数的线性约束二次规划问题是非常有效的;文献[9]提出的算法可以有效地求解带有盒约束的二次规划问题;文献[7]提出的算法专门用于求解带有可分离约束的混合整数二次规划问题。但是对于一般的QQP问题,目前尚没有较好的求解方法。在利用分支定界算法求解极小化问题时最关键的是定下界,能否成功构造出最优值的下界序列对算法设计成功与否是至关重要的,定下界过程要求把下界问题转化为一系列尽可能简单并易于求解的松弛子问题。……