Tổng quan luận án

Luận án tiến sĩ toán học của nghiên cứu sinh Đỗ Duy Thành có tiêu đề: "Một số phương pháp tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động của ánh xạ không giãn", được thực hiện tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội dưới sự hướng dẫn khoa học của PGS. Phạm Ngọc Anh và GS. Phạm Kỳ Anh; bảo vệ năm 2016 thuộc chuyên ngành Toán giải tích, mã số 62460102.

Tính cấp thiết và khoảng trống nghiên cứu

Mô hình cân bằng được xem là sự phát triển mở rộng của mô hình tối ưu hóa và bài toán bất đẳng thức biến phân. Lớp bài toán cân bằng dưới dạng bất đẳng thức Ky Fan xuất hiện từ năm 1972 và gắn liền với các ứng dụng trong cân bằng kinh tế theo khái niệm cân bằng Nash. Khi xử lý các bài toán đa chủ thể với mục tiêu xung đột, mô hình cân bằng cung cấp công cụ toán học thích hợp để mô tả trạng thái thỏa hiệp mà không chủ thể nào có lợi ích đơn phương thay đổi chiến lược.

Về mặt lý thuyết, sự tồn tại nghiệm của bài toán cân bằng trên không gian trừu tượng đã đạt được nhiều kết quả cơ bản; tuy nhiên về mặt thuật toán tính toán, các kết quả còn nhiều hạn chế:

  • Hầu hết các thuật toán đã biết chỉ áp dụng cho song hàm thực có tính chất đơn điệu hoặc đơn điệu mạnh. Lớp bài toán cân bằng với song hàm có tính đơn điệu suy rộng (như giả đơn điệu, tựa đơn điệu) và không thỏa mãn điều kiện liên tục Lipschitz còn ít được nghiên cứu do độ phức tạp cao.
  • Phần lớn các phương pháp giải bài toán tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động (như phương pháp xấp xỉ gắn kết, phương pháp chiếu) tại mỗi bước lặp $n$ đều phải giải một bài toán cân bằng phụ. Trong thực tế, nếu bài toán phụ này chỉ tìm được nghiệm xấp xỉ thì dãy lặp chưa chắc đã hội tụ về nghiệm cần tìm.
  • Điều kiện liên tục kiểu Lipschitz của song hàm thường bị áp đặt trong hầu hết các công trình trước đây, trong khi đây là một điều kiện rất mạnh và khó kiểm tra trong các ứng dụng thực tế.

Khoảng trống nghiên cứu mà luận án tập trung giải quyết là xây dựng các thuật toán lặp mới tìm nghiệm chung cho bài toán cân bằng giả đơn điệu (cả trường hợp thỏa mãn và không thỏa mãn điều kiện Lipschitz) với bài toán điểm bất động của một ánh xạ hoặc một họ ánh xạ không giãn, giúp loại bỏ việc giải bài toán cân bằng phụ hoặc loại bỏ hoàn toàn điều kiện Lipschitz.

Mục tiêu nghiên cứu

Luận án xác định 5 nhiệm vụ và mục tiêu cụ thể:

  1. Giải bài toán trong hai trường hợp: Song hàm $f$ giả đơn điệu liên tục kiểu Lipschitz và không liên tục kiểu Lipschitz.
  2. Giải bài toán với tập điểm bất động của một ánh xạ không giãn và tập điểm bất động của một họ vô hạn hay đếm được các ánh xạ không giãn.
  3. Xây dựng một số thuật toán mới và chứng minh sự hội tụ mạnh, hội tụ yếu của các thuật toán đó.
  4. Áp dụng các kết quả đạt được cho bài toán bất đẳng thức biến phân.
  5. Xây dựng một số ví dụ tính toán để minh họa cho các thuật toán tìm được.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Nghiệm chung thuộc tập giao giữa tập nghiệm của bài toán cân bằng $\operatorname{Sol}(C, f)$ (với song hàm $f$ giả đơn điệu), tập điểm bất động $\operatorname{Fix}(S)$ (hoặc $\bigcap \operatorname{Fix}(S_i)$) của ánh xạ không giãn, và tập nghiệm của bài toán bất đẳng thức biến phân $\operatorname{Sol}(C, F)$.
  • Phạm vi không gian: Không gian Hilbert thực $H$ tổng quát (cho việc thiết lập các định lý hội tụ lý thuyết) và không gian Euclid hữu hạn chiều $\mathbb{R}^n$ (cụ thể là $\mathbb{R}^3$ trong các thực nghiệm số).
  • Phạm vi toán học: Tập chấp nhận $C$ là tập con lồi, đóng, khác rỗng của $H$.

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu trước được điểm lại trong luận án

