Newton's method in optimization
In calculus, Newton's method (also called Newton–Raphson) is an iterative method for finding the roots of a differentiable function
These solutions may be minima, maxima, or saddle points; see section "Several variables" in Critical point (mathematics) and also section "Geometric interpretation" in this article.
This is relevant in optimization, which aims to find (global) minima of the function
The central problem of optimization is minimization of functions.
, we seek to solve the optimization problem Newton's method attempts to solve this problem by constructing a sequence
If the second derivative is positive, the quadratic approximation is a convex function of
Since the minimum is achieved for Putting everything together, Newton's method performs the iteration The geometric interpretation of Newton's method is that at each iteration, it amounts to the fitting of a parabola to the graph of
, having the same slope and curvature as the graph at that point, and then proceeding to the maximum or minimum of that parabola (in higher dimensions, this may also be a saddle point), see below.
happens to be a quadratic function, then the exact extremum is found in one step.
One thus obtains the iterative scheme Often Newton's method is modified to include a small step size
If f is a strongly convex function with Lipschitz Hessian, then provided that
generated by Newton's method will converge to the (necessarily unique) minimizer
[1] That is, Finding the inverse of the Hessian in high dimensions to compute the Newton direction
In such cases, instead of directly inverting the Hessian, it is better to calculate the vector
as the solution to the system of linear equations which may be solved by various factorizations or approximately (but to great accuracy) using iterative methods.
Many of these methods are only applicable to certain types of equations, for example the Cholesky factorization and conjugate gradient will only work if
While this may seem like a limitation, it is often a useful indicator of something gone wrong; for example if a minimization problem is being approached and
is not positive definite, then the iterations are converging to a saddle point and not a minimum.
On the other hand, if a constrained optimization is done (for example, with Lagrange multipliers), the problem may become one of saddle point finding, in which case the Hessian will be symmetric indefinite and the solution of
variant of Cholesky factorization or the conjugate residual method.
There also exist various quasi-Newton methods, where an approximation for the Hessian (or its inverse directly) is built up from changes in the gradient.
If the Hessian is close to a non-invertible matrix, the inverted Hessian can be numerically unstable and the solution may diverge.
In this case, certain workarounds have been tried in the past, which have varied success with certain problems.
One can, for example, modify the Hessian by adding a correction matrix
has the same eigenvectors as the Hessian, but with each negative eigenvalue replaced by
and small Hessian, the iterations will behave like gradient descent with step size
This results in slower but more reliable convergence where the Hessian doesn't provide useful information.
Newton's method, in its original version, has several caveats: The popular modifications of Newton's method, such as quasi-Newton methods or Levenberg-Marquardt algorithm mentioned above, also have caveats: For example, it is usually required that the cost function is (strongly) convex and the Hessian is globally bounded or Lipschitz continuous, for example this is mentioned in the section "Convergence" in this article.
If one looks at the papers by Levenberg and Marquardt in the reference for Levenberg–Marquardt algorithm, which are the original sources for the mentioned method, one can see that there is basically no theoretical analysis in the paper by Levenberg, while the paper by Marquardt only analyses a local situation and does not prove a global convergence result.
One can compare with Backtracking line search method for Gradient descent, which has good theoretical guarantee under more general assumptions, and can be implemented and works well in practical large scale problems such as Deep Neural Networks.
