双线性规划问题的凸松弛求解方法研究

发布时间：2017-03-29 21:22

  本文关键词：双线性规划问题的凸松弛求解方法研究，，由笔耕文化传播整理发布。

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

• 摘要3-4
• Abstract4-8
• 第1章 引言8-13
• 1.1 选题背景和基础知识8-10
• 1.1.1 研究背景8-9
• 1.1.2 BP问题的分类9-10
• 1.2 研究现状10-13
• 1.2.1 连续可分离约束的情况10-11
• 1.2.2 连续联合约束的情况11
• 1.2.3 整数双线性规划的情况11-13
• 第2章 二次规划问题的发展13-19
• 2.1 非凸二次规划问题是NP-hard的13-14
• 2.2 半定规划松弛14
• 2.3 协正锥规划变形14-15
• 2.4 线性化重构方法15-16
• 2.5 凸包络处理技术16-19
• 第3章 双线性规划问题的二次规划松弛问题求解办法19-27
• 3.1 二次规划变形19-20
• 3.2 二次约束二次规划问题的松弛20-21
• 3.3 分支定界算法21-23
• 3.4 主要定理23-27
• 第4章 关于二次松弛和线性松弛的数值实验对比27-35
• 第5章 延伸与总结35-38
• 5.1 二次规划求解延伸35-36
• 5.2 总结36-38
• 致谢38-40
• 个人简历、在学期间发表的学术论文与研究成果40

【相似文献】

中国期刊全文数据库 前2条

1 陈高波,刘海燕,商胜武;一类双线性规划的线性逼近算法[J];西南交通大学学报;2002年05期

2 ;[J];;年期

中国重要会议论文全文数据库 前1条

1 高岳林;雷崇民;马小华;;一种连接双线性规划问题的整体优化[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

中国硕士学位论文全文数据库 前1条

1 姜珊;双线性规划问题的凸松弛求解方法研究[D];清华大学;2015年

  本文关键词：双线性规划问题的凸松弛求解方法研究，由笔耕文化传播整理发布。

本文编号：275473