导读:本文包含了内点算法论文开题报告文献综述、选题提纲参考文献及外文文献翻译,主要关键词:算法,线性规划,函数,笛卡尔,点法,欧几里得,迭代。
内点算法论文文献综述
安婷[1](2019)在《非线性半定规划的一个原始对偶内点算法》一文中研究指出本学位论文研究带有等式约束与半正定矩阵约束的非线性半定规划问题.该问题在控制理论、特征值优化、金融等领域应用广泛,因此,研究其求解算法是十分必要的.本学位论文提出了一个求解非线性半定规划的原始对偶内点法.首先,我们将非线性半定规划的KKT条件进行扰动,然后基于该扰动的KKT条件,使用Newton法导出产生搜索方向的线性方程组.本学位论文的算法由外迭代和内迭代构成.外迭代由算法A实现,目的是产生非线性半定规划的KKT点;内迭代由算法B实现,目的是产生一个近似的扰动KKT点.在内迭代中引进了一个新的效益函数用于线搜索以确定步长.在适当的假设条件下算法具有全局收敛性.本文最后对提出的算法进行了数值实验,并且对仿射矩阵的两种取法进行了数值结果比较.数值结果表明算法是可行和有效的.(本文来源于《广西大学》期刊2019-06-01)
程欢,穆学文,宋琦悦[2](2019)在《一种新的求解圆锥规划的非内点算法》一文中研究指出针对一般的圆锥优化问题,本文提出了一种新的非内点算法.该算法根据圆锥与二阶锥的关系通过引入一个与圆锥规划互补条件等价的投影方程将问题转化为线性方程组求解,且在每步迭代中只需求解一个系数矩阵固定的线性方程组并执行两次投影运算.该算法还具有可以从任意初始点开始且不要求仿射约束系数矩阵的行向量组线性独立等特点.本文还在较弱的假设条件下证明了算法的全局收敛性.数值实验结果表明该算法快速有效.(本文来源于《四川大学学报(自然科学版)》期刊2019年02期)
杨林峰,胡桂莉,张晨,张振荣[3](2019)在《基于CPU-GPU协同并行内点算法求解结构化非线性规划》一文中研究指出大量工程应用问题可建模为结构化非线性规划,且这类问题的系数矩阵可分为稀疏型和稠密型两种类型.利用原始-对偶内点法(primal dual interior point method,PD-IPM),并结合分布式并行技术可高效求解此类问题.经典工程问题-机组组合(unit commitment,UC)为稀疏系数矩阵的结构化非线性规划,本文根据PD-IPM原理,对UC模型进行连续松弛预处理,结合快速解耦技术解耦牛顿修正方程并设计CPU-GPU协同并行算法求解子问题,最后将结果与带稠密型子问题的结构化非线性规划的求解结果进行比较和分析.实验结果显示,本文所设计的算法对于两种不同类型的结构化非线性规划求解均能获得较好的加速比.(本文来源于《电子学报》期刊2019年02期)
Shafqat,Ullah,KHAN,M.K.A.RAHIM,Liaqat,ALI[4](2018)在《采用内点算法的灰狼优化程序阵列纠错(英文)》一文中研究指出设计了一个采用内点算法的灰狼优化程序以纠错天线阵列。若单个传感器故障,整个阵列辐射功率图在旁瓣电平(sidelobe level,SLL)和深零度电平(nulldepthlevel,NDL)方向受干扰,零点被破坏并发生偏离。可通过设计新的适应函数解决这些问题,并减小预期辐射功率图与零限值之间的偏差。该混合算法用于控制天线阵列的辐射功率图。仿真实验使用了由21个传感器组成的天线阵列。仿真结果表明,与现有的SLL和NDL方法相比,所提方法具有良好性能。(本文来源于《Frontiers of Information Technology & Electronic Engineering》期刊2018年09期)
汪威威[5](2018)在《锥规划的核函数全牛顿步内点算法研究》一文中研究指出众所周知,原-对偶内点算法是求解线性规划问题最有效的算法之一。2001年以前,几乎所有的原-对偶内点算法都是采用牛顿方向作为搜索方向,这种搜索方向和原-对偶对数障碍函数有密切联系。通过替换对数障碍函数为新的核函数障碍函数,可以得到新的搜索方向并设计核函数内点算法。基于核函数的e-凸性在设计大步可行内点算法中大大简化算法分析的作用,本文将核函数的e-凸性引入线性规划的全牛顿步可行算法设计,接着给出线性规划基于核函数的全牛顿步不可行内点算法,并推广到半正定规划,就设计新算法和复杂性分析进行研究。首先,给出了线性规划基于有限障碍核函数的全牛顿步可行算法。不仅仅将核函数用来确定搜索方向,更为重要的是,将核函数的性质特别是e-凸性用于全牛顿步内点算法分析,简化了算法复杂性分析过程,并且算法得到了同迄今为止可行内点算法最好的复杂性一致的结果。接着,根据大步核函数内点算法框架研究了所讨论核函数的特点,明确指出其不可用于大步内点算法设计。实际上,此类核函数刚好可以用于设计全牛顿步内点算法,并且具有巨大的优势。为得到更好的数值表现,对核函数确定的搜索方向进行改进,定义新的宽邻域,结合经典宽邻域内点算法,给出了基于核函数的宽邻域内点算法。虽然理论复杂度较全牛顿步内点算法有所提高,但是数值实验显示了其优越性,弥补了核函数全牛顿步内点算法在数值表现上的不足。其次,基于简单的核函数设计了线性规划的新的不可行内点算法。传统的全牛顿步不可行内点算法理论上有优势,但是所采用的传统牛顿方向和临近度量使得算法分析复杂。新的简单核函数不仅仅用于构造搜索方向和二次收敛域,其性质特别是e-凸性的引入使得全牛顿步不可行内点算法的复杂性分析大大简化,并且算法得到了线性规划同迄今为止最好的不可行内点算法复杂性一致的结果。进一步,借助于核函数矩阵函数的定义以及矩阵分析工具,将求解线性规划问题基于简单函数的全牛顿步不可行内点算法推广到求解半正定规划问题中,在保持同迄今为止最好的不可行内点算法复杂性一致的结果的同时同样大大简化了传统半正定规划全牛顿步不可行内点算法的复杂性分析。最后,借助于在执行可行步之后寻找更低的临近度量的估计,用来简化全牛顿步不可行内点算法复杂性分析,即去除中心步的思想,针对半正定规划问题,对核函数所确定的搜索方向进行改进,使得可行步跟踪下一扰动问题的障碍参数更新后的中心路径,设计了新的全牛顿步不可行内点算法.该算法只需要执行可行步,不需要任何中心步,复杂性分析简化的同时得到了和线性规划问题不可行内点算法迄今为止最好的复杂性一致的结果。数值实验表明采用新的改进方向后,算法的临近度量值显着降低,并且优于传统半正定规划全牛顿步不可行内点算法。(本文来源于《西安电子科技大学》期刊2018-09-01)
赵花丽[6](2018)在《对称锥非线性互补问题的内点算法研究》一文中研究指出对称锥互补问题是一类十分广泛的问题,它包括标准互补问题,二阶锥互补问题以及半定互补问题.在经济、管理、交通、工程设计、通信、控制等实际部门有着十分广泛的应用.最近几十年,对称锥互补问题已经成为非常活跃的研究领域,吸引了一大批科学工作者从事这方面的研究,并在理论、算法以及应用等方面取得了丰硕的研究成果.内点算法是求解对称锥互补问题的最有效的方法之一,但是关于对称锥互补问题的内点算法的研究基本都是针对对称锥线性互补问题的,关于对称锥非线性互补问题内点算法的相关研究很少.本文针对单调对称锥非线性互补问题和笛卡尔P_*(κ)对称锥非线性互补问题,分别研究了齐次算法、路径跟踪内点算法以及Mehrotra型预估校正内点算法,分析了算法的复杂度.首先在Yoshise提出的齐次模型的基础上,研究求解单调对称锥非线性互补问题的齐次算法.由于估计齐次算法的理论复杂度时,需要非线性变换满足SLC条件,而Yoshise提出的SLC条件依赖于尺度参数p且不具有尺度不变性.鉴于此,将Andersen等提出的SCL条件由R_+~n推广到对称锥K,提出了一个新的SLC条件,该条件的特点是不依赖于尺度参数p的选择.同时也证明了该条件具有尺度不变性.基于这个SLC条件,分别获得了小步、半长步以及长步算法的理论复杂度.特别地,基于sx方向时,小步、半长步以及长步算法的复杂度和Yoshise提出的齐次算法的复杂度相同.其次研究了笛卡尔P_*(κ)对称锥非线性互补问题的路径跟踪内点算法.该算法是基于F范数宽领域的不可行内点算法.为了估计算法的理论复杂度,提出一个SLC条件,基于该SLC条件,估计了算法的理论复杂度.并且利用线性互补问题、半定互补问题以及非线性互补问题的算例来验证算法的实际计算效果.数据结果表明,该算法是有效的并且也是稳定的.最后研究了两个求解笛卡尔P_*(κ)对称锥线性互补问题的Mehrotra型预估校正算法.这两个算法都是基于宽邻域N_∞~-(1-γ)的预估校正算法.第一个算法将现有的求解线性规划问题的可行预估校正算法推广到对称锥非线性互补问题,与原算法不同的是,推广后的算法为不可行算法,同时采用与以往有所不同的中心参数的调整策略,提出了笛卡尔P_*(κ)对称锥非线性互补问题的不可行预估校正内点算法.并且估计了算法的理论复杂度.利用线性互补问题、半定互补问题以及非线性互补问题的算例验证了算法的实际计算效果.第二个算法将现有的笛卡尔P_*(κ)对称锥线性互补问题的自适应预估校正算法推广到对称锥非线性问题,提出了笛卡尔P_*(κ)对称锥非线性互补问题的一个不可行自适应预估校正内点算法并且证明了算法的理论复杂度.该算法的中心参数的调整策略与第一个算法不同,它可以使得算法在每次迭代中都能获得较大的步长,数据结果表明,算法是有效的也是稳定的。(本文来源于《西安电子科技大学》期刊2018-09-01)
陈华平,毕迎鑫[7](2018)在《线性规划的一个满牛顿步可行内点算法》一文中研究指出基于一个新的函数,为线性规划设计了一个可行内点算法。该算法的迭代步长为满步长,迭代方向由该新函数决定,算法最终得到了线性规划目前最好的迭代复杂性.(本文来源于《六盘水师范学院学报》期刊2018年03期)
王亚丹[8](2018)在《半定规划的全牛顿步不可行内点算法研究》一文中研究指出半定规划(SDP)作为线性规划(LP)的一种推广,被广泛应用于许多科学和工程领域,如组合优化、控制理论和模式识别等。近年来,许多求解LP的内点算法被成功推广到了SDP上,使得SDP逐渐受到学者们的关注。内点算法(IPM)是目前求解SDP问题最有效的算法,根据初始点是否可行分为可行内点算法(FIPM)和不可行内点算法(IIPM)。全牛顿步不可行内点算法因在迭代过程中仅使用牛顿步,不需要线搜索,可以降低算法的计算量而成为研究热点之一。全牛顿步不可行内点算法一般包含两个迭代过程:可行步和中心步。其中,可行步是为了得到新的扰动问题的一个严格可行点,并且该迭代点位于扰动问题中心路径的二次收敛区间内;中心步是以新的扰动问题的严格可行点作为初始点进行迭代,进而得到下一个扰动问题的可行点。本文基于新的可行步搜索方向提出一种全牛顿步不可行内点算法;其次,对Wang等人~([45])所提算法的理论分析进行改进,简化了算法的分析过程。主要成果如下:1.基于Liu和Sun~([35])提出的核函数,构造了一种新的全牛顿步不可行内点算法。新算法采用该核函数代替可行步搜索方向中的原始对偶障碍函数,得到了一个新的搜索方向。通过使用该搜索方向,算法在迭代过程中只进行一次全牛顿步不需要使用中心步就能够得到问题的近似最优解。同时,算法得到的复杂度与当前全牛顿步不可行内点算法中最好的迭代复杂度结果一致。2.改进Wang等人~([45])提出的不可行内点算法的理论分析,所采用的算法理论分析过程更加简单直观。新的理论分析方法不需要考虑D~f_(XS)的无穷范数的上界,而是借助于它的特征值信息对算法进行分析。同时,通过引入一个合适的中间变量,并对其进行适当放缩得到算法的迭代复杂度。(本文来源于《西安电子科技大学》期刊2018-04-01)
李萌萌,张明望[9](2018)在《求解凸二次规划的一个新的全牛顿步内点算法》一文中研究指出根据求解线性规划的原始-对偶内点算法的思想,对凸二次规划设计了一种新的全牛顿步内点算法。算法的搜索方向由一个含有线性增长项的核函数确定。利用这个核函数和相应的障碍函数良好的分析性质,得到算法的复杂性阶为O(n~(1/2)lognlog(n/ε),这是目前已知的此类算法最好的理论迭代阶。(本文来源于《南阳理工学院学报》期刊2018年02期)
韩平[10](2018)在《加权互补问题的内点算法研究》一文中研究指出本文主要研究了互补问题及其算法,并对互补问题在经济中的应用做了相应的介绍.作为互补问题的一个推广,加权互补问题(weighted complementrarity problem)由Potra(SIAM Journal on Optimization)在2012年首先提出.文中指出经济领域中的一些均衡问题,如Fisher市场均衡问题可以化为加权线性互补问题,并用内点算法有效求解.目前,对于加权互补问题这个新的数学模型,理论和算法的研究成果还很少,本课题在研究经典互补问题的基础上,重点研究加权互补问题的内点算法,分析了它的收敛性,并研究了相应的数值计算效果等.全文各部分内容安排如下:第一章为绪论,介绍了互补问题及其算法的研究背景及现状,同时给出了在互补问题中经常用到的一些基本概念及符号约定。第二章介绍了经典互补问题的几类模型,同时给出了加权互补问题尤其是单调加权互补问题的模型以及经济领域中的Fisher市场均衡问题与加权互补问题之间的转化.第叁章主要介绍了路径跟踪内点算法的基本思想,重要概念以及算法框架,在此基础上,基于新定义的宽邻域,提出了求解加权互补问题的路径跟踪算法,并分析了算法的可行性以及算法的迭代复杂性。第四章对第叁章中求解加权互补问题的路径跟踪算法进行改进,提出了一种基于一类带参数q的新方向的路径跟踪内点算法,证明了该算法可以降低算法的迭代复杂性,并给出了相应的数值实验验证了算法的有效性。第五章则是对本文工作的总结和对未来的展望。(本文来源于《河南科技大学》期刊2018-03-01)
内点算法论文开题报告
(1)论文研究背景及目的
此处内容要求:
首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。
写法范例:
针对一般的圆锥优化问题,本文提出了一种新的非内点算法.该算法根据圆锥与二阶锥的关系通过引入一个与圆锥规划互补条件等价的投影方程将问题转化为线性方程组求解,且在每步迭代中只需求解一个系数矩阵固定的线性方程组并执行两次投影运算.该算法还具有可以从任意初始点开始且不要求仿射约束系数矩阵的行向量组线性独立等特点.本文还在较弱的假设条件下证明了算法的全局收敛性.数值实验结果表明该算法快速有效.
(2)本文研究方法
调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。
实证研究法:依据现有的科学理论和实践的需要提出设计。
定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。
定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。
跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。
模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
内点算法论文参考文献
[1].安婷.非线性半定规划的一个原始对偶内点算法[D].广西大学.2019
[2].程欢,穆学文,宋琦悦.一种新的求解圆锥规划的非内点算法[J].四川大学学报(自然科学版).2019
[3].杨林峰,胡桂莉,张晨,张振荣.基于CPU-GPU协同并行内点算法求解结构化非线性规划[J].电子学报.2019
[4].Shafqat,Ullah,KHAN,M.K.A.RAHIM,Liaqat,ALI.采用内点算法的灰狼优化程序阵列纠错(英文)[J].FrontiersofInformationTechnology&ElectronicEngineering.2018
[5].汪威威.锥规划的核函数全牛顿步内点算法研究[D].西安电子科技大学.2018
[6].赵花丽.对称锥非线性互补问题的内点算法研究[D].西安电子科技大学.2018
[7].陈华平,毕迎鑫.线性规划的一个满牛顿步可行内点算法[J].六盘水师范学院学报.2018
[8].王亚丹.半定规划的全牛顿步不可行内点算法研究[D].西安电子科技大学.2018
[9].李萌萌,张明望.求解凸二次规划的一个新的全牛顿步内点算法[J].南阳理工学院学报.2018
[10].韩平.加权互补问题的内点算法研究[D].河南科技大学.2018