二次约束二次规划非升维条件下的松弛理论及算法

发布时间：2017-05-18 12:01

  本文关键词：二次约束二次规划非升维条件下的松弛理论及算法，由笔耕文化传播整理发布。

【摘要】：二次约束二次规划(QCQP)问题可描述系列离散优化和连续优化问题,如组合优化中的最大割、最大团、0-1二次背包问题,经典的线性规划、金融投资领域的马科维茨方差—均值模型等。因此对QCQP问题的研究有着重要的理论和应用价值。当QCQP问题的目标函数及约束函数都是凸函数时,该问题可以结合内点算法在多项式时间内求解,但一般的QCQP问题已被证明为NPH问题。针对QCQP问题目前有多个研究热点,但主要集中在问题的松弛及估界、最优解的判定条件、寻找多项式时间内的可解子问题类、设计全局最优搜索算法。在一般的QCQP问题的研究中,最常用的工具是SDP松弛和拉格朗日对偶理论,此外也常将RLT不等式加入到SDP松弛中,且往往这种处理方式比单独用SDP松弛或RLT不等式的效果都要好。本文首先就QCQP问题的研究背景、意义、目前的研究热点、常用的处理方法进行了简单的介绍,之后本文研究了凸约束下的非凸二次规划问题在不升维下的凸松弛方法,并设计了求解这类QCQP问题全局最优解的算法,接着从理论上给出了算法的收敛性及最坏情形下的迭代次数,同时通过求解一些随机算例将本文算法同SDP松弛下的分支定界算法进行了对比。数值结果表明当问题维度及负特征根个数较少时本文算法具有一定的优势。然后本文研究了有界区域上的一般的QCQP问题,给出了不升维下松弛原问题的方法,并设计了分支定界算法且从理论上论证了算法的收敛性和最坏情形下的迭代次数。最后经过数值实验表明算法在问题维度较低、负特征根较少的情形下迭代次数及运行时间都同SDP松弛下的分支定界算法效果相近,当负特征根增加时本文算法的运行时间会明显增加。本文主要的创新点如下:(1)针对一般的QCQP问题给出了在不升维的框架下用直线代替凹二次函数来松弛原问题问题的方法,并通过理论分析设计了相应的分支定界算法搜索原问题的全局最优解;(2)从理论上证明了本文设计的分支定界算法的收敛性及最坏情形下的迭代次数,并分别给出了本文算法、SDP松弛下的分支定界算法以及Baron的数值实验结果且对结果进行了对比分析;
【关键词】：QCQP问题 SDP松弛 分支定界算法 多项式时间
【学位授予单位】：清华大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221.2
【目录】：

• 摘要3-4
• abstract4-9
• 第1章 引言9-16
• 1.1 QCQP问题的研究背景及意义9-10
• 1.2 QCQP问题目前的研究热点10-15
• 1.2.1 QCQP问题的松弛方法11-13
• 1.2.2 锥规划方法的引入13-14
• 1.2.3 最优判定性条件与可解子类14-15
• 1.3 各章节主要内容15-16
• 第2章 凸约束下的非凸二次规划16-33
• 2.1 问题的分析和目标函数不升维的松弛处理16-19
• 2.2 松弛问题的分支定界算法19-24
• 2.2.1 分支19-23
• 2.2.2 定界23
• 2.2.3 分支定界算法23-24
• 2.3 算法的有效性分析24-32
• 2.3.1 算法的收敛性及最坏情形迭代次数24-26
• 2.3.2 算法的实例分析26-32
• 2.4 本章小结32-33
• 第3章 非凸约束下的非凸二次规划33-45
• 3.1 问题的分析及凸化处理33-36
• 3.1.1 变量替换下的松弛33-36
• 3.2 松弛问题的分支定界算法36-41
• 3.2.1 分支36-40
• 3.2.2 定界40
• 3.2.3 终止条件40-41
• 3.2.4 分支定界算法41
• 3.3 算法的有效性分析41-44
• 3.3.1 算法的收敛性及最坏情形迭代次数42
• 3.3.2 算法的实例分析42-44
• 3.4 本章小结44-45
• 第4章 总结45-46
• 参考文献46-49
• 致谢49-51
• 个人简历、在学期间发表的学术论文与研究成果51

【相似文献】

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

1 孙娟;盛红波;孙小玲;;多约束二次0-1背包问题的分支定界算法(英文)[J];Journal of Shanghai University(English Edition);2007年03期

2 杨夷梅;杨玉军;;分支定界算法优化研究[J];中国科技信息;2008年21期

3 井霞;高岳林;;线性分式和规划问题的分母输出空间分支定界算法[J];河南师范大学学报(自然科学版);2011年04期

4 牛淑芬;王国欣;孙小玲;;离散投资组合多因素模型的一种分支定界算法(英文)[J];Journal of Shanghai University(English Edition);2008年01期

5 杨金勇;宋海洲;;一类非线性比式和问题的分支定界算法[J];华侨大学学报(自然科学版);2014年03期

6 黎健玲;王鹏;马林;李杰;;求不定二次规划问题全局解的新的分支定界算法[J];广西大学学报(自然科学版);2009年04期

7 周雪刚;;线性乘性规划的因式输出空间分支定界算法[J];青岛科技大学学报(自然科学版);2013年06期

8 赵营峰;尹景本;;一类线性多乘积规划的分支定界算法[J];河南科技学院学报(自然科学版);2013年03期

9 吴国荣;高岳林;邓光智;;箱约束李普希兹优化问题的一种新的定界算法[J];宁夏大学学报(自然科学版);2008年01期

10 张玉忠;张咸昭;孙志慧;;关于问题P_m|intree;p_j=1;r_j|C_(max)的分支定界算法[J];运筹学学报;2006年02期

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

1 黎健玲;马林;王鹏;;箱子约束不定二次规划的一个分支定界算法(英文)[A];中国运筹学会第九届学术交流会论文集[C];2008年

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

1 曹先腾;二次约束二次规划非升维条件下的松弛理论及算法[D];清华大学;2015年

2 李景阳;基于多线程的并行分支定界算法框架及其应用[D];东北大学;2014年

3 秦平平;分支定界算法在运筹学模型中的应用[D];燕山大学;2009年

4 马艳利;混合整数非线性规划问题的分支定界算法研究[D];宁夏大学;2014年

5 魏飞;几类非凸规划问题的分支定界算法研究[D];北方民族大学;2011年

6 刘泳;基于拉格朗日松弛和分支定界算法的3PL运输调度问题[D];华中科技大学;2011年

7 林秀娟;面向入厂物流的可重用资源约束调度模型及分支定界算法[D];上海交通大学;2014年

8 余其旺;基于分支定界算法的三层决策模型与应用研究[D];武汉科技大学;2010年

9 李一明;分支定界算法的分布并行化研究[D];电子科技大学;2006年

10 俞亮;订货与发货整合批量调度模型研究[D];上海交通大学;2010年

  本文关键词：二次约束二次规划非升维条件下的松弛理论及算法，由笔耕文化传播整理发布。

，

本文编号：375970