导读:本文包含了可行与不可行内点法论文开题报告文献综述及选题提纲参考文献，主要关键词:半定规划,全牛顿步,不可行内点算法,迭代复杂度
可行与不可行内点法论文文献综述
王亚丹[1]（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）
刘金倩[2]（2017）在《半定规划的不可行内点算法研究》一文中研究指出半定规划是近20年以来发展起来的一个新的数学规划分支.随着半定规划的发展,实际生活很多领域中的问题可以转化为半定规划模型来求解,例如:经济、金融、工程、管理等.由于它的约束条件是非线性的和凸的,因此,半定规划是一个非光滑凸优化问题.内点算法是求解半定规划问题的一种非常有效的算法,由于其具有较低的理论复杂度和较好的实验效果,吸引了国内外众多学者的研究,并迅速成为了数学规划领域中的研究热点.内点算法依据初始点是否可行,可以分为可行内点算法和不可行内点算法;依据算法迭代邻域的大小,可以分为宽邻域内点算法和窄邻域内点算法.众所周知,宽邻域内点算法具有较好的实验效果但是理论复杂度相对较高,而窄邻域内点算法具有较低的理论复杂度但是实验效果相对较差.本文主要研究的是半定规划的不可行内点算法,其目的在于缩小宽邻域算法和窄邻域算法之间的这种矛盾.本论文所做的主要工作如下:一方面,针对M型预估矫正内点算法,将冯增哲和房亮~([32])提出的半定规划的一种可行内点算法推广到不可行的情形中,并改进了算法的迭代邻域.理论上证明了迭代点列在新的宽邻域中是收敛的,并且证明了当取Nesterov-Todd(NT)方向时,算法的迭代复杂度是(?)(r Tr(X ~0S~0)/e),其中r是问题的维数,(X~0,S~0)是迭代初始点,e为算法要求的精度.这与半定规划的不可行内点算法当前最好的理论复杂度一致.另一方面,针对MTY型预估矫正内点算法,Sungwoo Park~([76])提出了半定规划的一种减少约束的MTY型预估矫正内点算法.基于此框架,对算法的迭代邻域进行了改进,即将邻域中的矩阵F范数改为矩阵2范数.通过数值实验,对算法运行的迭代次数、迭代时间以及算法终止时的计算结果与改进之前的算法进行了对比.数值实验结果表明,改进之后的算法是有效的.(本文来源于《西安电子科技大学》期刊2017-06-01）
杨洋,罗洪林,罗慧林[3]（2016）在《关于半定规划的一种宽邻域不可行内点算法的注记》一文中研究指出针对半定规划的宽邻域不可行内点算法,将牛顿法和预估校正法进行结合,构造出适当的迭代方向,提出一个修正的半定规划宽邻域不可行内点算法,并在适当的假设条件下,证明了该算法具有O(n~(1/3)L)的迭代复杂界.最后利用Matlab编程,给出了基于KM方向和NT方向的数值实验结果.(本文来源于《运筹学学报》期刊2016年02期）
吴珊,张明望,黄正伟[4]（2016）在《一种单调线性互补问题的full-Newton步不可行内点算法》一文中研究指出对单调线性互补问题设计了一种新的full-Newton步不可行内点算法.该算法是对Liu Z和Sun W提出的线性规划的full-Newton步不可行内点算法的改进和推广.通过应用新的技术引理,证明了算法的多项式复杂性阶为O(nL),这与当前单调线性互补问题的不可行内点算法最好的迭代复杂性阶一致.(本文来源于《西南大学学报(自然科学版)》期刊2016年05期）
吴岳,刘红卫,谢迪[5]（2016）在《半定规划的齐次不可行内点算法》一文中研究指出为降低半定规划(SDP)问题的迭代复杂度,并且有更好的数值实验结果,提出一种新的宽邻域上的齐次不可行内点算法.半定规划的KKT条件是单调互补问题(MCP),通过构造齐次模型(HMCP)以及提出新的宽邻域来解这个齐次模型,得到半定规划问题的最优解.这种算法容易判定原问题是否可行.在NT方向,证明迭代点在新的宽邻域内是收敛的,且迭代复杂度为O(n~(1/2)log L),其中n是SDP问题的维数,L=Tr(X~0S~0)/ε,其中ε是需要的精度,(X~0,S~0)是迭代起始点.这个复杂度比一般的半定规划不可行算法的迭代复杂度低.提供了数值实验,证明此算法比其他不可行算法具有更好的数值实验结果.(本文来源于《中国科学院大学学报》期刊2016年03期）
吴岳[6]（2015）在《半定规划的不可行内点算法》一文中研究指出半定规划(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-11-01）
季萍,李鑫,张明望[7]（2014）在《求解P_*(κ)-LCP的自适应全-Newton步不可行内点算法》一文中研究指出对P*(κ)线性互补问题提出了一种自适应全-Newton步不可行内点算法.算法是对Mansouri等人(H.Mansouri and M.Pirhaji in Journal of Operations Research Society of China 1:523-536,2013)提出的单调线性互补问题的自适应不可行内点算法的推广.在算法的每一次迭代中,障碍校正参数θ的取值并不固定,它总在1/(51n(1+4κ)2)和1/(14n(1+4κ)2)之间取满足算法要求的最大值,使得算法快速收敛于问题的一个ε-近似解.(本文来源于《西华师范大学学报(自然科学版)》期刊2014年04期）
陈月姣,张明望[8]（2014）在《基于核函数求解LCPs的全-Newton步不可行内点算法》一文中研究指出本文对P_*(κ)线性互补问题设计了一种基于核函数的全-Newton步不可行内点算法,是对Mansouri等人提出的单调线性互补问题全-Newton步不可行内点算法的改进与推广.算法的主迭代由一个可行步和几个中心步构成且可行步采用小步校正.通过建立和应用一些新的技术性结果,证明了算法的多项式复杂性为O((1+2κ)~(3/2)(1og_2log_264(1+2κ))nlogmax{(x0)Ts0,||r0||}/ε),当k=0时,与当前单调线性互补问题的不可行内点算法最好的迭代复杂性界一致.最后,用Matlab数值实验验证了算法的可行性.(本文来源于《数学学报(中文版)》期刊2014年06期）
李敬华[9]（2014）在《线性规划的不可行内点算法研究》一文中研究指出内点算法是求解线性规划规划问题的一个相当有效的算法。该算法在经过许多成功的改进之后,受到了越来越多的研究工作者的青睐。本文主要研究线性规划问题内点算法,和以往线性搜索迭代方向不同的是后两章我们利用的是弧搜索迭代方向,从而寻求最优解,在初始点不可行的情况下,讨论它们的迭代理论复杂性和数值实验结果。首先,对算法研究的问题及算法研究中要用到的基本知识做了简单的介绍。其次,由于二阶Mehrotra型预估-矫正算法在线性规划问题中得到了广泛的应用,我们利用文献[44]给出的新的自适应更新方法,在没有引进任何”保障措施”的情况下,构造了宽邻域上线性规划问题的一个不可行Mehrotra型预估-矫正内点算法,并且理论上证明了算法具有O(n3/2log (1/ε))迭代复杂性。然后,考虑到在实际应用中,可行初始点的选择比较困难,根据,杨[34]提出了线性规划的一种可行的多项式弧搜索内点算法,利用矫正步沿着椭圆逼近中心路径寻求最优解,我们提出了相应的基于窄邻域的不可行内点算法,最后证明了算法的迭代复杂度为O(n5/4log (1/ε)).最后,由于窄邻域的限制性,我们给出了相应的基于宽邻域的不可行的多项式弧搜索内点算法,最后证明了算法的迭代复杂度为O(n3/2log(1/ε)).(本文来源于《西安电子科技大学》期刊2014-01-01）
龚小玉,孙立民,胡振鹏,王先甲[10]（2013）在《基于全牛顿步长求解凸二次规划问题的不可行内点算法》一文中研究指出借助于全牛顿步长对凸二次规划问题提出了一种新的不可行内点算法.算法主要迭代由可行迭代步和中心路径邻域迭代步组成.其优点是线性搜寻方向是不需要的.最后证明算法迭代复杂性为O(nlogn/ε),与目前最好的不可行内点算法复杂性一致.(本文来源于《数学的实践与认识》期刊2013年24期）
可行与不可行内点法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
半定规划是近20年以来发展起来的一个新的数学规划分支.随着半定规划的发展,实际生活很多领域中的问题可以转化为半定规划模型来求解,例如:经济、金融、工程、管理等.由于它的约束条件是非线性的和凸的,因此,半定规划是一个非光滑凸优化问题.内点算法是求解半定规划问题的一种非常有效的算法,由于其具有较低的理论复杂度和较好的实验效果,吸引了国内外众多学者的研究,并迅速成为了数学规划领域中的研究热点.内点算法依据初始点是否可行,可以分为可行内点算法和不可行内点算法;依据算法迭代邻域的大小,可以分为宽邻域内点算法和窄邻域内点算法.众所周知,宽邻域内点算法具有较好的实验效果但是理论复杂度相对较高,而窄邻域内点算法具有较低的理论复杂度但是实验效果相对较差.本文主要研究的是半定规划的不可行内点算法,其目的在于缩小宽邻域算法和窄邻域算法之间的这种矛盾.本论文所做的主要工作如下:一方面,针对M型预估矫正内点算法,将冯增哲和房亮~([32])提出的半定规划的一种可行内点算法推广到不可行的情形中,并改进了算法的迭代邻域.理论上证明了迭代点列在新的宽邻域中是收敛的,并且证明了当取Nesterov-Todd(NT)方向时,算法的迭代复杂度是(?)(r Tr(X ~0S~0)/e),其中r是问题的维数,(X~0,S~0)是迭代初始点,e为算法要求的精度.这与半定规划的不可行内点算法当前最好的理论复杂度一致.另一方面,针对MTY型预估矫正内点算法,Sungwoo Park~([76])提出了半定规划的一种减少约束的MTY型预估矫正内点算法.基于此框架,对算法的迭代邻域进行了改进,即将邻域中的矩阵F范数改为矩阵2范数.通过数值实验,对算法运行的迭代次数、迭代时间以及算法终止时的计算结果与改进之前的算法进行了对比.数值实验结果表明,改进之后的算法是有效的.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
可行与不可行内点法论文参考文献
[1].王亚丹.半定规划的全牛顿步不可行内点算法研究[D].西安电子科技大学.2018
[2].刘金倩.半定规划的不可行内点算法研究[D].西安电子科技大学.2017
[3].杨洋,罗洪林,罗慧林.关于半定规划的一种宽邻域不可行内点算法的注记[J].运筹学学报.2016
[4].吴珊,张明望,黄正伟.一种单调线性互补问题的full-Newton步不可行内点算法[J].西南大学学报(自然科学版).2016
[5].吴岳,刘红卫,谢迪.半定规划的齐次不可行内点算法[J].中国科学院大学学报.2016
[6].吴岳.半定规划的不可行内点算法[D].西安电子科技大学.2015
[7].季萍,李鑫,张明望.求解P_*(κ)-LCP的自适应全-Newton步不可行内点算法[J].西华师范大学学报(自然科学版).2014
[8].陈月姣,张明望.基于核函数求解LCPs的全-Newton步不可行内点算法[J].数学学报(中文版).2014
[9].李敬华.线性规划的不可行内点算法研究[D].西安电子科技大学.2014
[10].龚小玉,孙立民,胡振鹏,王先甲.基于全牛顿步长求解凸二次规划问题的不可行内点算法[J].数学的实践与认识.2013