Informatica

This paper reviews the interplay between global optimization and probability models, concentrating on a class of deterministic optimization algorithms that are motivated by probability models for the objective function. Some complexity results are described for the univariate and multivariate cases.

We describe an adaptive algorithm for approximating the global minimum of a continuous univariate function. The convergence rate of the error is studied for the case of a random objective function distributed according to the Wiener measure.

Methods for solving stochastic optimization problems by Monte-Carlo simulation are considered. The stoping and accuracy of the solutions is treated in a statistical manner, testing the hypothesis of optimality according to statistical criteria. A rule for adjusting the Monte-Carlo sample size is introduced to ensure the convergence and to find the solution of the stochastic optimization problem from acceptable volume of Monte-Carlo trials. The examples of application of the developed method to importance sampling and the Weber location problem are also considered.

In some recent papers a discussion on global minimization algorithms for a broad class of functions was started. An idea is presented here why such a case is different from a case of Lipshitzian functions in respect with the convergence and why for a broad class of functions an algorithm converges to global minimum of an objective function if it generates an everywhere dense sequence of trial points.

We consider a class of identification algorithms for distributed parameter systems. Utilizing stochastic optimization techniques, sequences of estimators are constructed by minimizing appropriate functionals. The main effort is to develop weak and strong invariance principles for the underlying algorithms. By means of weak convergence methods, a functional central limit theorem is established. Using the Skorohod imbedding, a strong invariance principle is obtained. These invariance principles provide very precise rates of convergence results for parameter estimates, yielding important information for experimental design.