jsat.math.optimization

Class BacktrackingArmijoLineSearch

java.lang.Object

jsat.math.optimization.BacktrackingArmijoLineSearch

All Implemented Interfaces:

LineSearch

public class BacktrackingArmijoLineSearch
extends Object
implements LineSearch

An implementation of Backtraking line search using the Armijo rule. The search for alpha is done by quadratic and cubic interpolation without using any derivative evaluations.

Author:

Edward Raff

Constructor Summary

Constructors

Constructor and Description
BacktrackingArmijoLineSearch() Creates a new Backtracking line search
BacktrackingArmijoLineSearch(double rho, double c1) Creates a new Backtracking line search object

Method Summary

Modifier and Type	Method and Description
BacktrackingArmijoLineSearch	clone() Returns a clone of the line search object
double	getC1() Returns the sufficient decrease condition constant
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)
void	setC1(double c1) Sets the constant used for the sufficient decrease condition f(x+α p) ≤ f(x) + c1 α pT∇f(x)
boolean	updatesGrad() When performing the linear search step some line searches may or may not use the gradient information.

Methods inherited from class java.lang.Object

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

Constructor Detail

BacktrackingArmijoLineSearch

public BacktrackingArmijoLineSearch()

Creates a new Backtracking line search

BacktrackingArmijoLineSearch

public BacktrackingArmijoLineSearch(double rho,
                                    double c1)

Creates a new Backtracking line search object

Parameters:

rho - constant to decrease alpha by in (0, 1) when interpolation is not possible

c1 - the sufficient decrease condition condition constant in (0, 1/2)

Method Detail

setC1

public void setC1(double c1)

Sets the constant used for the sufficient decrease condition f(x+α p) ≤ f(x) + c₁ α p^T∇f(x)

Parameters:

c1 - the sufficient decrease condition

getC1

public double getC1()

Returns the sufficient decrease condition constant

Returns:

the sufficient decrease condition constant

lineSearch

public 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)

Description copied from interface: LineSearch

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

Specified by:

lineSearch in interface LineSearch

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

public 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)

Description copied from interface: LineSearch

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

Specified by:

lineSearch in interface LineSearch

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

public boolean updatesGrad()

Description copied from interface: LineSearch

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

Specified by:

updatesGrad in interface LineSearch

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

public BacktrackingArmijoLineSearch clone()

Description copied from interface: LineSearch

Returns a clone of the line search object

Specified by:

clone in interface LineSearch

Overrides:

clone in class Object

Returns:

a clone of the line search object