Luận án hệ thống hóa các mốc phát triển lý thuyết và thuật toán liên quan:

  • Lý thuyết bài toán cân bằng: Ky Fan (1972) đề xuất bất đẳng thức Minimax Ky Fan mở đầu cho lý thuyết bài toán cân bằng; J. Nash đưa ra khái niệm điểm cân bằng trong lý thuyết trò chơi không hợp tác; E. Blum và W. Oettli (1994) hệ thống hóa bài toán cân bằng như một mô hình thống nhất bao hàm tối ưu hóa, bất đẳng thức biến phân, bài toán bù phi tuyến, điểm yên ngựa và điểm bất động Kakutani.
  • Lý thuyết điểm bất động của ánh xạ không giãn: F.E. Browder (1965), D. Gohde (1965), và W.A. Kirk (1965) thiết lập các định lý nền tảng về sự tồn tại điểm bất động của ánh xạ không giãn trong không gian Banach lồi đều và không gian có cấu trúc chuẩn tắc; W. Mann (1953) đề xuất dãy lặp Mann cho ánh xạ không giãn.
  • Phương pháp xấp xỉ gắn kết (viscosity approximation methods): P.L. Combettes và S.A. Hirstoaga (2005) nghiên cứu tính chất đơn trị và không giãn vững của ánh xạ nghiệm $T_r$; A. Moudafi (2000) phát triển phương pháp xấp xỉ cho bài toán điểm bất động; S. Takahashi và W. Takahashi (2007) kết hợp hai kết quả này để đề xuất phương pháp xấp xỉ gắn kết tìm nghiệm chung của bài toán cân bằng đơn điệu và ánh xạ không giãn.
  • Phương pháp chiếu (projection methods): W. Takahashi (2003, 2007) và K. Nakajo & W. Takahashi (2003) cải tiến phương pháp xấp xỉ gắn kết bằng cách chiếu xấp xỉ ban đầu lên giao của các tập lồi đóng để đạt được sự hội tụ mạnh.
  • Phương pháp đạo hàm tăng cường (extragradient methods): G.M. Korpelevich (1976) đề xuất sơ đồ đạo hàm tăng cường với hai phép chiếu trong mỗi bước lặp cho bài toán điểm yên ngựa và bất đẳng thức biến phân; T.V. Hien (2009) mở rộng sơ đồ này cho bài toán cân bằng trong $\mathbb{R}^n$; P.N. Anh (2012) áp dụng đạo hàm tăng cường để tìm điểm chung của bài toán cân bằng và ánh xạ không giãn (đạt hội tụ yếu).
  • Phương pháp đạo hàm tăng cường xấp xỉ: R. Wangkeeree (2008) kết hợp kỹ thuật điểm bất động của Y. Yao (2007) và phương pháp của S. Takahashi để giải bài toán cân bằng, bất đẳng thức biến phân và họ đếm được các ánh xạ không giãn.
  • Phương pháp chính quy hóa và lặp dạng ẩn: S. Sun (2010) đề xuất phương pháp chính quy thay phiên (alternative regularization); R.G. Ori (2001) đưa ra kỹ thuật lặp dạng ẩn cho họ hữu hạn ánh xạ không giãn; F. Su (2008) phát triển phương pháp lai ghép dạng ẩn; K. Saejung (2008) đề xuất phương pháp chiếu kết hợp lặp dạng ẩn cho họ đếm được; P.N. Anh, L.D. Muu và C.V. Chung (2014) phát triển phương pháp song song giảm số lượng phép chiếu.
  • Các tác giả trong nước: P.Q. Khanh, N.X. Tan, L.D. Muu, N.H. Dien, P.N. Anh, P.K. Anh, P.H. Sach, N.S. Pham...

Khoảng trống luận án lựa chọn giải quyết

