The Extensions Of Levenberg-Marquardt Method With Applications To Large-scale Problems

With the increasing size of data,traditional algorithms get more and more clumsy in modern applications.While the scale of problem has risen from tens or hundreds to tens of thousands or even millions,the computational complexity of traditional algorithms grow exponentially with problem sizes.Solving a single linear equation or even storing a coefficient matrix become prohibitive in such context.This greatly reduces the number of algorithms we can choose in practice.With such limitation,most current large-scale problems are solved using gradient methods,that is,algorithms use gradient of the model function to construct the descent directions in order to obtain the optimal solution.Since these algorithms only use the first-order information,their convergent speed are usually slow.In this paper,we focus on the extension of the LM method,which is effective in the traditional least squares problem,to large-scale problems.In the second chapter,we present an adaptive LM method for nonlinear equations.The algorithm is an extension of the previous multi-step LM method.In the traditional multi-step LM algorithm,the computation efficiency increases as the number of approximated steps grows,but as the step size gets larger,the algorithm may diverge.A clear criterion for these step sizes is unknown and may be problem dependent.Different from the previous multi-step algorithms with fixed step size,we present an adaptive LM method that automatically chooses the Jacobian matrix update and determines the acceptance of its descent step in every single step,which avoids the divergence issue in the multi-step LM algorithms.When the ratio between the actual reduction and the predicted reduction is greater than a certain threshold,we retain the latest evaluated Jacobian matrix,and to calculate the approximate LM step.This process reduces the number of Jacobian evaluation and the corresponding linear algebra work.Under general conditions,we prove the global convergence of the algorithm.If the local error bound condition is satisfied,we show that the adaptive LM algorithm has a superlinear convergence rate.The numerical results show that the adaptive LM algorithm is much better than the previous LM algorithms.In the third chapter,we propose an extended Levenberg-Marquardt(ELM)algorithm framework that generalizes the classic LM method for the unconstrained minimization problem of composite functions min?(r(x)),where r:R~n?R~m,?:R~m?R.When the iterations are far from solution,we propose some approximations that increase the computational speed.We also develop a few inexact variants which generalize ELM to the case where inner iterations are not solved exactly or the Jacobian matrix is simplified or perturbed.Under suitable assumptions,we establish the global convergence and local superlinear convergence of the algorithm.Numerical results show that our method is promising.In the fourth chapter,we propose a stochastic quasi-Newton method inspired by the ELM framework,which incrementally sub-samples an approximated Hessian matrix on a regular interval,and corrects its subsequent iterations with a modified limited memory BFGS framework under the stochastic settings.With the low-rank structure,we can effectively calculate the inverse of the approximated Hessian and improve the corresponding BFGS steps.This method differs from the classical approach in that the second order information is introduced to stabilize the algorithm and construct a Hessian approximation as well.We prove that the approximated Hessian is positive definite and the algorithm is convergent.Numerical experiments show that this algorithm is effective.