Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Một số phương pháp giải bài toán cân bằng trên tập điểm bất động" được thực hiện bởi nghiên cứu sinh Nguyễn Văn Hồng, dưới sự hướng dẫn khoa học của PGS. Phạm Ngọc Anh và GS. Lê Dũng Mưu. Công trình thuộc chuyên ngành Toán ứng dụng, mã số 9 46 01 12, được bảo vệ tại Trường Đại học Thăng Long vào năm 2024.

Tính cấp thiết của luận án bắt nguồn từ vị trí trung tâm của bài toán cân bằng (Equilibrium Problem - ký hiệu là $EP(C, f)$) và bài toán điểm bất động (Fixed Point Problem) trong lý thuyết tối ưu, giải tích phi tuyến và toán học ứng dụng. Xét không gian Hilbert thực $H$, tập con lồi, đóng, khác rỗng $C \subseteq H$, và song hàm cân bằng $f: C \times C \to \mathbb{R} \cup {+\infty}$ thỏa mãn $f(x, x) = 0$ với mọi $x \in C$. Bài toán cân bằng tìm điểm $x^* \in C$ sao cho $f(x^*, y) \ge 0$ với mọi $y \in C$. Dạng bài toán này bao hàm nhiều mô hình toán học quan trọng như bài toán tối ưu, bài toán điểm yên ngựa, bài toán bất đẳng thức biến phân, bài toán điểm bất động và bài toán cân bằng kinh tế Nash. Trong khi đó, lý thuyết điểm bất động cho các họ ánh xạ không giãn, ánh xạ nửa co hay giả co chặt đóng vai trò then chốt trong việc xác định nghiệm của các hệ phương trình toán tử phi tuyến.

Giao thoa giữa hai hướng nghiên cứu này là bài toán cân bằng trên tập điểm bất động (ký hiệu là $FEP(\Omega, f)$), được phát biểu dưới dạng: Tìm $x^* \in \Omega$ sao cho $f(x^*, y) \ge 0, \forall y \in \Omega$, trong đó miền ràng buộc $\Omega = \bigcap_{i \in I} Fix(S_i)$ là giao của tập các điểm bất động $Fix(S_i) = {x \in C : S_i(x) = x}$ của một họ các ánh xạ $S_i: C \to C$ ($i \in I \subseteq \mathbb{N}$) nửa co.

Khoảng trống nghiên cứu được tác giả chỉ ra xuất phát từ ba hạn chế căn bản của các công trình hiện có:

  1. Thứ nhất, nhiều thuật toán đã đề xuất chưa giải quyết được hiệu quả bài toán trên máy tính. Điển hình như ở mỗi bước lặp của các phương pháp hiệu chỉnh (regularization), người thực hiện buộc phải tìm nghiệm chính xác của một bài toán cân bằng phụ, điều này rất tốn kém tài nguyên tính toán.
  2. Thứ hai, các nghiên cứu trước đây chủ yếu tập trung vào trường hợp miền ràng buộc $\Omega$ là tập điểm bất động của một ánh xạ đơn lẻ. Bài toán giải trên miền ràng buộc là giao của một họ các tập điểm bất động của các ánh xạ giả co chặt hoặc nửa co vẫn là một hướng nghiên cứu mở.
  3. Thứ ba, sự hội tụ của nhiều thuật toán hiện hữu đòi hỏi các giả thiết rất chặt đặt lên song hàm $f$, chẳng hạn như tính đơn điệu mạnh trên toàn không gian hoặc các điều kiện hội tụ dãy phức tạp. Ngoài ra, do bài toán cân bằng và bài toán điểm bất động có thể có vô số nghiệm, chúng thuộc lớp bài toán đặt không chỉnh (ill-posed), nghĩa là một sai số nhỏ của dữ liệu đầu vào có thể dẫn tới sai số lớn của lời giải.

Mục tiêu nghiên cứu của luận án được xác định cụ thể gồm 4 nội dung:

  1. Nghiên cứu đề xuất thuật toán chiếu mới giải bài toán cân bằng trên tập điểm bất động.
  2. Nghiên cứu cải biên phương pháp dưới đạo hàm quán tính; nguyên lý bài toán phụ quán tính song song.
  3. Nghiên cứu đề xuất phương pháp chiếu xấp xỉ song song giải bài toán cân bằng trên giao của tập nghiệm một họ các bài toán điểm bất động và bài toán cân bằng.
  4. Tính toán ứng dụng với các ví dụ cụ thể trong không gian vô hạn chiều và hữu hạn chiều, so sánh hiệu năng tính toán với một số thuật toán đã được công bố của các tác giả khác.

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

  • Đối tượng nghiên cứu: Bài toán cân bằng xác định bởi song hàm $f$ trên tập ràng buộc $\Omega$ là giao của tập điểm bất động của họ các ánh xạ nửa co, cũng như trên giao của họ tập điểm bất động với tập nghiệm của bài toán cân bằng hoặc bài toán bất đẳng thức biến phân đa trị.
  • Phạm vi nghiên cứu: Luận án tập trung xây dựng cơ sở lý thuyết giải tích trong không gian Hilbert thực $H$ (bao gồm cả không gian hữu hạn chiều $\mathbb{R}^n$ và không gian vô hạn chiều); thiết lập điều kiện hội tụ mạnh của các dãy lặp; thực nghiệm số trên máy tính bằng ngôn ngữ lập trình tính toán trong không gian $\mathbb{R}^5$ với các số liệu cụ thể.

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

