×

zbMATH — the first resource for mathematics

An algorithm for finding the global maximum of a multimodal, multivariate function. (English) Zbl 0598.90075
A method is presented for finding the global maximum of a Lipschitzian function f(x) (with Lipschitz constant K) over a cube \(A_ i\leq x^ i\leq B_ i\), \(i=1,2,...,N\) in \(R^ N\) \((x^ i\) is the i-th coordinate of x). Like a number of previously known methods, this one constructs a sequence of points \(x_ 0\), \(x_ 1,...,x_ n,...\), starting from an arbitrary point \(x^ 0\) in the cube, such that \(x_{n+1}\) is a global maximizer of \(F_ n(x)=\min \{Kx-x_ j| +f(x_ j): j=0,1,...,n\}\) over the cube (it is proved in the paper that any cluster point of such a sequence is a global maximizer of f, though the fact has been known previously). The main difficulty with this approach is how to find a global maximizer of a function of the form \(F(x)=\min \{K| x-x_ j| +h_ i:\) \(i=0,1,...,m\}\). Starting from the observation that the graph of F is the intersection of a number of conical surfaces, the author establishes that any point of the graph which corresponds to a relative maximum must be a solution to a system of N linear equations (in \(N+1\) variables \(x^ 1,...,x^ N,z)\) and a quadratic equation. She then proposes to compute the solutions of all such systems of equations in order to chose the global maximizer.
The algorithm seems to be efficient only for N very small. Actually, the computational experience is reported only for functions of two variables.
Reviewer: H.Tuy

MSC:
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L.C.W. Dixon and G.P. Szegö,Towards global optimisation 2 (North-Holland, Amsterdam 1978).
[2] J. Kiefer, ”Sequential minimax search for a maximum”,Proceedings of the American Mathematical Society 4 (1953) 502–506. · Zbl 0050.35702 · doi:10.1090/S0002-9939-1953-0055639-3
[3] S.A. Pijavskii, ”An algorithm for finding the absolute extremum of a function”,USSR Computational Mathematics and Mathematical Physics (1972) 57–67. · Zbl 0282.65052
[4] B. Shubert, ”A sequential method seeking the global maximum of a function”,SIAM Journal of Numerical Analysis 9 (3) (1972) 379–388. · Zbl 0251.65052 · doi:10.1137/0709036
[5] A.G. Sukharev, ”A stochastic algorithm for extremum search, optimal in one step”,USSR Computational Mathematics and Mathematical Physics (1981) 23–39. · Zbl 0498.90072
[6] D.J. Wilde,Optimum seeking methods (Prentice Hall, Englewood Cliffs, New Jersey, 1964). · Zbl 0136.14601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.