Backtracking New Q-Newton's method: a good algorithm for optimization and solving systems of equations
share
In this paper, by combining the algorithm New Q-Newton's method - developed in previous joint work of the author - with Armijo's Backtracking line search, we resolve convergence issues encountered by Newton's method (e.g. convergence to a saddle point or having attracting cycles of more than 1 point) while retaining the quick rate of convergence for Newton's method. We also develop a family of such methods, for general second order methods, some of them having the favour of quasi-Newton's methods. The developed algorithms are very easy to implement. From a Dynamical Systems' viewpoint, the new iterative method has an interesting feature: while it is deterministic, its dependence on Armijo's Backtracking line search makes its behave like a random process, and thus helps it to have good performance. On the experimental aspect, we compare the performance of our algorithms with well known variations of Newton's method on some systems of equations (both real and complex variables). We also explore some basins of attraction arising from Backtracking New Q-Newton's method, which seem to be quite regular and do not have the fractal structures as observed for the standard Newton's method. Basins of attraction for Backtracking Gradient Descent seem not be that regular.
READ FULL TEXT