Stochastic Optimization for System Design

隨機最佳化應用在系統設計上

10.29977/JCIIE.200609.0001

陳慧芬(Hui-Fen Chen)；黃彥登(Yen-Deng Huang)

梯度估計 ； 回溯近似法 ； 回溯最佳化 ； 隨機最佳化 ； Gradient Estimation ； Retrospective Approximation ； Retrospective Optimization ； Stochastic Optimization

工業工程學刊

23卷5期（2006 / 09 / 01）

357 - 370

英文

最佳化問題發生在系統設計上且伴隨著模擬應用，決策變數是可控制的系統參數，目標函數是系統績效指標，可透過模擬實驗來估計之。利用目標函數之估計值來求解目標函數最佳解的問題稱為隨機最佳化問題。隨機最佳化之文獻偏重在隨機近似法，此法雖可證明收斂性，但若方法論參數值選擇不當，其收斂速度非常慢。以實用性而言，好的方法論除了提供收斂性外還需可提供時效性答案，我們提出FDRA方法論，在目標函數可微的假設下，FDRA利用RA-Broyden方法論來求解梯度函數的根，其中梯度函數是以有限差分法來估計。我們的實驗結果顯示，FDRA收斂是迅速的且對其方法論參數具穩健性。

Optimization problems occur in system designs with simulation applications. The decision variables are controllable system parameters of interest and the objective function is a system performance measure that can be estimated via simulation experiments. Using the estimates of objective function values to find the optimal point is called the stochastic optimization problem. The literature of such problems focuses on stochastic approximation. Despite its convergence proof, stochastic approximation may converge slowly if the algorithm parameter values are not well chosen. For practical uses, good algorithms should provide real-time solutions besides guaranteeing convergence. We propose the FDRA algorithm assuming that the objective function is differentiable. FDRA uses the RA-Broyden's algorithm to find the zero of the gradient function, where gradients are estimated by the finite-difference method. In our empirical results, FDRA converges quickly and is robust to its algorithm parameters.

1. Andradóttir, S.,B.L. Nelson,W.D. Kelton,G.M. Clark(1991).A Projected Stochastic Approximation Algorithm.In Proceedings of the 1991 Winter Simulation Conference.
2. Broyden, C.G.(1965).A Class of Methods for Solving Nonlinear Simultaneous Equations.Mathematics of Computation,19,577-593.
3. Chen, H.(1994).West Lafayette, Indiana, USA,Purdue University.
4. Chen, H.,B.W. Schmeiser(2001).Stochastic Root Finding via Retrospective Approximation Algorithms.IIE Transactions,33,259-275.
5. Chen, H.,H. Chen(2001).A Heuristic Algorithm for Stochastic Root Finding.Asian Pacific Journal of Operation Research,18,13-22.
6. Chen, H.,Y. Cheng(2005).Nonnormality Effects on the Economic-Statistical Design of Xbar Charts with Weibull In-Control Time.European Journal of Operational Research
7. Conte, S.D.,C. de Boor(1980).Elementary Numerical Analysis: An Algorithmic Approach.
8. Dennis, J.E.,R.B.(1983).Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations.
9. Fu, M.C.(2002).Optimization for Simulation: Theory vs. Practice.INFORMS Journal on Computing,14,192-215.
10. Fu, M.C.(1994).Optimization via Simulation: A Review.Annals of Operations Research,53,199-247.
11. Fu, M.C.,B. A. Peters,J. S. Smith,D. J. Medeiros,M. W. Rohrer(2001).Simulation Optimization.Proceedings of the 2001 Winter Simulation Conference.
12. Fu, M.C.,S. D. Hill(1997).Optimization of Discrete Event System via Simultaneous Perturbation.IIE Transactions,29,233-243.
13. Glasserman, P.(1991).Gradient Estimation Via Perturbation Analysis.
14. Glynn, P.W.(1989).Optimization of Stochastic Systems via Simulation.In Proceedings of the 1989 Winter Simulation Conference.
15. Himmelblau, D.M.(1972).Applied Nonlinear Programming.
16. Ho, Y.C.,.R. Cao(1991).Discrete Event Dynamic Systems and Perturbation Analysis.
17. Jin, J.(1998).West Lafayette, Indiana, USA,Purdue University.
18. Kiefer, J.,J. Wolfowitz(1952).Stochastic Estimation of the Maximum of a Regression Function.Annal Math. Statist,23,462-466.
19. Kushner, H.,D. Clark(1978).Stochastic Approximation Methods for Constrained and Unconstrained Systems.New York:Springer-Verlag.
20. Ljung, L.,G. Pflug,H. Walk(1992).Stochastic Approximation and Optimization of Random Systems.Berlin:Birkhauser Verlag.
21. Montgomery, D.C.(1980).The Economic Design of Control Charts: A Review and Literature Survey.Journal of Quality Technology,12,75-87.
22. Press, W.H.,S.A. Teukolsky,W. T. Vetterling,B. P. Flannery(1997).Numerical Recipes in C-The Art of Scientific Computing.
23. Robbins, H.,S. Monro(1951).A Stochastic Approximation Method.Annals of Mathematical Statistics,22,400-407.
24. Rubinstein, R.Y.(1986).Monte Carlo Optimization: Simulation and Sensitivity of Queueing Network.
25. Spall, J.C.(1992).Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation.IEEE Transactions on Automatic Control,37,332-341.
26. Wasan, M.T.(1969).Stochastic Approximation.Cambridge, UK:Cambridge University Press.

1. (2012).Robust optimization approach for system optimal dynamic traffic assignment with demand uncertainty.工業工程學刊,29(2),136-147.
2. (2013).A study on maximum covering transportation network design with facility location under uncertainty.工業工程學刊,30(2),78-93.