半定规划原始对偶内点算法的复杂度分析

发布时间：2017-03-31 21:00

  本文关键词：半定规划原始对偶内点算法的复杂度分析，，由笔耕文化传播整理发布。

【摘要】：在数学规划发展的长河中,内点法是解决线性规划的有效方法之一。半定规划是由线性规划推广而来的。由于半定规划广泛的应用于组合优化,传感器网络定位,结构设计,电机工程等。所以,研究半定规划问题的求解方法尤为重要。内点法是求解半定规划问题主要方法之一。本文主要研究求解半定规划的原始对偶内点算法。在原始对偶内点算法中,核函数在定义新的搜索方向方面起到重要作用,因此构造原始对偶内点算法的核心任务是构造一个良好的核函数。本文构造两个新的核函数,研究其性质,基于这两个核函数,构造求解半定规划问题的原始对偶内点算法,对给出的求解半定规划原始对偶内点算法进行复杂度分析,得到了算法的大步校正和小步校正的理论迭代界,结果能够达到当前已知最好的理论界。基于本文构造的两个新的核函数,我们也研究了求解线性规划原始对偶内点算法。由于求解线性规划的原始对偶内点算法与求解半定规划原始对偶内点算法在性质和算法的复杂度分析上十分相似,而且结果相同,所以本文只对半定规划的原始对偶内点算法进行阐述。
【关键词】：半定规划 原始对偶内点算法 核函数 大步迭代界 小步迭代界
【学位授予单位】：渤海大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O221
【目录】：

• 摘要4-5
• ABSTRACT5-10
• 1.绪论10-15
• 1.1 内点法的发展10-11
• 1.2 求解半定规划问题的内点法研究概况11
• 1.3 本文的研究背景和主要工作11-12
• 1.4 矩阵基础知识及符号含义12-14
• 1.4.1 符号含义12
• 1.4.2 矩阵基础知识12-14
• 1.5 本文的结构14-15
• 2.半定规划的原始对偶内点算法15-21
• 2.1 中心路径15-16
• 2.2 搜索方向16-18
• 2.3 解半定规划问题的一般原始-对偶内点算法18-21
• 3.两个新核函数及性质21-34
• 3.1 核函数的定义及障碍函数的定义21-22
• 3.2 两个新的核函数22-23
• 3.3 新核函数的验证23-29
• 3.3.1 核函数1的验证23-24
• 3.3.2 核函数2的验证24-29
• 3.4 核函数的性质29-34
• 4.基于新核函数的半定规划原始对偶内点算法复杂度分析34-45
• 4.1 Y(V) 的减少以及步长a 的选取34-37
• 4.2 半定规划的原始-对偶内点算法分析及迭代界的计算37-38
• 4.3 基于两个新核函数的大小步理论迭代界38-45
• 4.3.1 基于核函数1的大、小步理论迭代界38-41
• 4.3.2 基于核函数2的大、小步理论迭代界41-45
• 总结与展望45-46
• 参考文献46-50
• 发表论文情况50-51
• 致谢51-52

【相似文献】

中国期刊全文数据库 前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年

  本文关键词：半定规划原始对偶内点算法的复杂度分析，由笔耕文化传播整理发布。

本文编号：280064