A new search algorithm for discrete stochastic optimization

ABSTRACT

We present a new method for finding a global optimal solution to a discrete stochastic optimization problem. This method resembles the simulated annealing method for discrete deterministic optimization. However, in our method the annealing schedule (the cooling temperature) is kept fixed, and the mechanism for estimating the optimal solution is different from that used in the original simulated annealing method. We state a convergence result that shows that our method converges almost surely to a global optimal solution under mild conditions. We also present empirical results that illustrate the performance of the proposed approach on a simple example.

REFERENCES

• 1: Alrefaei, M. H., and S. Andrad6ttir. 1995. Simulated annealing for discrete stochastic optimization. Working paper.
• 2: Sigrún Andradóttir, A method for discrete stochastic optimization, Management Science, v.41 n.12, p.1946-1961, Dec. 1995 [doi>10.1287/mnsc.41.12.1946]
• 3: Andrad6ttir, S. 1996. A global search method for discrete stochastic optimization. To appear in the SIAM Journal on Optimization, 1996.
• 4: Devroye, L. 1976. On the convergence of statistical search. IEEE Transactions on Systems, Man and Cybernetics 6:46-56.
• 5: David Goldsman , Barry L. Nelson , Bruce Schmeiser, Methods for selecting the best system, Proceedings of the 23rd conference on Winter simulation, p.177-186, December 08-11, 1991, Phoenix, Arizona, United States
• 6: David Goldsman , Barry L. Nelson, Ranking, selection and multiple comparisons in computer simulations, Proceedings of the 26th conference on Winter simulation, p.192-199, December 11-14, 1994, Orlando, Florida, United States
• 7: Gong, W. B., Y. C. Ho, and W. Zhai. 1993. A stochastic comparison algorithm for discrete optimization with estimation. Preprint.
• 8: Jorge Haddock , John Mittenthal, Simulation optimization using simulated annealing, Computers and Industrial Engineering, v.22 n.4, p.387-395, Oct. 1992 [doi>10.1016/0360-8352(92)90014-B]
• 9: Lai, T. L., and H. Robbins. 1985. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6:4-22.
• 10: Mitra, D., F. Romeo, and A. Sangiovanni-Vincentelli. 1986. Convergence and finite-time behavior of simulated annealing. Advances ~n Applied Probability, 18:747-771.
• 11: S. Yakowitz , E. Lugosi, Random search in the presence of noise, with application to machine learning, SIAM Journal on Scientific and Statistical Computing, v.11 n.4, p.702-712, July 1990 [doi>10.1137/0911041]
• 12: Di Yan , H. Mukai, Stochastic discrete optimization, SIAM Journal on Control and Optimization, v.30 n.3, p.594-612, June 1992 [doi>10.1137/0330034]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Convergence

General Terms:
Algorithms, Performance, Theory