在回溯線搜索下結合梯度方向的反應曲面法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：5

、訪客IP：18.188.53.32

姓名

高慶展(Ching-Chan Kao) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

在回溯線搜索下結合梯度方向的反應曲面法
(Direct Gradient Augmented Response Surface Methodology Based on Backtracking Line Search)

相關論文

★ 應用失效模式效應分析於產品研發時程之改善	★ 服務品質因子與客戶滿意度關係研究-以汽車保修廠服務為例
★ 家庭購車決策與行銷策略之研究	★ 計程車車隊派遣作業之研究
★ 電業服務品質與服務失誤之探討-以台電桃園區營業處為例	★ 應用資料探勘探討筆記型電腦異常零件-以A公司為例
★ 車用配件開發及車主購買意願探討(以C公司汽車配件業務為實例)	★ 應用田口式實驗法於先進高強度鋼板阻抗熔接條件最佳化研究
★ 以層級分析法探討評選第三方物流服務要素之研究-以日系在台廠商為例	★ 變動良率下的最佳化批量研究
★ 供應商庫存管理架構下運用層級分析法探討供應商評選之研究-以某電子代工廠為例	★ 台灣地區快速流通消費產品銷售預測模型分析研究–以聯華食品可樂果為例
★ 競爭優勢與顧客滿意度分析以中華汽車為例	★ 綠色採購導入對電子代工廠的影響-以A公司為例
★ 以德菲法及層級分析法探討軌道運輸業之供應商評選研究–以T公司為例	★ 應用模擬系統改善存貨管理制度與服務水準之研究-以電線電纜製造業為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2025-7-25以後開放)

摘要(中)

回溯線搜索（Backtracking line search）是一種基於Armijo–Goldstein的充分下降條件下，在確定搜索方向後，沿著搜索方向移動最大步長的搜索方法。首先從搜索方向開始給定一個最大的估計步長，基於目標函數的局部梯度和函數值，利用插值法不斷的測試步長，直到觀察到目標函數的減小足以與預期的減小相對應為止。
本研究將回溯線搜索結合到帶有梯度方向的反應曲面法（Direct Gradient Augmented Response Surface Methodology, DiGARSM）中，它是一種用於優化隨機函數的一階元模型。這個方法結合了傳統的反應曲面法（Response surface methodology, RSM）所使用到的響應的測量以及梯度的測量（Gradient Response Surface Methodology, GRSM），能夠對搜索方向有更精確的估計。此外，本研究用兩種測試函數進行測試，分別在GRSM與DiGARSM中，比較原始方法中的步長設定和使用回溯線搜索決定步長結果的不同。最後，本文進行了數值模擬，以說明該方法的有效性。

摘要(英)

Backtracking line search is a search method to determine the maximum amount to move along a given search direction based on the Armijo condition. It starts with a maximum estimated step size given from the search direction. Based on the local gradient and function value of the objective function, the interpolation method is used to continuously test the step size until the decrease in the objective function is observed to be sufficient to correspond to the expected decrease.
This study integrates Backtracking line search into Direct Gradient Augmented Response Surface Methodology (DiGARSM), a sequential first-order metamodel for optimizing a stochastic function that combines traditional Response Surface Methodology (RSM) and gradient measurements（GRSM）. In this approach, gradients of the objective function with respect to the desired parameters are utilized in addition to response measurements. In addition, this study uses two test functions for testing in GRSM and DiGARSM, respectively, to compare the results of using the original step size and determining the step size by Backtracking line search. Overall, we conduct numerical simulations to illustrate the effectiveness of the proposed method.

關鍵字(中)

★ 反應曲面法
★ 回溯線搜索
★ Armijo-Goldstein 條件
★ 梯度
★ 元模型

關鍵字(英)

★ Response Surface Methodology
★ Backtracking line search
★ Armijo-Goldstein condition
★ Gradient
★ Metamodel

論文目次

摘要 i
Abstract ii
目錄 iii
圖目錄 v
表目錄 vi
第一章、緒論 1
1-1 研究背景 1
1-2 研究動機與目的 4
1-3 研究架構 5
第二章、文獻探討 6
2-1 反應曲面法（Response Surface Methodology） 6
2-2 線搜索法（Line Search） 9
2-2-1 回溯線搜索（Backtracking line search） 10
第三章、研究方法 12
3-1 基本假設與符號 12
3-2 一維問題的搜索方向估計 13
3-2-1 一維中的RSM 14
3-2-2 一維中的GRSM 14
3-2-3 一維中的DiGARSM 15
3-3 多維問題的搜索方向估計 16
3-3-1 多維中的RSM 16
3-3-2 多維中的GRSM 17
3-3-3 多維中的DiGARSM 17
3-4 回溯線搜索 18
3-4-1 回溯線搜索過程 19
3-5 流程圖 22
第四章、數值分析 23
4-1 DiGARSM 23
4-2 GRSM 24
4-3 回溯線搜索算法 25
4-4 Matyas函數（Matyas Function） 25
4-4-1 以GRSM估計搜索方向 26
4-4-2 以DiGARSM估計搜索方向 27
4-5 二次函數（Quadratic function） 28
4-5-1 以GRSM估計搜索方向 29
4-5-2 以DiGARSM估計搜索方向 31
第五章、結論 34
5-1 結論 34
5-2 未來研究方向 34
參考文獻 36

