A study of some numerical solution algorithms for least-squares problems

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：157

、訪客IP：3.135.183.89

姓名

陳忠謙(Chung-Chien Chen) 查詢紙本館藏

畢業系所

數學系

論文名稱

(A study of some numerical solution algorithms for least-squares problems)

相關論文

★ 非線性塊狀高斯消去牛頓演算法在噴嘴流體的應用	★ 以平行 Newton-Krylov-Schwarz 演算法解 Poisson-Boltzmann 方程式的有限元素解在膠體科學上的應用
★ 最小平方有限元素法求解對流擴散方程以及使用Bubble函數的改良	★ Bifurcation Analysis of Incompressible Sudden Expansion Flows Using Parallel Computing
★ Parallel Jacobi-Davidson Algorithms and Software Developments for Polynomial Eigenvalue Problems in Quantum Dot Simulation	★ An Inexact Newton Method for Drift-DiffusionModel in Semiconductor Device Simulations
★ Numerical Simulation of Three-dimensional Blood Flows in Arteries Using Domain Decomposition Based Scientific Software Packages in Parallel Computers	★ A Parallel Fully Coupled Implicit Domain Decomposition Method for the Stabilized Finite Element Solution of Three-dimensional Unsteady Incompressible Navier-Stokes Equations
★ A Study for Linear Stability Analysis of Incompressible Flows on Parallel Computers	★ Parallel Computation of Acoustic Eigenvalue Problems Using a Polynomial Jacobi-Davidson Method
★ Numerical Study of Algebraic Multigrid Methods for Solving Linear/Nonlinear Elliptic Problems on Sequential and Parallel Computers	★ A Parallel Multilevel Semi-implicit Scheme of Fluid Modeling for Numerical Low-Temperature Plasma Simulation
★ Performance Comparison of Two PETSc-based Eigensolvers for Quadratic PDE Problems	★ A Parallel Two-level Polynomial Jacobi-Davidson Algorithm for Large Sparse Dissipative Acoustic Eigenvalue Problems
★ A Full Space Lagrange-Newton-Krylov Algorithm for Minimum Time Trajectory Optimization	★ Parallel Two-level Patient-specific Numerical Simulation of Three-dimensional Rheological Blood Flows in Branching Arteries

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

模型擬合是科學計算的一部分，它可以幫助我們找出所研究的系統具有哪些屬性。這些系統可能是工程系統或是最近在機器學習中越來越常使用的概念系統。最小二乘法是一個經典且廣為人知的技術來幫助我們建立模型擬合到我們所得到的數據。在本文中，我們使用了幾種算法來研究如何解決最小二乘問題，例如最速下降法、有限內存 Broyden-Fletcher-Goldfarb-Shanno(LBFGS)、Gauss-Newton 方法(GN)、Levenberg-Marquardt 方法(LM) 和非線性廣義極小殘差（N-GMRES）與最速下降預處理。對於機器學習問題中的二元分類，我們有線性和非線性最小二乘分類器兩種模型，通過訓練精度來比較性能。
根據我們在求解測試問題、識別彈簧系統參數、鳶尾花和MNIST數據集的二元分類中獲得的數值結果。我們對如何解決最小二乘問題進行了具體討論。並且非線性最小二乘分類器模型在分類問題上有更好的表現。

摘要(英)

Data fitting is part of scientific computing which can help us find out what properties the investigated system has. These systems might be engineering systems or conceptual systems that are used in machine learning more frequently. Least squares is the classic and widely known technique for fitting model to data.
In this thesis, we use several algorithms to study how we solve the least square problem, such as Steepest descent method, Limited-memory Broyden–Fletcher–Goldfarb–Shanno (LBFGS), Gauss-Newton method (GN), Levenberg–Marquardt method (LM) and nonlinear generalized minimal
residual (N-GMRES) with steepest descent preconditioning. And for binary classification in machine learning problems, we have linear and nonlinear least squares classifier two models to compare the performance by the training accuracy.
With the numerical result we obtain in solving test problems, parameter identification of spring-mass system, and binary classification of Iris flowers and MNIST data set. We have a specific discussion on how we solve the least-squares problems. And the nonlinear least squares classifier model have the better performance in classification problem.

關鍵字(中)

★ 牛頓法
★ 分類問題
★ 參數辨識
★ 最速下降法
★ 牛頓法

關鍵字(英)

★ least-squares problem
★ Newton
★ Gauss-Newton
★ steepest descent
★ NGMRES

