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

二次规划的若干算法研究

作　者: 盛桂颖
导　师: 高雷阜
学　校: 辽宁工程技术大学
专　业: 应用数学
关键词: 二次规划凸二次规划 Lemke算法 Newton内点算法线性互补问题改进算法
分类号: O221.2
类　型: 硕士论文
年　份: 2009年
下　载: 220次
引　用: 0次
阅　读: 论文下载

内容摘要

本论文主要对某些二次规划的算法进行了研究,分析了一些常用的二次规划算法的局限性,同时改进了两种算法,并利用MATLAB数值试验验证了算法的有效性。论文在介绍了二次规划的基本知识的基础上,对一些常用算法进行了描述与分析,重点介绍并分析了Lemke互补转轴算法和Newton内点算法。分析了相关算法的优缺点,通过对经典的Lemke互补转轴算法求解凸二次规划问题的分析,找到了Lemke算法的局限性。同时,发现Newton内点算法的不足之处,以便进行改进。论文根据凸二次规划的Lemke算法的描述,给出了一种改进的Lemke算法,不用引入人工变量进行求解,并给出了改进算法的具体步骤并利用改进算法对具体实例进行检验。通过利用改进的Lemke算法对凸二次规划问题进行求解,把改进算法与经典的Lemke算法做了比较和分析,得出了改进算法的有效性。数值试验结果表明了改进算法的正确性,并减少凸二次规划问题的迭代过程。论文同时对Newton内点算法进行改进,提出了求解凸二次规划问题的新算法。此算法把对数罚函数法和拟Newton算法有效的结合,将约束问题转化为无约束问题,采用Wolf-Powell线搜索确定步长,避免了搜索步长过小的问题。利用拟Newton算法求最优解,并对算法收敛性进行分析,最后利用初步的数值试验表明算法是可行并且有效的。

全文目录

致谢  4-5
摘要  5-6
Abstract  6-9
1 绪论  9-13
  1.1 引言  9-10
  1.2 国内外二次规划问题的研究现状及发展趋势  10-12
    1.2.1 二次规划的研究现状  10-11
    1.2.2 二次规划的发展趋势  11-12
  1.3 论文的研究内容及主要工作  12-13
2 二次规划的基本知识及常用算法的描述与分析  13-33
  2.1 二次规划的模型及性质  13-16
    2.1.1 二次规划的模型  13
    2.1.2 二次规划的最优性条件  13-14
    2.1.3 二次规划的对偶性质  14-16
  2.2 Lagrange 算法  16-18
  2.3 路径跟踪法  18-20
  2.4 积极集法  20-24
  2.5 Lemke 算法的原理及计算步骤  24-29
    2.5.1 Lemke 算法的基本思想  24-26
    2.5.2 Lemke 算法的基本步骤  26-27
    2.5.3 Lemke 算法的局限性分析  27
    2.5.4 Lemke 算法产生退化的原因  27-29
  2.6 Newton 内点算法  29-33
    2.6.1 Newton 内点算法的基本思想  29-31
    2.6.2 Newton 内点算法的计算步骤  31
    2.6.3 Newton 内点算法的局限性分析  31-33
3 改进的Lemke 算法及实现过程  33-44
  3.1 改进的Lemke 算法的描述  33-36
    3.1.1 改进的Lemke 算法的基本思想  33-34
    3.1.2 改进的Lemke 算法的算法证明  34-35
    3.1.3 改进的Lemke 算法的计算步骤  35-36
  3.2 改进算法在求解凸二次规划中的实例分析  36-42
  3.3 改进算法与原始算法的比较  42-44
4 改进的Newton 内点算法及实现过程  44-50
  4.1 算法的推导  44-46
  4.2 算法的描述  46-47
  4.3 算法的收敛性分析  47-48
  4.4 算法的数值试验  48-50
结论  50-51
参考文献  51-54
附录A 改进的Lemke 算法的Matlab 程序  54-56
附录B 改进Newton 内点算法的Matlab 程序  56-58
作者简历  58-60
学位论文数据集  60-61

二次规划的若干算法研究

内容摘要

全文目录

相似论文