Pozicinių statistikų taikymas stochastinės aproksimacijos algoritmų optimalumui tirti

Abstract

In this paper we have considered the application of order statistics to establish the optimality in Stochastic Approximation (SA) algorithm. We have developed a method for the linear estimation of the minimum and its confidence interval using order statistics of the sequence of the objective function values provided in optimization. Coefficients of the estimators proposed have been computed using the theory of extreme values for i.i.d. values. The behaviour of these estimators has been studied by computer simulation minimizing several testing functions by various SA algorithms. The results of simulation studies by Monte-Carlo method have shown that we can estimate the confidence interval of a function extremum with admissible accuracy when the number of iterations is increased. The results obtained enable to introduce the stopping rule for the algorithm, namely, the algorithm stops when the length of the confidence interval becomes less than an admissible value.