Luận án đã tổng quan một cách hệ thống lịch sử hình thành và phát triển của bài toán cân bằng và lý thuyết điểm bất động:

  • Khởi đầu của bài toán cân bằng bắt nguồn từ công trình năm 1955 của Nikaido H. [60] khi nghiên cứu tổng quát hóa mô hình cân bằng Nash trong lý thuyết trò chơi không hợp tác.
  • Năm 1972, Fan K. thiết lập sự tồn tại nghiệm của bài toán dưới tên gọi bất đẳng thức minimax, với giả thiết tập ràng buộc $C$ là tập lồi compact và song hàm $f(x, \cdot)$ tựa lồi với mọi $x \in H$. Kết quả này sau đó được Brezis H. và các đồng nghiệp mở rộng vào năm 1972 [22].
  • Năm 1992, Muu L. D. (Lê Dũng Mưu) và Oettli W. [57] chính thức sử dụng thuật ngữ "bài toán cân bằng" (equilibrium problem) và đề xuất thuật toán hàm phạt tìm nghiệm khi song hàm $f$ đơn điệu.
  • Năm 1994, Blum E. và Oettli W. [21] công bố công trình nghiên cứu hệ thống về bài toán cân bằng, tạo tiền đề thu hút sự quan tâm của nhiều nhà toán học như Bigi G. và các nhóm nghiên cứu quốc tế.

Về lý thuyết điểm bất động:

  • Lịch sử ghi nhận hai mốc nền tảng là định lý điểm bất động Brouwer (1912) cho ánh xạ liên tục trên tập compact và nguyên lý ánh xạ co Banach (1922) cho ánh xạ co trên không gian metric đầy đủ.
  • Đến những năm 1960 của thế kỷ 20, các hướng mở rộng nguyên lý ánh xạ co phát triển mạnh theo hai nhánh: mở rộng sang ánh xạ không giãn, ánh xạ nửa co, ánh xạ giả co bởi các tác giả như Cegielski A. cho ánh xạ đơn trị; và mở rộng sang ánh xạ đa trị bởi Caristi C.

Về bài toán cân bằng trên tập điểm bất động $FEP(\Omega, f)$:

  • Hướng nghiên cứu định tính: Tập trung vào sự tồn tại nghiệm, cấu trúc tập nghiệm và tính ổn định nghiệm, tiêu biểu là các công trình của Bianchi M., Schaible S. [18, 19, 20], Iusem A. N., Kassay G. [47], và Mastroeni G. [56].
  • Hướng nghiên cứu định lượng và phương pháp giải: Nghiên cứu các phương pháp lặp và tính chất hội tụ của các dãy lặp qua các công trình của Anh P. N. (Phạm Ngọc Anh) [4, 6, 7, 10, 14], Ceng L. C. [24], Hieu D. V. [43], Iusem A. N. [46], Muu L. D. [58, 59], Peng J. W. [61, 62], Santos P. S. M., Scheimberg N. [66], Strodiot J. P., Nguyen V. H. [68], và Yamada I. [75].
  • Hướng nghiên cứu ứng dụng: Ứng dụng bài toán vào các mô hình kinh tế, bài toán cân bằng thị trường, dòng giao thông, được phân tích trong các tài liệu [9, 15, 45, 58, 59].

Vị trí của luận án: Kế thừa phương pháp xấp xỉ chiếu dưới đạo hàm (IPSM) của Santos P. S. M. và Scheimberg N. (2011) [66], kỹ thuật hướng giảm lai ghép của Yamada I. (2001) [75], lược đồ lặp điểm bất động của Mann W. (1953) [51], cùng các kỹ thuật tính toán song song và nguyên lý bài toán phụ của Phạm Ngọc Anh [10, 14], luận án định vị lời giải cho bài toán $FEP(\Omega, f)$ bằng cách:

  1. Thay thế việc giải chính xác bài toán cân bằng phụ ở mỗi bước bằng một bước tính xấp xỉ dưới đạo hàm trực tiếp hoặc phép chiếu xấp xỉ ngoài.
  2. Xử lý ràng buộc giao của một họ hữu hạn các tập điểm bất động $\Omega = \bigcap_{i \in I} Fix(S_i)$ bằng cơ chế tính toán song song kết hợp toán tử lấy chỉ số cực đại $\operatorname{argmax}$, giảm khối lượng tính toán tuần tự.
  3. Tích hợp số hạng ngoại suy quán tính (inertial extrapolation) nhằm cải thiện tốc độ hội tụ của các thuật toán lặp giải bài toán cân bằng trong không gian Hilbert.

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

Cơ sở lý thuyết và các khái niệm toán học

