Higher Dimensions
The above iterative scheme can be generalized to several dimensions by replacing the derivative with the gradient, and the reciprocal of the second derivative with the inverse of the Hessian matrix, . One obtains the iterative scheme
Usually Newton's method is modified to include a small step size instead of
This is often done to ensure that the Wolfe conditions are satisfied at each step of the iteration.
Where applicable, Newton's method converges much faster towards a local maximum or minimum than gradient descent. In fact, every local minimum has a neighborhood such that, if we start with Newton's method with step size converges quadratically (if the Hessian is invertible and a Lipschitz continuous function of in that neighborhood).
Finding the inverse of the Hessian in high dimensions can be an expensive operation. In such cases, instead of directly inverting the Hessian it's 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 is a positive definite matrix. While this may seem like a limitation, it's often 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 will need to be done with a method that will work for such, such as the LDLT 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 so as to make positive definite. One approach is to diagonalize and choose so that has the same eigenvectors as, but with each negative eigenvalue replaced by
An approach exploited in the Levenberg–Marquardt algorithm (which uses an approximate Hessian) is to add a scaled identity matrix to the Hessian, with the scale adjusted at every iteration as needed. For large 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.
Read more about this topic: Newton's Method In Optimization
Famous quotes containing the words higher and/or dimensions:
“It is the Late city that first defies the land, contradicts Nature in the lines of its silhouette, denies all Nature. It wants to be something different from and higher than Nature. These high-pitched gables, these Baroque cupolas, spires, and pinnacles, neither are, nor desire to be, related with anything in Nature. And then begins the gigantic megalopolis, the city-as-world, which suffers nothing beside itself and sets about annihilating the country picture.”
—Oswald Spengler (1880–1936)
“Is it true or false that Belfast is north of London? That the galaxy is the shape of a fried egg? That Beethoven was a drunkard? That Wellington won the battle of Waterloo? There are various degrees and dimensions of success in making statements: the statements fit the facts always more or less loosely, in different ways on different occasions for different intents and purposes.”
—J.L. (John Langshaw)