Rank Ordering And Positive Bases In Pattern Search Algorithms

. We present two new classes of pattern search algorithms for unconstrained minimization: the rank ordered and the positive basis pattern search methods. These algorithms can nearly halve the worst case cost of an iteration compared to the classical pattern search algorithms. The rank ordered pattern search methods are based on a heuristic for approximating the direction of steepest descent, while the positive basis pattern search methods are motivated by a generalization of the geometry characteristic of the patterns of the classical methods. We describe the new classes of algorithms and present the attendant global convergence analysis. Key words. direct search methods, pattern search, positive linear dependence 1. Introduction. In this paper we introduce two new classes of pattern search algorithms: the rank ordered and positive basis pattern search methods for the unconstrained minimization problem minimize x#R n f(x). The rank ordered and positive basis pattern search methods e..