Luận án vận dụng hệ thống giải tích hàm và giải tích lồi trong không gian Hilbert thực $H$:

  • Dãy ${u_k} \subset H$ hội tụ mạnh tới $u^$ ($u_k \to u^$) nếu $|u_k - u^| \to 0$; hội tụ yếu ($u_k \rightharpoonup u^$) nếu $\langle u, u_k - u^* \rangle \to 0, \forall u \in H$. Không gian $H$ thỏa mãn tính chất Kadec-Klee: nếu $u_k \rightharpoonup u^$ và $|u_k| \to |u^|$ thì $u_k \to u^*$.
  • Nón pháp tuyến ngoài của tập lồi đóng $C$ tại $x_0 \in C$ là $N_C(x_0) = {\omega \in H : \langle \omega, x - x_0 \rangle \le 0, \forall x \in C}$; nón pháp tuyến xấp xỉ ngoài cấp $\epsilon$ là $N_C^\epsilon(x_0) = {\omega \in H : \langle \omega, x - x_0 \rangle \le \epsilon, \forall x \in C}$.
  • Hàm $\varphi: C \to \mathbb{R} \cup {+\infty}$ được gọi là lồi mạnh với hằng số $\tau > 0$ nếu $\varphi(\alpha x + (1-\alpha)y) \le \alpha \varphi(x) + (1-\alpha)\varphi(y) - \frac{1}{2}\alpha(1-\alpha)\tau |x - y|^2$ với mọi $x, y \in C, \alpha \in [0, 1]$.
  • Dưới vi phân của hàm $f$ tại $x$ là tập $\partial f(x) = {w \in H : f(y) - f(x) \ge \langle w, y - x \rangle, \forall y \in H}$. Dưới vi phân cấp $\epsilon$ tại $x_0$ ký hiệu là $\partial_\epsilon f(x_0) = {w \in H : \langle w, x - x_0 \rangle \le f(x) - f(x_0) + \epsilon, \forall x \in H}$. Dưới vi phân chéo cấp $\epsilon$ theo biến thứ hai của song hàm $f$ tại điểm chéo $(x, x)$ được định nghĩa: $$\partial_{2,\epsilon} f(x, x) = {w \in H : f(x, y) + \epsilon \ge \langle w, y - x \rangle, \forall y \in H}$$
  • Ánh xạ $S: C \to C$ được gọi là $d$-nửa co ($d$-half-contractive) nếu $Fix(S) \neq \emptyset$ và tồn tại $d \in [0, 1)$ sao cho $|S(x) - x^|^2 \le |x - x^|^2 + d|x - S(x)|^2, \forall x \in C, x^* \in Fix(S)$. Ánh xạ $F: C \to H$ là giả co chặt nếu tồn tại $L > 0$ sao cho $|F(x) - F(y)|^2 \le |x - y|^2 + L|(I - F)x - (I - F)y|^2$. Khi $L = 0$, $F$ là ánh xạ không giãn.
  • Họ ánh xạ ${S_i}$ thỏa mãn điều kiện (Z) nếu với mọi dãy bị chặn ${x_k}$ mà $\lim_{k \to \infty} |x_k - S_i(x_k)| = 0$ với mọi $i$, thì mọi điểm tụ yếu của ${x_k}$ đều thuộc $\Omega = \bigcap_{i \in I} Fix(S_i)$.
  • Song hàm $f$ được gọi là:
    • $\beta$-đơn điệu mạnh trên $C$ nếu $f(x, y) + f(y, x) \le -\beta |x - y|^2, \forall x, y \in C$.
    • Thỏa mãn điều kiện kiểu Lipschitz trên $C$ nếu tồn tại $c_1, c_2 > 0$ sao cho $f(x, y) + f(y, z) \ge f(x, z) - c_1|x - y|^2 - c_2|y - z|^2, \forall x, y, z \in C$.
  • Phép chiếu metric $Pr_C(x) = \operatorname{argmin}{|y - x|^2 : y \in C}$. Phép chiếu xấp xỉ cấp $\epsilon$ trên $C$, ký hiệu $w_x \in Pr_C^\epsilon(x)$, được xác định qua bất đẳng thức: $\langle x - w_x, w_x - y \rangle \ge -\frac{\epsilon^2}{4}, \forall y \in C$.

Mối liên hệ giữa $EP(C, f)$ và các bài toán liên quan

Luận án trình bày dạng quy đổi tường minh của các bài toán tối ưu và biến phân về bài toán cân bằng:

Bài toán gốc Ký hiệu Định nghĩa bài toán Song hàm cân bằng $f(x, y)$ tương đương
Bài toán Tối ưu $OP(C, h)$ Tìm $x^* \in C: h(x^*) \le h(x), \forall x \in C$ $f(x, y) = h(y) - h(x)$ nếu $x, y \in C$; $+ \infty$ nếu ngược lại
Bài toán Cân bằng đối ngẫu (Minty) $EP^d(C, f)$ Tìm $x^* \in C: f(y, x^*) \le 0, \forall y \in C$ Quan hệ đối ngẫu trực tiếp với $EP(C, f)$
Bất đẳng thức biến phân đơn trị $VI(C, F)$ Tìm $x^* \in C: \langle F(x^), x - x^ \rangle \ge 0, \forall x \in C$ $f(x, y) = \langle F(x), y - x \rangle$ nếu $x, y \in C$; $-1$ nếu ngược lại
Bất đẳng thức biến phân đa trị $MVI(C, F)$ Tìm $x^* \in C, u^* \in F(x^): \langle u^, x - x^* \rangle \ge 0, \forall x \in C$ $f(x, y) = \max_{u \in F(x)} \langle u, y - x \rangle$
Điểm bất động Brouwer $FP(C, F)$ Tìm $x^* \in C: x^* = F(x^*)$ $f(x, y) = \langle x - F(x), y - x \rangle$
Mô hình cân bằng thị trường Nash Nash Model $\max_{x_i \in C_i} f_i(x_1^, \dots, x_i, \dots, x_N^)$ Hàm Nikaido-Isoda: $\Phi(x, y) = \sum_{i=1}^N [f_i(x) - f_i(x[y_i])]$

