org.ddogleg.optimization.impl

Class SearchInterpolate

java.lang.Object

org.ddogleg.optimization.impl.SearchInterpolate

public class SearchInterpolate
extends java.lang.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) + c₁α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 and Description
SearchInterpolate()

Method Summary

Modifier and Type	Method and 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

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

Constructor Detail

SearchInterpolate

public SearchInterpolate()

Method Detail

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.

&phi;(&alpha;) = a*&alpha;<sup>3</sup> + b*&alpha;<sup>2</sup> + &alpha;<sup>3</sup> + &alpha;*&phi;'(0) + &phi;(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