No Access

SIMULATION-BASED OPTIMIZATION BY NEW STOCHASTIC APPROXIMATION ALGORITHM

ZI XU

Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, People's Republic of China

Corresponding author.

Search for more papers by this author

YINGYING LI

Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, People's Republic of China

Search for more papers by this author

, and

XINGFANG ZHAO

Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, People's Republic of China

Search for more papers by this author

https://doi.org/10.1142/S0217595914500262Cited by:1 (Source: Crossref)

Abstract

This paper proposes one new stochastic approximation algorithm for solving simulation-based optimization problems. It employs a weighted combination of two independent current noisy gradient measurements as the iterative direction. It can be regarded as a stochastic approximation algorithm with a special matrix step size. The almost sure convergence and the asymptotic rate of convergence of the new algorithm are established. Our numerical experiments show that it outperforms the classical Robbins–Monro (RM) algorithm and several other existing algorithms for one noisy nonlinear function minimization problem, several unconstrained optimization problems and one typical simulation-based optimization problem, i.e., (s, S)-inventory problem.

Keywords:

References

F. Azadivar, A tutorial on simulation optimization, Proc. 1992 Winter Simulation Conf. (1992) pp. 198–204. Google Scholar
S. Andradóttir , Management Science 42 , 475 ( 1996 ) . Crossref, Web of Science, Google Scholar
R. R. Barton and J. S. Ivey Jr. , Management Science 42 , 954 ( 1996 ) . Crossref, Web of Science, Google Scholar
J. R. Blum , Annals of Mathematical Statistics 25 , 737 ( 1954 ) . Crossref, Web of Science, Google Scholar
Y. H. Dai and Y. Yuan , Nonlinear Conjugate Gradient Methods ( Shanghai Scientific and Technical Publishers , Shanghai , 2000 ) . Google Scholar
B. Delyon and A. Juditsky , SIAM Journal on Optimization 3 , 868 ( 1993 ) . Crossref, Web of Science, Google Scholar
V. Fabian , The Annals of Mathematical Statistics 39 , 1327 ( 1968 ) . Crossref, Web of Science, Google Scholar
M. C. Fu , Annals of Operations Research 53 , 199 ( 1994 ) . Crossref, Google Scholar
M. C. Fu and K. J. Healy , IIE Transactions 29 , 191 ( 1997 ) . Web of Science, Google Scholar
S. H. Jacobson and L. W. Schruben , Operations Research Letters 8 , 1 ( 1989 ) . Crossref, Web of Science, Google Scholar
C. Kao , W. M. Song and S. P. Chen , International Transactions in Operational Research 4 , 223 ( 1997 ) . Crossref, Google Scholar
H. Kesten , Annals of Mathematical Statistics 29 , 41 ( 1958 ) . Crossref, Web of Science, Google Scholar
J. Kiefer and J. Wolfowitz , Annals of Mathematical Statistics 23 , 462 ( 1952 ) . Crossref, Web of Science, Google Scholar
H. J. Kushner and D. S. Clark , Stochastic Approximation for Constrained and Unconstrained Systems ( Springer-Verleg , New York , 1978 ) . Crossref, Google Scholar
M. S. Meketon, Optimization in simulation: A survey of recent results, Proc. 1987 Winter Simulation Conf. (1987) pp. 58–67. Google Scholar
J. J. Moré , B. S. Garbow and K. E. Hillstrom , ACM Transactions on Mathematical Software 7 , 17 ( 1981 ) . Crossref, Web of Science, Google Scholar
Nevel'son, MB and RZ Khas'minskij (1973). Stochastic approximation and recursive estimation. Translated from Russian by the Israel Program for Scientific Translations. Translations of Mathematical Monographs, Vol. 47. American Mathematical Society, Providence, RI . Google Scholar
E. L. Plambeck et al. , Mathematical Programming 75 , 137 ( 1996 ) . Web of Science, Google Scholar
H. Robbins and S. Monro , Annals of Mathematical Statistics 22 , 400 ( 1951 ) . Crossref, Web of Science, Google Scholar
H. Robbins and D. Siegmund , Optimizing Methods in Statistics 233 ( 1971 ) . Crossref, Google Scholar
S. M. Robinson , Mathematics of Operations Research 21 , 513 ( 1996 ) . Crossref, Web of Science, Google Scholar
M. H. Safizadeh , Naval Research Logistics 37 , 807 ( 1990 ) . Crossref, Web of Science, Google Scholar
N. N. Schraudolph and T. Graepel, Combining conjugate direction methods with stochastic approximation of gradients, Proc. 9th Int. Workshop on Artificial Intelligence and Statistics (2002) pp. 7–13. Google Scholar
J. C. Spall , IEEE Transactions on Automatic Control 37 , 332 ( 1992 ) . Crossref, Web of Science, Google Scholar
J. C. Spall , IEEE Transactions on Automatic Control 45 , 1839 ( 2000 ) . Crossref, Web of Science, Google Scholar
J. C. Spall , Introduction to Stochastic Search and Optimization ( A John Wiley & Sons, Inc , Hoboken, NJ , 2003 ) . Crossref, Google Scholar
J. C. Spall , IEEE Transactions on Automatic Control 54 , 1216 ( 2009 ) . Crossref, Web of Science, Google Scholar
Z. Xu and Y. H. Dai , Numerical Mathematics: Theory, Methods and Applications 1 , 460 ( 2008 ) . Web of Science, Google Scholar
Z. Xu , Optimization Letters 4 , 117 ( 2010 ) . Crossref, Web of Science, Google Scholar
Z. Xu , Optimization Methods and Software 28 , 743 ( 2013 ) . Crossref, Web of Science, Google Scholar