黄小利，高岳林，谢金宵，谷剑峰

(1.北方民族大学数学与信息科学学院，宁夏 银川750021;2.宁夏科学计算与智能信息处理协同创新中心，宁夏 银川750021)

1.引言

本文主要考虑以下形式的二次约束二次规划问题:

这里fi(x)，i = 0，1，...，M是非凸二次函数.()n×n是n × n阶实对称矩阵，，εi∈R，i = 0，1，...，M，j = 1，...，n，q = 1，...，n，A ∈Rm×n，b ∈Rm，l0= (，...，T，u0=(，...，)T，X0为非空有界闭集，记H0= [l0，u0]，H0是超矩形.非凸二次约束二次规划(QCQP)问题在实际生活中应用范围广泛[1-4]，并且通常是全局优化问题，但在解决过程中往往存在许多局部最优解而不是全局最优解，且(QCQP)问题是一个NP-hard问题[5]，这就使得在理论和计算方面存在巨大的挑战.因此，寻找一种有效的算法全局求解(QCQP)问题是十分有必要的.从(QCQP)问题的研究历程来看，已经有许多算法都适用于求解全局(QCQP)问题，现如今分支定界算法已成为求解该问题最常用的工具之一.根据分支定界算法的框架，基于对(QCQP)问题的松弛，在分支定界树的每个节点求解松弛子问题的下界，得到一个高质量的下界对原问题起着至关重要的作用.目前的(QCQP)松弛方法建立在多种松弛技术上，包括基于凹凸包络的线性规划松弛[6-7]，拉格朗日对偶松弛[6，8]，基于二阶锥规划(SOCP)的松弛[9]，基于半定规划(SDP)的松弛[10].在求解盒约束非凸二次规划时，文[11]在有限分支中使用半定规划松弛技术.在求解带线性约束的非凸二次规划问题(LCQP)时，文[12]基于一阶KKT条件的有限分支和多面体半定松弛求解(LCQP).在求解带球和线性约束的非凸二次规划问题时，文[13]利用了半定规划松弛逼近非凸二次规划问……