TITLE:
Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function
AUTHORS:
Boris S. Verkhovsky
KEYWORDS:
Adversarial Minimax Analysis, Design Parameters, Dynamic Programming, Function Evaluation, Optimal Algorithm, Parallel Algorithm, System Design, Statistical Experiments, Time Complexity, Unbounded Search, Unimodal Function
JOURNAL NAME:
International Journal of Communications, Network and System Sciences,
Vol.4 No.9,
September
23,
2011
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 cp(n)=「2log「p/2」+1(n+1)」-1 parallel evaluations of f(x), where p is the number of processors.