基于非单调技术的信赖域算法的研究

摘要

无约束优化研究的是没有约束条件的问题的最优解,即对于给出的实际问题,从众多的方法中选出最优方法.由于约束优化问题可以转化为无约束优化问题,因此研究无约束优化问题的数值方法有着重要的意义.目前,求解无约束优化问题的数值方法主要有两类:信赖域算法和线搜索方法.与线搜索方法相比,信赖域算法思想新颖,具有较好的稳健性和很强的收敛性,能解决良态问题,也能解决病态问题,但大多数信赖域算法是单调的,单调算法对非线性程度较高的函数并不能保证算法的有效性,而非单调技术可以有效地克服这一缺点.在传统的二次模型信赖域算法中,子问题的求解花费了算法的大部分工作量,而如果子问题中Hessian矩阵或其近似是正定对角矩阵时,其解可以较容易地求出.传统的信赖域算法中,信赖域半径不包含当前迭代点的信息,而信赖域半径中包含当前迭代点的信息的自适应方法可以提高算法的效率.基于二次模型的滤子信赖域算法中,利用滤子技术可以加大试探点被接受的几率.另外,锥模型是比二次模型更一般的模型.
　　基于以上原因,我们研究了非单调信赖域算法,提出了三类新的非单调信赖域算法:
　　首先,我们提出一个基于简单二次函数模型的非单调自适应信赖域算法.在每一步迭代,新的信赖域半径根据当前迭代点的信息自适应调节.在一定的条件下,证明了算法的全局收敛性和超线性收敛性.数值试验表明算法是有效的.
　　其次,我们提出一个基于简单二次函数模型的滤子非单调信赖域算法.不同于传统的非单调信赖域算法,新算法在试探步不被接受时,采用滤子技术,增大试探步被接受的可能性;如果试探步也不能被滤子集接受,则采用固定的公式取搜索方向,并进行非单调线搜索,减少了计算量.在较少的条件下,证明了算法的全局收敛性.数值结果证明算法的有效性.
　　最后,我们提出一个基于锥模型的非单调自适应信赖域算法.该算法充分利用包含当前迭代点信息和水平向量信息的新的自适应策略调节信赖域半径.当试探步不被接受时,采用非单调线搜索,减少了计算量.在适当的条件下,证明了算法的全局收敛性和Q-二阶收敛性,并且给出了相应的数值试验结果。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 无约束优化问题概述

§1.1 最优化问题的提出及无约束优化问题的最优性条件

§1.2 常用的求解无约束优化问题的方法

§1.3 混合信赖域算法

§1.4 本文的主要工作

第二章 基于简单二次函数模型的非单调自适应信赖域算法

§2.1 引言

§2.2 算法

§2.3 收敛性分析

§2.4 数值试验

第三章 基于简单二次函数模型的滤子非单调信赖域算法

§3.1引言

§3.2 算法

§3.3 全局收敛性分析

§3.4 数值试验

第四章 基于锥模型的非单调自适应信赖域算法

§4.1 引言

§4.2 锥模型信赖域子问题及其算法

§4.3 全局收敛性和局部二阶收敛性

§4.4 数值实验

第五章 结论与展望

参考文献

致谢

作者在攻读硕士期间主要研究成果