Conditions For The Superlinear Convergence Of Quasi-Newton Methods On Degenerate Solutions

Quasi-Newton methods are welcome iterative methods for solving small and middle size unconstrained optimization problems. An attractive advantage of this class of methods is their superlinear convergence property without computation of second order derivative of the objective function. On the other hand, it well-known that for a quasi-Newton method to be superlinearly convergent, it requires the condition that the second order derivative of the objective function is positive definite. If this condition does not hold, the convergence rate of the quasi-Newton method may slow down to be linear. We call the problem degenerate if the second order derivative of the objective at the solution is not positive definite. In this paper, we further study the conditions for a quasi-Newton method to be superlinearly convergent when applied to the following unconstrained optimization problem: We focus our attention on the degenerate problems. We will derive some sufficient conditions that ensure the superlinear convergence of a quasi-Newton method. We also present some necessary and sufficient conditions for a quasi-Newton method to be superlinearly convergent. In particular, without requirement of the positive definiteness of the second order derivative of the objective function at the solution, we show that under some weaker conditions, the Dennis-More condition is still a necessary and sufficient condition for a quasi-Newton method to be superlinear con-vergence. Moreover, in the case where the second order derivative of the objective function at the solution is positive definite, our conditions are equivalent to the Dennis-More condition. Therefore, the results obtained in the thesis are important extensions of the Dennis-More condition. As an application, we give a condition for the PSB (Powell-Symmetric-Broyden) quasi-Newton method to be superlinearly convergent when applied to solve degenerate problems.