Optimization (Finding Max. and Min.) Using Quadratic Interpolation Method

by admin in , , , on April 26, 2019

This code uses Quadratic Interpolation method to find the optimum value of a given function within a predefined given interval.

Code Outputs:

  • Optimal Value Location
  • Optimal Value itself
  • The Accuracy of Result
  • Number of Iterations
  • Chart for the Position of the Optimal Value on the Given Function
  • Error Chart
  • Chart of the Optimal Value Convergence
  • Printed Values for (Optimal Value and Possition, Accuracy and Number of Iterations)

Optimal x: 1.4276 , Optimal Value: 1.7757 , accuray: 5.8172e-07 , NO Iterations: 11

Required Inputs:

  • The function Wanted to be Optimized
  • The Interval that you expect the optimal value located within it (make it large it you don’t know it)
  • Minimal Accuracy of the Result
  • Maximum Number of Iterations (The code has a self breaking algorithm when finding the answer)

 

About the Method:

Interpolation methods are a common approach to the more general area of line search for optimization. In the case of quadratic interpolation, the function’s critical value is bracketed, and a quadratic interpolant is fitted to the arc contained in the interval. Then, the interpolant is minimized, and the new interval is determined based on the relation of the minimizer to the original endpoints of the interval.

Put more formally, let x* maximize (or minimize) f(x). If x* is not easily found through analytic methods, then it is significantly easier to bracket the interval over which this critical point occurs. Let q(x) denote the quadratic interpolant of f(x). Minimizing a quadratic function is trivial, and so the critical point of q is easily obtained. We then form a new bracketing interval by throwing away the ”worst” point, which for our purposes would be the point that is the largest or smallest, depending on whether we want to approximate a maximum or minimum. The process is then iterated until a desired precision is reached.

 

Quadratic Interpolation Method:

This is a 3 point interpolation-optimization method.  Choose 3 points, 2 end points to bracket our critical point, and then a point within the interval as well. Using the Lagrange Interpolation formula, we can easily find our
interpolant q(x). We have:

To find the optimum value, we of course take the derivative of q(x) and set it to 0. By doing this, we obtain:

And the iteration scheme is easily deduced:

This method differs slightly from the previous two methods, because it is not as simple to determine the new bracketing interval. If xmin lies between x1 and x3, then we want to compare the distance between
xmin and x2. If  |xmin − x2| < er

Where er is the prescribed tolerance, then we are done. Otherwise we create the new interval by checking which point is the largest or smallest, depending on the nature of our critical point. If xmin lies outside of our bracketing interval [x1, x3], then we immediately create a new bracketing interval in the same way as we just described.

 

References:

[1] KELLER VANDEBOGERT, METHOD OF QUADRATIC INTERPOLATION, September 3, 2017.

[2] Wenyu Sun, YaXiang Yuan. Optimization Theory and Methods: Nonlinear Programming. 89-98.

1 Sale

Share Now!

Release Information

  • Price
    :

    $4.99

  • Released
    :

    April 26, 2019

  • Last Updated
    :

    May 29, 2019

Share Your Valuable Opinions