ACCELERATED RANDOM SEARCH
Let f(x) be a real function with compact support D (subset of R^d) and with a unique maximum. The classical Monte Carlo random search optimization technique (also called Pure Random Search) consists of sampling i.i.d. random variables {X_i} with uniform distribution on D and then computing M_n =max{f(X_i) : i=1,...,n}. This is very easy to implement and requires only that f(x) is computable; convergence to essential supremum is guaranteed if f(x) is measurable. The problem, of course, is that the convergence is very slow. We propose a new variant of random search. The algorithm constrains the search to a local neighborhood of a previously recorded value. We can prove that under very mild continuity conditions there exists a constant K (typically K>1000) such that our method, after only N trials, performs better than Pure Random Search after K*N trials. We will present a very extensive simulations justifying the method. Also, in order to demonstrate the flexibility of the method we will apply it to random polynomials of various degrees and dimension, to linear programing problems and to Traveling Salesmen problem.
Seminar to be held in Room 107, 24 Hillhouse Avenue at 4:15 pm