Luận án định vị trọng tâm giải quyết ba hạn chế chính của các nghiên cứu tiền nhiệm:

  1. Giảm nhẹ giả thiết đơn điệu hoặc đơn điệu mạnh của song hàm $f$ xuống tính chất giả đơn điệu.
  2. Loại bỏ việc phải giải các bài toán cân bằng phụ phức tạp tại từng bước lặp, thay thế bằng việc giải hai bài toán tối ưu lồi mạnh có nghiệm tường minh/chính xác.
  3. Loại bỏ hoàn toàn điều kiện liên tục kiểu Lipschitz đối với song hàm $f$ thông qua việc tích hợp kỹ thuật tìm kiếm theo tia kiểu Armijo kết hợp phép chiếu siêu phẳng.

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

Khung lý thuyết và các khái niệm sử dụng

Luận án vận dụng hệ thống khái niệm của giải tích hàm, giải tích lồi và lý thuyết toán tử phi tuyến trên không gian Hilbert thực $H$:

  • Không gian Hilbert thực: Cặp $(H, \langle \cdot, \cdot \rangle)$ đầy đủ với chuẩn $|x| = \sqrt{\langle x, x \rangle}$, tôpô mạnh (chuẩn) và tôpô yếu $\sigma(H, H^*)$, điều kiện Opial (nếu $x_n \rightharpoonup x$ thì $\liminf |x_n - x| < \liminf |x_n - y|$ với mọi $y \neq x$), tính chất nửa đóng (demiclosed) và tính liên tục yếu.
  • Phép chiếu metric: Cho tập lồi, đóng, khác rỗng $C \subset H$, phép chiếu trực giao $P r_C(x) = \operatorname{argmin}{|x - y| : y \in C}$ với tính chất cơ bản $\langle x - P r_C(x), y - P r_C(x) \rangle \le 0, \forall y \in C$.
  • Ánh xạ không giãn: Ánh xạ $S: C \to C$ thỏa mãn $|S(x) - S(y)| \le |x - y|, \forall x, y \in C$; tập các điểm bất động ký hiệu là $\operatorname{Fix}(S) = {x \in C : S(x) = x}$.
  • Song hàm và tính chất đơn điệu: Cho song hàm $f: C \times C \to \mathbb{R}$ với $f(x, x) = 0, \forall x \in C$:
    • Đơn điệu mạnh: $f(x, y) + f(y, x) \le -\beta |x - y|^2$ ($\beta > 0$).
    • Đơn điệu chặt: $f(x, y) + f(y, x) < 0$ với mọi $x \neq y$.
    • Đơn điệu: $f(x, y) + f(y, x) \le 0$.
    • Giả đơn điệu: $f(x, y) \ge 0 \implies f(y, x) \le 0$.
  • Các mô hình bài toán quy về bài toán cân bằng $EP(C, f)$:
    • Bài toán bất đẳng thức biến phân $VI(C, F)$: $f(x, y) = \langle F(x), y - x \rangle$.
    • Bài toán tối ưu hóa $(OP)$: $f(x, y) = F(y) - F(x)$.
    • Bài toán điểm bất động Kakutani: $f(x, y) = \max_{v \in \varphi(x)} \langle x - v, y - x \rangle$.
    • Bài toán điểm yên ngựa: $f(x, y) = f_1(y_1, x_2) - f_1(x_1, y_2)$ với $x = (x_1, x_2), y = (y_1, y_2)$.
    • Bài toán bù phi tuyến: $f(x, y) = \langle F(x), y - x \rangle$ trên nón lồi đóng $C$.
    • Bài toán cân bằng Nash: $f(x, y) = \sum_{i=1}^p [f_i(x[y_i]) - f_i(x)]$.
  • Ánh xạ nghiệm: $T_r(x) = {z \in C : f(z, y) + \frac{1}{r}\langle y - z, z - x \rangle \ge 0, \forall y \in C}$, là ánh xạ đơn trị, không giãn vững và $\operatorname{Fix}(T_r) = \operatorname{Sol}(C, f)$.

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

