Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một Góc Nhìn Dòng Chảy Trong Các Bài Toán Bình Phương Không Tuyến Tính
Tóm tắt
Cũng giống như phương pháp Newton bị giảm cho việc giải các bài toán đại số phi tuyến tính có thể được hiểu như là một bước tiến Euler về phía trước trên các phương trình dòng chảy Newton, phương pháp Gauß–Newton bị giảm cho các bài toán bình phương phi tuyến tính tương đương với một bước tiến Euler về phía trước trên các phương trình dòng chảy Gauß–Newton tương ứng. Chúng tôi nhấn mạnh những ưu điểm của dòng chảy Gauß–Newton và phương pháp Gauß–Newton từ quan điểm thống kê và số học so với phương pháp Newton, phương pháp giảm dần dốc nhất, và phương pháp Levenberg–Marquardt, mà tương ứng là khu vực tương đương với dòng chảy Newton bước tiến Euler về phía trước, dòng chảy gradien bước tiến Euler về phía trước và dòng chảy gradien bước lùi Euler. Cuối cùng, chúng tôi chỉ ra một đặc tính giảm không có điều kiện cho một dòng chảy Gauß–Newton tổng quát, điều này liên kết với các phương pháp Krylov–Gauß–Newton cho các bài toán bình phương phi tuyến tính quy mô lớn. Chúng tôi cung cấp các kết quả số cho các bài toán quy mô lớn: Một hàm Rosenbrock tổng quát học thuật và một bài toán điều chỉnh bó trong thế giới thực từ việc tái tạo 3D dựa trên hình ảnh 2D.
Từ khóa
#phương pháp Gauß–Newton #bài toán bình phương không tuyến tính #phương pháp Krylov–Gauß–Newton #dòng chảy Newton #dòng chảy gradienTài liệu tham khảo
Agarwal, S., Snavely, N., Seitz, S.M., Szeliski, R.: Bundle adjustment in the large. In: Daniilidis, K., Maragos, P., Paragios, N (eds.) Proceedings of the 11th European Conference on Computer Vision: Part II, ECCV’10, pp 29–42. Springer, Berlin (2010)
Andersson, J.A.E., Gillis, J., Horn, G., Rawlings, J.B., Diehl, M.: CasADi: a software framework for nonlinear optimization and optimal control. Math. Program. Comput. 11, 1–36 (2019)
Armijo, L.: Minimization of functions having Lipschitz continuous first partial derivatives. Pac. J. Math. 16, 1–3 (1966)
Bates, D.M., Watts, D.G.: Nonlinear Regression Analysis and its Applications. In: Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. Wiley, New York (1988)
Bock, H.G.: Randwertproblemmethoden zur Parameteridentifizierung in Systemen nichtlinearer Differentialgleichungen. Bonner Mathematische Schriften, vol. 183. Universität Bonn, Bonn (1987)
Bock, H.G., Kostina, E., Schlöder, J.P.: On the role of natural levelfunctions to achieve global convergence for damped newton methods. In: Powell, M.J.D., Scholtes, S (eds.) System Modelling and Optimization (Cambridge, 1999), pp 51–74. Kluwer Acad. Publ, Boston, MA (2000)
Davidenko, D.F.: On a new method of numerical solution of systems of nonlinear equations. Dokl. Akad. Nauk SSSR (N.S.) 88, 601–602 (1953)
Deuflhard, P.: A modified newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting. Numer. Math. 22, 289–315 (1974)
Deuflhard, P.: Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, vol. 35. Springer, Berlin (2004)
Deuflhard, P.: The grand four: affine invariant globalizations of newton’s method. Vietnam J. Math. 46, 761–777 (2018)
Fong, D.C.-L., Saunders, M.: LSMR: An iterative algorithm for sparse least-squares problems. SIAM J. Sci. Comput. 33, 2950–2971 (2011)
Golub, G.H., Pereyra, V.: The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. Anal. 10, 413–432 (1973)
Gratton, S., Lawless, A.S., Nichols, N.K.: Approximate Gauss–Newton methods for nonlinear least squares problems. SIAM J. Optim. 18, 106–132 (2007)
Hohmann, A.: Inexact Gauss Newton methods for parameter dependent nonlinear problems. Ph.D. thesis, Freie Universität Berlin (1994)
Levenberg, K.: A method for the solution of certain non-linear problems in least squares. Q. Appl. Math. 2, 164–168 (1944)
Marquardt, D.W.: An algorithm for least-squares estimation of nonlinear parameters. J. Soc. Indust. Appl. Math. 11, 431–441 (1963)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research. Springer-Verlag, New York (1999)
Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics, vol. 30. SIAM, Philadelphia, PA (2000). Reprint of the 1970 original
Paige, C.C., Saunders, M.A.: LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Softw. 8, 43–71 (1982)
Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1, 127–239 (2014)
Parlett, B.N.: The Symmetric Eigenvalue Problem. Classics in Applied Mathematics, vol. 20. SIAM, Philadelphia, PA (1998). Corrected reprint of the 1980 original
Potschka, A.: Backward step control for global newton-type methods. SIAM J. Numer. Anal. 54, 361–387 (2016)
Potschka, A.: Backward step control for Hilbert space problems. Numer. Algor. 81, 151–180 (2019)
Potschka, A., Bock, H.G.: A sequential homotopy method for mathematical programming problems. arXiv:1902.06984 (2019)
Schlöder, J.: Numerische Methoden Zur Behandlung Hochdimensionaler Aufgaben Der Parameteridentifizierung. Bonner Mathematische Schriften, 187 Universität Bonn, Bonn (1988)
Shang, Y.-W., Qiu, Y.-H.: A note on the extended rosenbrock function. Evol. Comput. 14, 119–126 (2006)
Sorensen, D.C.: Trust region methods for unconstrained minimization. In: Nonlinear Optimization, 1981 (Cambridge, 1981), NATO Conf. Ser. II: Systems Sci., pp 29–38. Academic Press, London (1982)
Suárez Garcés, M.E.: Iterative linear algebra for parameter estimation. Ph.D. Thesis Heidelberg University (2018)