带线搜索的非单调信赖域算法

摘要

现在广泛用来求解优化问题的方法大多数是单调的方法，当目标函数在可行域中存在细长弯曲的峡谷的情形时单调性算法就会大大丧失它的计算效率。由此非单调算法引起了学者们的重视，产生了许多有效的非单调的算法，特别是非单调线搜索与信赖域法相结合表现了突出的计算效果。 本文将非单调线搜索与非单调信赖域法相结合，信赖域法中每一步都实施线搜索，使得迭代每一步都充分下降，加快了迭代速度。对于无约束优化问题的传统非单调信赖域算法，子问题的求解是信赖域法的关键，也是信赖域法计算量的主要部分，如果试探步δk不可接受，令xk+1=xk，减小信赖域半径，重新求解子问题。这样就有可能多次求解子问题才能得到可接受的新的试探步δk，如果问题的规模比较大时，多次重新求解子问题加大了计算量，而线搜索确定一个新试验点xk+1只要求非常小的计算量。因此将线搜索与信赖域相结合，可减少子问题求解次数，从而减小信赖域法的计算量。引入线搜索要求子问题的解必须是下降方向，即gTkδk<0，本文研究了现存的子问题的求解方法，证明了Zhang和Xun1999折线法、Steihaug1983共轭梯度法满足“充分下降条件”，得到的解可以安全实施线搜索。在此基础上，我们将非单调线搜索与非单调信赖域法相结合，构造了一种算法，并证明了算法具有一阶全局收敛性和局部超线性收敛速度。数值试验表明算法非常有效。

目录

文摘

英文文摘

声明

1信赖域法的研究

1.1信赖域法简介

1.2信赖域子问题解的特性

1.3子问题的近似解解法

1.4共轭梯度法求子问题的近似解

1.5传统信赖域法与线搜索相结合

1.6信赖域法全局收敛性的证明

2非单调线搜索与非单调信赖域法

2.1非单调线搜索研究概述

2.2非单调信赖域法

3新的带线搜索非单调信赖域算法

4新算法的收敛性和收敛速度

4.1新算法的全局收敛性

4.2新算法的超线性收敛性

5数值试验

结论

致谢

参考文献