%0 Journal Article
%T Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function
%A Boris S. Verkhovsky
%J Int'l J. of Communications, Network and System Sciences
%P 549-561
%@ 1913-3723
%D 2011
%I Scientific Research Publishing
%R 10.4236/ijcns.2011.49066
%X 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.
%K Adversarial Minimax Analysis
%K Design Parameters
%K Dynamic Programming
%K Function Evaluation
%K Optimal Algorithm
%K Parallel Algorithm
%K System Design
%K Statistical Experiments
%K Time Complexity
%K Unbounded Search
%K Unimodal Function
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=7320