Bối cảnh và vấn đề nghiên cứu

Trong lý thuyết tối ưu hóa và giải tích số, các bài toán tối ưu không ràng buộc đóng vai trò trọng tâm trong nhiều ứng dụng khoa học và kỹ thuật. Để tìm cực trị của hàm mục tiêu, các thuật toán bậc một (như phương pháp Gradient Descent) thường được áp dụng nhờ chi phí tính toán mỗi bước lặp thấp; tuy nhiên, nhược điểm lớn của các phương pháp bậc một là tốc độ hội tụ chậm (chỉ đạt tốc độ tuyến tính hoặc dưới tuyến tính trong các trường hợp phức tạp). Nhằm cải thiện hiệu suất tính toán, các thuật toán bậc hai sử dụng thông tin đạo hàm cấp hai (ma trận Hessian) đã được phát triển, trong đó tiêu biểu nhất là phương pháp Newton.

Phương pháp Newton giải bài toán tối ưu được xây dựng dựa trên việc áp dụng phương pháp Newton giải hệ phương trình phi tuyến để tìm điểm dừng $\nabla f(x) = 0$. Ưu điểm nổi bật của phương pháp Newton là tốc độ hội tụ rất nhanh: đạt tốc độ siêu tuyến tính dưới các giả thiết tự nhiên và đạt tốc độ bậc hai khi ma trận Hessian thỏa mãn điều kiện liên tục Lipschitz địa phương quanh nghiệm. Tuy vậy, phương pháp Newton cổ điển tồn tại hai hạn chế căn bản:

  1. Chi phí tính toán tại mỗi bước lặp lớn do phải tính toán ma trận Hessian và giải hệ phương trình đại số tuyến tính để tìm hướng Newton, gây khó khăn cho các bài toán có số chiều lớn.
  2. Thuật toán chỉ đạt được sự hội tụ địa phương. Dãy lặp chỉ hội tụ về nghiệm khi điểm khởi đầu $x_0$ được chọn đủ gần điểm tối ưu. Với điểm khởi đầu không phù hợp, dãy lặp có thể phân kỳ hoặc không chứa điểm dừng trong tập các điểm tụ, ngay cả khi hàm mục tiêu là hàm lồi mạnh (nơi điểm dừng là duy nhất và là nghiệm tối ưu toàn cục).

Để khắc phục nhược điểm về tính hội tụ địa phương, phương pháp Damped Newton (Newton có hiệu chỉnh bước nhảy) được đưa ra. Bằng cách tích hợp kỹ thuật tìm kiếm đường lùi (backtracking line search) để xác định độ dài bước nhảy $t_k \in (0, 1]$ thay vì cố định $t_k = 1$ như phương pháp cổ điển, phương pháp Damped Newton đảm bảo dãy giá trị hàm mục tiêu ${f(x_k)}$ là một dãy giảm đơn điệu, từ đó thiết lập sự hội tụ toàn cục mà vẫn duy trì được tốc độ hội tụ tiệm cận siêu tuyến tính hoặc bậc hai.

Khóa luận tốt nghiệp "Các phương pháp Newton và ứng dụng trong tối ưu" của sinh viên Đặng Ngọc Đỗ Quyên (ngành Toán ứng dụng, Khoa Toán - Tin học, Trường Đại học Sư phạm Thành phố Hồ Chí Minh, thực hiện tháng 4 năm 2023 dưới sự hướng dẫn của TS. Phạm Duy Khánh và ThS. Võ Thành Phát) tập trung giải quyết các nhiệm vụ nghiên cứu sau:

  1. Hệ thống hóa các kiến thức chuẩn bị về giải tích hàm, tính khả vi cấp một và cấp hai, đại số ma trận và giải tích lồi.
  2. Khảo sát phương pháp Newton giải hệ phương trình phi tuyến và bài toán tối ưu không ràng buộc, phân tích chi tiết điều kiện hội tụ địa phương (siêu tuyến tính và bậc hai) cùng các phản ví dụ minh họa tính cục bộ.
  3. Phân tích và chứng minh chặt chẽ sự hội tụ toàn cục của thuật toán Damped Newton dưới các giả thiết mở rộng, khảo sát tốc độ hội tụ, phân tích các tính chất trong hai pha hoạt động và đánh giá số lần lặp tối thiểu của thuật toán.

