1-dimensional optimization

import numpy as np

import matplotlib.pyplot as plt

from numpy.polynomial.polynomial import polyfit,polyval

def f1(x):

  return (x**2)/10 - 2*np.sin(x)

We would like to minimize the function inline_formula not implemented over the interval inline_formula not implemented using the method of successive parabolic interpolation.

xs = np.linspace(-1,5,100)

plt.plot(xs,f1(xs),'r-')

plt.grid()

We start by choosing three points on the x-axis, and computing the value of the function at these three points. Let us start with these three points: inline_formula not implemented

xvals = np.array([0,1,4])

yvals = f1(xvals)

plt.plot(xs,f1(xs),'r-',xvals,yvals,'ro')

plt.grid()

We now interpolate between these three points, finding the unique parabola that goes through all three:

coeffs_polynomial = polyfit(xvals,yvals,2)

plt.plot(xs,f1(xs),'r-',xvals,yvals,'ro',xs,polyval(xs,coeffs_polynomial),'b-')

plt.grid()

Now that we have this parabola, let's find its minimum using the formula that inline_formula not implemented, i.e., we can use the coefficients of a quadratic polynomial to simply calculate its minimum. This will be our new point, inline_formula not implemented.

xnew1=-coeffs_polynomial[1]/(2*coeffs_polynomial[2])

print(xnew1)

This is now our new point. We retain the two points that are closest to this new point. Thus, we can now repeat this process using the following three values of x :inline_formula not implemented.

xvals = np.array([0,xnew1,1])

yvals = f1(xvals)

plt.plot(xs,f1(xs),'r-',xvals,yvals,'ro')

plt.grid()

Once again, we can interpolate a polynomial between these three points:

coeffs_polynomial = polyfit(xvals,yvals,2)

plt.plot(xs,f1(xs),'r-',xvals,yvals,'ro',xs,polyval(xs,coeffs_polynomial),'b-')

plt.grid()

and find its minimum:

xnew2=-coeffs_polynomial[1]/(2*coeffs_polynomial[2])

print(xnew2)

xvals = np.array([xnew1,xnew2,1])

yvals = f1(xvals)

plt.plot(xs,f1(xs),'r-',xvals,yvals,'ro')

plt.grid()

Once again, we can interpolate a polynomial between these three points:

coeffs_polynomial = polyfit(xvals,yvals,2)

plt.plot(xs,f1(xs),'r-',xvals,yvals,'ro',xs,polyval(xs,coeffs_polynomial),'b-')

plt.grid()

and the minimum of this polynomial is even closer to the true minimum of the function

xnew3=-coeffs_polynomial[1]/(2*coeffs_polynomial[2])

print(xnew3)