Tổng quan nghiên cứu

Trong lý thuyết tối ưu hóa hiện đại, hơn 80% các bài toán kỹ thuật, kinh tế lượng và trí tuệ nhân tạo đều quy về việc tìm nghiệm tối ưu hoặc điểm cân bằng trên các tập ràng buộc lồi đóng. Luận văn thạc sĩ khoa học chuyên ngành Toán giải tích (mã số 8460102) do học viên Trần Đoàn Thảo Nguyên thực hiện dưới sự hướng dẫn của Tiến sĩ Phạm Quý Mười tại Trường Đại học Sư phạm – Đại học Đà Nẵng năm 2019 đã tập trung giải quyết bài toán cốt lõi: Ứng dụng của phép chiếu metric để giải bài toán tối ưu hóa lồi có điều kiện và bài toán bất đẳng thức biến phân phi tuyến.

Vấn đề nghiên cứu trọng tâm xuất phát từ thực tế là khi giải các bài toán tối ưu phi tuyến quy mô lớn trong không gian $n$-chiều $\mathbb{R}^n$, việc tính toán ma trận đạo hàm cấp hai (ma trận Hessian) hoặc ma trận Jacobi thường đòi hỏi chi phí tính toán rất cao. Phép chiếu metric trực giao lên tập lồi đóng mang lại giải pháp thay thế vượt trội nhờ khả năng xác định nghiệm xấp xỉ mà không đòi hỏi các phép biến đổi ma trận phức tạp.

Mục tiêu cụ thể của công trình bao gồm: thiết lập cơ sở lý thuyết giải tích lồi cho phép chiếu; xây dựng thuật toán chiếu kết hợp quy tắc chọn bước Armijo để tìm nghiệm cực tiểu toàn cục của hàm khả vi trên tập lồi đóng; và phát triển thuật toán chiếu một lần giải bài toán bất đẳng thức biến phân với ánh xạ giả đơn điệu mạnh liên tục Lipschitz. Về mặt định lượng, nghiên cứu chứng minh thuật toán đạt tốc độ hội tụ tuyến tính với hệ số co thực nghiệm nhỏ hơn 1, giúp giảm thiểu từ 45% đến 60% khối lượng tính toán trung gian so với các phương pháp gradient truyền thống trên cùng miền ràng buộc.

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

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng của 2 trụ cột lý thuyết giải tích hiện đại: Lý thuyết giải tích lồi (Convex Analysis) theo tiếp cận của Moreau - Rockafellar và Lý thuyết điểm bất động cho ánh xạ không giãn (Non-expansive Mappings). Cấu trúc mô hình tập trung vào 2 dạng bài toán toán học chuẩn mực: bài toán tối ưu có điều kiện dạng $\min {f(x) : x \in C}$ và bài toán bất đẳng thức biến phân $\text{VI}(F,C)$ tìm $x^* \in C$ sao cho $\langle F(x^), x - x^\rangle \ge 0, \forall x \in C$.

Hệ thống khái niệm nền tảng bao gồm 5 cấu trúc cốt lõi:

  1. Phép chiếu metric $P_C(x) = \arg\min_{y \in C} |x - y|$, là ánh xạ biến một điểm bất kỳ trong không gian Euclide $\mathbb{R}^n$ thành điểm gần nhất thuộc tập lồi đóng $C$.
  2. Nón pháp tuyến ngoài $N_C(x^)$ và dưới vi phân $\partial f(x)$, thiết lập điều kiện tối ưu cần và đủ tại điểm dừng $0 \in \partial f(x^)$.
  3. Ánh xạ đơn điệu mạnh và giả đơn điệu mạnh (Strongly Pseudomonotone) với hằng số $\gamma > 0$, đảm bảo tính duy nhất nghiệm của bài toán biến phân.
  4. Ánh xạ liên tục Lipschitz với hằng số $L > 0$, khống chế độ dao động của trường vector $F(x)$.
  5. Ánh xạ giá tự nhiên $F^{nat}_\lambda(x) = x - P_C(x - \lambda F(x))$, biến bài toán tìm nghiệm bất đẳng thức biến phân thành bài toán tìm không điểm của ánh xạ.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp giải tích suy diễn toán học kết hợp với phương pháp thực nghiệm mô phỏng số trên máy tính. Dữ liệu thử nghiệm gồm 5 bộ bài toán mẫu điển hình trong không gian 2 chiều $\mathbb{R}^2$ với các tập ràng buộc hộp $[0,3] \times [0,4]$, nửa không gian và hình cầu đóng có bán kính $\alpha = 1.5$. Cỡ mẫu thử nghiệm được thiết kế bao gồm 2 mô hình tối ưu toàn phương lồi và 3 mô hình bất đẳng thức biến phân phi tuyến.

Phương pháp chọn mẫu có chủ đích được áp dụng nhằm đại diện đầy đủ cho cả 2 tình huống: ánh xạ đơn điệu mạnh tuyến tính và ánh xạ phi tuyến giả đơn điệu mạnh nhưng không đơn điệu thông thường. Lý do lựa chọn phương pháp phân tích giải tích kết hợp thuật toán lặp số là nhằm kiểm chứng tính đúng đắn của các định lý hội tụ lý thuyết, đồng thời định lượng trực quan sai số dừng $\epsilon = 10^{-4}$ qua từng bước lặp. Toàn bộ quá trình nghiên cứu được triển khai theo tiến độ chuẩn 36 tháng, căn cứ theo Quyết định số 1060/QĐ-ĐHSP của Hiệu trưởng Trường Đại học Sư phạm – Đại học Đà Nẵng và các quy chế đào tạo thạc sĩ hiện hành của Bộ Giáo dục và Đào tạo.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Nghiên cứu mang lại 4 kết quả định lượng và phát hiện thuật toán mang tính đột phá:

Thứ nhất, đối với bài toán tối ưu lồi có ràng buộc hộp, thuật toán chiếu kết hợp quy tắc tìm kiếm đường thẳng Armijo (với các tham số $\beta = 0.5, \gamma = 0.5$) đã tìm ra nghiệm tối ưu toàn cục $x^* = (1,1)$ từ điểm xuất phát $x^0 = (1,2)$ chỉ sau 3 bước lặp chính. Khoảng cách sai số giảm từ 1.0 ban đầu về 0 tuyệt đối, đạt độ chính xác 100% tại bước lặp thứ 3.

Thứ hai, thiết lập điều kiện hội tụ tuyến tính nghiêm ngặt cho thuật toán chiếu một lần giải bài toán $\text{VI}(F,C)$. Khi chọn dãy độ dài bước lặp $\lambda_k$ thỏa mãn $0 < a \le \lambda_k \le b < 2\gamma/L^2$, sai số nghiệm thỏa mãn bất đẳng thức $|x^{k+1} - x^| \le \mu |x^k - x^|$ với hệ số co $\mu = \sqrt{1 - \lambda_k(2\gamma - \lambda_k L^2)} < 1$. Đặc biệt, nghiên cứu xác định được độ dài bước lặp tối ưu tuyệt đối $\lambda^* = \gamma/L^2$, đem lại hệ số co nhỏ nhất $\mu^* = \sqrt{1 - \gamma^2/L^2}$.

Thứ ba, trong bài toán bất đẳng thức biến phân tuyến tính với ma trận $A = \begin{pmatrix} 5 & 1 \ 1 & 8 \end{pmatrix}$ có hệ số đơn điệu mạnh $\gamma = 5$ và hằng số Lipschitz $L = 8.0766$, thuật toán chiếu với bước lặp cố định $\lambda = 0.1$ đã hội tụ về nghiệm duy nhất $x^* = (0.4, 0)$ từ điểm $x^0 = (2,2)$. Chuẩn sai số giữa hai bước lặp $|x^{k+1} - x^k|$ giảm mạnh từ 1.8028 ở bước 1 xuống dưới ngưỡng dừng $\epsilon = 10^{-4}$ ở bước lặp thứ 10, tương đương mức giảm sai số trên 99.99%.

Thứ tư, khi thử nghiệm trên hàm phi tuyến $F(x) = (2 - |x|)x$ trên hình cầu bán kính 1.5 với $\gamma = 0.5$ và $L = 5.5$, việc điều chỉnh độ dài bước lặp từ $\lambda = 0.03$ lên $\lambda = 0.3$ đã giúp tăng tốc độ hội tụ gấp 10 lần, minh chứng tầm quan trọng của việc lựa chọn tham số bước lặp tối ưu trong thực tế tính toán.

Thảo luận kết quả

Cơ chế giúp phương pháp chiếu đạt hiệu quả vượt trội bắt nguồn từ đặc tính không giãn của toán tử chiếu metric: $|P_C(x) - P_C(y)| \le |x - y|$. Khi kết hợp cùng tính chất giả đơn điệu mạnh của trường vector, toán tử lặp trở thành ánh xạ co chặt, ép dãy lặp hội tụ đơn điệu về điểm bất động duy nhất.

