Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function

Boris S. Verkhovsky

.

DOI: 10.4236/ijcns.2011.49066                

Abstract

In this paper we consider a parallel algorithm that detects the maximizer of unimodal function f(x) 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 f 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 (n-1], then it can be detected after c_p(n)=「2log_「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.

Keywords

Adversarial Minimax Analysis, Design Parameters, Dynamic Programming, Function Evaluation, Optimal Algorithm, Parallel Algorithm, System Design, Statistical Experiments, Time Complexity, Unbounded Search, Unimodal Function

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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
[2]	R. Beigel, “Unbounded Searching Algorithm,” SIAM Journal of Computing, Vol. 19, No. 3, 1990, pp. 522-537. doi:10.1137/0219035
[3]	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
[4]	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
[5]	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
[6]	A. S. Nemirovsky and D. B. Yudin, “Problems Complexity and Method Efficiency in Optimization,” Wiley-Interscience, New York, 1983.
[7]	J. F. Traub and H. Wozniakowski, “A General Theory of Optimal Algorithms,” Academic Press, San Diego, 1980.
[8]	J. H. Beamer and D. J. Wilder, “Minimax Optimization of Unimodal Function by Variable Block Search,” Management Science, Vol. 16, 1970, pp. 629-641.
[9]	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
[10]	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
[11]	L. T. Oliver and D. J. Wilde, “Symmetric Sequential Minimax Search for a Maximum,” Fibonacci Quarterly, Vol. 2, No. 3, 1964, pp. 169-175.
[12]	C. Witzgall, “Fibonacci Search with Arbitrary First Evaluation,” Fibonacci Quaterly, Vol. 10, No. 2, 1972, pp. 113-134.
[13]	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
[14]	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
[15]	R. Karp and W. L. Miranker, “Parallel Minimax Search for a Maximum,” Journal of Combinatorial Theory, Vol. 4, 1968, pp. 59-90.
[16]	B. Verkhovsky, “Optimal Search Algorithm for Extrema of a Discrete Periodic Bimodal Function,” Journal of Complexity, Vol. 5, No. 2, 1989, pp. 238-250. doi:10.1016/0885-064X(89)90006-X
[17]	B. Veroy (Verkhovsky), “Optimal Algorithm for Search of Extrema of a Bimodal Function,” Journal of Complexity, Vol. 2, No. 4, 1986, pp. 323-332. doi:10.1016/0885-064X(86)90010-5
[18]	B. Veroy, “Optimal Search Algorithm for a Minimum of a Discrete Periodic Bimodal Function,” Information Processing Letters, Vol. 29, No. 5, 1988, pp. 233-239. doi:10.1016/0020-0190(88)90115-9
[19]	S. Gal, “Sequential Minimax Search for a Maximum When Prior Information Is Available,” SIAM Journal of Applied Mathematics, Vol. 21, No. 4, 1971, pp. 590-595. doi:10.1137/0121063
[20]	Yu. I. Neymark and R. T. Strongin, “Informative Approach to a Problem of Search for an Extremum of a Function,” Technicheskaya Kibernetika, Vol. 1, 1966, pp. 7-26.
[21]	R. Horst and P. M. Pardalos, “Handbook of Global Optimization,” Kluwer Academic Publishers, Norwell, 1994.
[22]	B. O. Shubert, “A Sequential Method Seeking the Global Maximum of a Function,” SIAM Journal of Numerical Analysis, Vol. 3, No. 1, 1972, pp. 43-51.
[23]	L. N. Timonov, “Search Algorithm for a Global Extremum,” Technicheskaya Kibernetika, Vol. 3, 1977, pp. 53- 60.
[24]	A. J. Hoffman and P. Wolfe, “Minimizing a Unimodal Function of Two Integer Variables,” Mathematical programming, II. Mathematical Programming Studies, Vol. 25, 1985, pp. 76-87.
[25]	A. I. Kuzovkin, “A Generalization of Fibonacci Search to the Multidimensional Case,” èkonomka i Matematicheskie Metody, Vol. 21, No. 4, 1968, pp. 931-940.
[26]	J. C. Kiefer, “Optimal Sequential Search and Approximation Methods under Minimum Regularity Assumptions,” SIAM Journal of Applied Mathematics, Vol. 5, 1957, pp. 105-136. doi:10.1137/0105009
[27]	S. Gal, “A Discrete Search Game,” SIAM Journal of Applied Mathematics, Vol. 27, No. 4, 1974, pp. 641-648. doi:10.1137/0127054
[28]	B. Verkhovsky, “Optimal Algorithm for Search of a Maximum of n-Modal Function on Infinite Interval,” In: D. Du and P. M. Pardalos, Eds., Minimax and Applications, Academic Publisher, Kluwer, 1997, pp. 245-261.
[29]	B. Verkhovsky, “Parallel Minimax Unbounded Searching for a Maximum of a Unimodal Function,” Research Report, CIS-95-03, New Jersey Institute of Technology, Newark, 1995, pp. 1-24.