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

几类优化问题的数值算法分析

作　者: 胡胜龙
导　师: 黄正海
学　校: 天津大学
专　业: 运筹学与控制论
关键词: 无约束优化互补问题多项式规划张量锥规划弥散张量影像非单调线搜索光滑Newton算法全局收敛 R-线性收敛超线性收敛
分类号: O224
类　型: 硕士论文
年　份: 2010年
下　载: 157次
引　用: 0次
阅　读: 论文下载

内容摘要

设计有效的算法是数值最优化中的重要研究课题.本硕士论文考察无约束优化问题、互补问题、多项式规划问题、张量规划问题等优化领域内的重点问题和近年来的热点问题,主要是从算法的设计、收敛性分析、数值计算效果、实际应用等方面进行研究.所设计的算法分别使用CUTEr、MCPLIB等标准的测试题库以及天津市第一中心医院的核磁共振影像数据来进行测试,并分别与SOSTOOLS、OptimizationTools(MatLab)等成熟的优化软件包进行了数值比较,实际计算效果是令人满意的.具体地,论文讨论的主要内容分成如下三个方面：本文的第二章主要考虑无约束优化问题,首先提出了一个新的非单调线搜索算法,在适当的条件下证明它的全局收敛性和局部R-线性收敛性.对于所提出的算法,用测试题库CUTEr中的问题进行了测试,并与两个流行的非单调线搜索框架进行了比较.数值实验表明新提出的算法是有效的.其次,将一个非单调线搜索算法推广到了求解一类约束优化问题上,并且证明：如果所考虑的目标函数是拟凸的,而且相应的约束集合所定义的流形具有非负的截面曲率,那么所设计的算法是全局收敛的,并且收敛到问题的全局最优解.第三章主要考虑互补问题.互补函数在互补问题的重构理论中起到了关键性的作用.本章首先提出了一族新的互补函数,该互补函数包含了众多流行的互补函数作为特例,并讨论了其若干性质,包括连续可微、Lipschitz连续、(强)半光滑、LC1、SC1等.利用这族互补函数,讨论了一个无导数的算法,使用测试题库MCPLIB来进行数值实验,实验结果表明新提出的函数是有价值的.其次,讨论了绝对值方程组与线性互补问题之间的关系：无需任何条件证明了Rn上的绝对值方程组等价于标准的线性互补问题,并给出了绝对值方程组的解集的一些性质；同时也提出了二阶锥上的绝对值方程组模型,设计了一个求解它的广义Newton算法,证明了算法的收敛性,一些数值计算表明该算法是有效的.作为一个应用,该算法为求解二阶锥上的互补问题提供了一个全新的方法.再次,对于互补问题的光滑Newton算法,现存的都是基于单调线搜索进行分析的,而实际计算中都用了非单调线搜索,缺乏相应的理论分析.本章第三部分引入了Kanzow-Kleinmichel光滑函数并证明了其Jacobian相容性,设计了一个求解非线性互补问题的具有新的非单调线搜索的光滑Newton算法并证明了其全局收敛性与局部二次收敛性,使用测试题库MCPLIB进行了数值实验,实验结果表明新设计的算法是有效的.最后,考虑对称锥互补问题,它为很多类互补问题提供了一个统一的框架,是近十几年优化领域研究的热点之一.本章第四部分给出了一个具有非单调线搜索的光滑Newton算法,在目前最弱的假设条件下证明了算法的全局收敛性.第四章主要是考虑多项式规划问题.首先,对于双二次规划问题,在不同于传统多项式时间算法的思路下给出了双二次规划的一个目前最好的近似率,而且对于所给的松弛问题,提出了一个交互方向法,证明了算法的全局收敛性,数值计算表明：该方法可以为双二次规划问题提供一个很好的近似解,在与已知方法的数值比较中占有绝对优势.同时,通过提出和分析一种张量特征值的方法,也得到了一些双二次规划的结论.其次,将带秩约束的二次规划的近似率从目标函数矩阵为半正定推广到了一般情况.再次,对于多项式系统,给出了两个新的矩阵分解定理,并且在此基础上给出了一些新的多项式系统的择一定理.特别地,在一定条件下,将S-引理推广到了高次多项式系统.作为一个应用,给出了Z-特征值极值问题的(充分必要)最优性条件.最后,提出了一个用序列SDP方法逼近空间张量锥规划的的数值算法,并对随机构造的问题进行了数值计算,数值结果与SOSTOOLS得到的计算结果作了比较,结果显示：提出的方法是有效的.基于空间张量锥规划,提出了一个更广的张量锥规划并给出了对偶理论,把序列SDP方法推广到张量锥规划上,称这个方法为TCOSS.对于核磁共振医学影像中的弥散陡度张量模型,用锥规划的方法作了正定性分析,提出了一个新的锥规划算法,用此算法与传统的OptimizationTools (MatLab)中的最小二乘方法对模拟数据与实际数据作了数值比较,结果是令人满意的.

