Simulation optimization with countably infinite feasible regions
Author:
Open Access
- 1 October 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Modeling and Computer Simulation
- Vol. 16 (4) , 357-374
Abstract
This article is concerned with proving the almost sure and global convergence of a broad class of algorithms for solving simulation optimization problems with countably infinite number of feasible points. We first describe the class of simulation optimization algorithms under consideration and discuss how the estimate of the optimal solution should be chosen when the feasible region of the underlying optimization problem is countably infinite. Then, we present a general result that guarantees the global convergence with probability one of the simulation optimization algorithms in this class. The assumptions of this result are sufficiently weak to allow the algorithms under consideration to be efficient, in that they are not required to either allocate the same amount of computer effort to all the feasible points these algorithms visit, or to spend an increasing amount of computer effort per iteration as the number of iterations grows. This article concludes with a discussion of how our assumptions can be satisfied and also generalized.Keywords
This publication has 27 references indexed in Scilit:
- Discrete stochastic optimization using variants of the stochastic ruler methodNaval Research Logistics (NRL), 2005
- Feature Article: Optimization for simulation: Theory vs. PracticeINFORMS Journal on Computing, 2002
- A modification of the stochastic ruler method for discrete stochastic optimizationEuropean Journal of Operational Research, 2001
- Accelerating the convergence of random search methods for discrete stochastic optimizationACM Transactions on Modeling and Computer Simulation, 1999
- A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic OptimizationManagement Science, 1999
- A Global Search Method for Discrete Stochastic OptimizationSIAM Journal on Optimization, 1996
- A Method for Discrete Stochastic OptimizationManagement Science, 1995
- Sample mean based index policies byO(logn) regret for the multi-armed bandit problemAdvances in Applied Probability, 1995
- Simulated annealing with noisy or imprecise energy measurementsJournal of Optimization Theory and Applications, 1989
- Probabilistic Search as a Strategy Selection ProcedureIEEE Transactions on Systems, Man, and Cybernetics, 1976