Stochastic Optimization and the Gambler's Ruin Problem

Abstract

An analogy between stochastic optimization and the gambler's ruin problem is used to estimate the expected value of the number of function evaluations required to reach the extremum of a special objective function with a pafrticular random walk. The objective function is the sum of the squares of the independent variables. The optimization is accomplished when the random walk enters a suitably defined small neighborhood of the extremum. The results indicate that for this objective function the expected number of function evaluations increases as the number of dimensions to the five halves power. Results of extensive computations of optimizing random walks in spaces with dimensions ranging from 2 to 30 agree with the analytically predicted behavior.

Key Words:

• Expectation
• Geometric probability
• Nonlinear optimization
• Probabilistic optimization
• Random walks
• Simulated annealing