对大部分求最小值的二次约束二次规划问题来说,若其目标函数是非凸的,或者约束中存在非凸的约束条件,这个问题是NP-hard的。在本文中,我们主要关注二次约束二次规划中的一类特殊问题――双线性规划问题。本文的主要工作是提出双线性规划问题的一个非多项式时间求解算法。双线性规划问题(BP)是一类特殊的二次约束二次规划问题(QCQP),这类问题是NP-hard问题。双线性模型在现实中有许多应用:生产规划,动态识别,多代理规划等其他问题都可以被描述成双线性模型来求解。尽管近年来人们提出了很多求解二次约束二次规划问题的高效算法,但是专门针对双线性模型的算法很少被人关注。虽然我们可以用求解二次规划问题的通用算法来求解双线性规划问题,但是考虑到双线性模型的特殊结构,这将加大问题的维度,降低算法的效率。针对这一情况,本文的主要工作是提出了一个利用双线性规划问题的结构来对其求解的凸松弛迭代算法。算法的主要思路是借助双线性规划问题目标函数中的交叉项矩阵的奇异值分解,将一个双线性规划问题变形成了一个二次规划问题。之后,采用凸包松弛的方法来处理变形后的二次规划问题。经过一系列变形,算法最终得到了原问题的一个凸的二次约束二次规划松弛问题,这是一个可在多项式时间内求解的问题。与原问题相比,这个松弛问题中引入了O(n)个附加变量和线性约束。将这个凸松弛问题嵌入分支定界算法中,能够得到原双线性规划问题全局最优值的上界和下界序列。文章的第二部分主要证明了本文所提出的算法的正确性。我们证明了算法中得到原规划问题最优值的上界、下界序列将收敛到目标函数的最优值,并对求出给定精度范围内全局最优解所需的最大迭代步数做出了估计。文章第三部分展示的数值实验结果验证了本文提出的算法在求解高维双线性问题时有更高的效率。本文的创新点主要包括:?通过SVD分解降低了松弛问题的维度。?引入了由目标函数值确定分支策略的分支定界算法。?进行了高维数值实验,证明了我们的算法在求解高维问题时更为有效。