SỰ HỘI TỤ VÀ TỐC ĐỘ HỘI TỤ CỦA CÁC PHƯƠNG PHÁP DAMPED NEWTON
Nội dung chính của bài viết
Tóm tắt
Trong bài báo này, chúng tôi nghiên cứu sự hội tụ và tốc độ hội tụ của các thuật toán damped Newton để giải các bài toán tối ưu không ràng buộc với các hàm mục tiêu khả vi liên tục cấp hai. Dưới giả thiết về tính xác định dương của ma trận Hessian của hàm mục tiêu trên một tập mở chứa tập mức ứng với giá trị hàm mục tiêu tại điểm khởi động, chúng tôi chứng minh dãy lặp sinh bởi thuật toán damped Newton sẽ nằm trong tập mở đó và dãy giá trị hàm tương ứng là đơn điệu giảm. Nếu dãy lặp có điểm tụ thì điểm tụ sẽ là điểm cực tiểu mạnh của hàm mục tiêu, và dãy lặp hội tụ toàn cục siêu tuyến tính về điểm cực tiểu này. Hơn nữa, nếu ma trận Hessian liên tục Lipschitz, dãy lặp đạt được tốc độ hội tụ bậc hai.
Từ khóa
các tốc độ hội tụ, thuật toán damped Newton, sự hội tụ toàn cục, tính xác định dương, bậc hai, siêu tuyến tính
Chi tiết bài viết
Tài liệu tham khảo
Beck, A. (2017). First-Order Methods in Optimization. SIAM. https://doi.org/10.1137/1.9781611974997
Ben-Tal, A., & Nemirovski, A. (1987). Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM. https://doi.org/10.1137/1.9780898718829
Bertsekas, D. P. (1999). Nonlinear programming. Athena Scientific. ISBN: 978-1-886529-05-2
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. https://doi.org/10.1017/CBO9780511804441
Chieu, N. H., Lee, G. M., & Yen, N. D. (2017). Second-order subdifferentials and optimality conditions for -smooth optimization problems. Applied Analysis and Optimization, 1(3), 461-476.
Dennis, J. E., & Schnabel, R. B. (1987). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Pennsylvania. SIAM. https://doi.org/10.1137/1.9781611971200
Facchinei, F., & Pang, J.-S. (2003). Finite-dimensional Variational Inequalities and Complementarity Problems, volume II. Springer. https://doi.org/10.1007/b97544
Hiriart-Urruty, J.-B., & Lemaréchal, C. (2004). Fundamentals of Convex Analysis. Springer. https://doi.org/10.1007/978-3-642-56468-0
Izmailov, A., & Solodov, M. (2014). Newton-Type Methods for Optimization and Variational Problems. Springer. https://doi.org/10.1007/978-3-319-04247-3
James, V. B. (2014). Nonlinear Optimization. University of Washington.
Mordukhovich, B. S., & Nam, N. M. (2014). An Easy Path to Convex Analysis and Applications. Morgan & Claypool Publishers. https://doi.org/10.1007/978-3-031-02406-1
Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A basic course. Springer US. https://doi.org/10.1007/978-1-4419-8853-9
Nocedal, J., & Wright, S. (1999). Numerical optimization. Springer. https://doi.org/10.1007/978-0-387-40065-5
Pham, D. K., Mordukhovich, B. S., & Vo, T. P.(2022). A generalized Newton method for subgradient systems. Mathematics of Operations Research, 48(4). https://doi.org/10.1287/moor.2022.1320
Polyak, B. T. (1987). Introduction to Optimization. Optimization Software.
Rockafellar, R. T., & Wets, R.-B. (1998). Variational Analysis. Springer. https://doi.org/10.1007/978-3-642-02431-3
Ruszczyński, A. (2006). Nonlinear Optimization. Princeton University Press. https://doi.org/10.2307/j.ctvcm4hcj