学位论文 > 优秀研究生学位论文题录展示

预估校正光滑算法研究

作　者: 谌永荣
导　师: 黄崇超
学　校: 武汉大学
专　业: 应用数学
关键词: Karmarkar算法 内点算法 路径跟踪算法 光滑算法 预估校正算法 凸二次规划
分类号: O241
类　型: 硕士论文
年　份: 2005年
下　载: 60次
引　用: 1次
阅　读: 论文下载
 

内容摘要


单纯形算法和内点算法是线性规划的经典算法,虽然线性规划单纯形算法在实际应用中是一种高效的方法,然而在理论上它并不是多项式算法,因而吸引了无数学者去试图设计线性规划的多项式算法。1978年,L.G.Khachiyan提出了第一个多项式算法——椭球算法。1984年N.Karmarkar提出了线性规划的一种新的多项式算法。与单纯形算法沿着可行区域的边界寻优不同,Karmarkar算法是建立在单纯形结构之上的,它是从初始内点出发,沿着最速下降方向,从可行区域内部逐渐走向最优解,因此Karmarkar算法又被称为内点算法,自从Karmarkar划时代的论文发表以来,内点算法一直是数学规划领域一个非常活跃的研究方向。 但是内点算法必须从问题的可行域的内部出发,并且在迭代过程中通过适当的线性搜索来保证迭代点的非负性,这就给算法的启动带来了一定的困难。近年来提出了一类非内点算法—光滑算法,其中研究得最多的是非内点路径跟踪算法,这类算法中引入了光滑函数,利用光滑函数的性质,算法过程中不必要保证迭代点的非负性,但最后得到的最优解能自动保证非负。 本文致力于预估校正光滑算法的研究,提出了凸二次规划的预估校正算法。算法中首先将问题的中心线条件改造为一个非线性方程组,然后对它应用牛顿法,这样光滑算法避免了不等式约束而且算法中的迭代点也不必保证大于零,给算法的启动性带来了极大的便利。对于本文中的算法,我们证明了它的全局收敛性和局部二次收敛性。并用MATLAB编程进行了数值实验,数值结果表明本文提出的算法在实际应用中有一定的优越性。

全文目录


中文摘要  4-5
英文摘要  5-7
第一章 引言  7-10
  §1.1 光滑算法的回顾及研究现状  7-8
  §1.2 预估校正算法  8-9
  §1.3 本文主要内容及章节安排  9-10
第二章 凸二次规划的预估校正光滑算法  10-25
  §2.1 算法的基本思想  10-12
  §2.2 算法的迭代步骤  12-16
  §2.3 算法的全局收敛性  16-21
  §2.4 算法的局部收敛性  21-25
第三章 基于MATLAB的光滑算法数值实验  25-32
第四章 总结与展望  32-33
参考文献  33-39
致谢  39

相似论文

  1. 二次规划的若干算法研究,O221.2
  2. 一类互补问题基于核函数的原始—对偶大步—校正内点算法,O221.2
  3. 补偿随机规划的若干算法及其应用研究,F224
  4. 佛山电网无功优化应用研究,TM714.3
  5. 基于神经网络求解区间二次规划及支持向量机分类问题,TP183
  6. 应用神经网络求解二次规划问题的研究,TP183
  7. 时间分数阶Fokker-Planck方程的数值算法,O241.82
  8. 半定规划的灵敏度分析,O221.2
  9. 一全局收敛的求解不等式约整非线性半定规划的内点算法,O221.2
  10. 非负最小二乘问题的算法研究,O221.2
  11. 基于D.C.分解的非凸二次规划SDP近似算法,O221.2
  12. 有界约束半光滑系统的非单调投影梯度信赖域方法,O224
  13. 关于广义互补问题的内点算法研究,O221.2
  14. 线性约束优化的仿射尺度内点算法,O221
  15. 一种发电滚动计划的优化算法研究,TM73
  16. 基于改进原——对偶内点法的节能发电调度优化算法,TM744
  17. 线性互补问题在经济中的应用,O221
  18. 解一般约束优化的一个全局和超线性收敛的原始对偶内点QP-free型算法,O224
  19. 几类二次约束二次优化问题的全局最优性条件,O224
  20. 有限元方法在非线性发展方程中的应用,O241.82
  21. 水库防洪调度方案优选及库淀联合防洪调度问题的研究,TV697.13

中图分类: > 数理科学和化学 > 数学 > 计算数学 > 数值分析
© 2012 www.xueweilunwen.com