Luận án sử dụng phương pháp giải tích toán học thuần túy kết hợp mô phỏng tính toán số:

  • Phương pháp giải tích phi tuyến và giải tích lồi: Sử dụng giải tích dưới vi phân $\partial_2 f$, định lý Moreau-Rockafellar, lý thuyết nón pháp tuyến ngoài $N_C$, bất đẳng thức biến phân và các tính chất hình học của không gian Hilbert để phân tích sự hội tụ của dãy lặp.
  • Phương pháp xây dựng thuật toán lặp:
    • Kỹ thuật kết hợp đạo hàm tăng cường với chính quy hóa tương đối/thay phiên.
    • Kỹ thuật chiếu lai ghép (hybrid projection) trên giao các tập lồi đóng.
    • Kỹ thuật tìm kiếm theo tia (linesearch) kiểu Armijo để nội suy bước lặp tự điều chỉnh không phụ thuộc hằng số Lipschitz.
  • Phương pháp tính toán số và mô phỏng thực nghiệm: Cài đặt thuật toán bằng ngôn ngữ và phần mềm tính toán khoa học, đo lường số bước lặp ($n$), nghiệm xấp xỉ $\bar{x}$ và thời gian CPU thực thi (giây).

Nguồn tư liệu và công cụ

  • Tư liệu nghiên cứu là các công trình toán học chuyên ngành công bố trên các tạp chí quốc tế và trong nước về lý thuyết tối ưu, điểm bất động và giải tích biến phân.
  • Công cụ tính toán: Phần mềm Matlab R2010b thực thi trên máy tính cá nhân CPU Intel(R) Core(TM) i3-2330M @ 2.20GHz, 2GB RAM.

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

Chương 1. Bài toán cân bằng và ánh xạ không giãn

Chương 1 giữ vai trò bổ trợ và cung cấp cơ sở lý thuyết cho toàn bộ luận án, gồm các nội dung chính:

  • Sự hội tụ mạnh và yếu trong không gian Hilbert thực (Mục 1.1): Trình bày tích vô hướng, chuẩn, bất đẳng thức Cauchy-Schwarz, không gian $\mathbb{R}^n$, không gian $l_2$, định lý biểu diễn Riesz cho phiếm hàm tuyến tính liên tục, tôpô yếu $\sigma(H, H^*)$, tính chất của dãy hội tụ yếu/mạnh, bổ đề về tính chất của cơ sở trực chuẩn và tính nửa đóng (demiclosed), tính liên tục yếu của ánh xạ.
  • Phép chiếu và các tính chất (Mục 1.2): Định nghĩa phép chiếu trực giao $P r_C(x)$ và chứng minh các bất đẳng thức đặc trưng của phép chiếu metric lên tập lồi đóng.
  • Ánh xạ không giãn và các định lý điểm bất động (Mục 1.3): Trình bày định nghĩa ánh xạ không giãn, tập điểm bất động $\operatorname{Fix}(S)$; các khái niệm không gian Banach lồi chặt, lồi đều, cấu trúc chuẩn tắc; các định lý tồn tại điểm bất động của F.E. Browder, D. Gohde, W.A. Kirk; các ví dụ phản chứng về ánh xạ không giãn không có điểm bất động (ánh xạ dịch chuyển trong không gian Banach, ánh xạ trên hình cầu đơn vị của $c_0$) hoặc có điểm bất động ngoài tập xác định.
  • Bài toán cân bằng (Mục 1.4): Định nghĩa bài toán $EP(C, f)$; chi tiết hóa 6 trường hợp riêng (Bất đẳng thức biến phân, Tối ưu, Điểm bất động Kakutani, Điểm yên ngựa, Bù phi tuyến, Cân bằng Nash); các điều kiện tồn tại nghiệm dưới giả thiết nửa liên tục dưới $(A_1)$, tựa lồi $(A_2)$, nửa liên tục trên $(A_3)$ và tính duy nhất nghiệm khi song hàm đơn điệu mạnh hoặc giả đơn điệu chặt.
  • Một số phương pháp tìm nghiệm chung đã biết (Mục 1.5): Trình bày chi tiết 3 thuật toán nền tảng:
    1. Phương pháp xấp xỉ gắn kết của S. Takahashi & W. Takahashi (2007): Dãy lặp $x_{n+1} = \alpha_n g(x_n) + (1 - \alpha_n) S u_n$, trong đó $u_n$ giải bài toán cân bằng phụ $f(u_n, y) + \frac{1}{r_n}\langle y - u_n, u_n - x_n \rangle \ge 0$.
    2. Phương pháp chiếu của W. Takahashi (2007): Chiếu điểm ban đầu lên giao của hai tập lồi đóng $C_n \cap D_n$ để đạt hội tụ mạnh.
    3. Phương pháp đạo hàm tăng cường xấp xỉ của R. Wangkeeree (2008): Kết hợp giải bài toán cân bằng phụ với bước chiếu đạo hàm tăng cường $y_n = P r_C(u_n - \lambda_n A u_n)$ và dãy các ánh xạ không giãn ${S_n}$.

