jsat.math.optimization

Interface LineSearch

All Known Implementing Classes:

BacktrackingArmijoLineSearch, WolfeNWLineSearch

public interface LineSearch

Line search defines a method of minimizing a function φ(α) = f(x+α p) where α > 0 is a scalar value, and x and p are fixed vectors.

Different line search methods may or may not use all the input variables.

The LineSearch is allowed to maintain a history of update values to use on future calls. For this reason, a clone of the line search should be used for each new optimization problem.

Author:

Edward Raff

Method Summary

Modifier and Type	Method and Description
LineSearch	clone() Returns a clone of the line search object
double	lineSearch(double alpha_max, Vec x_k, Vec x_grad, Vec p_k, Function f, FunctionVec fp, double f_x, double gradP, Vec x_alpha_pk, double[] fxApRet, Vec grad_x_alpha_pk) Attempts to find the value of α that minimizes f(x+α p)
double	lineSearch(double alpha_max, Vec x_k, Vec x_grad, Vec p_k, Function f, FunctionVec fp, double f_x, double gradP, Vec x_alpha_pk, double[] fxApRet, Vec grad_x_alpha_pk, ExecutorService ex) Attempts to find the value of α that minimizes f(x+α p)
boolean	updatesGrad() When performing the linear search step some line searches may or may not use the gradient information.

Method Detail

lineSearch

double lineSearch(double alpha_max,
                  Vec x_k,
                  Vec x_grad,
                  Vec p_k,
                  Function f,
                  FunctionVec fp,
                  double f_x,
                  double gradP,
                  Vec x_alpha_pk,
                  double[] fxApRet,
                  Vec grad_x_alpha_pk)

Attempts to find the value of α that minimizes f(x+α p)

Parameters:

alpha_max - the maximum value for α to search for

x_k - the initial value to search from

x_grad - the gradient of ∇ f(x_k)

p_k - the direction update

f - the function to minimize the value of f(x_k + α p_k)

fp - the gradient of f, ∇f(x), may be null depending upon the linesearch method

f_x - the value of f(x_k), or Double.NaN if it needs to be computed

gradP - the value of ∇f(x_k)^Tp_k, or Double.NaN if it needs to be computed

x_alpha_pk - the location to store the value of x_k + α p_k

fxApRet - an array to store the computed result of f(x_k + α p_k) in the first index contain. May be null and the value will not be returned

grad_x_alpha_pk - location to store the value of ∇ f(x_kα+p_k). May be null, local storage will be allocated if needed

Returns:

the value of α that satisfies the line search in minimizing f(x_k + α p_k)

lineSearch

double lineSearch(double alpha_max,
                  Vec x_k,
                  Vec x_grad,
                  Vec p_k,
                  Function f,
                  FunctionVec fp,
                  double f_x,
                  double gradP,
                  Vec x_alpha_pk,
                  double[] fxApRet,
                  Vec grad_x_alpha_pk,
                  ExecutorService ex)

Attempts to find the value of α that minimizes f(x+α p)

Parameters:

alpha_max - the maximum value for α to search for

x_k - the initial value to search from

x_grad - the gradient of ∇ f(x_k)

p_k - the direction update

f - the function to minimize the value of f(x_k + α p_k)

fp - the gradient of f, ∇f(x), may be null depending upon the linesearch method

f_x - the value of f(x_k), or Double.NaN if it needs to be computed

gradP - the value of ∇f(x_k)^Tp_k, or Double.NaN if it needs to be computed

x_alpha_pk - the location to store the value of x_k + α p_k

fxApRet - an array to store the computed result of f(x_k + α p_k) in the first index contain. May be null and the value will not be returned

grad_x_alpha_pk - location to store the value of ∇ f(x_kα+p_k). May be null, local storage will be allocated if needed

ex - the source of threads for parallel computation, or null to perform serial computation

Returns:

the value of α that satisfies the line search in minimizing f(x_k + α p_k)

updatesGrad

boolean updatesGrad()

When performing the linear search step some line searches may or may not use the gradient information. If the gradient information is used and updated, this method will return true. If not the given vector will be unused and not updated, and this method will return false

Returns:

true if the grad_x_alpha_pk parameter of lineSearch will be up-to-date after the call, or false if the gradient value will need to be computed after.

clone

LineSearch clone()

Returns a clone of the line search object

Returns:

a clone of the line search object