Scanning method

From Encyclopedia of Mathematics
Jump to: navigation, search

A method for maximizing or minimizing a function by means of sequential sorting and comparison of its values at all points of some subset of the admissible set. In contrast to sorting by the Monte-Carlo method, the points used in the scanning method lie on a predetermined trajectory.

The name "scanning method" comes from technology, where part of the problem of survey and detection of aims is equivalent to maximizing or minimizing an intensity function, and which is solved with the aid of analogous or digital variants of the scanning method. Subsequently, the scanning method has attracted attention as a convenient means of optimization on a computer in dialogue state.

The scanning trajectory, in particular, can form an everywhere-dense set in the admissible set of the argument.

The merits of the scanning method are the absence of limitations on the way of defining a function and the class to which it can belong. The latter (along with the large amount of labour needed for sorting) is at the same time the main deficiency of the method: supplementary information at the disposal of the numerical analyst is not used to reduce the computations. Therefore, in computing practice, the scanning method is rarely applied without combining it with other optimization methods. For example, for functions which satisfy a Lipschitz condition, the search for a global extremum is more effectively carried out by the method of "sorting on a non-uniform grid" than by the scanning method (see [2], [3]).


[1] L.A. Rastrigin, "Systems of extremal control" , Moscow (1974) (In Russian)
[2] Yu.G. Evtushenko, "Numerical optimization techniques" , Optim. Software (1985) (Translated from Russian)
[3] L.C.W. Dixon (ed.) G.P. Szegö (ed.) , Towards global optimisation , 1–2 , North-Holland (1975–1978)
How to Cite This Entry:
Scanning method. Encyclopedia of Mathematics. URL: