Mahmoud H. Alrefaei
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.
- Alrefaei, M. H., and S. Andrad6ttir. 1995. Simulated annealing for discrete stochastic optimization. Working paper.Google Scholar
- Andrad6ttir, S. 1995. A method for discrete stochastic optimization. To appear in Management Science, 1995. Google ScholarDigital Library
- Andrad6ttir, S. 1996. A global search method for discrete stochastic optimization. To appear in the SIAM Journal on Optimization, 1996.Google Scholar
- Devroye, L. 1976. On the convergence of statistical search. IEEE Transactions on Systems, Man and Cybernetics 6:46-56.Google ScholarCross Ref
- Goldsman, D., B. L. Nelson, and B. Schmeiser. 1991. Methods for selecting the best system. In Proceedings of the 1991 Winter Simulation Conference, eds. B. L. Nelson, W. D. Kelton, and C. M. Clark, 177-186. Institute of Electrical and Electronics Engineers, Piscataway, New :Jersey. Google ScholarDigital Library
- Goldsman, D., and B. L. Nelson. 1994. Ranking, selection and multiple comparisons in computer simulation. In Proceedings of the 199~ Winter Simulaion Conference, eds. :I. D. Tew, S. M anivannan, D. A. Sadowski, and A. F. Seila, 192-199. Institute of Electrical and Electronics Engineers, Piscataway, New Jersey. Google ScholarDigital Library
- Gong, W. B., Y. C. Ho, and W. Zhai. 1993. A stochastic comparison algorithm for discrete optimization with estimation. Preprint.Google Scholar
- Haddock, 3., and :I. Mittenthal. 1992. Simulation optimization using simulated annealing. Computers and Industrial Engineering 22:387-395. Google ScholarDigital Library
- Lai, T. L., and H. Robbins. 1985. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6:4-22.Google ScholarDigital Library
- Mitra, D., F. Romeo, and A. Sangiovanni-Vincentelli. 1986. Convergence and finite-time behavior of simulated annealing. Advances ~n Applied Probability, 18:747-771.Google Scholar
- Yakowitz, S. J., and E. Lugosi. 1990. Random search in the presence of noise, with applications to machine learning. SIAM Journal on Scien~ific and Statistical Computing 11:702-712. Google ScholarDigital Library
- Yan, D., and H. Mukai. 1992. Stochastic discrete optimization. SIAM Journal on Control and Optimization 30:594-612. Google ScholarDigital Library
Index Terms
- A new search algorithm for discrete stochastic optimization
Recommendations
A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic Optimization
We present a modification of the simulated annealing algorithm designed for solving discrete stochastic optimization problems. Like the original simulated annealing algorithm, our method has the hill climbing feature, so it can find global optimal ...
A New QP-Free, Globally Convergent, Locally Superlinearly Convergent Algorithm For Inequality Constrained Optimization
In this paper, we propose a new QP-free method, which ensures the feasibility of all iterates, for inequality constrained optimization. The method is based on a nonsmooth equation reformulation of the KKT optimality condition, by using the Fischer--...
Accelerating the convergence of random search methods for discrete stochastic optimization
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 ...
Comments