Parallel Line Search

Abstract

We consider the well-known line search algorithm that iteratively refines the search interval by subdivision and bracketing the optimum. In our applications, evaluations of the objective function typically require minutes or hours, so it becomes attractive to use more than the standard three steps in the subdivision, performing the evaluations in parallel. A statistical model for this scenario is presented giving the total execution time T in terms of the number of steps k and the probability distribution for the individual evaluation times. Both the model and extensive simulations show that the expected value of T does not fall monotonically with k, in fact more steps may significantly increase the execution time. We propose heuristics for speeding convergence by continuing to the next iteration before all evaluations are complete. Simulations are used to estimate the speedup achieved.