Computational behavior of a feasible direction method for linear programming (Q1119474)

Monte Carlo optimization is concerned with using randomly generated points to approximate optimal solutions of mathematical programs. The simplest algorithm for Monte Carlo optimization is pure random search, which generates a sequence of independent, uniformly distributed points in the feasible region and returns the best point as the approximation. In this paper the authors give a theoretical analysis of pure adaptive search, which generates a sequence of points uniformly distributed in a sequence of nested areas of the feasible region. They show that for convex programming, the number of iterations required to achieve a given accuracy of the solution increases at most linearly in the dimension of the problem. This compares to exponential growth in iterations required for pure random search.