package jsat.math.optimization;
import jsat.linear.Vec;
import jsat.math.Function;
import jsat.math.FunctionVec;
/**
* 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
*/
public class BacktrackingArmijoLineSearch implements LineSearch
{
private double rho;
private double c1;
/**
* Creates a new Backtracking line search
*/
public BacktrackingArmijoLineSearch()
{
this(0.5, 1e-1);
}
/**
* Creates a new Backtracking line search object
* @param rho constant to decrease alpha by in (0, 1) when interpolation is
* not possible
* @param c1 the sufficient decrease condition condition constant in
* (0, 1/2)
*/
public BacktrackingArmijoLineSearch(double rho, double c1)
{
if(!(rho > 0 && rho < 1))
throw new IllegalArgumentException("rho must be in (0,1), not " + rho);
this.rho = rho;
setC1(c1);
}
/**
* Sets the constant used for the sufficient decrease condition
* f(x+α p) ≤ f(x) + c1 α pT∇f(x)
* @param c1 the sufficient decrease condition
*/
public void setC1(double c1)
{
if(c1 <= 0 || c1 >= 0.5)
throw new IllegalArgumentException("c1 must be in (0, 1/2) not " + c1);
this.c1 = c1;
}
/**
* Returns the sufficient decrease condition constant
* @return the sufficient decrease condition constant
*/
public double getC1()
{
return c1;
}
@Override
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)
{
if(Double.isNaN(f_x))
f_x = f.f(x_k, parallel);
if(Double.isNaN(gradP))
gradP = x_grad.dot(p_k);
double alpha = alpha_max;
if(x_alpha_pk == null)
x_alpha_pk = x_k.clone();
else
x_k.copyTo(x_alpha_pk);
x_alpha_pk.mutableAdd(alpha, p_k);
double f_xap = f.f(x_alpha_pk, parallel);
if(fxApRet != null)
fxApRet[0] = f_xap;
double oldAlpha = 0;
double oldF_xap = f_x;
while (f_xap > f_x + c1 * alpha * gradP)//we return start if its already good
{
final double tooSmall = 0.1*alpha;
final double tooLarge = 0.9*alpha;
//see INTERPOLATION section of chapter 3.5
//XXX double compare.
if(alpha == alpha_max)//quadratic interpolation
{
double alphaCandidate = -gradP*oldAlpha*oldAlpha/(2*(f_xap-f_x-gradP*oldAlpha));
oldAlpha = alpha;
if(alphaCandidate < tooSmall || alphaCandidate > tooLarge || Double.isNaN(alphaCandidate))
{
alpha = rho*oldAlpha;
}
else
{
alpha = alphaCandidate;
}
}
else//cubic interpoation
{
//g = φ(α1)−φ(0)−φ'(0)α1
double g = f_xap-f_x-gradP*alpha;
//h = φ(α0) − φ(0) − φ'(0)α0
double h = oldF_xap-f_x-gradP*oldAlpha;
double a0Sqrd = oldAlpha*oldAlpha;
double a1Sqrd = alpha*alpha;
double a = a0Sqrd*g-a1Sqrd*h;
a /= (a0Sqrd*a1Sqrd*(alpha-oldAlpha));
double b = -a0Sqrd*oldAlpha*g+a1Sqrd*alpha*h;
b /= (a0Sqrd*a1Sqrd*(alpha-oldAlpha));
double alphaCandidate = (-b + Math.sqrt(b*b-3*a*gradP))/(3*a);
oldAlpha = alpha;
if(alphaCandidate < tooSmall || alphaCandidate > tooLarge || Double.isNaN(alphaCandidate))
{
alpha = rho*oldAlpha;
}
else
{
alpha = alphaCandidate;
}
}
if(alpha < 1e-20)
return oldAlpha;
x_alpha_pk.mutableSubtract(oldAlpha - alpha, p_k);
oldF_xap = f_xap;
f_xap = f.f(x_alpha_pk, parallel);
if(fxApRet != null)
fxApRet[0] = f_xap;
}
return alpha;
}
@Override
public boolean updatesGrad()
{
return false;
}
@Override
public BacktrackingArmijoLineSearch clone()
{
return new BacktrackingArmijoLineSearch(rho, c1);
}
}
Ads help maintain this website.