论文摘要
1947年,Danzig提出了线性规划及其著名的算法—单纯形算法,该算法具有很好的实际计算性能,但从复杂性理论上来说并不是一个好算法;1978年,同样针对线性规划问题,Khachiyan提出了第一个线性规划的多项式算法—椭球算法,但此算法的实际计算性能并不如单纯形算法,这自然吸引了许多学者去试图设计具有较好计算性能的线性规划的多项式算法;1984年,Karmarkar利用势函数和投影变换的技巧提出了线性规划的一个新的多项式算法,这个算法具有比椭球算法更好的复杂性,而且实际计算性能又优于单纯形算法,尤其对大规模问题更显其高效性。与单纯形算法沿着可行区域的边界寻优不同,Karmarkar算法是建立在单纯形结构之上的,它是从初始内点出发,沿着最速下降方向,从可行区域内部逐渐走向最优解,因此Karmarkar算法又被称为内点算法。自从Karmarkar划时代的论文发表以来,内点算法一直是数学规划领域一个非常活跃的研究方向。 本文主要研究了组合同伦内点算法,并提出了线性规划和线性互补问题基于预-校正的组合同伦内点算法。在以往的路径跟踪算法中,为证明算法的收敛性,需要原问题的对数障碍函数满足严格凸的条件,但这一要求即使对线性规划问题来说也是较为严格的要求。如要推广到一般的非线性规划问题将会更为困难。本文中将同伦方法和内点法结合运用,放宽了对对数障碍函数的限制,获得了较好的结果。并利用Matlab编程进行了数值实验,数值实验结果表明本文提出的算法具有一定优越性。
论文目录
相关论文文献
- [1].辅助函数在同伦扰动方法上的应用[J]. 郑州大学学报(理学版) 2010(04)
- [2].输电线非线性振动问题的同伦映射近似解[J]. 物理学报 2011(06)
- [3].基于同伦分析方法的一种改进的试位法[J]. 应用数学和力学 2008(02)
- [4].交通拥堵相变问题的同伦分析法[J]. 物理学报 2013(17)
- [5].一类广义鸭解系统的同伦映射解[J]. 数学物理学报 2011(06)
- [6].求解双层规划问题的动边界组合同伦法[J]. 高等函授学报(自然科学版) 2013(02)
- [7].一个新混沌系统的同伦分析解法[J]. 科学技术与工程 2011(02)
- [8].道路同伦映射的分块构造[J]. 渤海大学学报(自然科学版) 2011(03)
- [9].一类扰动Burgers方程的孤子同伦映射解[J]. 物理学报 2010(05)
- [10].大规模变工况流程模拟的回溯同伦法[J]. 高校化学工程学报 2009(04)
- [11].同伦分析方法进展综述[J]. 力学进展 2019(00)
- [12].同伦连续法求解矩阵特征值的研究[J]. 绵阳师范学院学报 2012(08)
- [13].同伦变换不变性与变分不等式中的解的存在性[J]. 宜宾学院学报 2010(12)
- [14].改进同伦分析方法及非线性热传导问题的同伦解[J]. 四川师范大学学报(自然科学版) 2014(03)
- [15].基于同伦分析的Falkner-skan方程近似解[J]. 廊坊师范学院学报(自然科学版) 2013(01)
- [16].改进同伦分析方法及推广Kuramoto-Sivashinsky方程的近似解[J]. 动力学与控制学报 2012(01)
- [17].同伦分析方法的推广及其实现[J]. 华东师范大学学报(自然科学版) 2011(03)
- [18].基于同伦函数的水电站小波动特征值研究[J]. 华中科技大学学报(自然科学版) 2020(08)
- [19].大范围求解非线性方程组的指数同伦法[J]. 计算数学 2014(02)
- [20].Sinh-Gordon方程的同伦近似解[J]. 物理学报 2011(03)
- [21].基于同伦技术的偶应力反问题求解[J]. 计算力学学报 2011(02)
- [22].(2+1)维Toda格子方程的同伦分析解[J]. 青岛农业大学学报(自然科学版) 2012(04)
- [23].同伦分析方法:研究背景和现状[J]. 科学观察 2011(06)
- [24].同伦分析法在求解耗散系统中的应用[J]. 物理学报 2010(01)
- [25].扰动KdV方程的同伦分析法求解[J]. 常熟理工学院学报 2010(04)
- [26].用同伦分析方法求解一类燃烧模型[J]. 河南科技大学学报(自然科学版) 2010(05)
- [27].基于同伦映射的两轮机器人控制器设计[J]. 计算机测量与控制 2010(09)
- [28].一类非线性方程激波解的同伦分析方法[J]. 河南大学学报(自然科学版) 2009(06)
- [29].地球物理资料非线性反演方法讲座(七) 同伦反演法[J]. 工程地球物理学报 2008(05)
- [30].超越摄动：同伦分析方法基本思想及其应用[J]. 力学进展 2008(01)
标签：内点算法论文; 组合同伦内点算法论文; 预校正算法论文; 线性规划论文; 线性互补问题论文;