论文摘要
对于求解无约束问题最优解的传统信赖域算法，其子问题中二次模型的逼近精度和信赖域的大小的选择是影响算法收敛速度的关键。例如使用海森矩阵的牛顿信赖域算法具有局部二次收敛速度，但当海森矩阵的计算较为复杂时，很多人考虑了使用拟牛顿方程产生近似的海森矩阵。另一方面如果信赖域较大，则每次迭代中点的跳跃也较大，收敛速度自然加快，对此有人提出了在子问题求解不理想时，增加线性搜索策略，并以此来调整信赖域大小。由于新的拟牛顿方程可以产生对海森矩阵有更高逼近精度的B_k，本文使用了基于新的拟牛顿方程的MBFGS公式来产生二次模型中的矩阵B_k，以得到有更高逼近精度的二次模型。在求得子问题的解S_k后直接进行线性搜索，并找到满足强沃尔夫准则的点α_kS_k，因而可以得到自然保持正定的矩阵B_k，使子问题的求解简便。为使线性搜索方法与信赖域算法更好结合，我们要求α_kS_k所达到的下降量要大于S_k，并使用α_k的信息来调整新的信赖域的大小。当子问题的解S_k不可接受时，即ρ_k＜η时，用α_k‖S_k‖来设定下一步的信赖域大小。此时如果线性搜索策略能够使目标函数达到较好的下降量且α_k≥1，则较传统的信赖域方法相比，我们的信赖域大小保持不减或增加。即虽然S_k对于ρ_k＜η来说不可接受，但由于满足线性搜索的下降量条件，因而在线性搜索意义下S_k可以接受，此时根据α_kS_k的大小来确定下一步的信赖域大小也更加合理。因此线性搜索不仅保证了算法有充分的下降量，而且有助于信赖域大小的改善。我们根据以上分析构造了新的算法，并证明了算法具有一阶全局收敛性和局部超线性收敛速度。数值实验结果表明算法对中小规模问题有优势。