Phương pháp nghiên cứu thực tế

Luận án sử dụng phương pháp nghiên cứu lý thuyết giải tích kết hợp mô phỏng số:

  1. Phương pháp phân tích giải tích: Xây dựng các đánh giá bất đẳng thức biến phân, sử dụng kỹ thuật ước lượng khoảng cách Hausdorff đối với tập dưới vi phân, khai thác tính chất tựa không giãn của các toán tử chiếu và toán tử nửa co để chứng minh sự hội tụ mạnh của dãy lặp trong không gian Hilbert.
  2. Phương pháp lặp tối ưu: Kết hợp phương pháp chiếu song song, kỹ thuật lặp Mann, lược đồ hướng giảm lai ghép Yamada, và kỹ thuật ngoại suy quán tính.
  3. Phương pháp thực nghiệm tính toán: Thiết lập các bài toán kiểm nghiệm trong không gian $\mathbb{R}^5$ với các ma trận thực ngẫu nhiên có cấu trúc; lập trình thuật toán trên phần mềm tính toán khoa học, đo lường số bước lặp (Iter.) và thời gian chạy CPU (CPU-times).
  4. Công cụ và nền tảng tính toán: Toàn bộ các thử nghiệm số được lập trình và chạy trên phần mềm MATLAB R2016a, cài đặt trên máy vi tính để bàn trang bị bộ vi xử lý Intel(R) Core(TM) i9-9900KS CPU @ 4.00GHz.

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

Chương 1. Một số kiến thức cơ bản về bài toán cân bằng và điểm bất động

Chương 1 đóng vai trò cung cấp khung kiến thức bổ trợ, định nghĩa toán học và tổng quan các thuật toán kinh điển. Chương được kết cấu thành ba nội dung chính:

  • Mục 1.1 trình bày giải tích hàm trong không gian Hilbert thực: các đẳng thức chuẩn, tích vô hướng, khái niệm tập lồi, tập affine, nón pháp tuyến ngoài, hàm lồi mạnh, dưới vi phân, dưới vi phân cấp $\epsilon$, phép chiếu metric và phép chiếu xấp xỉ.
  • Mục 1.2 giới thiệu bài toán cân bằng $EP(C, f)$, bài toán cân bằng đối ngẫu Minty $EP^d(C, f)$, định lý Ky Fan về sự tồn tại nghiệm khi $C$ compact lồi và $f(x, \cdot)$ tựa lồi. Khẳng định tính lồi đóng của tập nghiệm $S(C, f)$ và tính duy nhất nghiệm khi song hàm $f$ đơn điệu chặt.
  • Mục 1.3 phát biểu bài toán cân bằng trên tập điểm bất động $FEP(\Omega, f)$ với miền ràng buộc $\Omega = \bigcap_{i \in I} Fix(S_i)$, trong đó các ánh xạ $S_i$ là $\beta_i$-nửa co. Mục này điểm lại hai thuật toán thông dụng:
    • Thuật toán kiểu dưới đạo hàm kết hợp giữa phương pháp hướng giảm lai ghép Yamada và lược đồ Iusem (Định lý 1.4): Dãy lặp xác định bởi $y^k \in K_k := {x \in \mathbb{R}^n : |x| \le \rho_k + 1}$ thỏa mãn $f(y^k, x_k) \ge 0$, $\xi^k \in \partial f(y^k, \cdot)(x_k)$, $x_{k+1} = T(x_k - \lambda_k f(y^k, x_k)\xi^k)$, với bước lặp $\lambda_k \in [a, b] \subset (0, 2/M^2)$.
    • Thuật toán nguyên lý bài toán phụ của Phạm Ngọc Anh (2021) giải bài toán cân bằng trên tập nghiệm của bài toán bất đẳng thức biến phân đa trị và điểm bất động chung $\bigcap_{i=1}^r Fix(S_i) \cap \Omega$, sử dụng toán tử tiệm cận $\operatorname{prox}_{\lambda_k g}$, bước chiếu và tìm kiếm song song qua chỉ số $j_k \in \operatorname{argmax}{|u_j^k - z^k| : j \in I}$.

Chương 2. Một số phương pháp chiếu mở rộng

Chương 2 trình bày các thuật toán chiếu mới giải bài toán $FEP(\Omega, f)$ trong không gian Hilbert thực $H$, thiết lập dựa trên các công trình công bố [CT1, CT4] của tác giả.

1. Phương pháp chiếu song song xấp xỉ (Thuật toán 2.1)

Thuật toán được xây dựng nhằm giải bài toán khi song hàm $f$ là $\beta$-đơn điệu mạnh và ánh xạ dưới vi phân chéo $x \mapsto \partial_{2,\epsilon} f(x, x)$ liên tục Lipschitz theo khoảng cách Hausdorff với hằng số $L > 0$ trên $C$ thỏa mãn $\beta \le L$.

Các bước của Thuật toán 2.1:

  • Khởi tạo: Chọn điểm bất kỳ $x_0 \in C$. Các dãy tham số thỏa mãn: $$\tau \in (0, \beta), \quad 0 < \tau_k \le \gamma_k < \min\left{\frac{2\beta}{L^2}, \frac{2(\beta-\tau)}{L^2-\tau^2}, \frac{1}{\tau}\right}$$ $$0 < a \le \alpha_{k,i} < \min\left{\frac{1-\beta_i}{2} : i \in I\right}, \quad \epsilon_k \le \gamma_k, \quad \sum_{k=0}^\infty \epsilon_k^2 < +\infty, \quad \sum_{k=0}^\infty \gamma_k = +\infty, \quad \sum_{k=0}^\infty \gamma_k^2 < +\infty$$
  • Bước 1 (Tính toán song song): Với mỗi $i \in I$, tính: $$y_i^k = (1 - \alpha_{k,i})x_k + \alpha_{k,i} S_i(x_k)$$ Chọn phần tử có độ lệch lớn nhất: $y^k := y_{i_0}^k$ với $i_0 \in \operatorname{argmax}{|y_i^k - x_k| : i \in I}$.
  • Bước 2 (Chiếu xấp xỉ dưới đạo hàm): Chọn $u_k \in \partial_{2,\tau_k} f(y^k, y^k)$ và tính: $$x_{k+1} \in Pr_{C_k}^{\epsilon_k}(y^k - \gamma_k u_k)$$ Đặt $k := k + 1$ và quay lại Bước 1.

Cơ sở lý thuyết quan trọng của phương pháp này là Bổ đề 2.1: Ánh xạ đa trị $S(x) := {x - \gamma w_x : w_x \in \partial_{2,\epsilon} g(x, x)}$ là ánh xạ $2\sqrt{\epsilon\gamma}$-co với hệ số co $\delta = \sqrt{1 - \gamma(2\beta - \gamma L^2)} \in (0, 1)$ trên $C$ khi $\gamma \in (0, 2\beta/L^2)$.

Định lý 2.1 chứng minh rằng các dãy ${x_k}$ và ${y^k}$ sinh bởi Thuật toán 2.1 hội tụ mạnh về nghiệm duy nhất $x^*$ của bài toán. Luận án chỉ ra rằng khi các ánh xạ $S_i$ là ánh xạ đồng nhất ($S_i = I$), Thuật toán 2.1 quy về phương pháp IPSM của Santos và Scheimberg (2011), chứng minh tính mở rộng của lược đồ đề xuất.

2. Phương pháp dưới đạo hàm song song (Thuật toán 2.2)

Xét bài toán trong trường hợp toàn bộ không gian $C = H$. Thuật toán 2.2 kết hợp phép lặp Mann và phương pháp dưới đạo hàm song song:

  • Bước 1: Tính toán song song các véc tơ $y_i^k$ và xác định $y^k = y_{i_0}^k$ tương tự Thuật toán 2.1.
  • Bước 2: Chọn $u_k \in \partial_{2,\tau_k} f(y^k, y^k)$ và cập nhật nghiệm lặp không cần dùng phép chiếu lên tập lồi: $$x_{k+1} = \beta_k x_k + (1 - \beta_k) y^k - \mu \gamma_k u_k$$ Định lý 2.2 khẳng định dãy lặp ${x_k}$ hội tụ mạnh tới nghiệm duy nhất $x^* \in \Omega$ trong không gian $H$.

3. Ví dụ minh họa và kết quả tính toán thực nghiệm (Mục 2.3)

Tác giả thiết lập bài toán kiểm nghiệm trong không gian hữu hạn chiều $\mathbb{R}^5$:

  • Ràng buộc $C \subset \mathbb{R}^5$ là đa giác lồi.
  • Hai ánh xạ phi tuyến $S_1, S_2: \mathbb{R}^5 \to \mathbb{R}^5$ được xác định cụ thể: $$S_1(x) = \left(\frac{1}{3}x_1, \sin x_2, \frac{1}{3}x_3, x_4, \sin^3 x_5\right)$$ $$S_2(x) = \left(x_1, \frac{1}{2}x_2, \sin x_3, \sin^2 x_4, \frac{1}{4}x_5\right)$$
  • Song hàm cân bằng $f(x, y) = \langle F(x) + Qy + q, y - x \rangle$, với ma trận $Q = AA^T + B + D$, trong đó $A$ là ma trận vuông, $B$ là ma trận phản xứng ($B^T = -B$), $D$ là ma trận đường chéo dương, và vectơ $q \in \mathbb{R}^5$.
  • Ánh xạ $F: \mathbb{R}^5 \to \mathbb{R}^5$ được xác định với tham số $\eta > 1 + |Q|$: $$F(x) = (\eta x_1 + \eta x_2 + \sin x_1, -\eta x_1 + \eta x_2 + \sin x_2, (\eta - 1)x_3, (\eta - 1)x_4, (\eta - 1)x_5)$$ Tác giả chứng minh chặt chẽ $F$ là ánh xạ liên tục Lipschitz với hằng số $L = \sqrt{2(2\eta^2 + 2\eta + 1)}$ và $(\eta - 1)$-đơn điệu mạnh trên $\mathbb{R}^5$. Khi đó song hàm $f$ đơn điệu mạnh với hằng số $(\eta - |Q| - 1)$. Dưới vi phân đường chéo của $f$ là điểm duy nhất: $\partial_2 f(x, x) = {F(x) + Qx + q}$.

