Given that Newton's method is one of the most prevalent methods in solving nonlinear system of multi-variable equations but it still remains quite costly when it comes to solve big systems due to the calculation of Jacobian at every iteration (let's say our unknowns are up to a million).
So why is it still used so widely used? How do we mitigate its shortcomings such as being expensive time-wise?
There are Quasi-Newton Methods that are less costly, but they converge slower so how do we exactly decide what method to use?
Thanks in advance
Best Answer
As Ethan Bolker points out in the comments, you can't make blanket statements about which method to use. You look at each particular problem and use insights from that problem to make a decision.
Newton's method (and in particular, its "hardened" variants that include a line search or trust region) is so popular because it is so often successful when solving black-box optimization problems, even for non-convex problems well outside of the regime where theoretical guarantees exist. BFGS and Gauss-Newton are also very popular variants.
For concrete classes of problems, coming up with efficient and robust quasi-Newton schemes is often an active area of research. For example, here's a recent paper that studies equations that arise from the physics of elastic bodies, in particular: Blended Cured Quasi-Newton for Geometry Optimization.
EDIT: as for mitigation strategies, there are many approaches. Sometimes you can analyze the Hessian and argue that some of the more computationally intensive terms are "negligible" and can be neglected. Or you compute the full Hessian only every so many iterations and perform rank-one updates in between. Etc.
Note also that for many large problems the cost of the linear solve in Newton's method dominates the Hessian construction cost.