Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function
- 1
Abstract
In this paper we consider a parallel algorithm that detects the maximizer of unimodal function <i>f(x)</i> computable at every point on unbounded interval (0, ∞). The algorithm consists of two modes: scanning and detecting. Search diagrams are introduced as a way to describe parallel searching algorithms on unbounded intervals. Dynamic programming equations, combined with a series of liner programming problems, describe relations between results for every pair of successive evaluations of function <i>f</i> in parallel. Properties of optimal search strategies are derived from these equations. The worst-case complexity analysis shows that, if the maximizer is located on a priori unknown interval (<i>n</i>-1], then it can be detected after <i>c</i><sub><i>p</i></sub>(<i>n</i>)=「2log<sub>「<i>p</i>/2」+1</sub>(n+1)」-1 parallel evaluations of <i>f(x)</i>, where p is the number of processors.
- J. L. Bentley and A. C.-C. Yao, “An Almost Optimal Algorithm for Unbounded Searching,” Information Processing Letters, Vol. 5, No. 1, 1976, pp. 82-87. doi:10.1016/0020-0190(76)90071-5
- R. Beigel, “Unbounded Searching Algorithm,” SIAM Journal of Computing, Vol. 19, No. 3, 1990, pp. 522-537. doi:10.1137/0219035
- E. M. Reingold and X. Shen, “More Nearly-Optimal Algorithms for Unbounded Searching, Part I, the Finite Case,” SIAM Journal of Computing, Vol. 20, No. 1, 1991, pp. 156-183. doi:10.1137/0220010
- E. M. Reingold and X. Shen, “More Nearly-Optimal Algorithms for Unbounded Searching, Part II, the Transfinite Case,” SIAM Journal of Computing, Vol. 20, No. 1, 1991, pp. 184-208. doi:10.1137/0220011
- A. S. Goldstein and E. M. Reingold, “A Fibonacci-Kraft Inequality and Discrete Unimodal Search,” SIAM Journal of Computing, Vol. 22, No. 4, 1993, pp. 751-777. doi:10.1137/0222049
- A. S. Nemirovsky and D. B. Yudin, “Problems Complexity and Method Efficiency in Optimization,” Wiley-Interscience, New York, 1983.
- J. F. Traub and H. Wozniakowski, “A General Theory of Optimal Algorithms,” Academic Press, San Diego, 1980.
- J. H. Beamer and D. J. Wilder, “Minimax Optimization of Unimodal Function by Variable Block Search,” Management Science, Vol. 16, 1970, pp. 629-641.
- D. Chasan and S. Gal, “On the Optimality of the Exponential Function for Some Minimax Problems,” SIAM Journal of Applied Mathematics, Vol. 30, No. 2, 1976, pp. 324-348. doi:10.1137/0130032
- J. C. Kiefer, “Sequential Minimax Search for a Maximum,” Proceedings of American Mathematical Society, Vol. 4, No. 3, 1953, pp. 502-506. doi:10.1090/S0002-9939-1953-0055639-3
- L. T. Oliver and D. J. Wilde, “Symmetric Sequential Minimax Search for a Maximum,” Fibonacci Quarterly, Vol. 2, No. 3, 1964, pp. 169-175.
- C. Witzgall, “Fibonacci Search with Arbitrary First Evaluation,” Fibonacci Quaterly, Vol. 10, No. 2, 1972, pp. 113-134.
- M. Avriel and D. J. Wilde, “Optimal Search for a Maximum with Sequences of Simultaneous Function Evaluations,” Management Science, Vol. 12, No. 9, 1966, pp. 722-731. doi:10.1287/mnsc.12.9.722
- S. Gal and W. L. Miranker, “Optimal Sequential and Parallel Search for Finding a Root,” Journal of Combinatorial Theory, Series A, Vol. 23, No. 1, 1977, pp. 1-14. doi:10.1016/0097-3165(77)90074-7