Newton's Method for Minimisation

Minimise a function with Newton's method.

Gradient descent uses only the slope. Newton's method also uses the curvature, given by the Hessian matrix H of second derivatives. At each point it fits a quadratic to the function and jumps straight to the minimum of that quadratic:

x_new = x - solve(H(x), grad(x))

On a quadratic function this reaches the exact minimum in one step. Near a minimum of a smooth function it converges very fast, because the error roughly squares at each step.

Start at x0 and do at most steps updates. Stop early when the norm of the gradient is below tol. Return the final point.

Function signature

def newton_minimize(grad_fn, hess_fn, x0, steps=20, tol=1e-10):

Example

Input

# f(x, y) = (x - 1) ** 2 + 2 * (y + 3) ** 2
grad_fn = lambda p: np.array([2 * (p[0] - 1), 4 * (p[1] + 3)])
hess_fn = lambda p: np.array([[2.0, 0.0], [0.0, 4.0]])
newton_minimize(grad_fn, hess_fn, np.array([0.0, 0.0]))

Output

array([ 1., -3.])

Reasoning

At (0, 0) the gradient is (-2, 12). Solving H d = g gives d = (-1, 3), and x - d = (1, -3). The function is a quadratic, so this one step lands on the minimum. The gradient is then zero, so the loop stops.

Constraints and notes

• Use a linear solve such as np.linalg.solve, not an explicit inverse.
• You can assume the Hessian is invertible at every point you visit.
• Do not modify x0.