So với các nghiên cứu trong giai đoạn 2015 – 2018 sử dụng phương pháp chiếu hai lần (Extragradient) hoặc phương pháp suy rộng đòi hỏi phải giải một bài toán quy hoạch phụ ở mỗi vòng lặp, phương pháp chiếu một lần trong luận văn này giúp tiết kiệm xấp xỉ 50% thời gian thực thi tính toán trên mỗi vòng lặp. Dữ liệu thực nghiệm của luận văn được tổ chức khoa học qua hệ thống 5 bảng số liệu chi tiết (từ Bảng 2.1 đến Bảng 3.3), ghi nhận đầy đủ tọa độ vector nghiệm $x^k$, vector hướng $d^k$ và độ suy giảm chuẩn $|x^{k+1} - x^k|$. Dữ liệu này có thể được biểu diễn trực quan bằng biểu đồ suy giảm sai số thang đo logarit (Logarithmic Convergence Plot), thể hiện đường dốc tuyến tính thẳng đứng đặc trưng của thuật toán bậc một tối ưu.

Đề xuất và khuyến nghị

Dựa trên các kết quả giải tích và mô phỏng thực nghiệm, tác giả và nhóm nghiên cứu đưa ra 4 khuyến nghị hành động cụ thể:

  1. Mở rộng nghiên cứu thuật toán chiếu hai lần và phương pháp chiếu siêu phẳng cắt (Hyperplane Projection): Các nhóm nghiên cứu giải tích lồi tại các trường đại học cần phát triển các biến thể thuật toán cho lớp bài toán chỉ thỏa mãn tính đơn điệu thông thường hoặc tựa đơn điệu (bỏ qua điều kiện đơn điệu mạnh), nhằm nâng tỷ lệ giải quyết thành công các bài toán biến phân phức tạp lên trên 90% trong giai đoạn 12 đến 18 tháng tới.

  2. Ứng dụng kỹ thuật tự động điều chỉnh độ dài bước lặp thích ứng (Adaptive Stepsize): Các kỹ sư thuật toán tối ưu cần tích hợp công thức ước lượng cục bộ hằng số Lipschitz $L_k$ vào từng bước lặp, giúp loại bỏ việc chọn bước thủ công và cắt giảm thêm 30% số vòng lặp không cần thiết, hoàn thành thử nghiệm trong vòng 6 tháng.

  3. Xây dựng gói thư viện mã nguồn mở chuyên dụng: Khuyến nghị các cơ sở đào tạo đại học số hóa các thuật toán trong luận văn thành thư viện trên nền tảng Python và MATLAB, phục vụ trực tiếp cho 100% sinh viên và học viên cao học ngành Toán ứng dụng trong thời gian 9 tháng.

  4. Triển khai mô hình bài toán bù phi tuyến vào tối ưu hóa giao thông và kinh tế lượng: Các viện nghiên cứu liên ngành và cơ quan quản lý đô thị cần ứng dụng mô hình bất đẳng thức biến phân $\text{VI}(F,C)$ để mô phỏng bài toán cân bằng lưu lượng giao thông và cân bằng thị trường điện cạnh tranh, hướng tới tối ưu hóa từ 15% đến 25% chi phí vận hành hệ thống trong lộ trình 24 tháng.

Đối tượng nên tham khảo luận văn

Công trình luận văn thạc sĩ này là nguồn tư liệu chuyên khảo giá trị cho 4 nhóm đối tượng chính:

  1. Học viên cao học và nghiên cứu sinh ngành Toán giải tích, Toán ứng dụng: Cung cấp khung lý thuyết chặt chẽ, các kỹ thuật chứng minh giải tích lồi chuẩn mực và cách thức xây dựng bổ đề hội tụ cho thuật toán lặp. Sử dụng làm tài liệu tham khảo trực tiếp khi viết luận văn thạc sĩ và bài báo khoa học.

  2. Giảng viên và nhà nghiên cứu tại các trường đại học: Sở hữu tài liệu bài giảng chất lượng cao với 5 ví dụ tính toán số học tường minh, hỗ trợ biên soạn giáo trình chuyên đề về Lý thuyết tối ưu hóa, Giải tích lồi và Phương pháp tính nâng cao.

  3. Kỹ sư Trí tuệ nhân tạo và Khoa học dữ liệu: Vận dụng kỹ thuật chiếu metric để xử lý các bài toán huấn luyện mô hình học máy có ràng buộc tham số (Projected Gradient Descent), đặc biệt là trong mạng nơ-ron sâu và tối ưu hóa hàm mục tiêu không trơn.

  4. Chuyên gia kinh tế lượng và kỹ sư quy hoạch hệ thống: Sử dụng công cụ bất đẳng thức biến phân và bài toán bù phi tuyến $\text{CP}(F,C)$ để giải quyết bài toán cân bằng thị trường Nash, cân bằng mạng lưới cung ứng và phân bổ tài nguyên tối ưu trong thực tế vận hành doanh nghiệp.

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

1. Phép chiếu metric lên tập lồi đóng có vai trò gì trong lý thuyết tối ưu?
Phép chiếu metric $P_C(x)$ là ánh xạ tìm điểm gần nhất thuộc tập lồi đóng $C$ so với điểm $x$. Vai trò cốt lõi của phép chiếu là đưa các bước nhảy gradient nằm ngoài miền ràng buộc quay trở lại tập chấp nhận được, đồng thời chuyển việc giải bài toán tối ưu hoặc bất đẳng thức biến phân về bài toán tìm điểm bất động $x^* = P_C(x^* - \lambda \nabla f(x^*))$.

2. Quy tắc Armijo trong thuật toán chiếu tối ưu lồi hoạt động như thế nào?
Quy tắc Armijo là thủ tục tìm kiếm đường thẳng không chính xác nhằm xác định số mũ nguyên dương $m_k$ nhỏ nhất thỏa mãn mức suy giảm hàm mục tiêu $f(x^k + \gamma^{m_k} d^k) \le f(x^k) + \beta \gamma^{m_k} \langle d^k, \nabla f(x^k)\rangle$. Trong ví dụ với $\beta = 0.5, \gamma = 0.5$, quy tắc này đảm bảo bước nhảy luôn giảm giá trị hàm mục tiêu và đưa thuật toán hội tụ sau 3 đến 5 bước lặp.

3. Điều kiện để thuật toán chiếu một lần hội tụ tuyến tính là gì?
Thuật toán chiếu một lần đạt tốc độ hội tụ tuyến tính khi và chỉ khi ánh xạ $F$ là giả đơn điệu mạnh với hằng số $\gamma > 0$, liên tục Lipschitz với hằng số $L > 0$, và độ dài bước lặp $\lambda_k$ được chọn trong khoảng mở $(0, 2\gamma/L^2)$. Khi đó, chuẩn sai số nghiệm giảm theo cấp số nhân với công bội $\mu < 1$.

4. Mối liên hệ giữa bài toán bù phi tuyến $\text{CP}(F,C)$ và bất đẳng thức biến phân $\text{VI}(F,C)$ là gì?
Điểm $x^$ là nghiệm của bài toán bù phi tuyến $\text{CP}(F,C)$ trên nón dương $\mathbb{R}^n_+$ (thỏa mãn $x^ \ge 0, F(x^) \ge 0$ và $\langle F(x^), x^\rangle = 0$) khi và chỉ khi $x^$ là nghiệm của bài toán bất đẳng thức biến phân $\text{VI}(F,C)$ trên cùng tập lồi đóng đó.

5. Việc điều chỉnh độ dài bước lặp ảnh hưởng thế nào đến tốc độ tính toán?
Độ dài bước lặp $\lambda$ quyết định trực tiếp hệ số co $\mu$. Trong thực nghiệm hàm phi tuyến tại luận văn, khi tăng bước lặp từ $\lambda = 0.03$ lên bước lặp tối ưu gần $\lambda = 0.3$, số vòng lặp để đạt ngưỡng sai số $\epsilon = 10^{-4}$ đã giảm gần 10 lần, chứng minh bước lặp tối ưu giúp tiết kiệm phần lớn tài nguyên tính toán.

Kết luận

  • Luận văn hệ thống hóa xuất sắc các kiến thức nền tảng về giải tích lồi, nón pháp tuyến và tính chất ánh xạ không giãn của phép chiếu metric trong không gian $\mathbb{R}^n$.
  • Thiết lập thành công thuật toán chiếu kết hợp quy tắc chọn bước Armijo cho bài toán tối ưu lồi, đảm bảo tìm được nghiệm cực tiểu toàn cục với số bước lặp tối thiểu.
  • Chứng minh chặt chẽ định lý hội tụ tuyến tính và xác định công thức bước lặp tối ưu $\lambda^* = \gamma/L^2$ cho thuật toán chiếu một lần giải bài toán bất đẳng thức biến phân $\text{VI}(F,C)$.
  • Cung cấp hệ thống 5 ví dụ thực nghiệm số học chi tiết với độ chính xác cao, minh chứng sai số giảm hơn 99.99% sau 10 bước lặp.
  • Định hướng nghiên cứu tiếp nối trong 12 đến 24 tháng tới tập trung mở rộng sang phương pháp chiếu hai lần và chiếu siêu phẳng cho các bài toán đa mục tiêu phức tạp.

Công trình là tài liệu học thuật giá trị cao, kết hợp hài hòa giữa toán học lý thuyết trừu tượng và ứng dụng tính toán số thực tiễn. Quý độc giả, giảng viên và các bạn học viên cao học quan tâm có thể tra cứu toàn văn luận văn tại thư viện Trường Đại học Sư phạm – Đại học Đà Nẵng để khai thác sâu hơn các bổ đề và thuật giải chi tiết.