Stochastic Optimization for System Design

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

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

《工業工程學刊》 23卷5期 (2006/09) Pp. 357-370

https://doi.org/10.29977/JCIIE.200609.0001

摘要

最佳化問題發生在系統設計上且伴隨著模擬應用，決策變數是可控制的系統參數，目標函數是系統績效指標，可透過模擬實驗來估計之。利用目標函數之估計值來求解目標函數最佳解的問題稱為隨機最佳化問題。隨機最佳化之文獻偏重在隨機近似法，此法雖可證明收斂性，但若方法論參數值選擇不當，其收斂速度非常慢。以實用性而言，好的方法論除了提供收斂性外還需可提供時效性答案，我們提出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.

並列關鍵字

Gradient Estimation ； Retrospective Approximation ； Retrospective Optimization ； Stochastic Optimization

參考文獻

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).

Broyden, C.G.(1965).A Class of Methods for Solving Nonlinear Simultaneous Equations.Mathematics of Computation.19,577-593.

Chen, H.(1994).Stochastic Root Finding in System Design.Purdue University.

Chen, H.,H. Chen(2001).A Heuristic Algorithm for Stochastic Root Finding.Asian Pacific Journal of Operation Research.18,13-22.

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.