Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Performs an inexact line-search for optimization . Finds a step-size satisfying the Wolfe conditions by binary search.
//Performs a binary search to satisfy the Wolfe conditions
//returns alpha where next x =should be x0 + alpha*d
//guarantees convergence as long as search direction is bounded away from being orthogonal with gradient
//x0 is starting point, d is search direction, alpha is starting step size, maxit is max iterations
//c1 and c2 are the constants of the Wolfe conditions (0.1 and 0.9 can work)
public static double stepSize(OptimizationProblem problem, double[] x0, double[] d, double alpha, int maxit, double c1, double c2){
//get error and gradient at starting point
double fx0 = problem.error(x0);
double gx0 = dot(problem.gradient(x0), d);
//bound the solution
double alphaL = 0;
double alphaR = 100;
for (int iter = 1; iter <= maxit; iter++){
double[] xp = add(x0, scale(d, alpha)); //get the point at this alpha
double erroralpha = problem.error(xp); //get the error at that point
if (erroralpha >= fx0 + alpha * c1 * gx0) { // if error is not sufficiently reduced
alphaR = alpha;//move halfway between current alpha and lower alpha
alpha = (alphaL + alphaR)/2.0;
}else{//if error is sufficiently decreased
double slopealpha = dot(problem.gradient(xp), d); // then get slope along search direction
if (slopealpha <= c2 * Math.abs(gx0)){ // if slope sufficiently closer to 0
return alpha;//then this is an acceptable point
}else if ( slopealpha >= c2 * gx0) { // if slope is too steep and positive then go to the left
alphaR = alpha;//move halfway between current alpha and lower alpha
alpha = (alphaL+ alphaR)/2;
}else{//if slope is too steep and negative then go to the right of this alpha
alphaL = alpha;//move halfway between current alpha and upper alpha
alpha = (alphaL+ alphaR)/2;
}
}
}
//if ran out of iterations then return the best thing we got
return alpha;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.