Dữ liệu ma trận và vectơ thực nghiệm được cho trong văn bản như sau: $$A = \begin{pmatrix} -2 & 1 & 0 & 1 & -1 \ 1 & 2 & 1 & 0 & 2 \ 0 & 1 & 3 & 1 & 2 \ 0 & 1 & 3 & 1 & 0 \ 2 & 0 & 1 & -1 & 3 \end{pmatrix}, \quad B = \begin{pmatrix} 0 & 1 & 2 & 1 & -1 \ -1 & 3 & 2 & 0 & 2 \ -2 & -2 & 1 & 1 & -3 \ -1 & 0 & -1 & 1 & 0 \ 1 & -2 & 3 & 0 & 2 \end{pmatrix}$$ $$D = \begin{pmatrix} 5 & 0 & 0 & 0 & 0 \ 0 & 3 & 0 & 0 & 0 \ 0 & 0 & 12 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 \end{pmatrix}, \quad q = \begin{pmatrix} 2 \ 3 \ -4 \ 0 \ 0 \end{pmatrix}$$

4. Phương pháp chiếu đạo hàm tăng cường song song (Mục 2.4)

Mục này trình bày Thuật toán 2.4, phát triển ý tưởng từ phương pháp đạo hàm tăng cường của Phạm Ngọc Anh (2011) [4]. Thuật toán kết hợp phép lặp Mann và kỹ thuật chiếu song song nhằm tăng hiệu quả tính toán. Định lý hội tụ mạnh và các kết quả tính toán so sánh thực nghiệm được tác giả trình bày chi tiết ở cuối chương.

Chương 3. Phương pháp dưới đạo hàm quán tính

Chương 3 đề xuất hai thuật toán lặp mới giải bài toán $FEP(\Omega, f)$ trong không gian Hilbert $H$, tích hợp kỹ thuật ngoại suy quán tính để tăng tốc độ lặp, dựa trên hai bài báo [CT2, CT3]:

1. Phương pháp dưới đạo hàm quán tính (Mục 3.1)

  • Thuật toán 3.1 kết hợp kỹ thuật hướng giảm lai ghép của Yamada, phương pháp dưới đạo hàm giải bài toán cân bằng và kỹ thuật lặp điểm bất động của ánh xạ không giãn.
  • Tại mỗi bước lặp, thuật toán bổ sung số hạng quán tính có dạng $\theta_k (x_k - x_{k-1})$ vào điểm lặp trước khi thực hiện bước tính dưới đạo hàm.
  • Định lý 3.1 chứng minh dãy lặp sinh bởi thuật toán hội tụ mạnh về nghiệm duy nhất của bài toán dưới giả thiết song hàm $f$ đơn điệu mạnh (hoặc giả đơn điệu mạnh) và liên tục kiểu Lipschitz trên $H$. Các tính toán thực nghiệm minh họa tính hội tụ được thể hiện ở Mục 3.1.2.

2. Nguyên lý bài toán phụ quán tính song song (Mục 3.2)

  • Thuật toán 3.2 là sự kết hợp giữa ba kỹ thuật: kỹ thuật ngoại suy quán tính, phép chiếu song song lên các tập thành phần, và nguyên lý bài toán phụ (auxiliary problem principle) để giải bài toán cân bằng.
  • Điểm lặp trung gian được tạo ra từ tổ hợp quán tính, sau đó giải một bài toán tối ưu phụ trợ có dạng lồi mạnh thay vì phải giải trực tiếp bài toán cân bằng ban đầu.
  • Định lý 3.2 thiết lập điều kiện trên các tham số điều chỉnh và chứng minh dãy lặp hội tụ mạnh trong không gian Hilbert. Các kết quả tính toán số so sánh được thể hiện ở Mục 3.2.2.

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