Đối tượng nghiên cứu của đề tài là các thuật toán thuộc họ Newton (gồm phương pháp Newton cổ điển và phương pháp Damped Newton) áp dụng cho bài toán tối ưu không ràng buộc $\min_{x \in \mathbb{R}^n} f(x)$ với hàm mục tiêu $f: \mathbb{R}^n \to \mathbb{R}$ khả vi liên tục cấp hai ($f \in C^2$). Phạm vi nghiên cứu tập trung vào các suy diễn lý thuyết toán học, các chứng minh giải tích và đánh giá tiệm cận.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khóa luận sử dụng khung lý thuyết giải tích toán học hiện đại kết hợp giữa giải tích lồi, giải tích ma trận và lý thuyết tối ưu hóa số. Các khái niệm và định lý cơ sở được viện dẫn chính xác bao gồm:

  • Tính khả vi và khai triển Taylor: Định nghĩa khả vi Fréchet cấp một, cấp hai; tính liên tục Lipschitz của ánh xạ gradient $\nabla f$; Định lý Taylor mở rộng bậc hai; ma trận Jacobi $J_F(x)$ của ánh xạ vector $F: \mathbb{R}^n \to \mathbb{R}^n$ và ma trận Hessian $\nabla^2 f(x)$ của hàm số thực.
  • Đại số ma trận: Chuẩn ma trận cảm sinh, giá trị riêng, vector riêng; ma trận đối xứng xác định dương ($A \succ 0$), nửa xác định dương ($A \succeq 0$), xác định âm, không xác định; tính chất $\kappa$-xác định dương đều ($A \succeq \kappa I$ với $\kappa > 0$); Bổ đề mở rộng tính xác định dương của ma trận Hessian ra lân cận mở (Bổ đề 1.34); Bổ đề khả nghịch của ma trận nhiễu dạng $(I - A)^{-1}$.
  • Giải tích lồi và điểm tối ưu: Khái niệm hàm lồi, hàm lồi chặt, hàm $\alpha$-lồi mạnh, hàm lồi địa phương và lồi mạnh địa phương; tính chất đóng của tập mức $\Omega = \text{Lev}(f, f(x_0)) = {x \in \mathbb{R}^n \mid f(x) \le f(x_0)}$; đặc trưng cấp hai của điểm cực tiểu địa phương mạnh thông qua điều kiện $\nabla f(x^) = 0$ và $\nabla^2 f(x^) \succ 0$.
  • Kỹ thuật tìm kiếm đường lùi (Backtracking Line Search): Xác định bước nhảy $t_k = \beta^{m_k}$ (với $\beta \in (0, 1)$) thỏa mãn điều kiện Armijo: $$f(x_k + t_k d_k) \le f(x_k) + \sigma t_k \langle \nabla f(x_k), d_k \rangle \quad (\sigma \in (0, 1))$$

Phương pháp nghiên cứu chủ đạo của khóa luận là phương pháp suy diễn logic toán học thuần túy: phân tích tiên đề, xây dựng bổ đề trung gian, áp dụng các bất đẳng thức giải tích (như bất đẳng thức Cauchy-Schwarz, nguyên lý kẹp, định lý Bolzano-Weierstrass) để thực hiện các chứng minh quy nạp và giới hạn dãy. Bên cạnh đó, tác giả sử dụng phương pháp xây dựng phản ví dụ giải tích trên không gian một chiều để kiểm chứng sự cần thiết của các điều kiện giả thiết.

Dữ liệu nghiên cứu trong khóa luận là các mô hình toán học giải tích, các biểu thức hàm số và hệ phương trình vi phân/đại số giải tích được trích xuất và phát triển từ các tài liệu kinh điển về giải tích lồi và tối ưu hóa số.

Nội dung chính theo từng chương

Chương 1: Kiến thức chuẩn bị

Chương 1 thiết lập toàn bộ nền tảng toán học phục vụ cho các lập luận ở hai chương tiếp theo, được chia thành ba nhóm nội dung chính:

  • Một số tính chất khả vi: Trình bày định nghĩa đạo hàm Fréchet, tính liên tục Lipschitz, đạo hàm riêng bậc hai, ma trận Jacobi, ma trận Hessian và công thức khai triển Taylor. Khảo sát khái niệm hướng giảm (descent direction), chỉ ra rằng điều kiện $\langle \nabla f(x), d \rangle < 0$ là điều kiện đủ để $d$ là hướng giảm nhưng không phải điều kiện cần (thông qua phản ví dụ $f(x) = x^3 - x^2 - x + 2$ và $f(x) = x^3$). Đồng thời chứng minh tính chất tiệm cận của đại lượng vô cùng bé $o(t)$ và khai triển bậc hai mở rộng.
  • Ma trận và một số kết quả liên quan: Hệ thống hóa các kết quả về chuẩn ma trận, giá trị riêng của ma trận nghịch đảo, ma trận đối xứng, dạng toàn phương. Trọng tâm của phần này là việc chứng minh Bổ đề 1.34 về sự lan rộng tính xác định dương của ma trận Hessian: nếu $\nabla^2 f(x^) \succ 0$ và $f \in C^2$ thì tồn tại lân cận $B(x^, \delta)$ và hằng số $\kappa > 0$ sao cho $\nabla^2 f(x) \succeq \kappa I$ với mọi $x \in B(x^*, \delta)$.
  • Hàm lồi và một số kết quả liên quan: Phân loại các cấp độ lồi của hàm số (lồi, lồi chặt, $\alpha$-lồi mạnh toàn cục và địa phương). Chứng minh các đặc trưng cấp một và cấp hai của tính lồi thông qua gradient và ma trận Hessian. Trình bày các định lý về điểm cực tiểu địa phương mạnh, chứng minh tính đóng của tập mức $\text{Lev}(f, f(x_0))$ và mối quan hệ tương đương giữa tính liên tục Lipschitz của $\nabla f$ với tính bị chặn trên của ma trận Hessian ($\nabla^2 f(x) \preceq l I$).

Chương 2: Phương pháp Newton

Chương 2 phân tích cơ chế hoạt động và tính chất hội tụ địa phương của thuật toán Newton qua hai bài toán:

  • Phương pháp Newton giải hệ phương trình: Trình bày sơ đồ lặp $x_{k+1} = x_k - (J_F(x_k))^{-1} F(x_k)$ cho hệ $F(x) = 0$. Thiết lập Bổ đề 2.1 đánh giá sai số $|x - (J_F(x))^{-1}F(x) - x^|$. Từ đó, chứng minh Định lý 2.3 khẳng định dãy lặp hội tụ địa phương siêu tuyến tính về nghiệm $x^$ nếu $J_F$ liên tục tại $x^$ và $J_F(x^)$ khả nghịch. Tiếp theo, Định lý 2.4 chứng minh nếu bổ sung giả thiết $J_F$ liên tục Lipschitz địa phương xung quanh $x^$ thì thuật toán đạt tốc độ hội tụ bậc hai $|x_{k+1} - x^| \le \beta |x_k - x^*|^2$.
  • Phản ví dụ về tính cần thiết của điều kiện Lipschitz: Tác giả đưa ra Ví dụ 2.5 với hàm số $F(x) = \frac{2}{3}x^{3/2} + x$ (với $x \neq 0$) và $F(0) = 0$. Hàm này có đạo hàm liên tục tại $x^* = 0$ và $F'(0) = 1 \neq 0$, tạo ra dãy lặp hội tụ siêu tuyến tính nhưng không đạt được bậc hai vì $F'$ không thỏa mãn tính liên tục Lipschitz địa phương tại gốc tọa độ.
  • Phương pháp Newton cho bài toán tối ưu: Áp dụng hệ thống giải hệ phương trình cho hệ điểm dừng $\nabla f(x) = 0$, dẫn đến công thức lặp $x_{k+1} = x_k - (\nabla^2 f(x_k))^{-1} \nabla f(x_k)$. Thiết lập Bổ đề 2.6 và Bổ đề 2.7 chỉ ra mối liên hệ chặt chẽ về tốc độ hội tụ giữa ba dãy số: dãy điểm lặp ${x_k}$, dãy giá trị hàm mục tiêu ${f(x_k)}$ và dãy gradient ${\nabla f(x_k)}$. Khi ${x_k}$ hội tụ siêu tuyến tính (hoặc bậc hai) về $x^$ thì ${f(x_k)}$ và ${\nabla f(x_k)}$ cũng hội tụ siêu tuyến tính (hoặc bậc hai) tương ứng về $f(x^)$ và $0$.
  • Phản ví dụ về sự không hội tụ toàn cục: Phân tích Ví dụ 2.11 với hàm lồi mạnh $f(x) = \sqrt{1 + x^2}$ trên $\mathbb{R}$. Mặc dù hàm số có nghiệm tối ưu toàn cục duy nhất $x^* = 0$ và $\nabla^2 f(x) > 0, \forall x$, công thức lặp Newton tạo ra dãy $x_{k+1} = -x_k^3$. Khi chọn điểm khởi đầu $|x_0| \ge 1$, dãy lặp phân kỳ hoàn toàn, minh chứng cho sự thất bại của phương pháp Newton cổ điển khi điểm khởi đầu nằm ngoài bán kính hội tụ địa phương.