論文目次

Contents
Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Least-squares problems and their applications . . . . . . . . . . . . . . . 2
2.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Application I: Parameter identification . . . . . . . . . . . . . . . . . . . . 3
2.3 Application II: Classification . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Algorithms for least-squares problems . . . . . . . . . . . . . . . . . . . . 6
3.1 Steepest-descent method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Newton method and its variants . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.1 Classical Newton method . . . . . . . . . . . . . . . . . . . . . . . 11
3.2.2 Limited-Memory BFGS . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Steepest descent preconditioning for N-GMRES optimization . . . . . . . . 14
4 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.1 Test problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.2 Numerical result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2.1 Parameter identification for single damped spring-mass system . . . 20
4.2.2 Iris flower classification . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2.3 MNIST classification . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Tables
4.1 Number of iteration for solving test problems with n = 100 . . . . . . . . . 20
4.2 Computational time in seconds for solving test problems with n = 100 . . 20
4.3 iterations status for solving parameter identification . . . . . . . . . . . . . 23
4.4 the comparison of linear classifier solved by L-M method, NGMRES with
steepest descent preconditioned, and steepest descent method. . . . . . . 26
4.5 the comparison of nonlinear classifier. . . . . . . . . . . . . . . . . . . . . 27
4.6 Comparison of linear and nonlinear least squares classifier model for Iris
classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.7 linear classifier over the number 0 and 1 classification. . . . . . . . . . . . 28
4.8 nonlinear classifier over the number 0 and 1 classification. . . . . . . . . . 29
4.9 linear classifier for number 9 and 4 classification. . . . . . . . . . . . . . . 30
4.10 Nonlinear classifier for number 9 and 4 classification. . . . . . . . . . . . . 30
4.11 Training accuracy comparison of linear and nonlinear least squares classifier
model for MNIST classification . . . . . . . . . . . . . . . . . . . . . . . . 30
4.12 Testing accuracy comparison of linear and nonlinear least squares classifier
model for MNIST classification . . . . . . . . . . . . . . . . . . . . . . . . 30

Figures
4.1 contour of Problem A with n=2 . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 Left: Problem A with n = 100, Right: Problem C with n = 100 . . . . . . 19
4.3 Left: Problem F with n = 100, Right: Problem G with n = 100 . . . . . . 19
4.4 The motion trajectory in different c with four fixed k . . . . . . . . . . . . 22
4.5 The motion trajectory in different k with four fixed c . . . . . . . . . . . . 23
4.6 Iterations of Parameter identification . . . . . . . . . . . . . . . . . . . . . 24
4.7 iterations of linear classifier . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.8 iterations of nonlinear classifier . . . . . . . . . . . . . . . . . . . . . . . . 27
4.9 confusion matrix of CNN model for MNIST classification [1] . . . . . . . . 28
4.10 iteration of linear classifier with number 0 and 1 . . . . . . . . . . . . . . . 29

參考文獻

Bibliography
[1] F. Chollet. Deep Learning with Python. Simon and Schuster, 2017.
[2] Wright S. Nocedal, J. Numerical Optimization. Springer Science & Business Media,
2006.
[3] Pereyra V. Scherer G. Hansen, P. C. Least-Squares Data Fitting with Applications.
JHU Press, 2013.
[4] H.D. Sterck. Steepest descent preconditioning for nonlinear gmres optimization.
Numerical Linear Algebra with Applications, 20:453–471, 2013.
[5] C.T. Kelley. Iterative Methods for Optimization. SIAM, 1999.
[6] Vandenberghe L. Boyd, S. Introduction to Applied Linear Algebra: Vectors,
Matrices, and Least-Squares. Cambridge university press, 2018.
[7] D.G. Luenberger. Introduction to Linear and Nonlinear Programming, volume 28.
Addison-wesley Reading, MA, 1973.
[8] R.M. Freund. The steepest descent algorithm for unconstrained optimization and
a bisection line-search method. Journal of Massachusetts Institute of Technology.
United States of america, 2004.
[9] H.D. Sterck. A nonlinear gmres optimization algorithm for canonical tensor decomposition.
SIAM Journal on Scientific Computing, 34:A1351–A1379, 2012.
[10] Oosterlee C. W. Washio, T. Krylov subspace acceleration for nonlinear multigrid
schemes. Electronic Transactions on Numerical Analysis, 6:3–1, 1997.

指導教授

黃楓南(Feng-Nan Hwang)

審核日期

2021-9-6

推文