We have one more one dimensional search method to go over, and this one is important. I am sure you are familiar with Isaac Newton Well this method is named after him. Newton’s method like both GSS and FS Newton’s method helps us find the minimum of our function, but Newton’s method varies greatly from these two.
The first and most important thing when thinking about using Newton’s method is to ensure that the function is twice differentiable. Newton’s method uses a truncated taylor series to estimate where the minimum lies. But we are getting ahead of ourselves. Let’s start from the beginning.Newton’s method uses a single point to begin, unlike the GSS and FS. This point is used as a basis for our Taylor expansion. We need to take a brief detour to go over why we want to construct a Taylor Expansion. Just a quick reminder, a Taylor series (or expansion) is an approximation of a function as a sum of terms that are determined by the functions derivatives at a single point. This is described by the equation below (from wikipedia):
As you can see, each term of the expansion has a derivative of the function evaluated at the same point. For our method, we are only going to concern ourselves with the first three terms. This is why we need our function to be twice differentiable. This allows us to create a taylor expansion based off our initial guess (and our following guesses). But why would we want to do this? What is the benefit? Making a Taylor expansion allows us to create a quadratic function through our initial point which has the same first and second derivatives as our function. Our quadratic function (k(x)) is listed below:
We then try to minimize our new function. Using the first order necessary condition for a minimizer (the first derivative must equal zero at the minimizer), we take the derivative of the above equation and set it equal to zero. This produces the following:
In order to find the minimum we need to solve for x. We do this in hopes that the x we solve for is closer to the minimum of our true function. This is shown below:
This looks awfully like our iterative steps from GSS and FS. Replace x0 with xi and x with xi+1 and we have a search method. Like GSS and FS, we then repeat our method in hopes of getting closer to our minimum. As we get closer to our minimum the first derivative of our function moves toward 0 which makes xi ≈ xi+1. This is when we know our method has found a minimum (hopefully). Like GSS, we use a tolerance termination condition rather than certain number of iterations like FS.Hopefully you followed me on this brief overview of our third ODSM. Next post we use a real example.-Marcello