Chương 2. Phương pháp điểm bất động

Chương 2 trình bày phương pháp lặp mới giải bài toán tìm điểm chung của tập nghiệm bài toán cân bằng giả đơn điệu, liên tục kiểu Lipschitz trên không gian Hilbert thực $H$ và tập điểm bất động của ánh xạ không giãn $S$:

  • Tiếp cận điểm bất động của ánh xạ không giãn (Mục 2.1): Tổng quan các sơ đồ lặp kinh điển gồm dãy lặp Mann (1953), sơ đồ lặp cải tiến của W. Takahashi đạt hội tụ mạnh, kỹ thuật lặp dạng ẩn của R.G. Ori (2001) cho họ hữu hạn, phương pháp lai ghép dạng ẩn của F. Su (2008) và phương pháp song song của P.N. Anh, L.D. Muu, C.V. Chung (2014).
  • Xây dựng dãy lặp mới (Mục 2.2): Kết hợp phương pháp đạo hàm tăng cường của P.N. Anh (2012) và phương pháp chính quy hóa tương đối của S. Sun (2010). Thay vì giải bài toán cân bằng phụ, thuật toán chỉ giải hai bài toán tối ưu lồi mạnh tại mỗi bước lặp: $$\begin{cases} y_n = \operatorname{argmin} \left{ \lambda_n f(x_n, y) + \frac{1}{2} |y - x_n|^2 : y \in C \right} \ t_n = \operatorname{argmin} \left{ \lambda_n f(y_n, t) + \frac{1}{2} |t - x_n|^2 : t \in C \right} \ x_{n+1} = \beta_n g(x_n) + (1 - \beta_n) S(\alpha_n u + (1 - \alpha_n) t_n) \end{cases}$$ trong đó $x_0, u \in C$, $g: C \to C$ là ánh xạ co với hệ số $\delta \in (0, \frac{\sqrt{2}}{2})$, các dãy tham số thỏa mãn ${\alpha_n}, {\beta_n} \subset (0, 1)$, $\sum \alpha_n < \infty$, $\sum \beta_n < \infty$, và ${\lambda_n} \subset [a, b] \subset (0, \frac{1}{L})$ với $L = \max{2c_1, 2c_2}$.
  • Kết quả hội tụ (Mục 2.3 - Định lý 2.1): Dưới các giả thiết $(C_1)-(C_5)$ (song hàm $f$ giả đơn điệu, liên tục Lipschitz với hằng số $c_1, c_2$, liên tục yếu, lồi và khả dưới vi phân theo biến thứ hai; $S$ không giãn; $\operatorname{Fix}(S) \cap \operatorname{Sol}(C, f) \neq \emptyset$), chứng minh các dãy ${x_n}, {y_n}, {t_n}$ cùng hội tụ yếu về điểm $x^* \in \operatorname{Fix}(S) \cap \operatorname{Sol}(C, f)$ khi $\lim_{n \to \infty} |x_{n+1} - x_n| = 0$.
  • Kết quả tính toán số (Mục 2.4): Áp dụng giải bài toán cân bằng trên $\mathbb{R}^3$ với ánh xạ không giãn $S$ là ánh xạ đồng nhất $I$, tiêu chuẩn dừng $\epsilon$-nghiệm xấp xỉ khi $|x_n - y_n| \le \epsilon = 10^{-4}$.
    • Tập lồi đa diện: $C = {(x_1, x_2, x_3)^T \in \mathbb{R}^3_+ : x_1 + 2x_2 + x_3 \le 12, 2x_1 + x_2 - x_3 \le 10, x_1 + x_2 + x_3 \ge 5}$.
    • Song hàm $f(x, y) = \langle Ax + By + q, y - x \rangle$ với các ma trận $A, B$ đối xứng nửa xác định dương, $B - A$ nửa xác định âm, hằng số Lipschitz $c_1 = c_2 = \frac{1}{2}|A - B| = 1.4$.
    • Bảng kết quả tính toán số với hai điểm xuất phát khác nhau:
