jsat.math.optimization

Class WolfeNWLineSearch

java.lang.Object

jsat.math.optimization.WolfeNWLineSearch

All Implemented Interfaces:

LineSearch

public class WolfeNWLineSearch
extends java.lang.Object
implements LineSearch

An implementation of the Wolfe Line Search algorithm described by Nocedal and Wright in Numerical Optimization (2nd edition) on pages 59-63.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	WolfeNWLineSearch.AlphaInit

Constructor Summary

Constructors

Constructor and Description
WolfeNWLineSearch() Creates a new Wolfe line search with setC1(double) set to 1e-4 and setC2(double) to 0.9
WolfeNWLineSearch(double c1, double c2) Creates a new Wolfe line search

Method Summary

Modifier and Type	Method and Description
WolfeNWLineSearch	clone() Returns a clone of the line search object
double	getC1() Returns the sufficient decrease condition constant
double	getC2() Returns the curvature 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, boolean parallel) 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) This value must always be less than setC2(double)
void	setC2(double c2) Sets the constant used for the curvature condition pT ∇f(x+α p) ≥ c2 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, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jsat.math.optimization.LineSearch

lineSearch

Constructor Detail

WolfeNWLineSearch

public WolfeNWLineSearch()

Creates a new Wolfe line search with setC1(double) set to 1e-4 and setC2(double) to 0.9

WolfeNWLineSearch

public WolfeNWLineSearch(double c1,
                         double c2)

Creates a new Wolfe line search

Parameters:

c1 - the sufficient decrease condition constant

c2 - the curvature condition constant

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)

This value must always be less than setC2(double)

Parameters:

c1 - the sufficient decrease condition

getC1

public double getC1()

Returns the sufficient decrease condition constant

Returns:

the sufficient decrease condition constant

setC2

public void setC2(double c2)

Sets the constant used for the curvature condition p^T ∇f(x+α p) ≥ c₂ p^T∇f(x)

Parameters:

c2 - the curvature condition constant

getC2

public double getC2()

Returns the curvature condition constant

Returns:

the curvature 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,
                         boolean parallel)

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 line search 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

parallel - true if this line search should be done using multiple cores, or false to be single threaded.

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 WolfeNWLineSearch clone()

Description copied from interface: LineSearch

Returns a clone of the line search object

Specified by:

clone in interface LineSearch

Overrides:

clone in class java.lang.Object

Returns:

a clone of the line search object