全文目录

中文摘要  3-5
ABSTRACT  5-10
第一章绪论  10-18
  1.1 研究内容  10-17
    1.1.1 非单调线搜索与互补问题  10-14
    1.1.2 多项式规划与张量规划  14-17
  1.2 论文框架  17-18
第二章求解优化问题的非单调线搜索算法分析  18-39
  2.1 求解无约束优化问题的非单调线搜索算法  18-31
    2.1.1 算法及收敛性分析  20-28
    2.1.2 数值计算  28-31
    2.1.3 小结  31
  2.2 求解约束优化问题的非单调线搜索算法  31-39
第三章求解互补问题的算法分析  39-105
  3.1 求解互补问题的重构函数  41-60
    3.1.1 新定义的NCP-函数的性质  42-50
    3.1.2 效用函数的性质  50-54
    3.1.3 一个无导数算法  54-55
    3.1.4 数值计算  55-56
    3.1.5 NCP-函数的进一步讨论  56-60
  3.2 将互补问题转化成绝对值方程组求解  60-70
    3.2.1 互补问题与绝对值方程组的相互转化  61-67
    3.2.2 基于绝对值方程组的求解二阶锥线性互补问题的广义Newton算法  67-70
  3.3 求解非线性互补问题的非单调线搜索光滑Newton算法  70-81
    3.3.1 基本理论  71-75
    3.3.2 算法和基本结论  75-77
    3.3.3 算法的收敛性分析  77-80
    3.3.4 数值计算  80-81
    3.3.5 小结  81
  3.4 求解对称锥互补问题的非单调线搜索光滑Newton算法  81-105
    3.4.1 算法设计  83-88
    3.4.2 算法的全局收敛性  88-93
    3.4.3 算法的收敛行为  93-96
    3.4.4 小结  96-105
第四章求解多项式规划的算法分析  105-161
  4.1 双二次规划  105-122
    4.1.1 基本结论  106-111
    4.1.2 求解双二次规划的ADM及其收敛性分析  111-118
    4.1.3 数值计算  118-119
    4.1.4 双二次规划的进一步讨论  119-122
  4.2 带秩约束的二次规划  122-123
  4.3 多项式系统  123-138
    4.3.1 二次多项式系统  123-132
    4.3.2 高次多项式系统  132-136
    4.3.3 多项式系统的进一步讨论  136-138
  4.4 张量规划及其在医学影像中的应用  138-161
    4.4.1 空间张量锥分析  139-142
    4.4.2 求解STLP的序列SDP方法  142-146
    4.4.3 数值计算  146-150
    4.4.4 张量规划的进一步讨论与TCOSS  150-154
    4.4.5 核磁共振弥散张量影像的正定性  154-161
第五章总结及展望  161-164
参考文献  164-180
论文及科研情况  180-182
致谢  182

几类优化问题的数值算法分析

内容摘要

全文目录

相似论文