Bước lặp ($n$) Điểm xuất phát $x_0 = (3, 2, 4)^T$ Điểm xuất phát $x_0 = (5, 2, 3)^T$
$n = 0$ $x_0 = (3.0000, 2.0000, 4.0000)^T$ $x_0 = (5.0000, 2.0000, 3.0000)^T$
Nghiệm xấp xỉ đạt được $\bar{x} \approx (3.6777, \dots)^T$ $\bar{x} \approx (3.6772, \dots)^T$
Số bước lặp hoàn thành 13 bước lặp 11 bước lặp
Thời gian CPU thực thi 0.55 giây 0.45 giây

Chương 3. Phương pháp đạo hàm tăng cường mở rộng

Chương 3 mở rộng kỹ thuật đạo hàm tăng cường để xử lý bài toán tìm điểm chung của bài toán cân bằng và tập điểm bất động của một họ các ánh xạ không giãn:

  • Phương pháp chiếu cho một họ ánh xạ không giãn (Mục 3.1): Tổng quan phương pháp của K. Saejung (2008) kết hợp phép chiếu và kỹ thuật lặp dạng ẩn cho họ đếm được các ánh xạ không giãn ${S_n}$.
  • Phương pháp đạo hàm tăng cường (Mục 3.2): Phân tích cơ chế hoạt động của sơ đồ đạo hàm tăng cường kinh điển cho bài toán cân bằng trong không gian Hilbert.
  • Phương pháp đạo hàm tăng cường mở rộng (Mục 3.3): Đề xuất thuật toán mới kết hợp phương pháp lặp kiểu Mann và phép chiếu dạng lai ghép (hybrid projection). Tại mỗi bước lặp, xấp xỉ ban đầu của dãy lặp được chiếu lên giao của hai họ các tập lồi đóng chứa tập nghiệm của bài toán. Kết quả chính của chương chứng minh được sự hội tụ mạnh của dãy lặp về nghiệm chung mà không cần bất kỳ giả thiết nào về tính bị chặn của miền chấp nhận $C$.

Chương 4. Phương pháp tìm kiếm theo tia

Chương 4 nghiên cứu và áp dụng phương pháp tìm kiếm theo tia (linesearch) kiểu Armijo để giải ba lớp bài toán:

  1. Bài toán 1 (Mục 4.1): Tìm điểm chung của tập nghiệm bài toán cân bằng và tập điểm bất động của một ánh xạ không giãn đơn lẻ.
  2. Bài toán 2 (Mục 4.2): Tìm điểm chung của tập nghiệm bài toán cân bằng và tập điểm bất động của một họ các ánh xạ không giãn.
  3. Bài toán 3 (Mục 4.3): Tìm điểm chung của tập nghiệm bài toán cân bằng, tập nghiệm bài toán bất đẳng thức biến phân và tập điểm bất động của ánh xạ không giãn.

Nét đặc thù của phương pháp tìm kiếm theo tia kiểu Armijo trong chương này:

  • Loại bỏ điều kiện Lipschitz: Thuật toán không đòi hỏi song hàm $f$ phải thỏa mãn điều kiện liên tục kiểu Lipschitz (vốn là điều kiện rất chặt và khó thỏa mãn trong thực tế).
  • Cấu trúc thuật toán: Sử dụng kỹ thuật Armijo để xác định kích thước bước lặp thích nghi; xây dựng một siêu phẳng chứa tập nghiệm của bài toán cân bằng, bài toán bất đẳng thức biến phân và tập điểm bất động của ánh xạ không giãn.
  • Kỹ thuật chiếu: Chiếu điểm lặp hiện tại vào phần giao của siêu phẳng nói trên với tập con lồi đóng khác rỗng chứa điểm xuất phát $x_0$, sau đó kết hợp với toán tử điểm bất động để tạo điểm lặp tiếp theo, chứng minh đầy đủ các định lý về sự hội tụ mạnh và hội tụ yếu.

Kết quả và những đóng góp mới