Chương 3: Phương pháp Damped Newton cho bài toán tối ưu

Chương 3 là phần đóng góp trọng tâm của khóa luận, nghiên cứu thuật toán Damped Newton với bước nhảy $t_k$ được hiệu chỉnh bằng kỹ thuật backtracking:

  • Mô tả thuật toán Damped Newton (Thuật toán 3.1): Tại mỗi bước lặp, hướng Newton $d_k$ được xác định bởi $\nabla^2 f(x_k) d_k = -\nabla f(x_k)$. Độ dài bước $t_k = \beta^m$ được giảm dần cho đến khi thỏa bất đẳng thức Armijo $f(x_k + t_k d_k) \le f(x_k) + \sigma t_k \langle \nabla f(x_k), d_k \rangle$. Điểm lặp mới được cập nhật theo quy tắc $x_{k+1} = x_k + t_k d_k$.
  • Chứng minh sự hội tụ toàn cục (Định lý 3.2): Giả sử $f \in C^2$ trên tập mở chứa tập mức $\Omega = \text{Lev}(f, f(x_0))$ và $\nabla^2 f(x) \succ 0$ trên $\Omega$. Tác giả chứng minh chi tiết qua ba khẳng định cấu thành:
    • Khẳng định 1: Thuật toán tạo ra dãy ${x_k} \subset \Omega$, dãy giá trị ${f(x_k)}$ giảm đơn điệu và $\langle \nabla f(x_k), d_k \rangle < 0$ tại mọi bước lặp.
    • Khẳng định 2: Mọi điểm giới hạn $x^$ của dãy ${x_k}$ đều là điểm cực tiểu địa phương mạnh của $f$. Trong khẳng định này, tác giả chứng minh dãy bước nhảy ${t_{k_j}}$ bị chặn dưới bởi một số thực dương $\gamma > 0$ và thiết lập bất đẳng thức giảm giá trị hàm: $f(x_{k_j}) - f(x_{k_j+1}) \ge \sigma \gamma \kappa |d_{k_j}|^2$. Qua đó suy ra $\nabla f(x^) = 0$ và $\nabla^2 f(x^*) \succ 0$.
    • Khẳng định 3: Dãy ${x_k}$ hội tụ toàn bộ về duy nhất điểm cực tiểu $x^*$, dựa trên nguyên lý không tồn tại điểm tụ thứ hai trong lân cận lồi mạnh và bất đẳng thức co $|x_{k_j+1} - x_{k_j}|^2 \le \frac{1}{\sigma \gamma \kappa} [f(x_{k_j}) - f(x_{k_j+1})]$.
  • Nội dung phân tích mở rộng: Trình bày cấu trúc phân tích hai pha của thuật toán Damped Newton (pha giảm giá trị hàm mục tiêu có bước nhảy $t_k < 1$ và pha hội tụ bậc hai khi bước nhảy $t_k = 1$ được chấp nhận toàn bộ) cùng đánh giá số lần lặp tối thiểu cần thiết để thuật toán đạt độ chính xác cho trước.

Bảng dưới đây tổng hợp và so sánh các đặc tính kỹ thuật cốt lõi giữa hai thuật toán được khảo sát trong khóa luận:

Đặc tính so sánh Phương pháp Newton cổ điển Phương pháp Damped Newton
Công thức lặp $x_{k+1} = x_k + d_k$ với $\nabla^2 f(x_k) d_k = -\nabla f(x_k)$ $x_{k+1} = x_k + t_k d_k$ ($t_k$ tìm qua Backtracking Line Search)
Độ dài bước nhảy Cố định $t_k = 1, \forall k$ Biến thiên $t_k \in (0, 1]$ thỏa mãn điều kiện Armijo
Tính chất dãy ${f(x_k)}$ Không đảm bảo tính đơn điệu (có thể tăng hoặc dao động) Dãy giảm đơn điệu ngặt ($f(x_{k+1}) < f(x_k)$ khi $\nabla f(x_k) \neq 0$)
Phạm vi hội tụ Hội tụ địa phương (phụ thuộc chặt vào điểm khởi đầu $x_0$) Hội tụ toàn cục trên tập mức $\Omega = \text{Lev}(f, f(x_0))$
**Ứng xử khi $ x_0 \ge 1$ trên hàm $f(x)=\sqrt{1+x^2}$**
Tốc độ hội tụ tiệm cận Siêu tuyến tính (hoặc bậc hai nếu Hessian Lipschitz) Siêu tuyến tính (hoặc bậc hai trong pha thứ hai khi $t_k = 1$)
Chi phí tính toán/bước Tính 01 Hessian + giải 01 hệ phương trình tuyến tính Tính 01 Hessian + giải 01 hệ tuyến tính + kiểm tra điều kiện Armijo

Kết quả và đóng góp

Khóa luận đã đạt được các kết quả giải tích cụ thể:

  • Chứng minh hoàn chỉnh định lý hội tụ toàn cục dưới giả thiết nới lỏng: Khóa luận đã chứng minh tính hội tụ toàn cục của phương pháp Damped Newton với các giả thiết yếu hơn so với các kết quả được công bố trong tài liệu tham khảo chuẩn (cụ thể là nới lỏng điều kiện so với hệ quả [Corollary 6.3] trong y văn), nhưng vẫn thu được kết luận hội tụ mạnh về điểm cực tiểu địa phương mạnh.
  • Xác lập chặn dưới dương của bước nhảy Backtracking: Khóa luận đã chứng minh dãy bước nhảy sinh ra bởi kỹ thuật backtracking line search trong thuật toán Damped Newton không thể suy biến về 0 trên tập mức compact mà luôn bị chặn dưới bởi một hằng số $\gamma > 0$, từ đó bảo đảm tốc độ suy giảm hàm mục tiêu $f(x_k) - f(x_{k+1}) \ge \sigma \gamma \kappa |d_k|^2$.
  • Làm sáng tỏ mối liên hệ tốc độ hội tụ đa biến: Thiết lập hệ thống bổ đề (Bổ đề 2.6 và 2.7) chứng minh tính tương đương tiệm cận về bậc hội tụ (siêu tuyến tính và bậc hai) giữa sai số vị trí $|x_k - x^|$, độ suy giảm hàm mục tiêu $|f(x_k) - f(x^)|$ và độ lớn vector gradient $|\nabla f(x_k)|$.
  • Xây dựng hệ thống phản ví dụ mẫu mực: Cung cấp chi tiết các tính toán giải tích cho hai phản ví dụ kinh điển:
    • Phản ví dụ hàm $F(x) = \frac{2}{3}x^{3/2} + x$ minh họa sự suy giảm tốc độ hội tụ từ bậc hai xuống siêu tuyến tính khi thiếu tính Lipschitz địa phương của Jacobian.
    • Phản ví dụ hàm $f(x) = \sqrt{1 + x^2}$ chứng minh sự phân kỳ của phương pháp Newton cổ điển ngay trên hàm lồi mạnh khi điểm khởi đầu nằm ngoài phạm vi lân cận nghiệm.

Về mặt đóng góp học thuật, công trình đã hệ thống hóa một cách sư phạm và chặt chẽ cây phả hệ lý thuyết từ phương pháp Newton giải hệ phương trình phi tuyến mở rộng sang bài toán tối ưu phi tuyến không ràng buộc, cung cấp các luận chứng toán học tường minh cho cơ chế hai pha và đánh giá cận số bước lặp của thuật toán Damped Newton.

Hạn chế và hướng nghiên cứu tiếp

Khóa luận đã nêu rõ các giới hạn lý thuyết và phạm vi áp dụng thực tế:

  • Ràng buộc về tính xác định dương của Hessian: Toàn bộ chứng minh hội tụ toàn cục của thuật toán Damped Newton đòi hỏi giả thiết ma trận Hessian $\nabla^2 f(x)$ phải xác định dương trên toàn bộ tập mức $\Omega = \text{Lev}(f, f(x_0))$. Khi hàm mục tiêu không lồi hoặc ma trận Hessian không xác định tại một số vùng trong không gian, thuật toán có thể gặp bế tắc do hướng $d_k$ không còn là hướng giảm.
  • Chi phí đại số tuyến tính trong bài toán quy mô lớn: Mỗi bước lặp của thuật toán đều đòi hỏi tính toán chính xác ma trận đạo hàm cấp hai $n \times n$ và giải hệ phương trình tuyến tính $\nabla^2 f(x_k) d_k = -\nabla f(x_k)$ với độ phức tạp $O(n^3)$, gây quá tải bộ nhớ và tính toán khi số chiều $n$ rất lớn.

