部分可分非线性方程组与优化问题的稀疏拟牛顿法

发布时间：2018-03-26 15:01

  本文选题：部分可分非线性方程组　切入点：部分可分最优化问题　出处：《湖南大学》2016年博士论文

【摘要】：拟牛顿法是求解非线性方程组和最优化问题颇受欢迎的一类算法.该类算法具有超线性收敛速度,而且,若采用适当线性搜索或信赖域技术,算法可具有全局收敛性.然而,拟牛顿法产生的拟牛顿矩阵往往是稠密的,因此不能直接用于求解大规模问题.来自科学计算和工程等领域的许多实际问题一般都具有一些特殊的稀疏结构.比如微分方程采用有限元法或者有限差分法离散化后得到的非线性方程组,其Jacobian矩阵具有一定的稀疏结构.很多无约束优化问题可写成若干个分量函数的和,其中每个分量函数只跟少数几个变量有关.因此,根据问题的稀疏特征或者目标函数的特殊结构,设计高效的稀疏拟牛顿算法,具有重要的理论意义和实际应用价值,也是优化界关注的一个重要课题,并取得了一系列重要成果.目前已提出了多种稀疏拟牛顿法,这些算法充分利用了问题的稀疏特征,并且保留了传统拟牛顿法的超线性收敛性等重要性质.稀疏拟牛顿法已成为求解大规模非线性方程组和最优化问题的一类重要算法.迄今为止,关于稀疏拟牛顿法的研究主要集中于对算法的局部收敛性质的研究,对于算法的全局收敛性质的研究工作很少.这是由于稀疏拟牛顿法产生的拟牛顿矩阵要保持问题的稀疏结构,使得传统拟牛顿法的某些重要性质如对称正定性、最小变化性等发生了改变,从而大大增加了研究稀疏拟牛顿法的全局收敛性的难度.本文在对稀疏拟牛顿法的性质进行深入分析的基础上,采用线性搜索技术,研究求解非线性方程组和最优化问题的一些重要的稀疏拟牛顿法的全局收敛性.我们首先研究求解大规模非线性方程组的稀疏拟牛顿法.Schubert方法是较早被提出的用于求解方程组的稀疏拟牛顿法,作为Broyden秩一修正公式的稀疏推广,Schubert修正公式能够精确保持方程组的Jacobian矩阵的稀疏结构.但在实际计算中,由于Schubert修正公式过于严格地保持矩阵的稀疏结构,数值表现有时不如Broyden秩一方法好.在本文中我们重点关注部分可分离的非线性方程组,借助于分块BFGS算法的思想,我们提出两种分块拟牛顿算法.当非线性方程组的导数信息不可用时,我们提出一种分块Broyden秩一算法,算法中采用分块Broyden秩一修正.该算法无需计算导数,且能够近似保持Jacobian矩阵的稀疏结构.当非线性方程组的导数信息可通过自动微分间接计算时,我们提出一种分块伴随Broyden算法,算法中采用分块伴随Broyden修正.该修正公式也可近似保持Jacobian矩阵的稀疏结构,并保留了伴随Broyden修正公式的线性不变性.我们采用一种无导数非单调线性搜索技术研究算法的全局收敛性,在适当条件下,建立了上述两种稀疏拟牛顿算法的全局收敛性.我们还证明,经过一定的迭代步后,单位步长可以取到.此时,算法在方程组解的局部还原为单位步长稀疏拟牛顿法,从而具有超线性收敛速度.我们还对算法进行数值检验,并将该两种稀疏拟牛顿算法与Broyden秩一方法和伴随Broyden方法进行了比较.结果表明,稀疏算法在迭代次数,函数值计算次数和计算时间方面均有出色表现.我们也将这两种稀疏算法与Schubert方法进行比较,数值结果进一步验证了这两种稀疏拟牛顿算法的优越性.其次,针对目标函数具有部分可分离结构的无约束优化问题,我们提出一种稀疏的投影分块PSB算法.算法针对目标函数的Hessian矩阵的稀疏结构,采用分块PSB修正.由于简单的分块PSB修正公式不能保正Hessian矩阵的近似矩阵的正定性,从而不能保证拟牛顿方向是目标函数的下降方向.因此我们对拟牛顿方向进行投影,提出一种投影的分块PSB算法,该算法可以保证产生目标函数的一个充分下降方向.在适当条件下,我们证明了采用Armijo或者Wolfe搜索的算法用于求解一致凸函数极小化问题时具有全局收敛性和超线性收敛速度.此外我们还通过数值计算,将分块PSB算法与已有的求解大规模最优化问题的著名的分块BFGS算法以及有限内存BFGS(L-BFGS)算法在30个测试问题上进行数值比较.结果表明,本文提出的分块PSB算法在迭代次数,函数值计算次数,梯度值计算次数和计算时间方面均有较好的表现.最后,我们研究求解对称非线性方程组的拟牛顿算法,基于自动微分技术,我们提出两类拟牛顿算法.首先,类似于Powell对称化技术,我们将伴随Broyden修正公式对称化,提出一种对称伴随Broyden修正.该修正公式保持了原伴随Broyden修正公式的最小变化性质和仿射不变性.此外,我们还提出一类新的伴随秩二拟牛顿修正公式,该修正公式不仅具有和BFGS修正公式类似的正定性和最小变化性质,而且能够精确保证拟牛顿矩阵与方程组的Jacobian矩阵沿拟牛顿方向一致.我们证明,在适当条件下这两种算法均具有全局收敛性和超线性收敛速度.数值结果显示,当用于对称非线性方程组求解时,这两类新算法相比于BFGS方法均具有优势.
[Abstract]:......
【学位授予单位】：湖南大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O242.23