參考文獻

[1]　Andrei, N. “An acceleration of gradient descent algorithm with backtracking for unconstrained optimization”, Numerical Algorithms, 42.1, pp. 63-73, 2006.
[2]　Armijo, L. “Minimization of functions having Lipschitz continuous first partial derivatives”, Pac. J. Math, 6, pp. 1-3, 1966.
[3]　Barton, Russell R., Martin M. “Metamodel-based simulation optimization”, Handbooks in operations research and management science, 13, pp. 535-574, 2006.
[4]　Bartz-Beielstein, T., Preuss, M. “Experimental research in evolutionary computation”, Proceedings of the 9th annual conference companion on Genetic and evolutionary computation, 2007.
[5]　Cahya, S., Del Castillo, E., Peterson, J. J. “Computation of confidence regions for optimal factor levels in constrained response surface problems”, Journal of Computational and Graphical Statistics, 13.2, pp. 499-518, 2004.
[6]　Carson, Y, Maria, A. “Simulation optimization: methods and applications”, Proceedings of the 29th conference on Winter simulation, 1997.
[7]　Chang, K. H., Hong, L. J., Wan, H. “Stochastic trust region gradient-free method (STRONG)-a new response-surface-based algorithm in simulation optimization”, 2007 Winter Simulation Conference, 2007.
[8]　Chau, M., et al. “Simulation optimization: a tutorial overview and recent developments in gradient-based methods”, Proceedings of the Winter Simulation Conference 2014. IEEE, 2014.
[9]　Chau, M., Qu, H., Fu, M. C. “A New Hybrid Stochastic Approximation Algorithm”, IFAC Proceedings Volumes, 47.2, pp. 241-246, 2014.
[10]　Fletcher, R. “Practical Methods of Optimization”, Wiley, 1987.
[11]　Fu, M. C. “Optimization via Simulation: A Review”, Annals of Operations Research, 53.1, pp. 199-247, 1994.
[12]　Fu, M. C., H. Qu. “Regression Models Augmented with Direct Stochastic Gradient Estimators”, INFORMS Journal on Computing, 26.3, pp. 484–499, 2014.
[13]　Ghadimi, S., G. Lan. “Stochastic Approximation Methods and Their Finite-Time Convergence Properties”, Handbook of Simulation Optimization, pp. 179–206, 2015.
[14]　Glasserman, P. Gradient Estimation via Perturbation Analysis. Vol. 116. Springer Science & Business Media, 1991.
[15]　Goldstein, A. A., On Steepest Descent, SIAM Journal on Control, Vol. 3, pp. 147-151, 1965.
[16]　Goldstein, A. A., Constructive Real Analysis, Harpers and Row, New York, New York, 1967.
[17]　Goldstein, A. A., Price, J. F. “An effective algorithm for minimization”, Numerische Mathematik, 10.3, pp. 184-189, 1967.
[18]　Grippo, L., Lampariello, F., Lucidi, S. “A nonmonotone line search technique for Newton′s method”, SIAM Journal on Numerical Analysis, 23.4, pp. 707-716, 1986.
[19]　Hedar, A. R. “Global optimization test problems”, 2007.
[20]　Hill, W. J., Hunter, W. G. “A review of response surface methodology: a literature survey”, Technometrics, 8.4, pp. 571-590, 1966.
[21]　Ho, Y. C., X. Cao. “Perturbation Analysis and Optimization of Queueing Networks”, Journal of Optimization Theory and Applications, 40.4, pp. 559–582, 1983.
[22]　Ho, Y. C., Shi, L., Dai, L., Gong, W. B. “Optimizing Discrete Event Dynamic Systems via the Gradient Surface Method”, Discrete Event Dynamic Systems 2.2, pp. 99–120, 1992.
[23]　Horng, J. T., Liu, N. M., Chiang, K. T. “Investigating the Machinability Evaluation of Hadfield Steel in the Hard Turning with Al2O3/TiC Mixed Ceramic Cool Based on the Response Surface Methodology”, Journal of Materials Processing Technology, 208.1, pp. 532-541, 2008.
[24]　Jamil, M., Yang, X. S. “A Literature Survey of Benchmark Functions for Global Optimization Problems”, arXiv preprint arXiv, 1308.4008, 2013.
[25]　Keyzer, F., Kleijnen, J., Mullenders, E., et al. “Optimization of Priority Class Queues, with a Computer Center Case Study”, American Journal of Mathematical and Management Sciences 1.4, pp. 341– 358, 1981.
[26]　Kim, W. B., Draper, N. R. “Choosing a Design for Straight Line Fits to Two Correlated Responses”, Statistica Sinica, 4.1, pp. 275-280, 1994.
[27]　Kleijnen, J. P. C. “Response Surface Methodology”, Handbook of Simulation Optimization, pp. 81-104, 2015.
[28]　Krafft, O., Schaefer, M. 1992. “D-optimal Designs for a Multivariate Regression Model”, Journal of Multivariate Analysis, 42.1, pp. 130-140, 1992.
[29]　Law, A. M., Kelton, W. D. 2007. “Simulation Modeling and Analysis”, McGraw-Hill, 2007.
[30]　Lemaréchal, C. “A view of line-searches”, Optimization and Optimal Control. pp. 59-78, 1981.
[31]　Li, Y. C., Fu, M. C. “Sequential first-order response surface methodology augmented with direct gradients”, 2018 Winter Simulation Conference (WSC). IEEE, 2018.
[32]　Mead, R., Pike, D. J. “A Biometrics Invited Paper. A Review of Response Surface Methodology from a Biometric Viewpoint”, Biometrics, 31.4, pp. 803-851, 1975.
[33]　Miro-Quesada, G., Castillo, E. D. “An Enhanced Recursive Stopping Rule for Steepest Ascent Searches in Response Surface Methodology”, Communications in Statistics-Simulation and Computation, 33.1, pp. 201-228, 2004.
[34]　Moré, J. J., Thuente, D. J. “Line search algorithms with guaranteed sufficient decrease”, ACM Transactions on Mathematical Software (TOMS), 20.3, pp. 286-307, 1994.
[35]　Myers, R. H., Khuri, A. I., Carter, W. H. “Response Surface Methodology: 1966-1988”, Technometrics, 31.2, pp. 137-157, 1989.
[36]　Nemirovski, A. S., Juditsky, A., Lan, G. et al. “Robust Stochastic Approximation Approach to Stochastic Programming”, SIAM Journal on Optimization 19.4, pp. 1574–1609, 2009.
[37]　Nocedal, J., Yuan, Y. “Combining Trust Region and Line Search Techniques”, Advances in Nonlinear Programming, pp. 153-175, 1998.
[38]　Nocedal, J., Wright, S. J. Numerical optimization, pp. 36-63, 1999.
[39]　Plackett, R. L., Burman, J. P. “The Design of Optimum Multifactorial Experiments”. Biometrika, 3.4, pp. 305-325, 1946.
[40]　Potra, F. A., Shi, Y. “Efficient line search algorithm for unconstrained optimization”, Journal of Optimization Theory and Applications, 85.3, pp. 677-704, 1995.
[41]　Powell, M. J. D. “Some global convergence properties of a variable-metric algorithm for minimization without exact line searches”, Nonlinear programming 9 ,53, 1976.
[42]　Raydan, M. “The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem”, SIAM Journal on Optimization, 7.1, pp. 26-33, 1997.
[43]　Schropp, J. “A note on minimization problems and multistep methods”, Numeric Mathematic, 78, pp. 87-101, 1997.
[44]　Schropp, J. “One-step and multistep procedures for constrained minimization problems”, IMA Journal of Numerical Analysis, 20, pp. 135-152, 2000.
[45]　Shi, Z. J. “Convergence of line search methods for unconstrained optimization”, Applied Mathematics and Computation, 157.2, pp. 393-405, 2004.
[46]　Wächter, A., Biegler, L. T. “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming”, Mathematical programming, 106.1, pp. 25-27, 2006.
[47]　Waltz, R. A., Morales, J. L., Nocedal, J., et al. “An interior algorithm for nonlinear optimization that combines line search and trust region steps”, Mathematical Programming, 107.3, pp. 391-408, 2005.
[48]　Wolfowitz, J. “On the Stochastic Approximation Method of Robbins and Monro”, The Annals of Mathematical Statistics, 23.3, pp. 457-461, 1952.
[49]　Wu, S. M. “Tool-life testing by response surface methodology—Part 1”, pp. 105-110, 1964.
[50]　Yuan, G., Wei, Z. “New line search methods for unconstrained optimization”, Journal of the Korean Statistical Society, 38.1, pp. 29-39, 2009.

指導教授

葉英傑(Ying-Chieh Yeh)

審核日期

2020-7-29

推文