论文部分内容阅读
随着数据规模的日渐增大,传统计算方式碰到了越来越多的问题。在目前的应用中,问题的尺度已由原来通常考虑的几十几百增长到几千上万甚至数百万。这个时候,方程组的求解,甚至系数矩阵的存储都成为了限制算法速度乃至高阶算法实现的瓶颈。在这样的限制下,目前大多数的大规模问题使用的都是梯度算法,即利用模型函数的导数信息,构造问题的下降方向,反复地迭代,以期获得问题的最优解。然而这些算法由于往往只利用了问题的一阶信息,其目标函数的下降速度通常不会太快。在本论文中,我们着力尝试推广在传统最小二乘问题中行之有效的Levenberg-Marquardt(LM)算法在大规模问题中的应用。在第二章中,我们提出了一种用于非线性方程组的自适应LM算法。该算法推广了之前的多步LM方法。在传统的多步LM算法中,增大步数能够对经典LM算法进行有效的加速,但对不同的问题,其最高效的步数往往是不确定的。另一方面,经典的多步LM算法的计算速度并不一定会随着步数的增大而加快。有别于之前每步更新或固定多步更新一次的LM算法,我们的自适应LM算法在每个单步均自动判断雅可比矩阵的更新以及试探步的舍取,从而避免了多步LM算法中的步数选取问题。当实际下降量与预估下降量的比值大于阈值,我们保留原来的雅可比矩阵,并用以计算近似的LM步,从而减少雅可比矩阵的计算次数以及相应的线性代数工作。在一般性的条件下,我们证明了算法的全局收敛性。若局部误差界条件成立,我们证明自适应LM算法具有超线性收敛速度。数值结果表示我们算法的性能要优于以往的LM算法。在第三章中,我们提出一个扩展的Levenberg-Marquardt(ELM)算法框架。它将经典的LM方法推广至复合函数的无约束最小化问题minρ(r(x)),其中r:R~n→R~m,ρ:R~m→R。当迭代点离解较远时,我们提出了一些海森矩阵的近似以提高计算速度。针对内迭代子问题提前截断或者雅可比矩阵被简化或扰动的情况,我们还开发了一些非精确的ELM算法。在适当的条件下,我们建立了算法的全局收敛性和局部超线性收敛性。数值结果显示我们的方法是有前途的。在第四章中,我们基于ELM算法的框架提出了一种随机拟牛顿法。其在等距的迭代区间上少量地抽取海森矩阵的一个低秩逼近,并利用一个随机版本的有限内存BFGS框架校正后续的迭代。利用逼近矩阵的低秩性,我们可以直接计算抽样矩阵的逆并改进相应的BFGS迭代。有别于经典的随机梯度方法,我们的方法引入了二阶信息来保证算法的稳定性并利用抽样矩阵的特殊结构给出了可快速计算的拟牛顿搜索方向。我们证明了该算法是收敛的。数值实验表明这个算法是有效的。