Random search in high dimensional stochastic optimization

We consider the use of random search for high dimensional optimization problems where the objective function to be optimized can only be computed with error. Random search is easy to carry out, but extraction of information concerning the objective function is not so straightforward. We propose fitting a statistical model to the objective function values obtained in such a search, and show how the fitted model can be used to estimate the best value obtained when the search effort is limited and how this value compares with the unknown true optimum value. A possible use of this approach is in combinatorial optimization problems. The dimension in such a problem is not usually considered, but if a dimension can be associated with it, then it is likely to be high. We illustrate our method with a numerical example involving a travelling salesman problem.