Accelerating the convergence of random search methods for discrete stochastic optimization

ABSTRACT

We discuss the choice of the estimation of the optimal solution when random search methods are applied to solve discrete stochastic optimization problems. At the present time, such optimization methods usually estimate the optimal solution using either the feasible solution the method is currently exploring or the feasible solution visited most often so far by the method. We propose using all the observed objective function values generated as the random search method moves around the feasible region seeking an optimal solution to obtain increasingly more precise estimates of the objective function values at the different points in the feasible region. At any given time, the feasible solution that has the best estimated objective function value (largest one for maximization problems; the smallest one for minimization problems) is used as the estimate of the optimal solution. We discuss the advantages of using this approach for estimating the optimal solution and present numerical results showing that modifying an existing random search method to use tnhis approach for estimating the optimal soluation appears to yield improved performance. We also present sereval rate of convergence results for random search methods using our approach for estimating the optimal solution. One these random search methods is a new variant of the stochastic comparison method; in addition to specifying the rate of convergence of this method, we prove that it is guaranteed to converge almost surely to the set of global optimal solutions and present a result that demonstrates that this method is likely to perform well in practice.

REFERENCES

• 1: Mahmoud H. Alrefaei , Sigrún Andradóttir, Discrete stochastic optimization via a modification of the stochastic ruler method, Proceedings of the 28th conference on Winter simulation, p.406-411, December 08-11, 1996, Coronado, California, United States [doi>10.1145/256562.256698]
• 2: Mahmoud H. Alrefaei , Sigrún Andradóttir, A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic Optimization, Management Science, v.45 n.5, p.748-764, May 1999 [doi>10.1287/mnsc.45.5.748]
• 3: ALREFAEI, M. H. AND ANDRAD TTIR, S. 2000a. A modification of the stochastic ruler method for discrete stochastic optimization. Working paper.
• 4: ALREFAEI, M. H. AND ANDRAD TTIR, S. 2000b. Discrete stochastic optimization using variants of the stochastic ruler method. Working paper.
• 5: 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]
• 6: ANDRAD TTIR, S. 1996. A global search method for discrete stochastic optimization. SIAM J. Optim. 6, 513-530.
• 7: ANDRAD TTIR, S. 2000. Rate of convergence of random search methods for discrete optimization using steady-state simulation. Working paper.
• 8: BILLINGSLEY, P. 1968. Convergence of Probability Measures. John Wiley and Sons, Inc., New York, NY.
• 9: CHUNG, K. L. 1974. A Course in Probability Theory. 2nd. ed. Academic Press, Inc., New York, NY.
• 10: DEVROYE, L. 1976a. On the convergence of statistical search. IEEE Trans. Syst. Man Cybern. 6, 46-56.
• 11: DEVROYE, L. 1976b. Probabilistic search as a strategy selection procedure. IEEE Trans. Syst. Man Cybern. 6, 315-321.
• 12: DURHAM, S. D. AND YU, K. F. 1990. Randomized play-the-leader rules for sequential sampling from two populations. Probab. Eng. Inf. Sci. 4, 355-367.
• 13: Bennett L. Fox, Integrating and accelerating tabu search, simulated annealing, and genetic algorithms, Annals of Operations Research, v.41 n.1-4, p.47-67, 1993
• 14: Fox, B. L. 1995. Simulated annealing: folklore, facts, and directions. In Monte Carlo and Quasi Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S. Shiue, Eds. Springer-Verlag, New York, NY, 17-48.
• 15: Fox, B. L. AND HEINE, G.W. 1996. Probabilistic search with overrides. Ann. Appl. Probab. 6, 1087-1094.
• 16: GELFAND, S. B. AND MITTER, S. K. 1989. Simulated annealing with noisy or imprecise energy measurements. J. Optim. Theory Appl. 62, 49-62.
• 17: GONG, W. -B., HO, Y. -C., AND ZHAI, W. 1992. Stochastic comparison algorithm for discrete optimization with estimation. In Proceedings of the 31st Conference on Decision Control, 795-800.
• 18: GURIN, L. S. 1966. Random search in the presence of noise. Eng. Cybern. 4, 252-260.
• 19: GURIN, L. S. AND RASTRIGIN, L.A. 1965. Convergence of the random search method in the presence of noise. Autom. Remote Contr. 26, 1505-1511.
• 20: GUTJAHR, W. J. AND PFLUG, G. C. 1996. Simulated annealing for noisy cost functions. J. Global Optim. 8, 1-13.
• 21: Ho, Y. C., SREENIVAS, R. S., AND VAKILI, P. 1992. Ordinal optimization of DEDS. Discrete Event Dyn. Syst. 2, 61-88.
• 22: LAI, T. L. 1987. Adaptive treatment allocation and the multi-armed bandit problem. Ann. Stat. 15, 1091-1114.
• 23: T L Lai, Asymptotically efficient adaptive control in Stochastic regression models, Advances in Applied Mathematics, v.7 n.1, p.23-45, March 1986 [doi>10.1016/0196-8858(86)90004-7]
• 24: LEE, g. -Y. 1995. Faster simulated annealing techniques for stochastic optimization problems, with application to queueing network simulation. Ph.D. Dissertation. North Carolina State University at Raleigh, Raleigh, NC.
• 25: MARTI, K. 1982. Minimizing noisy objective functions by random search methods. Z. Angew. Math. Mech. 62, T377T380.
• 26: MITRA, D., ROMEO, F., AND SANGIOVANNI-VINCENTELLI, A. 1986. Convergence and finite-time behavior of simulated annealing. Adv. Appl. Probab. 18, 747-771.
• 27: NELSON, B. L., SWANN, J., GOLDSMAN, D., AND SONG, W. 2000. Simple procedures for selecting the best simulated system when the number of alternatives is large. Working paper, School of Industrial and Systems Engineering. College of Computing, Georgia Institute of Technology, Atlanta, GA.
• 28: ROBBINS, H. 1952. Some aspects of the sequential design of experiments. Bull. Am. Math. Soc. 58, 527-535.
• 29: ROBBINS, H., SOBEL, M., AND STARR, N. 1968. A sequential procedure for selecting the largest of k means. Ann. Math. Stat. 39, 88-92.
• 30: Sid Yakowitz, A globally convergent stochastic approximation, SIAM Journal on Control and Optimization, v.31 n.1, p.30-40, Jan. 1993 [doi>10.1137/0331003]
• 31: YAKOWITZ, S. AND KOLLIER, M. 1992. Machine learning for optimal blackjack counting strategies. J. Stat. Plan. Inference 33, 295-309.
• 32: 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:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Experimentation

Keywords:
accelerated convergence, convergence rate, discrete stochastic optimization, estimating the optimal solution, random search methods