Package org.ddogleg.optimization.quasinewton

Class SearchInterpolate

java.lang.Object
org.ddogleg.optimization.quasinewton.SearchInterpolate
public class SearchInterpolate extends Object

Contains interpolation functions for use in line searches. These interpolation algorithms are designed to meet the condition below, without being too small,

Sufficient decrease equation:
f(α) ≤ f(0) + c1αg(0)
where f is the function, g is its derivative, and α is the step length.

See Chapter 3 in "Numerical Optimization 2nd Ed." by Jorge Nocedal and Stephen J. Wright, 2006

  • Constructor Summary

    Constructors
    Constructor
    Description
    SearchInterpolate()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static double
    cubic(double f0, double g0, double f1, double alpha1, double f2, double alpha2)
    Interpolates the next step using a cubic model.
    static double
    cubic2(double f0, double g0, double x0, double f1, double g1, double x1)
    Cubic interpolation using the function and derivative computed at two different points.
    static double
    cubicSafe(double f0, double g0, double x0, double f1, double g1, double x1, double min, double max)
    Use cubic interpolation only if the cubic tends to infinity in the direction of the step or if the minim of the cubic is beyond x1.
    static double
    quadratic(double f0, double g0, double x0, double f1, double x1)
    Quadratic interpolation using two function values and one derivative.
    static double
    quadratic2(double g0, double x0, double g1, double x1)
    Quadratic interpolation using two derivatives.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • SearchInterpolate

      public SearchInterpolate()

  • Method Details

    • quadratic

      public static double quadratic(double f0, double g0, double x0, double f1, double x1)

      Quadratic interpolation using two function values and one derivative.

      Parameters:
      f0 - Value of f(x0)
      g0 - Derivative f'(x0)
      x0 - First sample point
      f1 - Value of f(x1)
      x1 - Second sample point
      Returns:
      Interpolated point

    • quadratic2

      public static double quadratic2(double g0, double x0, double g1, double x1)

      Quadratic interpolation using two derivatives.

      Parameters:
      g0 - Derivative f'(x0)
      x0 - First sample point
      g1 - Derivative f'(x1)
      x1 - Second sample point
      Returns:
      Interpolated point

    • cubic

      public static double cubic(double f0, double g0, double f1, double alpha1, double f2, double alpha2)

      Interpolates the next step using a cubic model. Interpolation works by solving for 'a' and 'b' in the equation below. Designed to minimize the number of times the derivative needs to be computed. Care has been taken reduce overflow/underflow by normalizing.

      φ(α) = a*α3 + b*α2 + α3 + α*φ'(0) + φ(0)

      Parameters:
      f0 - Function value at f(0)
      g0 - Derivative value at g(0)
      f1 - Function value at f(a1)
      alpha1 - value of a1
      f2 - Function value at f(a2)
      alpha2 - value of a2
      Returns:
      Interpolated step length

    • cubic2

      public static double cubic2(double f0, double g0, double x0, double f1, double g1, double x1)

      Cubic interpolation using the function and derivative computed at two different points. This particular implementation taken from [1] and appears to be designed to maximize stability.

      [1] MINPACK-2 source code http://ftp.mcs.anl.gov/pub/MINPACK-2/dcstep.f

      Parameters:
      f0 - Value of f(x0)
      g0 - Derivative f'(x0)
      x0 - First sample point
      f1 - Value of f(x1)
      g1 - Derivative g'(x1)
      x1 - Second sample point
      Returns:
      Interpolated point

    • cubicSafe

      public static double cubicSafe(double f0, double g0, double x0, double f1, double g1, double x1, double min, double max)

      Use cubic interpolation only if the cubic tends to infinity in the direction of the step or if the minim of the cubic is beyond x1. Otherwise the the step will be max if x0 > x1 else it will be min.

      [1] MINPACK-2 source code http://ftp.mcs.anl.gov/pub/MINPACK-2/dcstep.f

      Parameters:
      f0 - Value of f(x0)
      g0 - Derivative f'(x0)
      x0 - First sample point
      f1 - Value of f(x1)
      g1 - Derivative g'(x1)
      x1 - Second sample point
      Returns:
      Interpolated point