Parallel Minimax Searching Algorithm for Extremum of Unimodal Unbounded Function

• 作者: Boris S. Verkhovsky
• 来源期刊: 通讯、网络与系统学国际期刊(英文)
• 学科: 数学
• 关键词: Adversarial MINIMAX Analysis DESIGN Parameters Dynamic Programming FUNCTION Evaluation Optimal ALGORITHM PARALLEL ALGORITHM System DESIGN Statistical Experiments Time Complexity Unbounded Search UNIMODAL FUNCTION
• 年，卷（期）: 2011,（9）
• 页码范围: 549-561
• 页数: 13页
• 分类号: O1

摘要

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.