簡易檢索 / 詳目顯示

回結果列表
研究生： 陳厚安
Chen, Hou-An
論文名稱： 以梯度估計的類電磁演算法處理稀疏最佳化問題
Gradient Estimation Based Electromagnetism-like Algorithm for Sparse Optimization Problems
指導教授： 許瑞麟
Sheu, Ruey-Lin
學位類別： 碩士
Master
系所名稱： 理學院 - 數學系應用數學碩博士班
Department of Mathematics
論文出版年： 2021
畢業學年度： 109
語文別： 英文
論文頁數： 59
中文關鍵詞： 稀疏性 、類電磁演算法 、LASSO估計 、鏡像下降法
外文關鍵詞： Sparsity, Electromagnetism-Like Algorithm, LASSO Estimator, Mirror Descent
相關次數： 點閱：102  下載：23 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在本研究中，我們的工作是修正Birbil, Fang and Sheu 所提出的類電磁演算法，使其具有處理稀疏性的能力。我們使用梯度估計來選擇變數、並將梯度估計應用在鏡像下降法之中。在數值測試中，使用稀疏資訊並搭配鏡像下降法確實節省計算時間，也提高解的品質。

    In this study, we equip the electromagnetism-like algorithm (EM method) proposed by Birbil, Fang and Sheu with the ability of handling sparsity. By solving the convex minimization sub-problems, we obtain the LASSO gradient estimates. We recover the sparsity information with these gradient estimates and use these gradient estimates as the search direction in the mirror descent algorithm. From our numerical testings, retrieving the sparsity information by LASSO gradient estimation as well as incorporating with the mirror descent algorithm does save the computational time and improve the solution quality.

    1 Introduction 1 2 Preliminary 5 2.1 General Scheme for Ordinary EM 5 2.2 Initialization 6 2.3 Local Search 6 2.4 Total Force 7 2.4.1 Charge Calculation 7 2.4.2 EM Force and Premature Convergence 7 2.5 EM Update and Termination 9 3 The Gradient EM Method 10 3.1 General Scheme for Gradient EM 10 3.2 Initialization 11 3.2.1 Motivation and Sampling 11 3.2.2 Illustrative Example 12 3.3 LASSO Gradient Estimation 13 3.3.1 Motivation 13 3.3.2 Solving l1-Regularized Minimization Sub-Problems 14 3.3.3 Illustrative Example 17 3.3.4 Handling Under-Determined Linear Systems 17 3.4 Component Selection 19 3.4.1 Selection via a Threshold 19 3.4.2 False Positive Component Revision 19 3.4.3 Illustrative Example 20 3.4.4 Choice of Threshold 21 3.5 Mirror Descent 22 3.5.1 Correcting Bias of LASSO Estimators 22 3.5.2 Illustrative Example 24 3.5.3 Projected Gradient Descent with Non-linear Projection 24 3.5.4 Illustrative Example 26 3.5.5 EM Method on Local Samples 26 3.5.6 Illustrative Example 28 3.6 Charge, Force and EM Update 29 3.6.1 Illustrative Example 31 3.7 Termination 33 4 Computational Results 34 4.1 Parameter Tuning 35 4.1.1 Probing Parameter 37 4.1.2 Regularization Parameter 37 4.2 Testing Results of Gradient EM 42 4.3 Comparison with Ordinary EM Method 42 4.4 Sparsity Information and Solution Quality 45 4.5 Bias-Correcting Mechanism 47 4.6 Mirror Descent 49 4.6.1 Modification of Mirror Descent 49 4.6.2 Removal of Mirror Descent 51 5 Conclusion & Future Research 54 5.1 Conclusion 54 5.2 Future Research 55 References 57

    Alatas, B. (2011). Acroa: artificial chemical reaction optimization algorithm for global optimization.Expert Systems with Applications, 38(10):13170–13180.

    Beck, A. (2017).First-order methods in optimization. SIAM.

    Beck, A. and Teboulle, M. (2003). Mirror descent and non-linear projected subgradient methods for convex optimization.Operations Research Letters, 31(3):167–175.

    Beck, A. and Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM Journal on Imaging Sciences, 2(1):183–202.

    Birbil, Ş. İ., Fang, S.-C., and Sheu, R.-L. (2004). On the convergence of a population-based global optimization algorithm.Journal of Global Optimization, 30(2-3):301–318.

    Conn, A. R., Scheinberg, K., and Vicente, L. N. (2009).Introduction to derivative-free optimization. SIAM.

    Debels, D. and Vanhoucke, M. (2005). The electromagnetism meta-heuristic applied to the resource-constrained project scheduling problem. International Conference on Artificial Evolution (Evolution Artificielle),pages 259–270. Springer.

    Donoho, D. L. (2006). For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution.Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(6):797–8

    Grant, M. and Boyd, S. (2014). CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx.

    Higham, C. F. and Higham, D. J. (2019). Deep learning:An introduction for applied mathematicians.SIAM Review, 61(4):860–891.

    Kaveh, A. and Mahdavi, V. R. (2014). Colliding bodies optimization: a novel meta-heuristic method.Computers & Structures, 139:18–27.

    Kennedy, J. and Eberhart, R. (1995). Particle swarm optimization. In Proceedings of ICNN’95-International Conference on Neural Net-works, volume 4, pages 1942–1948. IEEE.

    Lee, K. S. and Geem, Z. W. (2005). A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice.Computer Methods in Applied Mechanics and Engineering, 194(36-38):3902–3933.

    Naji-Azimi, Z., Toth, P., and Galli, L. (2010). An electromagnetism metaheuristic for the unicost set covering problem.European Journal of Operational Research, 205(2):290–300.

    Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A.(2009). Robust stochastic approximation approach to stochastic programming.SIAM Journal on Optimization, 19(4):1574–1609.

    Nemirovski, A. S. and Yudin, D. B. (1983). Problem complexity and method efficiency in optimization.

    Surjanovic, S. and Bingham, D. (2013). Virtual library of simulation experiments: Test functions and datasets.

    Tibshirani, R. (1996) Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), 58(1):267-288

    Turabieh, H., Abdullah, S., and Mccollum, B. (2009).Electromagnetism-like mechanism with force decay rate great deluge for the course timetabling problem. International Conference on Rough Sets and Knowledge Technology, pages 497–504. Springer.

    Wang, K.-J., Adrian, A. M., Chen, K.-H., and Wang, K.-M. (2015).An improved electromagnetism-like mechanism algorithm and its application to the prediction of diabetes mellitus. Journal of Biomedical Informatics, 54:220–229.

    Wang, Y., Du, S., Balakrishnan, S., and Singh, A. (2018). Stochastic zeroth-order optimization in high dimensions. International Conference on Artificial Intelligence and Statistics, pages 1356–1365

    Wu, W.-Y., Sheu, R.-L., and Birbil, Ş. İ. (2008). Solving the sum-of-ratios problem by a stochastic search algorithm.Journal of Global Optimization,42(1):91.

    Yazdani, M. and Jolai, F. (2016). Lion optimization algorithm (loa): a nature-inspired metaheuristic algorithm.Journal of Computational Design and Engineering, 3(1):24–36.

    Zhang, C.-H. and Zhang, S. S. (2014). Confidence intervals for low dimensional parameters in high dimensional linear models.Journal of the Royal Statistical Society: Series B: Statistical Methodology, pages 217

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE