Title

Stochastic Optimization And The Gambler’S Ruin Problem

Keywords

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

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 anging from 2 to 30 agree with the analytically predicted behavior. © 1992 Taylor & Francis Group, LLC.

Publication Date

1-1-1992

Publication Title

Journal of Computational and Graphical Statistics

Volume

1

Issue

4

Number of Pages

367-384

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1080/10618600.1992.10474591

Socpus ID

6244261320 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/6244261320

This document is currently not available here.

Share

COinS