A Spectral-Scaling MBFGS Method For Nonconvex Minimization

The quasi-Newton methods are very welcome iterative methods for solving small and middle size unconstrained optimization problems. This class of iterative methods posses fast convergent property. Among various quasi-Newton methods, the BFGS method is the most welcome method due to its favorable numerical per-formance. But this algorithm does not have global convergence, when it is used to solve nonconvex minimization. MBFGS algorithm can be used to solve noncon-vex minimum problems. However, when applied to solving large scale problems, the matrix generated by the MBFGS method is generally very dense and not well conditioned, which makes it difficult get the solution of the subproblem. As a result, the method could not be applied to solving large scale problems. To over-come this drawback, in this thesis, we introduce a spectral-scaling strategy to MBFGS method and propose a spectral-scaling MBFGS method. The basic idea of the spectral-scaling MBFGS method is to modify the traditional quasi-Newton equation such that the quasi-Newton matrix is no longer the approximation to the Hessian of the objective function but an approximation to its preconditioned form. The purpose of this approximation is to reduce the condition number of the quasi-Newton matrix so that the related subproblem is relatively easy to solve. Iteration matrix produced by the algorithm possess good natures, such as iterative matrix is symmetric positive definite which has nothing with convex of function and linear search; iteration matrix has the nature of the self-correction trace which can effectively correct the excessive eigenvalue and makes the condition number of iterative matrix smaller.Under mild conditions, we show that the proposed spectral-scaling MBFGS method with Armijo or Wolfe line search is globally and R-linearly convergent even for solving nonconvex problems. We also introduce a nonmonotone line search by Grippo, consider the nonmonotone version of the spectral-scaling MBFGS method and establish its global convergence. At last, we do some numerical experiments to test the proposed methods. The results show that the proposed method can solve large-scale problems effectively.