Các kết quả và đóng góp mới của luận án được tổng hợp từ phần tự công bố của tác giả:

  1. Đóng góp về lý thuyết phương pháp chiếu song song: Đề xuất hai thuật toán mới (Thuật toán 2.1 và Thuật toán 2.2) giải bài toán cân bằng trên tập điểm bất động trong không gian Hilbert thực $H$ với giả thiết song hàm $f$ đơn điệu mạnh và có tập dưới vi phân xấp xỉ liên tục Lipschitz theo khoảng cách Hausdorff. Các thuật toán này mở rộng trực tiếp phương pháp IPSM của Santos và Scheimberg từ ràng buộc một ánh xạ đơn lẻ sang họ các ánh xạ nửa co, giải quyết bài toán bằng kỹ thuật song song kết hợp toán tử cực đại $\operatorname{argmax}$.
  2. Đóng góp về kỹ thuật dưới đạo hàm quán tính: Đề xuất hai thuật toán lặp mới trong Chương 3 kết hợp kỹ thuật ngoại suy quán tính, phép chiếu song song và nguyên lý bài toán phụ giải bài toán cân bằng trên giao của các tập điểm bất động của họ ánh xạ nửa co.
  3. Chứng minh toán học về sự hội tụ mạnh: Toàn bộ 4 thuật toán chính (Định lý 2.1, 2.2, 3.1, 3.2) đều được chứng minh đạt sự hội tụ mạnh (strong convergence) trong không gian Hilbert thực $H$, khắc phục nhược điểm chỉ đạt hội tụ yếu của nhiều phương pháp chiếu truyền thống.
  4. Đóng góp về mặt tính toán thực nghiệm: Luận án đã lập trình và thực thi các thử nghiệm số trên phần mềm MATLAB R2016a (trên phần cứng máy tính CPU Intel Core i9-9900KS @ 4.00GHz) cho các ví dụ trong không gian hữu hạn chiều ($\mathbb{R}^5$) và vô hạn chiều. Kết quả thực nghiệm cung cấp các dữ liệu so sánh cụ thể về số bước lặp (Iter.) và thời gian CPU (CPU-times), minh chứng khả năng giải được của các thuật toán đề xuất trên máy tính.
  5. Công bố khoa học: Các kết quả nghiên cứu trong luận án được công bố qua 04 bài báo khoa học, bao gồm:
    • 01 bài báo xuất bản trên tạp chí quốc tế thuộc danh mục SCI.
    • 02 bài báo xuất bản trên tạp chí quốc tế thuộc danh mục SCIE.
    • 01 bài báo gửi đăng trên tạp chí quốc tế thuộc danh mục SCIE.
    • Các kết quả đã được báo cáo và thảo luận tại 04 hội nghị, hội thảo chuyên ngành toán học trong nước và quốc tế (Hội thảo tại Viện Nghiên cứu cao cấp về Toán VIASM năm 2021; Hội nghị quốc tế ISAS 2022 tại ĐH Bách khoa TP.HCM; Hội thảo Tối ưu và Tính toán Khoa học lần thứ 21 năm 2023 tại Ba Vì; Hội nghị Toán học toàn quốc lần thứ X năm 2023 tại Đà Nẵng).

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

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

  • Điều kiện áp đặt lên dữ liệu đầu vào còn chặt: Thuật toán yêu cầu song hàm $f$ phải thỏa mãn tính đơn điệu mạnh (hoặc giả đơn điệu mạnh), đồng thời toán tử dưới vi phân đường chéo $\partial_2 f(x, x)$ phải thỏa mãn tính liên tục Lipschitz theo khoảng cách Hausdorff trên tập ràng buộc $C$.
  • Yêu cầu về tham số: Các điều kiện ràng buộc đối với các bước lặp và tham số điều chỉnh ($\tau_k, \gamma_k, \alpha_{k,i}, \beta_k, \epsilon_k$) khá phức tạp, đòi hỏi phải thỏa mãn đồng thời nhiều bất đẳng thức và chuỗi số hội tụ/phân kỳ.

Hướng nghiên cứu tiếp theo (trang 89 của luận án):

  • Nghiên cứu cải tiến các thuật toán lặp để giải bài toán cân bằng trên tập điểm bất động dưới các giả thiết yếu hơn đặt lên song hàm $f$, như giả thiết đơn điệu, giả đơn điệu thông thường thay vì đơn điệu mạnh.
  • Mở rộng lớp ánh xạ của tập ràng buộc $\Omega$ từ ánh xạ nửa co sang các lớp ánh xạ suy rộng khác (chẳng hạn ánh xạ tựa giả co chặt, ánh xạ không giãn suy rộng).
  • Nghiên cứu phát triển các thuật toán giải bài toán cân bằng hai cấp (Bilevel Equilibrium Problems - BEP) hoặc bài toán cân bằng đa trị xác định trên tập điểm bất động.
  • Mở rộng việc áp dụng các thuật toán vào giải quyết các bài toán thực tế quy mô lớn, đặc biệt là các mô hình cân bằng thị trường kinh tế phức tạp.

Giá trị tham khảo