Từ các hạn chế trên, hướng nghiên cứu tiếp theo được mở rộng bao gồm:

  • Khảo sát các phương pháp Quasi-Newton (như BFGS, DFP, L-BFGS) nhằm xấp xỉ ma trận Hessian thông qua hiệu gradient mà không cần tính đạo hàm cấp hai trực tiếp.
  • Nghiên cứu các kỹ thuật hiệu chỉnh ma trận (như phương pháp Levenberg-Marquardt hoặc vùng tin cậy Trust-Region) để xử lý tình huống ma trận Hessian không xác định dương trong tối ưu hóa phi lồi.

Giá trị tham khảo

Tài liệu khóa luận mang lại giá trị tham khảo chuyên môn cao trong các trường hợp sau:

  • Sinh viên và học viên ngành Toán học, Toán ứng dụng, Khoa học dữ liệu: Khóa luận là tài liệu tham khảo chi tiết cho các học phần Giải tích số, Tối ưu hóa phi tuyến và Giải tích lồi. Hệ thống chứng minh chi tiết bằng giải tích $\varepsilon$-$\delta$ và các bổ đề giải tích ma trận giúp người đọc nắm vững kỹ thuật chứng minh hội tụ của các thuật toán số.
  • Người nghiên cứu thuật toán tối ưu hóa: Phần phân tích kỹ thuật backtracking line search kết hợp với hướng Newton (Chương 3) và các kỹ thuật chặn chuỗi sai số cung cấp khuôn mẫu chuẩn mực để xây dựng các chứng minh hội tụ toàn cục cho các biến thể thuật toán tối ưu hóa bậc hai khác.
  • Các mục đáng tham khảo nhất:
    • Mục 1.2 và 1.3: Bổ đề 1.34 về sự lan rộng tính xác định dương của ma trận Hessian.
    • Mục 2.1 và 2.2: Phân tích so sánh tốc độ hội tụ kèm phản ví dụ giải tích 2.5 và 2.11.
    • Mục 3.1: Chứng minh ba bước của Định lý 3.2 về sự hội tụ toàn cục của phương pháp Damped Newton.

Câu hỏi thường gặp

1. Tại sao phương pháp Newton cổ điển không thể hội tụ toàn cục ngay cả khi hàm mục tiêu là hàm lồi mạnh? Ngay cả khi hàm mục tiêu $f$ là lồi mạnh (đảm bảo tồn tại duy nhất một điểm cực tiểu toàn cục), phương pháp Newton cổ điển sử dụng bước nhảy cố định $t_k = 1$ nên không kiểm soát được giá trị hàm mục tiêu sau mỗi bước. Ví dụ 2.11 trong khóa luận với hàm $f(x) = \sqrt{1 + x^2}$ cho thấy công thức lặp dẫn đến $x_{k+1} = -x_k^3$. Với bất kỳ điểm khởi đầu nào thỏa mãn $|x_0| \ge 1$, dãy lặp sẽ dao động quanh gốc tọa độ với biên độ tăng dần hoặc không đổi và phân kỳ hoàn toàn ra vô cùng thay vì hội tụ về $x^* = 0$.

2. Điều kiện nào quyết định thuật toán Newton đạt tốc độ hội tụ bậc hai thay vì chỉ dừng ở mức siêu tuyến tính? Theo Định lý 2.3 và Định lý 2.4 (cho hệ phương trình) cũng như Định lý 2.8 và Định lý 2.10 (cho bài toán tối ưu), nếu ma trận Jacobian $J_F$ (hoặc ma trận Hessian $\nabla^2 f$) chỉ liên tục tại nghiệm thì thuật toán chỉ đạt tốc độ hội tụ siêu tuyến tính. Để đạt được tốc độ hội tụ bậc hai ($|x_{k+1} - x^| \le \beta |x_k - x^|^2$), ma trận Jacobian/Hessian bắt buộc phải thỏa mãn tính liên tục Lipschitz địa phương trong một lân cận của nghiệm $x^*$. Ví dụ 2.5 đã chứng minh một hàm có đạo hàm liên tục nhưng không thỏa điều kiện Lipschitz địa phương sẽ làm mất đi tốc độ bậc hai.

