Parallel Line Search

There are no files associated with this record.

Title Parallel Line Search
Author Peachey, T. C.; Abramson, D.; Lewis, Andrew
Book Title Optimization: Structure and Applications
Editor C. Pearce and E. Hunt
Year Published 2009
Place of publication New York
Publisher Springer
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.
Peer Reviewed Yes
Published Yes
Publisher URI http://www.springerlink.com/
Alternative URI http://dx.doi.org/10.1007/978-0-387-98096-6_20
Chapter Number 20
Page from 369
Page to 381
ISBN 978-0-387-98095-9
Date Accessioned 2009-09-21
Date Available 2010-08-19T07:04:59Z
Language en_AU
Faculty Faculty of Science, Environment, Engineering and Technology
Subject Optimisation
URI http://hdl.handle.net/10072/29270
Publication Type Book Chapters
Publication Type Code b1

Brief Record

Griffith University copyright notice