【相似文献】

相关期刊论文 前10条

1 卢慧芳;杨月婷;;一种新的修正有限内存拟牛顿法[J];华东师范大学学报(自然科学版);2010年01期

2 孙文瑜;拟牛顿法中的数值相关技术[J];高等学校计算数学学报;1983年04期

3 张建中;双边投影拟牛顿法的收敛性[J];科学通报;1988年18期

4 姜子文;;直接优化矩阵分解因子的阻尼拟牛顿法[J];滨州师专学报;1991年04期

5 杨富贵,盛松柏;锥模型拟牛顿法[J];高等学校计算数学学报;1995年04期

6 高岩;极大值函数非光滑方程组的牛顿法和拟牛顿法[J];自然杂志;2000年01期

7 怀丽波;;利用函数值信息的修正多步拟牛顿法[J];南京大学学报数学半年刊;2007年01期

8 黄海;林穗华;;几种修正拟牛顿法的比较[J];广西民族师范学院学报;2011年03期

9 桂胜华;张倩;邢丽;徐玲;;弱互补函数的拉格朗日-拟牛顿法[J];上海第二工业大学学报;2005年04期

10 李亮;孙秦;;求解高维非线性优化的并行分块对角拟牛顿法[J];南昌航空大学学报(自然科学版);2013年01期

相关会议论文 前6条

1 时贞军;孙国;;对角稀疏拟牛顿法及其收敛特征[A];第六届中国青年运筹与管理学者大会论文集[C];2004年

2 王乐斌;王晓纯;白玉星;高建岭;;拟牛顿法在火灾作用下结构倒塌机构中的应用[A];北京力学会第15届学术年会论文摘要集[C];2009年

3 于杰;倪勤;;改进的多步拟牛顿法及其收敛性[A];中国运筹学会第十届学术交流会论文集[C];2010年

4 樊宇璐;李世作;张志斌;;基于拟牛顿法的电力系统潮流计算[A];中国高等学校电力系统及其自动化专业第二十四届学术年会论文集（上册）[C];2008年

5 刘洪伟;王明洁;章祥荪;;基于非单调线搜索非拟牛顿法的全局收敛性[A];中国运筹学会第八届学术交流会论文集[C];2006年

6 樊宇璐;李世作;张志斌;;基于拟牛顿法的电力系统潮流计算[A];第二十届电工理论学术年会论文集[C];2008年

相关博士学位论文 前3条

1 曹慧平;部分可分非线性方程组与优化问题的稀疏拟牛顿法[D];湖南大学;2016年

2 周伟军;拟牛顿法及其收敛性[D];湖南大学;2006年

3 程万友;求解最优化问题的非线性共轭梯度法和自调比拟牛顿法[D];湖南大学;2008年

相关硕士学位论文 前9条

1 陈金慧;带函数值的多步拟牛顿法[D];南京理工大学;2009年

2 于杰;改进的多步拟牛顿法及其收敛性[D];南京航空航天大学;2012年

3 王伟;不精确拟牛顿法的收敛性[D];大连理工大学;2006年

4 金红艳;求解大规模优化问题的有限记忆拟牛顿法[D];湖南大学;2013年

5 冯冬冬;一类精细修正牛顿法和拟牛顿法研究[D];中南大学;2012年

6 夏丹丹;求不可约非负张量的最大特征值的拟牛顿法[D];南京航空航天大学;2012年

7 孙国;无约束优化问题的稀疏拟牛顿法[D];曲阜师范大学;2003年

8 王娟;Hilbert空间中算子方程的不精确拟牛顿法的局部收敛性分析[D];大连理工大学;2006年

9 李宝美;多维filter与两项迭代算法[D];南京理工大学;2013年

，

本文编号：1668352