Boris Polyak
V.A. Trapeznikov Institute for Control Sciences of the RAS

Monte Carlo and randomization in optimization problems

The Monte Carlo method, invented in the late 1940s by the outstanding physicists and mathematicians von Neumann, Teller, Metropolis, and Ulam, is widely applied in modelling, numerical integration, and estimation. It is therefore natural to apply this method to optimization problems. We consider several cases of its application to convex and global optimization and clarify the reason why these attempts fail in large dimension. At the same time, the idea of randomization per se turns out to be quite fruitful for deterministic optimization, and we give some examples to this effect.