Scientific Research

An Academic Publisher

**Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function** ()

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

Share and Cite:

B. Verkhovsky, "Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function,"

*International Journal of Communications, Network and System Sciences*, Vol. 4 No. 9, 2011, pp. 549-561. doi: 10.4236/ijcns.2011.49066.Conflicts of Interest

The authors declare no conflicts of interest.

[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. |

Copyright © 2020 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.