基于SDP松弛的0-1二次规划全局算法

发布时间：2017-10-14 21:22

  本文关键词：基于SDP松弛的0-1二次规划全局算法

  更多相关文章： 0-1二次规划 SDP松弛 矩阵分解 片段线性逼近 分枝定界算法

【摘要】：0-1二次规划是整数规划中一类重要的最优化问题,广泛应用于工程、经济管理、金融和管理科学等许多重要领域,是近年来国际优化领域中重要而富有挑战性的课题。近年来半定规划(简记SDP)方法的发展更促进了0-1二次规划研究。本文研究0-1二次规划的SDP松弛和全局算法。我们给出了基于矩阵分解方法的紧SDP松弛,给出了基于SDP松弛的分枝定界算法。以下是本文的主要工作：(1)利用矩阵分解方法,给出了带线性约束0-1二次规划的一个紧的SDP松弛。通过目标函数的矩阵分解并利用二次项的片段线性逼近技术,得到了原问题的一个凸松弛。证明了寻找凸松弛中的最优参数问题可以归结为一个SDP问题。数值结果表明该SDP松弛能提供原问题的一个更紧的下界。(2)给出了带线性约束0-1二次规划的基于SDP松弛的分枝定界算法及其收敛性。首先,给出原问题和SDP松弛问题的最优值之间的关系。其次,给出基于SDP松弛的一个新的分枝定界算法,证明算法在有限步内收敛于问题全局最优解。初步数值结果表明我们所提出的算法能有效地找到问题全局最优解。
【关键词】：0-1二次规划 SDP松弛 矩阵分解 片段线性逼近 分枝定界算法
【学位授予单位】：浙江工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221.4
【目录】：

• 摘要3-4
• Abstract4-8
• 第一章 绪论8-13
• 1.1 问题提出及应用背景8-10
• 1.2 研究现状、困难及挑战10-11
• 1.3 本文的主要结果11-13
• 第二章 0-1二次规划文献综述13-23
• 2.1 无约束0-1二次规划13-17
• 2.1.1 线性化方法13-14
• 2.1.2 SDP松弛方法14-17
• 2.1.3 凸0-1二次规划变换17
• 2.2 约束0-1二次规划17-22
• 2.2.1 SDP松弛方法18-19
• 2.2.2 凸0-1二次规划变换19-22
• 2.3 0-1二次规划的分枝定界方法22-23
• 第三章 基于矩阵分解的0-1二次规划SDP松弛23-31
• 3.1 引言23-24
• 3.2 最佳矩阵分解和SDP松弛24-29
• 3.3 数值结果29-31
• 第四章 基于SDP松弛的0-1二次规划分枝定界算法31-36
• 4.1 引言31-32
• 4.2 分枝定界算法32-33
• 4.3 数值结果33-36
• 第五章 结束语与展望36-37
• 参考文献37-41
• 致谢41-42
• 攻读学位期间发表的学术论文42

【相似文献】

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

1 吴秉惠;二次规划的分解问题[J];国防科技大学学报;1985年03期

2 李明霞,黄石清,蔡奇志;解某一特殊二次规划的一个算法[J];高等学校计算数学学报;1989年01期

3 隋允康;完全二阶的“二次规划”的一种解法[J];工程数学学报;1990年03期

4 巴达拉胡;一类参数二次规划参数延拓的作用集法和稳定性分析[J];高校应用数学学报A辑(中文版);1997年01期

5 刘小冬,张胜贵,胡国雷;正定二次规划的一个对偶算法[J];纯粹数学与应用数学;2000年04期

6 胡国雷;求解大规模带二次简单约束的二次规划的显式自调比投影收缩算法[J];高等学校计算数学学报;2001年04期

7 钟万勰,张洪武;二次规划的混合能方法及杆系结构弹塑性分析[J];固体力学学报;2002年02期

8 王新辉,刘三阳,刘红卫;最大割问题的二次规划方法(英文)[J];运筹学学报;2003年04期

9 田小丽;李炜;蔡逸凡;;完全型区间系数二次规划的数值解法[J];杭州电子科技大学学报;2008年01期

10 朱剑森 ,乔新;用序列二次规划作复合材料结构的优化设计[J];南京航空航天大学学报;1985年03期

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

1 黄锋;王彩华;;工程结构的序列模糊二次规划[A];中国系统工程学会模糊数学与模糊系统委员会第五届年会论文选集[C];1990年

2 张立峰;;一个求解二次规划的微分方程方法[A];第四届全国决策科学/多目标决策研讨会论文集[C];2007年

3 石培培;刘红英;;具有单个等式和界约束二次规划的新算法[A];中国运筹学会第八届学术交流会论文集[C];2006年

4 陈伟;张连生;;整数二次规划的全局最优性条件(英文)[A];中国运筹学会第八届学术交流会论文集[C];2006年

5 王其冬;王丽燕;冯恩民;;临界项目集剖分的双层规划模型及主要性质[A];第四届中国青年运筹与管理学者大会论文集[C];2001年

6 刘建信;隋允康;;基于Sigmoid函数的0-1规划变换与解法[A];北京力学会第14届学术年会论文集[C];2008年

中国重要报纸全文数据库 前1条

1 记者 张丹;地区江落康莎文化产业项目二次规划汇报会召开[N];日喀则报(汉);2014年

中国博士学位论文全文数据库 前9条

1 穆学文;{-1，，1}二次规划算法及其应用研究[D];西安电子科技大学;2006年

2 黎健玲;连续与离散单调优化和不定二次规划算法研究[D];上海大学;2007年

3 肖现涛;求解半定约束二次规划逆问题的数值方法[D];大连理工大学;2009年

4 陈伟;0-1二次规划的全局最优性条件及算法[D];上海大学;2005年

5 唐春明;强次可行方法与序列二次约束二次规划算法的研究[D];上海大学;2008年

6 郭晓玲;二次规划的线性锥规划表示及算法研究[D];清华大学;2014年

7 路程;非负二次函数锥规划[D];清华大学;2011年

8 胡清洁;求解约束优化问题的序列二次规划方法研究[D];湖南大学;2008年

9 李山春;生产过程稳态模型的寻优方法及应用研究[D];中南大学;2011年

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

1 刘玮;基于线性方程组的无序列二次规划方法的研究[D];河北大学;2015年

2 姜勇;Lasserre松弛方法在二次规划中的应用[D];湘潭大学;2015年

3 蔡伟荣;基于SDP松弛的0-1二次规划全局算法[D];浙江工业大学;2015年

4 王倩;一种新的正定二次规划算法[D];西安科技大学;2011年

5 张璐;大规模二次规划相关算法的研究[D];辽宁工程技术大学;2010年

6 樊炳倩;基于距离的正定二次规划算法[D];西安科技大学;2012年

7 董彦诚;一类二次规划反问题的研究[D];大连理工大学;2007年

8 林苗珊;一类二次规划反问题的光滑函数法[D];大连理工大学;2007年

9 冯婷婷;二次规划的并行变量分配算法研究[D];山东科技大学;2011年

10 闻昆仑;一个有限内存序列二次规划算法的研究[D];北京交通大学;2012年

本文编号：1033254