Các đóng góp mới về mặt lý luận

  1. Phát triển thuật toán giải bài toán cân bằng giả đơn điệu Lipschitz và ánh xạ không giãn (Chương 2): Đề xuất sơ đồ lặp kết hợp giữa đạo hàm tăng cường và chính quy hóa tương đối; chứng minh sự hội tụ yếu của dãy lặp mà chỉ cần giải hai bài toán tối ưu lồi mạnh tại mỗi bước, loại bỏ hoàn toàn yêu cầu giải bài toán cân bằng phụ.
  2. Đề xuất phương pháp đạo hàm tăng cường mở rộng dạng lai ghép (Chương 3): Kết hợp lặp kiểu Mann và phép chiếu lên giao các họ tập lồi đóng để tìm nghiệm chung của bài toán cân bằng và họ các ánh xạ không giãn; thiết lập sự hội tụ mạnh mà không cần giả thiết về tính bị chặn của tập $C$.
  3. Xây dựng phương pháp tìm kiếm theo tia kiểu Armijo không Lipschitz (Chương 4): Thiết lập thuật toán giải bài toán cân bằng giả đơn điệu khi song hàm $f$ không thỏa mãn điều kiện liên tục Lipschitz; chứng minh sự hội tụ mạnh và hội tụ yếu cho cả 3 mô hình: bài toán cân bằng với một ánh xạ không giãn, bài toán cân bằng với một họ ánh xạ không giãn, và bài toán kết hợp đồng thời cân bằng, bất đẳng thức biến phân và ánh xạ không giãn.

Đóng góp về mặt thực tiễn và tính toán

  • Thuật toán có cấu trúc tính toán đơn giản, giảm khối lượng tính toán phụ trợ, giải quyết được vấn đề sai số tích tụ khi giải bài toán phụ dạng xấp xỉ.
  • Xây dựng và thực thi thành công các chương trình tính toán số trên phần mềm Matlab R2010b trong không gian $\mathbb{R}^3$, khẳng định tính khả thi và tốc độ hội tụ của thuật toán đề xuất (hoàn thành sau 11–13 bước lặp với thời gian dưới 0.6 giây).

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

Hạn chế của nghiên cứu

  • Các định lý hội tụ lý thuyết và cấu trúc thuật toán được thiết lập chủ yếu trên không gian Hilbert thực $H$; chưa mở rộng cho các không gian Banach tổng quát không có tích vô hướng.
  • Kết quả hội tụ ở Chương 2 mới dừng lại ở hội tụ yếu (trường hợp hội tụ mạnh đòi hỏi bổ sung kỹ thuật chiếu hoặc phép chiếu dạng lai ghép như ở Chương 3 và Chương 4).
  • Phần thực nghiệm số mới được kiểm thử trên không gian hữu hạn chiều $\mathbb{R}^3$ với tập ràng buộc là tập lồi đa diện; chưa tiến hành thử nghiệm số quy mô lớn trên không gian vô hạn chiều hoặc các mô hình cân bằng kinh tế thực tế phức tạp.

Hướng nghiên cứu tiếp

  • Mở rộng các phương pháp đạo hàm tăng cường và tìm kiếm theo tia kiểu Armijo cho lớp các bài toán cân bằng đa trị hoặc bài toán cân bằng tựa đơn điệu.
  • Nghiên cứu thuật toán tìm điểm bất động chung cho nửa nhóm không giãn (nonexpansive semigroups) hoặc các họ toán tử không giãn suy rộng trên không gian Banach.
  • Phát triển các thuật toán song song hóa và tối ưu hóa thời gian thực thi cho các bài toán cân bằng cỡ lớn trong thực tiễn.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên ngành hữu ích cho các đối tượng sau:

  • Nghiên cứu sinh và học viên cao học ngành Toán giải tích, Toán ứng dụng, Tối ưu hóa: Cung cấp hệ thống lý thuyết chuẩn mực về giải tích lồi, phép chiếu metric, lý thuyết toán tử không giãn và phương pháp chứng minh sự hội tụ mạnh/yếu của các dãy lặp trong không gian Hilbert.
  • Giảng viên và nhà nghiên cứu trong lĩnh vực giải tích biến phân: Có thể tham khảo trực tiếp các kỹ thuật kỹ thuật:
    • Sơ đồ thay thế bài toán cân bằng phụ bằng hai bài toán lồi mạnh tại Chương 2.
    • Kỹ thuật chiếu lai ghép không cần giả thiết bị chặn tại Chương 3.
    • Kỹ thuật tìm kiếm theo tia kiểu Armijo loại bỏ điều kiện Lipschitz tại Chương 4.
  • Chuyên gia mô hình hóa trong kinh tế toán và lý thuyết trò chơi: Cung cấp cơ sở thuật toán số để tìm điểm cân bằng Nash và giải quyết các bài toán xung đột lợi ích đa chủ thể.

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

