半定规划的不可行内点算法

发布时间：2017-08-03 11:18

  本文关键词：半定规划的不可行内点算法

  更多相关文章： 半定规划 不可行内点法 迭代复杂度 单调互补问题 全牛顿步

【摘要】：半定规划(SDP)是线性规划(LP)的进一步推广,它的约束条件是非光滑的、凸的,因此,SDP是一个非光滑凸优化问题。近年来,SDP在算法和理论上日渐发展,并广泛的应用于组合优化、图像处理、模式识别等相关领域,成为数学规划中一个非常重要的研究方向。在解决数学规划问题的若干方法中,内点法(IPM)具有较好的实验效果和较低的理论复杂度,成为半定规划的核心算法。SDP内点法按其约束条件是否可行分成可行内点法(FIPM)和不可行内点法(IIPM),本文主要研究的是IIPM。一般内点法中理论复杂度小的算法实验效果差,而实验效果好的算法理论复杂度很高[1],而实际中往往希望在保持较好的实验效果的同时降低算法的理论复杂度。为此,本文提出了两种新的算法,分析了它们的多项式复杂度,并且做了数值实验进行比较。主要完成了以下工作:1.首先概括了SDP的发展背景,然后简要总结了SDP的基本概念和理论以及求解SDP问题的常用算法,介绍了SDP的研究现状。2.齐次不可行内点法:为了降低SDP模型的迭代复杂度,并且有更好的数值实验效果,本论文研究了一种新的宽邻域上的齐次不可行内点法。SDP问题的KKT条件可以看作一个单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个单调互补问题,从而提出了一种新算法,这种算法容易判定原来的SDP模型是否可行。当取NT方向时,证明了迭代点在新的宽邻域内是收敛的,且迭代复杂度降低到(?)((?)logL),其中n是SDP问题的维数,L=Tr(X~0 S~0)/ε,ε是需要的精度,(X~0,S~0)是迭代起始点,这比一般的SDP不可行内点法的迭代复杂度低,同时做出了数值实验列表,证明了此方法比其他不可行内点法具有更好的数值实验效果。3.一种新的全牛顿步不可行内点法:全牛顿步算法分为可行步和中心步两种全牛顿步,最大的优势就是不用求解步长,使算法的计算量降低。新算法引入了一个特别的核函数,用此核函数来代替可行步中的原始对数障碍函数,得到一种不同于一般算法的可行步,同时给出了一个更大的邻域,在新邻域中对二次收敛性结果的证明进行了改进,并且迭代复杂度和当前全牛顿步不可行内点法最好的迭代复杂度结果一致。
【关键词】：半定规划 不可行内点法 迭代复杂度 单调互补问题 全牛顿步
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221
【目录】：

• 摘要5-6
• ABSTRACT6-9
• 符号对照表9-10
• 缩略语对照10-13
• 第一章 绪论13-25
• 1.1 半定规划的研究背景与进展13-14
• 1.2 半定规划的基本理论14-17
• 1.2.1 半定规划的基本概念14-16
• 1.2.2 半定规划的对偶理论16-17
• 1.3 半定规划的主要算法17-22
• 1.3.1 内点法18-21
• 1.3.2 非内点法21-22
• 1.4 半定规划的研究现状22-24
• 1.5 本文的主要工作和内容安排24-25
• 第二章 半定规划的齐次不可行内点法25-43
• 2.1 引言25-27
• 2.2 齐次MCP模型HMCP27-29
• 2.3 齐次模型的中心路径29-30
• 2.4 具有(?)((?)log L) 复杂性的齐次不可行内点法30-39
• 2.4.1 计算搜索方向30-34
• 2.4.2 不可行性和对偶间隙的下降关系34-36
• 2.4.3 齐次不可行内点法36
• 2.4.4 算法的复杂性分析36-39
• 2.5 数值实验39-40
• 2.6 本章小结40-43
• 第三章 半定规划的全牛顿步不可行内点法43-51
• 3.1 引言43-44
• 3.2 基于核函数的全牛顿步不可行内点法44-47
• 3.3 算法的复杂性分析47-50
• 3.4 本章小结50-51
• 结束语51-53
• 参考文献53-59
• 致谢59-61
• 作者简介61-62

