Pure adaptive search in global optimization
type: Item
instance of: scholarly article
title: Pure adaptive search in global optimization
zbMATH Open document ID: 0756.90086
DOI: 10.1007/BF01585710
author: Zelda B. Zabinsky
author: Robert L. Smith
published in: Mathematical Programming. Series A. Series B
publication date: 1992-06-28T00:00:00Z
review text: The authors provide a theoretical analysis of pure adaptive search for general global optimization. The algorithm proceeds by generating a sequence of points uniformly distributed in a sequence of nested regions of the feasible space. At any iteration the next point in the sequence is uniformly distributed over the region of feasible space containing all points that are strictly better in value to the previous points in the sequence. It has been shown in a paper by \textit{N. R. Patel, R. L. Smith, Z. B. Zabinsky} and \textit{B. Zelda} [ibid. 43, No. 3, 317-328 (1989; Zbl 0671.90047)] that for convex programs the expected number of iterations required to achieve a given accuracy of the solution increases at most linearly in the dimension of the problem. In this paper, the authors extend this linear complexity result for non-convex or global optimization problems satisfying the Lipschitz condition.
Mathematics Subject Classification ID: 90C30
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 90-08
zbMATH DE Number: 34353
zbMATH Keywords: random search
zbMATH Keywords: Monte Carlo optimization
zbMATH Keywords: complexity
zbMATH Keywords: pure adaptive search
zbMATH Keywords: global optimization
reviewed by: Nada Djuranović-Miličić
MaRDI profile type: Publication
cites work: Hit-and-run algorithms for the identification of nonredundant linear inequalities
cites work: Q5563181
cites work: Q4068464
cites work: Q4165315
cites work: Q4162318
cites work: Polynomial affine algorithms for linear programming
cites work: Estimation of the Minimum of a Function Using Order Statistics
cites work: Q5540119
cites work: A new polynomial-time algorithm for linear programming
cites work: Q3286701
cites work: Technical Note—The Asymptotic Extreme Value Distribution of the Sample Minimum of a Concave Function under Linear Constraints
cites work: Pure adaptive search in Monte Carlo optimization
cites work: A polynomial-time algorithm, based on Newton's method, for linear programming
cites work: Stochastic Methods for Global Optimization
cites work: Stochastic global optimization methods part I: Clustering methods
cites work: Stochastic global optimization methods part II: Multi level methods
cites work: Generating random vectors uniformly distributed inside and on the surface of different regions
cites work: Q5684493
cites work: Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
cites work: Minimization by Random Search Techniques
full work available at URL: https://doi.org/10.1007/bf01585710
OpenAlex ID: W1979881015
description: scientific article; zbMATH DE number 34353