A deterministic algorithm for global optimization
type: Item
instance of: scholarly article
title: A deterministic algorithm for global optimization
zbMATH Open document ID: 0807.90103
DOI: 10.1007/BF01581266
author: Leo Breiman
author: Adele Cutler
published in: Mathematical Programming. Series A. Series B
publication date: 1993-06-29T00:00:00Z
review text: Consider the global optimization problem (1) \(\max_{x\in X} f(x)\), where \(f: X\to\mathbb{R}^ 1\) is a differentiable function and \(X\subset \mathbb{R}^ m\) is a compact polytope. To solve (1) the author presents a deterministic space covering algorithm strictly related to algorithms introduced in the literature by \textit{B. O. Shubert} [SIAM J. Numer. Analysis 9, No. 3, 379--388 (1972; Zbl 0251.65052)] and by \textit{R. H. Mladineo} [Math. Program. 34, 188--200 (1986; Zbl 0598.90075)]. While those authors assumed \(f\) to satisfy the Lipschitz condition, in this paper the following condition is assumed to hold: \[ f(x)\leq f(y)+ \nabla f(y)'(x- y)+ K\| x- y\|^ 2\quad\text{for any }x,y\in X, \] where \(K\) is a known constant. This leads to simpler geometric properties. The main idea of the algorithm is to construct a sequence of upper envelopes for \(f\); their global maxima are easily found and converge to the solution of (1). An implementation of the algorithm has been tested in solving standard test functions; the results are reported.
Mathematics Subject Classification ID: 90C30
zbMATH DE Number: 221249
zbMATH Keywords: deterministic space covering algorithm
reviewed by: Marco Gaviano
describes a project that uses: BRENT
MaRDI profile type: Publication
cites work: Q4180153
cites work: A method of unconstrained global optimization
cites work: Q5657612
cites work: Q4068464
cites work: Q4165315
cites work: Generalized descent for global optimization
cites work: An algorithm for finding the global maximum of a multimodal, multivariate function
cites work: An algorithm for finding the absolute extremum of a function
cites work: Global optimization by controlled random search
cites work: Stochastic global optimization methods part I: Clustering methods
cites work: Stochastic global optimization methods part II: Multi level methods
cites work: A Sequential Method Seeking the Global Maximum of a Function
cites work: The determination of the location of the global maximum of a function in the presence of several local extrema
cites work: A multi-start global minimization algorithm with dynamic search trajectories
cites work: A Monte Carlo simulated annealing approach to optimization over continuous variables
description: scientific article; zbMATH DE number 221249