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

互补问题及非光滑凸极小化问题的几种算法

作　者: 李琼
导　师: 李董辉
学　校: 湖南大学
专　业: 计算数学
关键词: 非线性互补问题不可微凸极小化牛顿法无导数算法共轭梯度型算法全局收敛性
分类号: O224
类　型: 博士论文
年　份: 2012年
下　载: 78次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究非线性互补问题及非光滑凸极小化问题的数值算法.对于非线性互补问题,我们提出几种基于半光滑方程组的算法.对于非光滑凸函数极小化问题,我们基于止则化技术,提出求解问题的一类共轭梯度型算法和谱梯度方法.我们建立这几种算法的全局收敛性,并通过数值试验对所提出的算法进行数值检验.结果表明本文提出的算法具有很好的实用性.在第二章,我们首先导出一个与非线性互补问题等价的半光滑方程组,称之为几乎光滑方程组.该方程组具有很好性质：它在方程组的解集之外的任何点都连续可微.而且,它在解集合中的任一点半光滑.特别地,如果解集是单点集,则该函数是基本的强几乎光滑的.该方程组较已有非线性互补问题等价的半光滑方程组具有更好的光滑性.同时保留已有半光滑方程组的许多好的性质如水平集的有界性、局部／全局误差界等.在此基础上我们提出求解非线性互补问题的一种牛顿法,并证明算法的全局收敛性和超线性收敛性.数值试验结果表明所提出的算法很有效.在第三章,我们提出求解非线性互补问题的一种光滑化牛顿法和一种同伦光滑化方法.我们首先构造一种非线性互补问题的新的光滑化函数.与已有的光滑化函数不同,我们首先构造绝对值函数的导数的光滑化函数,进而导出绝对值函数的光滑化函数.该函数具有Jacobian相容性.基于此光滑化函数,我们提出一个光滑化牛顿法和同伦光滑化方法来解非线性互补问题.在适当的条件下,我们分别证明两种算法的全局收敛性和超线性收敛性.我们还证明了当同伦光滑化算法用于解线性互补问题时,经过有限步迭代后,算法终止于问题的解.在第四章,我们研究用无导数算法解对称互补问题.我们先将求解互补问题转化为求解与其等价的非光滑方程组,在此基础上将最近提出的两种修正PRP共轭梯度法的思想加以改进,应用于解非光滑方程组,所提出的方法是无导数的,但算法产生的点列使得方程组的模函数值序列单调递减,因而算法是一种下降算法.在较弱的条件下分别证明两种算法的全局收敛性.数值结果表明算法有效.在第五章,借助Moreau-Yosida正则化,我们首先将求解非光滑凸函数极小化问题转化为求解光滑凸函数极小化问题.利用Moreau-Yosida正则化的近似函数值、近似梯度值而不是其精确值,我们提出一类共轭梯度型算法,先研究这类算法的共同性质,再着重研究三种具体的共轭梯度型算法.在较弱的条件下,我们分别证明这三种算法都具有全局收敛性.与已有算法相比,本文算法易于实现,且可用于解大规模问题.在第六章,充分利用Moreau-Yosida正则化的内在性质,我们首先将求解非光滑问题转化为求解光滑凸函数极小化问题.然后提出一种易于实现的谱共轭梯度法来解非光滑凸极小化问题.算法利用Moreau-Yosida正则化的近似函数值、近似梯度值而不是其精确值.在较弱的条件下,我们证明算法的全局收敛性.此博士论文得到了教育部重大项目(309023)和国家自然科学基金(11071087)的资助.

全文目录

摘要  5-7
Abstract  7-11
第1章绪论  11-26
  1.1 非线性互补问题及其等价形式  11-13
  1.2 基于非光滑方程组的数值算法  13-17
    1.2.1 非光滑牛顿法  13-14
    1.2.2 光滑化算法  14-16
    1.2.3 无导数算法  16-17
  1.3 非光滑凸极小化问题  17-19
  1.4 本文的主要工作  19-20
  1.5 本文的各章节安排  20
  1.6 记号及基本概念  20-26
    1.6.1 记号  21
    1.6.2 基本概念  21-26
第2章与非线性互补问题等价的几乎光滑方程组及牛顿法  26-39
  2.1 与非线性互补问题等价的几乎光滑方程组  26-29
  2.2 函数S(x)的性质  29-32
  2.3 牛顿法及其收敛性  32-35
  2.4 数值实验  35-37
  2.5 本章小结  37-39
第3章解非线性互补问题的光滑化牛顿法和同伦光滑化方法  39-56
  3.1 绝对值函数的光滑化  39-43
  3.2 求解NCP(F)的一种光滑化牛顿法  43-51
  3.3 求解NCP(F)的一种同伦光滑化方法  51-55
  3.4 本章小结  55-56
第4章求解对称互补问题的无导数共轭梯度型算法  56-68
  4.1 两种无导数共轭梯度型算法  56-59
  4.2 收敛性分析  59-64
  4.3 数值试验  64-67
  4.4 本章小结  67-68
第5章求解非光滑凸极小化问题的一类共轭梯度型算法  68-80
  5.1 预备知识  68-69
  5.2 共轭梯度型算法及其收敛性  69-79
    5.2.1 TTPRP型算法  73-76
    5.2.2 TMPRP型算法  76-77
    5.2.3 MFR型算法  77-79
  5.3 本章小结  79-80
第6章求解非光滑凸极小化问题的谱共轭梯度型算法  80-87
  6.1 SVFR算法描述  80-82
  6.2 收敛性分析  82-86
  6.3 本章小结  86-87
结论  87-89
参考文献  89-97
致谢  97-98
附录A 攻读学位期间完成和发表的学术论文目录  98-99
附录B 第二章测试问题和初始点  99-100
附录C 第四章测试问题和初始点  100-102

互补问题及非光滑凸极小化问题的几种算法

内容摘要

全文目录

相似论文