Speeding up COMPASS for high-dimensional discrete optimization via simulation
✍ Scribed by L. Jeff Hong; Barry L. Nelson; Jie Xu
- Publisher
- Elsevier Science
- Year
- 2010
- Tongue
- English
- Weight
- 333 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0167-6377
No coin nor oath required. For personal study only.
✦ Synopsis
The convergent optimization via most promising area stochastic search (COMPASS) algorithm is a locally convergent random search algorithm for solving discrete optimization via simulation problems. COMPASS has drawn a significant amount of attention since its introduction. While the asymptotic convergence of COMPASS does not depend on the problem dimension, the finite-time performance of the algorithm often deteriorates as the dimension increases. In this paper, we investigate the reasons for this deterioration and propose a simple change to the solution-sampling scheme that significantly speeds up COMPASS for high-dimensional problems without affecting its convergence guarantee.