Parallel and Interacting Stochastic Approximation Annealing Algorithms for Global Optimization

• Activity Number: 502
• Type: Contributed
• Date/Time: Wednesday, August 12, 2015 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Computing
• Author(s): Georgios Karagiannis* and Bledar Konomi and Guang Lin and Faming Liang
• Companies: Purdue University and University of Cincinnati and Purdue University and University of Florida
• Keywords: Stochastic optimisation ; stochastic approximation Monte Carlo ; stochastic approximation annealing ; population MCMC

Abstract

We present the parallel and interacting stochastic approximation annealing (PISAA) algorithm which is a stochastic simulation procedure for global optimisation. The standard stochastic approximation annealing (SAA) guarantees convergence to the global minimum when a square-root cooling schedule is used; however its performance depends crucially on its self-adjusted mechanism. Because this mechanism is based on information obtained from only a single Markov chain, SAA can present slow convergence in complex optimisation problems. The proposed algorithm involves simulating a population of SAA chains that interact each other in a manner that ensures significant improvement of the self-adjusted mechanism and better exploration of the sampling space. PISAA presents a significantly improved performance in terms of convergence while it inherits the good properties of SAA. PISAA can be implemented in parallel computing environments if available. The good performance of the proposed algorithm is demonstrated on challenging applications. Our results suggest that PISAA outperforms other competitors especially in high dimensional or rugged scenarios.