Newton's Method

Overview


Newtons method is a method to numerically find the optimal value of function through an interative procedure that converges to the solution under some conditions. It works well when the function is convex, or a point near the optimum is known.

The newton library can be found at Newton.mjs

Intuition


Newtons method is an optimization technique inspired by the Taylor Series.

The first step of the optimization is to approximate the function to be optimized by the first two terms in the Taylor series. That is,
{% f(x) \approx f(x_0) + \frac{df(x)}{dx} \Delta x + \frac{1}{2}\frac{d^2f(x)}{dx^2} \Delta x^2 %}
The optimal value of this approximating function can be found exactly, by taking the derivative of the funciton with respect to {% \Delta x %} and setting the result equal to zero. (see analytic optimization through differentiation)

{% \frac{df(x)}{dx} + \frac{d^2f(x)}{dx^2} \Delta x = 0 %}
{% \Delta x = -\frac{df(x)}{dx} / \frac{d^2f(x)}{dx^2} %}


Unless the function has only two Taylor terms, the result will not be the optimal value, but will be closer to the optimal value assuming some conditions on the function. Then the process is run iteratively until it has sufficiently converged to the solution.

The same intuition is used in the general formulatin of a multi-variable function, using the multi-variable Taylors theorem and linear algebra.

Algorithm


The algorithm starts with a set of inputs {% \theta_{0} %}, and then interatively updates the parameters according to the following formula:

{% \vec{ \theta_{k+1} } = \vec{ \theta_k } - \nu_k H_k ^{-1} \vec{g_k} %}


where {% \theta_{k} %} is the kth iteration of the function arguments, {% H_k %} is the Hessian at the kth iteration, {% \vec{g_k} %} is the gradient. {% \nu_k %} is a speed parameter, which is set by the user to tune the algorithm. 


let op = await import('/lib/numeric/optimization/v1.0.0/newton.mjs');

let f = function(x){
  return -1*x[0]*x[0]*(x[1]-0.2)*(x[1]-0.2);
}
let x = [1,1];
let test = op.optimize(f, x);
Try it!

(see murphy - pg. 249)

Pitfalls


There are known situations in which Newtons method will not converge. In these cases, one should use another algorithm, such as gradient descent

Contents