Newton's Method for Optimization

Welcome to our lesson on Newton's Method for Optimization! This method helps us find the lowest point in a valley (minimum) or the highest peak on a mountain (maximum). By the end of this lesson, you'll understand Newton's Method, how it works, and how to use it in Python.

Imagine you're on a hike, looking for the lowest point in a valley. Newton's Method will guide you step-by-step to this point.

We're starting with a function $f(x)$ that we want to minimize. Let's use:

Here's a plot of this function:

This plot shows the function's landscape with multiple local minima and maxima.

To minimize this function using Newton's Method, we start with an initial guess. Let's choose $x_0 = 3$. The choice here is simply random.

The red point shows our starting point. We will update this guess step by step, moving closer to the minimum.

Newton's Method updates our guess using the first and second derivatives. The update formula is:

$x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}$

For our function $f(x) = x^4 - 3x^3 + 2$:

• $f'(x) = 4x^3 - 9x^2$
• $f''(x) = 12x^2 - 18x$

Important note: the Newton's method is designed to find the critical point. It could be a minimum, maximum or a saddle point.

Let's implement Newton's Method in Python and see it in action.

def f_prime(x):
    return 4*x**3 - 9*x**2

def f_double_prime(x):
    return 12*x**2 - 18*x

def newtons_method(f_prime, f_double_prime, x0, max_iterations=10, tolerance=1e-6):
    x = x0
    steps = [x]  # Track the optimization path
    for _ in range(max_iterations):
        f_prime_value = f_prime(x)
        f_double_prime_value = f_double_prime(x)
        
        if abs(f_prime_value) < tolerance:
            break  # Convergence criterion
        
        x = x - f_prime_value / f_double_prime_value
        steps.append(x)
        
    return x, steps

Here, we take multiple steps according to the formula above. We stop once the first derivative is very close to zero, indicating the minimum is reached. The code also defines the maximum amount of iterations. It is needed in case the minimum of the function doesn't exist or won't be found because the process will stuck in a loop.

Our function keeps track of all the steps, so we can plot it later.