锥规划的核函数全牛顿步内点算法研究

发布时间：2020-04-25 13:07

【摘要】：众所周知,原-对偶内点算法是求解线性规划问题最有效的算法之一。2001年以前,几乎所有的原-对偶内点算法都是采用牛顿方向作为搜索方向,这种搜索方向和原-对偶对数障碍函数有密切联系。通过替换对数障碍函数为新的核函数障碍函数,可以得到新的搜索方向并设计核函数内点算法。基于核函数的e-凸性在设计大步可行内点算法中大大简化算法分析的作用,本文将核函数的e-凸性引入线性规划的全牛顿步可行算法设计,接着给出线性规划基于核函数的全牛顿步不可行内点算法,并推广到半正定规划,就设计新算法和复杂性分析进行研究。首先,给出了线性规划基于有限障碍核函数的全牛顿步可行算法。不仅仅将核函数用来确定搜索方向,更为重要的是,将核函数的性质特别是e-凸性用于全牛顿步内点算法分析,简化了算法复杂性分析过程,并且算法得到了同迄今为止可行内点算法最好的复杂性一致的结果。接着,根据大步核函数内点算法框架研究了所讨论核函数的特点,明确指出其不可用于大步内点算法设计。实际上,此类核函数刚好可以用于设计全牛顿步内点算法,并且具有巨大的优势。为得到更好的数值表现,对核函数确定的搜索方向进行改进,定义新的宽邻域,结合经典宽邻域内点算法,给出了基于核函数的宽邻域内点算法。虽然理论复杂度较全牛顿步内点算法有所提高,但是数值实验显示了其优越性,弥补了核函数全牛顿步内点算法在数值表现上的不足。其次,基于简单的核函数设计了线性规划的新的不可行内点算法。传统的全牛顿步不可行内点算法理论上有优势,但是所采用的传统牛顿方向和临近度量使得算法分析复杂。新的简单核函数不仅仅用于构造搜索方向和二次收敛域,其性质特别是e-凸性的引入使得全牛顿步不可行内点算法的复杂性分析大大简化,并且算法得到了线性规划同迄今为止最好的不可行内点算法复杂性一致的结果。进一步,借助于核函数矩阵函数的定义以及矩阵分析工具,将求解线性规划问题基于简单函数的全牛顿步不可行内点算法推广到求解半正定规划问题中,在保持同迄今为止最好的不可行内点算法复杂性一致的结果的同时同样大大简化了传统半正定规划全牛顿步不可行内点算法的复杂性分析。最后,借助于在执行可行步之后寻找更低的临近度量的估计,用来简化全牛顿步不可行内点算法复杂性分析,即去除中心步的思想,针对半正定规划问题,对核函数所确定的搜索方向进行改进,使得可行步跟踪下一扰动问题的障碍参数更新后的中心路径,设计了新的全牛顿步不可行内点算法.该算法只需要执行可行步,不需要任何中心步,复杂性分析简化的同时得到了和线性规划问题不可行内点算法迄今为止最好的复杂性一致的结果。数值实验表明采用新的改进方向后,算法的临近度量值显著降低,并且优于传统半正定规划全牛顿步不可行内点算法。
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O221.1

【相似文献】

相关期刊论文 前10条

1 温春燕;乌彩英;;二阶锥规划基于核函数凸组合的内点算法[J];内蒙古大学学报(自然科学版);2017年02期

2 冯增哲;张西学;刘建波;房亮;;半定规划的一个新的宽邻域非可行内点算法[J];运筹学学报;2014年02期

3 张维泉;张圣贵;;基于新函数下的半定规划原始对偶内点算法的复杂度分析[J];福建师范大学学报(自然科学版);2013年02期

4 龚小玉;王先甲;胡振鹏;;基于核函数求解线性互补问题的不可行内点算法[J];数学杂志;2013年03期

5 陈飞翔;刘金魁;武忠祥;张辉;;半定规划的一种修正原对偶内点算法研究[J];数学的实践与认识;2011年01期