【相似文献】

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

1 房亮;;一类模糊半定规划问题的解法[J];山东科技大学学报(自然科学版);2007年01期

2 徐引玲;;半定规划问题的光滑化方法[J];西北师范大学学报(自然科学版);2008年02期

3 李明山;张明;李兴玮;董国华;;基于半定规划的量子状态最优无错区分[J];计算机仿真;2008年10期

4 马宗刚;成央金;邓胜岳;张美芳;;求解无线传感器网络定位的半定规划松驰法[J];太原科技大学学报;2009年01期

5 田苗;刘红卫;叶峰;;求解半定规划问题的一种光滑化方法[J];西北大学学报(自然科学版);2009年01期

6 李蕊;;半定规划的改进的外梯度法[J];重庆文理学院学报(自然科学版);2010年05期

7 李成进;;解特殊凸二次半定规划的正则法[J];武夷学院学报;2010年05期

8 苏丽娜;;圆形几何布局优化问题的非线性半定规划解法[J];阴山学刊(自然科学);2011年04期

9 韩乔明;解半定规划的Levenberg-Marquardt方法[J];数值计算与计算机应用;1998年02期

10 关秀翠,刁在筠;半定规划的逆问题[J];经济数学;1999年03期

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

1 房亮;冯增哲;贺国平;李树全;;非线性半定规划问题的一种基于松弛变量的内点法[A];第八届中国青年运筹信息管理学者大会论文集[C];2006年

2 王建宏;林道荣;;具线性矩阵不等式约束半定规划问题的一种原始-对偶中心路径算法[A];第九届中国青年信息与管理学者大会论文集[C];2007年

3 崔艳;;二次{-1,1}规划的半定规划松弛的非线性规划算法[A];第十二届中国青年信息与管理学者大会论文集[C];2010年

4 王晓敏;刘灵;;半定规划的原始-对偶不可行内点算法[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

5 袁彦;白晓清;韦化;;求解变压器新模型OPF的半定规划法[A];中国高等学校电力系统及其自动化专业第二十四届学术年会论文集（下册）[C];2008年

6 王建宏;王晓敏;孔鹏志;王文庆;;半定规划问题中的几个择一性定理[A];中国企业运筹学学术交流大会论文集[C];2007年

7 田媛;田志远;;解半定规划问题的Log-Sigmoid乘子法[A];中国运筹学会第九届学术交流会论文集[C];2008年

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

1 刘红卫;半定规划及其应用[D];西安电子科技大学;2002年

2 乌彩英;互补问题与半定规划算法研究[D];内蒙古大学;2009年

3 李阳;求解非凸半定规划的一类非线性Lagrange方法[D];大连理工大学;2009年

4 田君杨;基于矩量理论的电力系统全局优化算法研究[D];广西大学;2014年

5 李庆娜;最优低秩相关系数矩阵问题[D];湖南大学;2010年

6 祝宇楠;凸规划技术在水火联合调度问题中的应用[D];广西大学;2014年

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

1 田苗;半定规划的光滑化方法研究[D];西安电子科技大学;2008年

2 蒋耀伟;半定规划及其应用研究[D];西安电子科技大学;2009年

3 李蕊;半定规划的外梯度法研究[D];西安电子科技大学;2010年

4 徐凤敏;半定规划的算法及其在组合优化中的应用[D];西安电子科技大学;2001年

5 王淑华;半定规划的算法研究[D];西安电子科技大学;2005年

6 王建宏;复半定规划及其在系统和控制理论中的应用[D];上海交通大学;2007年

7 褚洪生;最优值意义下半定规划反问题的结构与求解[D];河北工业大学;2007年

8 冯昌利;半定规划问题的若干算法研究[D];辽宁工程技术大学;2011年

9 李敬玉;解半定规划的两种数值方法[D];青岛大学;2011年

10 李思琦;半定规划原始对偶内点算法的复杂度分析[D];渤海大学;2015年

，

本文编号：614105