Nonsmooth exclusion test for finding all solutions of nonlinear equations (Q616162)

This is a great paper about Newton-methods for finding all real solutions of nonlinear equations in a connected compact subset of \({\mathbb R^n}\). After a comprehensive review of the existing Newton methods, quasi-Newton type methods, interval Newton-type methods, the authors reformulate the root finding problem into a global optimization problem and introduce the McCormick non-smooth convex relaxation and its properties for developing a branch-and-bound algorithm. Furthermore, they establish an inclusion relation between the solution set of the relaxed problem and the solution set of the original non-convex problem and propose a process to generate automatically starting points for a Newton-type method. Based on the componentwise Krawczyk operator and interval Newton operator with Gauss-Seidel based root inclusive and exclusive tests, they refine the variables bounds and restrictive monotonically tests in the proposed branch-and-bound algorithm to ensure uniqueness of a solution in the inclusion and convergence of the iteration. Efficiency and performance of the proposed algorithm and its various variations are discussed and demonstrated extensively with numerical examples.