Backtracking New Q-Newton’s Method

In this paper, we introduce a new Newton-type method-named Backtracking New Q-Newton’s method (BNQN)-which retains the same quick local rate of convergence while having much stronger global convergence guarantees. It is a combination of a previously designed algorithm (New Q-Newton’s method) and Armijo’s Backtracking line search. The main contribution of this paper is as follows: We prove that this new algorithm, applied to a general C 3 cost function f , has the following good properties: For a sequence {xn} constructed by this algorithm from a random initial point x0: -Finding critical points: Any cluster point of the sequence is a critical point of f . -Fast convergence rate: Near any non-degenerate local minimum, it has local quadratic convergence rate. -Avoidance of saddle points: If x0 is outside an exceptional set of Lebesgue measure 0, then {xn} cannot converge to a saddle points. BNQN is the first variant of Newton’s method in the literature satisfying all these 3 properties. We also prove some further results, and propose some other variants. We illustrate the main results with both theoretical and experimental examples. 2020 Mathematics Subject Classification. 37N40, 49M15, 49M37, 65Exx, 65Hxx, 65K05, 90C26.