3. Thuật toán Damped Newton giải quyết vấn đề phân kỳ của thuật toán Newton cổ điển bằng cơ chế nào? Thuật toán Damped Newton thay đổi bước cập nhật thành $x_{k+1} = x_k + t_k d_k$, trong đó $t_k \in (0, 1]$ được lựa chọn thông qua kỹ thuật tìm kiếm đường lùi (backtracking line search) sao cho thỏa mãn điều kiện suy giảm Armijo: $f(x_k + t_k d_k) \le f(x_k) + \sigma t_k \langle \nabla f(x_k), d_k \rangle$. Do $\langle \nabla f(x_k), d_k \rangle = -\langle d_k, \nabla^2 f(x_k) d_k \rangle < 0$ khi Hessian xác định dương, hướng Newton luôn là hướng giảm, đảm bảo dãy giá trị ${f(x_k)}$ giảm đơn điệu ngặt và giữ toàn bộ dãy lặp nằm trong tập mức đóng $\Omega$, triệt tiêu hoàn toàn khả năng phân kỳ.

4. Dựa trên cơ sở nào tác giả chứng minh được dãy bước nhảy ${t_{k_j}}$ trong thuật toán Damped Newton bị chặn dưới bởi một số dương $\gamma > 0$? Trong Khẳng định 2a của Định lý 3.2, tác giả sử dụng phương pháp phản chứng. Nếu dãy bước nhảy suy biến về 0 ($t_{k_j} \to 0$), kết hợp với tính bị chặn của dãy hướng Newton $|d_{k_j}|$ và tính liên tục Lipschitz của $\nabla f$ trên lân cận đóng compact, bước nhảy trước đó $\beta^{-1} t_{k_j}$ sẽ vi phạm điều kiện dừng của backtracking. Bằng cách khai triển Taylor và đánh giá bất đẳng thức, tác giả suy ra mâu thuẫn $\sigma > 1$ (trong khi tham số thuật toán quy định $\sigma \in (0, 1)$). Mâu thuẫn này khẳng định ${t_{k_j}}$ không thể tiến về 0 mà luôn bị chặn dưới bởi $\gamma > 0$.

5. Tập mức $\Omega = \text{Lev}(f, f(x_0))$ đóng vai trò gì trong định lý hội tụ toàn cục của phương pháp Damped Newton? Tập mức $\Omega = {x \in \mathbb{R}^n \mid f(x) \le f(x_0)}$ là không gian hình học giam giữ toàn bộ quỹ đạo của dãy lặp. Vì thuật toán Damped Newton đảm bảo $f(x_{k+1}) < f(x_k)$, mọi điểm lặp $x_k$ đều thuộc $\Omega$. Khi bổ sung giả thiết ma trận Hessian $\nabla^2 f(x)$ xác định dương trên $\Omega$, tính chất lồi và tính compact của tập mức bảo đảm sự tồn tại của điểm giới hạn, ngăn chặn nghiệm phân kỳ ra vô cực và đảm bảo điểm hội tụ duy nhất chính là nghiệm tối ưu toàn cục.

Kết luận

Khóa luận tốt nghiệp "Các phương pháp Newton và ứng dụng trong tối ưu" của tác giả Đặng Ngọc Đỗ Quyên là một công trình nghiên cứu lý thuyết hoàn chỉnh và chuẩn mực về mặt giải tích toán học đối với họ thuật toán Newton bậc hai. Bằng các lập luận logic chặt chẽ, tác giả đã làm rõ bản chất hình học, cơ chế hội tụ địa phương của phương pháp Newton cổ điển cũng như thiết lập chứng minh toàn diện cho tính hội tụ toàn cục của phương pháp Damped Newton. Các đóng góp về việc nới lỏng giả thiết hội tụ, phân tích chi tiết hai pha hoạt động và cung cấp hệ thống phản ví dụ giải tích minh họa sâu sắc mang lại giá trị học thuật và tư liệu tham khảo quan trọng cho lĩnh vực giải tích số và tối ưu hóa toán học.