1. Luận án giải quyết khó khăn gì của các phương pháp tìm nghiệm cân bằng trước đây?

Trước đây, hầu hết các thuật toán tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động đều đòi hỏi tại mỗi bước lặp phải giải một bài toán cân bằng phụ. Quá trình này phức tạp và thông thường chỉ tìm được nghiệm xấp xỉ, dẫn đến việc không đảm bảo dãy lặp sẽ hội tụ về nghiệm cần tìm. Luận án giải quyết khó khăn này bằng hai hướng: (1) thay thế bài toán cân bằng phụ bằng hai bài toán tối ưu lồi mạnh có lời giải chính xác (Chương 2); (2) sử dụng kỹ thuật tìm kiếm theo tia kiểu Armijo kết hợp phép chiếu siêu phẳng (Chương 4).

2. Sự khác biệt giữa tính đơn điệu và tính giả đơn điệu của song hàm trong luận án là gì?

Song hàm $f$ được gọi là đơn điệu trên $C$ nếu $f(x, y) + f(y, x) \le 0, \forall x, y \in C$. Trong khi đó, $f$ được gọi là giả đơn điệu trên $C$ nếu với mọi $x, y \in C$, điều kiện $f(x, y) \ge 0$ suy ra $f(y, x) \le 0$. Giả đơn điệu là lớp tính chất tổng quát hơn (đơn điệu suy rộng), làm giảm bớt yêu cầu khắt khe của tính đơn điệu thông thường nhưng làm tăng đáng kể độ phức tạp khi phân tích sự hội tụ toán học.

3. Phương pháp tìm kiếm theo tia ở Chương 4 có ưu điểm gì nổi bật so với các chương trước?

Ưu điểm nổi bật nhất của phương pháp tìm kiếm theo tia kiểu Armijo ở Chương 4 là loại bỏ hoàn toàn điều kiện liên tục kiểu Lipschitz của song hàm $f$ — một điều kiện rất mạnh và khó kiểm tra trong thực tế. Thuật toán tự điều chỉnh độ dài bước lặp thông qua quy tắc tìm kiếm Armijo và sử dụng siêu phẳng phân tách để chiếu, giúp cấu trúc thuật toán đơn giản và áp dụng được cho lớp bài toán tổng quát hơn.

4. Kết quả thực nghiệm tính toán số trong luận án được thực hiện với cấu hình và dữ liệu nào?

Thực nghiệm số được trình bày ở Mục 2.4 (Chương 2), giải bài toán cân bằng trên $\mathbb{R}^3$ với tập ràng buộc lồi đa diện $C$ và song hàm dạng toàn phương $f(x, y) = \langle Ax + By + q, y - x \rangle$ có hằng số Lipschitz $c_1 = c_2 = 1.4$. Chương trình chạy trên Matlab R2010b, máy tính Intel Core i3-2330M CPU @ 2.20GHz, 2GB RAM. Với điểm xuất phát $x_0 = (3, 2, 4)^T$, thuật toán đạt $\epsilon$-nghiệm xấp xỉ sau 13 bước lặp (thời gian 0.55 giây); với $x_0 = (5, 2, 3)^T$, thuật toán hoàn thành sau 11 bước lặp (thời gian 0.45 giây).

Kết luận

Luận án tiến sĩ của tác giả Đỗ Duy Thành đã nghiên cứu và phát triển thành công các phương pháp lặp mới để tìm nghiệm chung của bài toán cân bằng giả đơn điệu, bài toán điểm bất động của ánh xạ không giãn và bài toán bất đẳng thức biến phân trên không gian Hilbert thực. Công trình đóng góp các giải pháp kỹ thuật quan trọng như thay thế bài toán cân bằng phụ bằng các bài toán tối ưu lồi mạnh, ứng dụng kỹ thuật chiếu lai ghép để đạt hội tụ mạnh không cần điều kiện bị chặn, và sử dụng tìm kiếm theo tia kiểu Armijo nhằm loại bỏ giả thiết liên tục Lipschitz của song hàm. Các định lý hội tụ mạnh, hội tụ yếu cùng kết quả tính toán mô phỏng trên Matlab đã khẳng định tính đúng đắn lý thuyết và giá trị ứng dụng thực tiễn của các thuật toán đề xuất.