DocumentCode :
425172
Title :
Discrete optimization, SPSA and Markov chain Monte Carlo methods
Author :
Gerencsér, László ; Hill, Stacy D. ; Vágó, Zsuzsanna ; Vincze, Zoltán
Author_Institution :
SZTAKI, Budapest, Hungary
Volume :
4
fYear :
2004
fDate :
June 30 2004-July 2 2004
Firstpage :
3814
Abstract :
The minimization of a convex function defined over the grid Z/sup p/ is considered. A few relevant mathematical devices such as integer convexity, Markov chain Monte Carlo (MCMC) methods, including stochastic comparison (SC), and simultaneous perturbation stochastic approximation (SPSA) are summarized. A truncated fixed gain SPSA method is proposed and investigated in combination with devices borrowed from the MCMC literature. The main contribution of the paper is the development and testing a number of devices that may eventually improve the convergence properties of the algorithm, such as various truncation techniques, averaging and choices of acceptance probabilities. The basis for comparison of performances is accuracy vs. number of function evaluations. We present experimental evidence for the superiority of an SC method allowing moves in wrong directions with small probability, where the underlying method is an SPSA method using averaging and adaptive truncation.
Keywords :
Markov processes; Monte Carlo methods; approximation theory; convergence; convex programming; minimisation; probability; stochastic programming; Markov chain Monte Carlo methods; adaptive truncation techniques; convergence; convex function minimization; discrete optimization; integer convexity; mathematical devices; probability; simultaneous perturbation stochastic approximation; stochastic comparison method;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
American Control Conference, 2004. Proceedings of the 2004
Conference_Location :
Boston, MA, USA
ISSN :
0743-1619
Print_ISBN :
0-7803-8335-4
Type :
conf
Filename :
1384507
Link To Document :
بازگشت