Luận án mang lại giá trị tham khảo học thuật cho các nhóm đối tượng:

  • Giảng viên, nghiên cứu sinh và học viên cao học chuyên ngành Toán ứng dụng, Lý thuyết tối ưu và Giải tích phi tuyến: Có thể tham khảo kỹ thuật chứng minh tính co của ánh xạ đa trị dưới vi phân chéo (Bổ đề 2.1), phương pháp phân tích hội tụ mạnh kết hợp bổ đề Maingé, và kỹ thuật kết hợp số hạng quán tính với bài toán phụ.
  • Các nhà nghiên cứu về giải thuật tính toán và tính toán khoa học: Tham khảo lược đồ thuật toán song song hóa qua bước chọn $i_0 \in \operatorname{argmax}{|y_i^k - x_k| : i \in I}$ giúp giảm tải tính toán tuần tự khi xử lý bài toán tối ưu trên giao của nhiều tập ràng buộc.
  • Các nhà nghiên cứu mô hình hóa kinh tế và kỹ thuật: Mô hình chuyển đổi từ bài toán cân bằng thị trường Nash thông qua hàm Nikaido-Isoda (trình bày ở Mục 1.2) và ví dụ xây dựng song hàm từ ma trận phản xứng và ma trận đường chéo (Mục 2.3) cung cấp phương pháp tham khảo trực tiếp để thiết lập và giải các mô hình thực nghiệm.

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

1. Bài toán cân bằng trên tập điểm bất động $FEP(\Omega, f)$ được phát biểu như thế nào trong luận án?

Bài toán được phát biểu như sau: Tìm vectơ $x^* \in \Omega$ sao cho $f(x^*, y) \ge 0$ với mọi $y \in \Omega$, trong đó miền ràng buộc $\Omega = \bigcap_{i \in I} Fix(S_i)$ là giao của các tập điểm bất động $Fix(S_i) = {x \in C : S_i(x) = x}$ của một họ các ánh xạ $S_i: C \to C$ ($i \in I = {1, 2, \dots, p}$) là các ánh xạ $\beta_i$-nửa co trong không gian Hilbert thực $H$.

2. Ý nghĩa của kỹ thuật lựa chọn chỉ số cực đại $i_0 \in \operatorname{argmax}{|y_i^k - x_k| : i \in I}$ trong các thuật toán song song là gì?

Kỹ thuật này cho phép tính toán độc lập và song song các điểm lặp trung gian $y_i^k = (1 - \alpha_{k,i})x_k + \alpha_{k,i} S_i(x_k)$ ứng với từng ánh xạ $S_i$. Việc chọn ra chỉ số $i_0$ có khoảng cách $|y_i^k - x_k|$ lớn nhất giúp thuật toán tập trung hiệu chỉnh tại hướng có sai số vi phạm ràng buộc điểm bất động lớn nhất tại bước lặp đó, đảm bảo dãy lặp tiến về điểm bất động chung của toàn bộ họ ánh xạ mà không cần chiếu tuần tự qua từng tập.

3. Trong ví dụ kiểm nghiệm ở Mục 2.3, song hàm $f$ và ánh xạ $F$ được xây dựng ra sao trong không gian $\mathbb{R}^5$?

Song hàm có dạng $f(x, y) = \langle F(x) + Qy + q, y - x \rangle$ với $Q = AA^T + B + D$, trong đó $B$ là ma trận phản xứng cấp $5 \times 5$, $D$ là ma trận đường chéo có các phần tử $(5, 3, 12, 0, 0)$, vectơ $q = (2, 3, -4, 0, 0)^T$. Ánh xạ $F(x) = (\eta x_1 + \eta x_2 + \sin x_1, -\eta x_1 + \eta x_2 + \sin x_2, (\eta-1)x_3, (\eta-1)x_4, (\eta-1)x_5)$ với $\eta > 1 + |Q|$. Ánh xạ này được chứng minh là liên tục Lipschitz với hằng số $L = \sqrt{2(2\eta^2 + 2\eta + 1)}$ và $(\eta-1)$-đơn điệu mạnh.

4. Thuật toán 2.1 của luận án mở rộng kết quả nghiên cứu nào đã có trước đây?

Thuật toán 2.1 mở rộng phương pháp xấp xỉ chiếu dưới đạo hàm (IPSM) của Santos P. S. M. và Scheimberg N. (2011). Trong trường hợp họ ánh xạ $S_i$ quy về ánh xạ đồng nhất ($S_i = I, \forall i$), tập ràng buộc $\Omega$ trùng với tập lồi $C$, và dãy lặp của Thuật toán 2.1 trở thành lược đồ giải bài toán cân bằng thông thường trên tập lồi theo phương pháp IPSM.

5. Môi trường phần mềm và cấu hình phần cứng nào được sử dụng để thực hiện các tính toán thực nghiệm trong luận án?

Các chương trình tính toán số được lập trình và chạy bằng phần mềm MATLAB phiên bản R2016a. Môi trường phần cứng thực thi là máy vi tính cá nhân sử dụng bộ vi xử lý Intel(R) Core(TM) i9-9900KS CPU @ 4.00GHz.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Văn Hồng đã giải quyết bài toán cân bằng trên tập điểm bất động thông qua việc đề xuất các phương pháp chiếu mở rộng, phương pháp dưới đạo hàm song song và phương pháp dưới đạo hàm quán tính. Các thuật toán đề xuất khắc phục được hạn chế phải giải bài toán phụ chính xác tại mỗi bước lặp và mở rộng miền ràng buộc sang giao của một họ các ánh xạ nửa co trong không gian Hilbert. Toàn bộ các định lý hội tụ mạnh đều được chứng minh toán học và được kiểm chứng bằng thực nghiệm số trên phần mềm tính toán với số liệu cụ thể.