6 张锋;段余平;邱军;冯小琴;;基于粒子群算法与内点算法的无功优化研究[J];电力系统保护与控制;2010年13期

7 陈飞翔;张辉;武忠祥;;凸二次规划的原-对偶内点算法数值实验初步[J];科学技术与工程;2009年01期

8 杨春艳;雍龙泉;;求解凸二次规划的一种改进的原-对偶内点算法[J];长江大学学报(自然科学版)理工卷;2009年02期

9 王永丽;王鑫;贺国平;;求解半定规划的原始对偶势下降内点算法研究[J];山东科技大学学报(自然科学版);2008年06期

10 迟晓妮;刘三阳;李炳杰;;二次锥规划的不可行内点算法[J];兰州大学学报(自然科学版);2007年04期

相关会议论文 前9条

1 岳玉静;蔡新中;何冰洁;王国强;;马科维茨均值-方差模型的原-对偶内点算法[A];第四届全国决策科学/多目标决策研讨会论文集[C];2007年

2 王国强;钱忠根;;凸二次规划的新的原始-对偶内点算法[A];数学·力学·物理学·高新技术研究进展——2006（11）卷——中国数学力学物理学高新技术交叉研究会第11届学术研讨会论文集[C];2006年

3 盛玉红;热西达;;凸二次规划问题的一种内点算法[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

4 朱志斌;张可村;;非凸非线性规划一个全局收敛的可行内点算法[A];中国运筹学会第七届学术交流会论文集（下卷）[C];2004年

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

6 韦化;阳育德;;微分-代数方程约束的电力系统最优化问题——模型与现代内点算法[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

7 王浚岭;;一类线性约束凸规划问题的内点算法及其计算复杂性[A];中国运筹学会第七届学术交流会论文集（下卷）[C];2004年

8 张环;潘平奇;;线性规划的一个内点算法[A];中国运筹学会第九届学术交流会论文集[C];2008年

9 杨国梁;黄思明;;应用内点算法求解效用函数意义下证券组合有效选择问题[A];2002年中国管理科学学术会议论文集[C];2002年

相关博士学位论文 前10条

1 马晓珏;线性规划和互补问题的宽邻域内点算法研究[D];西安电子科技大学;2017年

2 汪威威;锥规划的核函数全牛顿步内点算法研究[D];西安电子科技大学;2018年

3 王言金;最优化的不可行内点算法研究[D];武汉大学;2004年

4 杨喜美;对称锥规划的宽邻域内点算法研究[D];西安电子科技大学;2014年

5 刘新泽;对称锥互补问题若干内点算法的复杂性研究[D];西安电子科技大学;2014年

6 张立溥;锥规划的全牛顿步不可行内点算法[D];上海大学;2011年

7 刘长河;锥规划中若干内点算法的复杂性研究[D];西安电子科技大学;2012年

8 迟晓妮;二次锥规划的算法研究[D];西安电子科技大学;2008年

9 马鹏飞;旋转锥互补函数及旋转锥规划内点算法研究[D];上海大学;2015年

10 杨林峰;计及机组启停的动态最优潮流问题研究[D];广西大学;2012年

相关硕士学位论文 前10条

1 王亚丹;半定规划的全牛顿步不可行内点算法研究[D];西安电子科技大学;2018年

2 徐志宇;基于二阶锥规则的投资追踪问题[D];南京大学;2018年

3 张慧;求解非线性规划问题的原始对偶内点算法[D];吉林大学;2017年

4 温春燕;二阶锥规划的内点算法研究[D];内蒙古大学;2017年

5 刘金倩;半定规划的不可行内点算法研究[D];西安电子科技大学;2017年

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

7 田文娟;半定规划的原对偶内点算法[D];西安电子科技大学;2014年

8 李秀峰;锥规划基于宽邻域的内点算法[D];西安电子科技大学;2014年

9 钟兆伟;半定规划的内点算法[D];西安电子科技大学;2010年

10 张博;原-对偶内点算法用于优化问题的研究及其在风险投资领域的应用[D];西安电子科技大学;2005年

，

本文编号：2640284