Performs an inexact line-search for optimization . Finds a step-size satisfying the Wolfe conditions by binary search.

WolfeConditionInexactLineSearch.java

//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;
}