Author(s)

Boris S. Verkhovsky

.

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.

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

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.