Tổng quan luận án

Luận án tiến sĩ toán học của nghiên cứu sinh Nguyễn Thị Thanh Huyền, với đề tài "Một số phương pháp giải bài toán chấp nhận tách suy rộng liên quan đến bài toán cân bằng", được thực hiện dưới sự hướng dẫn khoa học của GS. Lê Dũng Mưu tại Trường Đại học Sư phạm – Đại học Thái Nguyên (năm 2020), thuộc chuyên ngành Toán Giải tích, mã số 946 01 02. Luận án tập trung giải quyết bài toán chấp nhận tách suy rộng trong các trường hợp tập ràng buộc được cho dưới dạng ẩn và toán tử chuyển có tính chất phi tuyến.

Về tính cấp thiết và khoảng trống nghiên cứu, bài toán cân bằng (Equilibrium Problem - EP, còn gọi là bất đẳng thức Ky Fan) là một mô hình toán học tổng quát bao hàm nhiều lớp bài toán quan trọng như bài toán tối ưu hóa, bài toán bất đẳng thức biến phân, bài toán điểm bất động Kakutani, bài toán bù, bài toán tối ưu Pareto yếu và bài toán cân bằng Nash trong lý thuyết trò chơi không hợp tác. Do tính chất bao hàm rộng và độ phức tạp cao, việc tìm nghiệm của bài toán cân bằng tổng quát không thể thực hiện bằng một thuật toán vạn năng duy nhất mà đòi hỏi các giả thiết cấu trúc cụ thể (như tính đơn điệu, giả đơn điệu hoặc lồi). Bên cạnh đó, bài toán chấp nhận tách (Split Feasibility Problem - SFP), được Y. Censor và T. Elfving đề xuất năm 1994 trong mô hình bài toán ngược, đã được ứng dụng trong xử lý tín hiệu, khôi phục hình ảnh y tế và điều khiển cường độ xạ trị ung thư. Tuy nhiên, phần lớn các phương pháp giải SFP trước đây đều dựa trên hai giả định cơ bản: toán tử chuyển $A$ là toán tử tuyến tính và các tập lồi $C, Q$ được cho tường minh. Khi các tập ràng buộc $C$ hoặc $Q$ được cho dưới dạng tập nghiệm của bài toán cân bằng hoặc bài toán tối ưu lồi (bài toán chấp nhận tách suy rộng), các phương pháp chiếu cổ điển gặp khó khăn do không thể tính trực tiếp phép chiếu lên các tập nghiệm ẩn này. Đồng thời, đối với bài toán chấp nhận tách phi tuyến, các công trình trước đây (tiêu biểu như nghiên cứu của Li và cộng sự) buộc phải đưa ra giả thiết ngặt nghèo về tính lồi của hàm khoảng cách để bảo đảm sự hội tụ của thuật toán. Do đó, việc xây dựng các thuật toán giải bài toán chấp nhận tách suy rộng khi tập ràng buộc là tập nghiệm của bài toán cân bằng và khi toán tử chuyển là phi tuyến là một yêu cầu khoa học cần được giải quyết.

Mục tiêu nghiên cứu của luận án bao gồm:

  1. Xây dựng thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii để giải bài toán chấp nhận tách suy rộng trong trường hợp tập ràng buộc $C$ là tập nghiệm của bài toán cân bằng và tập $Q$ là tập nghiệm của bài toán tối ưu lồi, với toán tử chuyển tuyến tính.
  2. Chứng minh sự hội tụ mạnh của dãy lặp sinh bởi thuật toán đề xuất dưới điều kiện song hàm cân bằng thỏa mãn tính chất para-đơn điệu (paramonotone).
  3. Xây dựng thuật toán dưới đạo hàm giải bài toán chấp nhận tách phi tuyến với toán tử chuyển là phép biến đổi tựa tuyến tính dựa trên kỹ thuật tối ưu hàm tựa lồi và dưới đạo hàm Clarke, chứng minh sự hội tụ mà không cần giả thiết tính lồi của hàm khoảng cách.
  4. Ứng dụng các thuật toán đã đề xuất vào các mô hình thực tế, bao gồm mô hình cân bằng bán độc quyền Nash-Cournot trong sản xuất điện có tính đến chi phí môi trường và mô hình cân bằng Nash có ràng buộc chung.

Đối tượng nghiên cứu của luận án là bài toán chấp nhận tách suy rộng, bài toán cân bằng, bài toán tối ưu lồi, toán tử gần kề, hàm tựa tuyến tính và các dãy lặp số học. Phạm vi nghiên cứu được xác định trong không gian vectơ Euclid thực hữu hạn chiều $\mathbb{R}^n$ và $\mathbb{R}^m$, xét trên các tập lồi đóng, khác rỗng, lớp song hàm para-đơn điệu và các phép biến đổi tựa tuyến tính.

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

Tổng quan tài liệu trong luận án hệ thống hóa các mốc phát triển chính của lý thuyết bài toán cân bằng và bài toán chấp nhận tách:

  • Về bài toán cân bằng: Bất đẳng thức cân bằng được H. Isoda sử dụng lần đầu tiên vào năm 1955 trong nghiên cứu trò chơi không hợp tác. Năm 1972, Ky Fan gọi đây là bất đẳng thức minimax và thiết lập các kết quả cơ bản về sự tồn tại nghiệm. Thuật ngữ "bài toán cân bằng" chính thức được E. Blum và W. Oettli giới thiệu trong công trình công bố năm 1994. Lý thuyết bài toán cân bằng sau đó được G. Bigi và các cộng sự tổng hợp trong chuyên khảo xuất bản năm 2019, đồng thời được mở rộng sang cân bằng vectơ và cân bằng tập bởi nhiều tác giả.
  • Về các phương pháp giải bài toán cân bằng: Các hướng tiếp cận cơ bản được điểm lại gồm:
    • Phương pháp điểm bất động dựa trên nguyên lý bài toán phụ: Khởi xướng bởi G. Cohen (năm 1980 cho bài toán tối ưu và năm 1988 cho bất đẳng thức biến phân), được G. Mastroeni mở rộng cho bài toán cân bằng năm 2003 bằng việc sử dụng hàm khoảng cách Bregman; kỹ thuật sử dụng ánh xạ nghiệm không giãn (khi song hàm tự bức) hoặc ánh xạ tựa không giãn (khi song hàm giả đơn điệu); phương pháp hiệu chỉnh gần kề định nghĩa ánh xạ Combettes.
    • Phương pháp hàm đánh giá (gap function): Sử dụng hàm đánh giá Auslender, hàm đánh giá Fukushima, hàm đánh giá Minty (cho bài toán đối ngẫu) và hàm D-gap không ràng buộc để quy việc giải bài toán cân bằng về bài toán tối ưu hóa tương đương, được khảo sát bởi G. Quoc.
    • Phương pháp hiệu chỉnh Tikhonov và phương pháp điểm gần kề: Áp dụng cho các bài toán đặt không chỉnh, sử dụng song hàm hiệu chỉnh để bảo đảm tính duy nhất nghiệm và nghiên cứu quỹ đạo nghiệm qua kỹ thuật tối ưu hai cấp.
    • Phương pháp đạo hàm và đạo hàm tăng cường (extragradient method): Đề xuất bởi A. S. Antipin với khoảng cách Bregman trên tập lồi compact, được Langenberg mở rộng cho tập không bị chặn, và tiếp tục được phát triển trong các luận án tiến sĩ của Bùi Văn Định, Trịnh Ngọc Hải, Phạm Gia Hưng với kỹ thuật chiếu lên siêu phẳng hoặc tách song hàm.
  • Về bài toán chấp nhận tách: Y. Censor và T. Elfving giới thiệu năm 1994 cho mô hình bài toán ngược. C. Byrne ứng dụng năm 2002 trong phục hồi và tái tạo hình ảnh y tế. Y. Censor ứng dụng năm 2006 trong điều khiển cường độ xạ trị ung thư. Các thuật toán chiếu giải bài toán chấp nhận tách dựa trên ý tưởng phương pháp chiếu của C. Cimmino và S. Kaczmarz; trường hợp tập ràng buộc là tập điểm bất động hoặc nghiệm của bất đẳng thức biến phân được tổng hợp trong luận án của Trần Việt Anh. Về hướng chuyển SFP về bài toán tối ưu lồi, A. Moudafi và B. S. Thakur (năm 2013) sử dụng hàm mục tiêu khoảng cách $\frac{1}{2\lambda}|(I - P_Q)(Ax)|^2$. Đối với toán tử chuyển phi tuyến, Li và các cộng sự đã xét bài toán chấp nhận tách nhưng phải phụ thuộc vào giả thiết hàm khoảng cách là hàm lồi.
  • Về hàm tựa lồi và song hàm para-đơn điệu: Khái niệm hàm tựa lồi được B. De Finetti giới thiệu năm 1949. Lớp song hàm para-đơn điệu được nghiên cứu và ứng dụng bởi A. N. Iusem, Scheimberg và các cộng sự.
Hướng tiếp cận trước đây Tác giả, công trình tiêu biểu Đặc điểm và phạm vi áp dụng Hạn chế mà luận án nhận diện
Phương pháp đạo hàm tăng cường cho bài toán cân bằng A. S. Antipin; Langenberg; Bùi Văn Định; Trịnh Ngọc Hải Yêu cầu giải hai bài toán tối ưu phụ hoặc thực hiện hai phép chiếu ở mỗi bước lặp Khối lượng tính toán lớn; khó kết hợp trực tiếp khi giải bài toán chấp nhận tách
Phương pháp tối ưu giải bài toán chấp nhận tách A. Moudafi; B. S. Thakur (2013) Cực tiểu hóa hàm khoảng cách mêtric; áp dụng cho toán tử chuyển tuyến tính $A$ Hàm mục tiêu chỉ lồi và khả vi khi $A$ là tuyến tính; không áp dụng được khi $A$ phi tuyến
Bài toán chấp nhận tách phi tuyến Li và cộng sự Xét toán tử chuyển phi tuyến với $C, Q$ là giao của hữu hạn tập lồi Bắt buộc phải giả thiết tính lồi của hàm khoảng cách $|P_Q(F(x)) - F(x)|^2$
Thuật toán chiếu giải bài toán cân bằng giả đơn điệu P. Scheimberg và cộng sự Sử dụng phép chiếu một lần với bước dịch chuyển dưới đạo hàm Chưa tích hợp để giải bài toán chấp nhận tách có ràng buộc thứ hai là bài toán tối ưu

Vị trí của luận án: Luận án định vị nghiên cứu vào hai khoảng trống cụ thể: (1) thiết lập thuật toán chiếu một lần kết hợp phép lặp Mann-Krasnoselskii thông qua toán tử gần kề để giải bài toán chấp nhận tách khi $C$ là tập nghiệm bài toán cân bằng para-đơn điệu và $Q$ là tập nghiệm bài toán tối ưu lồi; (2) thiết lập thuật toán dưới đạo hàm Clarke cho bài toán chấp nhận tách với toán tử chuyển phi tuyến tựa tuyến tính mà không cần giả thiết về tính lồi của hàm khoảng cách.

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

Luận án xây dựng trên nền tảng giải tích lồi, giải tích biến phân và lý thuyết tối ưu hóa:

  • Không gian và mêtric: Không gian Euclid thực $\mathbb{R}^n$ với tích vô hướng $\langle x, y \rangle = \sum_{i=1}^n x_i y_i$ và chuẩn Euclid $|x| = \sqrt{\langle x, x \rangle}$. Tập con $K \subset \mathbb{R}^n$ là tập lồi nếu $\alpha x + (1-\alpha)y \in K$ với mọi $x, y \in K, \alpha \in [0, 1]$.
  • Phép chiếu mêtric và nón pháp tuyến: Cho $K$ là tập lồi đóng khác rỗng, phép chiếu $P_K(x) = \arg\min_{z \in K} |z - x|$ tồn tại duy nhất và thỏa mãn:
    • $\langle x - P_K(x), y - P_K(x) \rangle \le 0, \forall y \in K$;
    • $\langle x - y, P_K(x) - P_K(y) \rangle \ge |P_K(x) - P_K(y)|^2, \forall x, y \in \mathbb{R}^n$;
    • $|x - P_K(x)|^2 \le |x - y|^2 - |y - P_K(x)|^2, \forall y \in K$. Nón pháp tuyến ngoài của $K$ tại $x_0$ là $N_K(x_0) = {w \in \mathbb{R}^n : \langle w, y - x_0 \rangle \le 0, \forall y \in K}$.
  • Giải tích dưới vi phân: Với hàm lồi chính thường $f: \mathbb{R}^n \to (-\infty, +\infty]$, dưới vi phân tại $x_0$ là tập $\partial f(x_0) = {p \in \mathbb{R}^n : \langle p, x - x_0 \rangle + f(x_0) \le f(x), \forall x \in \mathbb{R}^n}$. Với $\varepsilon > 0$, $\varepsilon$-dưới vi phân là $\partial^\varepsilon f(x_0) = {p \in \mathbb{R}^n : \langle p, x - x_0 \rangle + f(x_0) - \varepsilon \le f(x), \forall x \in \mathbb{R}^n}$. Điều kiện cần và đủ cho điểm cực tiểu của hàm lồi trên tập lồi đóng $K$ là $0 \in \partial f(x^) + N_K(x^)$.
  • Hàm tựa lồi và tựa tuyến tính: Hàm $\phi: X \to \mathbb{R}$ ($X$ lồi) là tựa lồi nếu tập mức dưới $S_{\phi, \alpha} = {x \in X : \phi(x) \le \alpha}$ là tập lồi với mọi $\alpha \in \mathbb{R}$; là tựa lõm nếu $-\phi$ là tựa lồi; là tựa tuyến tính nếu vừa tựa lồi vừa tựa lõm, tương đương với $\min{\phi(x_1), \phi(x_2)} \le \phi(\lambda x_1 + (1-\lambda)x_2) \le \max{\phi(x_1), \phi(x_2)}$ với mọi $x_1, x_2 \in X, \lambda \in [0, 1]$.
  • Tính đơn điệu của song hàm: Cho song hàm $f: K \times K \to \mathbb{R}$ thỏa mãn $f(x, x) = 0$. Song hàm $f$ được gọi là:
    • Đơn điệu mạnh với hằng số $\tau > 0$ nếu $f(x, y) + f(y, x) \le -\tau |x - y|^2$;
    • Đơn điệu chặt nếu $f(x, y) + f(y, x) < 0$ với mọi $x \ne y$;
    • Đơn điệu trên $K$ đối với $S$ nếu $f(x, y) + f(y, x) \le 0, \forall x \in S, y \in K$;
    • Giả đơn điệu trên $K$ đối với $S$ nếu $f(x, y) \ge 0 \Rightarrow f(y, x) \le 0, \forall x \in S, y \in K$;
    • Para-đơn điệu (paramonotone) trên $K$ đối với $S$ nếu $f$ đơn điệu và với $x \in S, y \in K$ thỏa mãn $f(x, y) = f(y, x) = 0$ thì suy ra $y \in S$.
  • Các bài toán quy về bài toán cân bằng: Luận án trình bày sự tương đương của $EP(K, f)$ với: bài toán tối ưu lồi (với $f(x, y) = \phi(y) - \phi(x)$); bài toán điểm yên ngựa; bài toán cân bằng Nash; bài toán điểm bất động ($f(x, y) = \langle x - Tx, y - x \rangle$); bài toán bất đẳng thức biến phân và bài toán bù ($f(x, y) = \langle F(x), y - x \rangle$); bài toán tối ưu Pareto yếu ($f(x, y) = \max_{1 \le i \le m} [\psi_i(y) - \psi_i(x)]$).
  • Toán tử gần kề (proximal operator): Cho hàm lồi chính thường nửa liên tục dưới $g$ và $\lambda > 0$, toán tử $\text{prox}{\lambda g}(u) = \arg\min{v \in \mathbb{R}^m} {g(v) + \frac{1}{2\lambda}|v - u|^2}$ là ánh xạ đơn trị và xác định trên toàn không gian.
  • Các phương pháp lặp điểm bất động cơ bản: Nguyên lý ánh xạ co Banach (lặp Picard), lặp Mann ($x_{n+1} = (1 - \alpha_n)x_n + \alpha_n T x_n$), lặp Krasnoselskii ($x_{n+1} = \frac{1}{2}(x_n + T x_n)$), và lặp Mann-Krasnoselskii ($x_{n+1} = (1 - \alpha_n)x_n + \alpha_n T x_n$ với $\alpha_n \in (0, 1)$).

Phương pháp nghiên cứu thực tế của luận án là phương pháp toán học thuần túy kết hợp mô phỏng giải tích số:

  • Thiết kế thuật toán lặp giải tích dựa trên phép chiếu mêtric, xấp xỉ dưới đạo hàm và toán tử gần kề.
  • Kỹ thuật chứng minh giải tích toán học: Đánh giá chặn trên khoảng cách mêtric qua các bổ đề dãy số thực không âm và phân tích chuỗi hội tụ.
  • Dữ liệu và thực nghiệm: Các mô hình toán kinh tế (Cournot-Nash trong thị trường điện và cân bằng Nash có ràng buộc chung) được thiết lập với các hệ số ma trận và hàm số cụ thể để chạy thử nghiệm tính toán số, kiểm tra tính khả thi và tốc độ hội tụ của thuật toán.

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

Chương 1: Một số kiến thức chuẩn bị

Chương 1 (từ trang 12 đến trang 25) gồm 5 phần chính, hệ thống hóa toàn bộ công cụ toán học được sử dụng trong các chương sau:

  • Mục 1.1 trình bày các khái niệm và kết quả cơ bản của giải tích lồi trong không gian $\mathbb{R}^n$: định nghĩa tập lồi, phép chiếu mêtric $P_K$, các bất đẳng thức đặc trưng của phép chiếu; nón pháp tuyến ngoài $N_K(x_0)$; miền hữu hiệu $\text{dom} f$, trên đồ thị $\text{epi} f$, hàm lồi, hàm lõm, dưới vi phân $\partial f(x_0)$, $\varepsilon$-dưới vi phân $\partial^\varepsilon f(x_0)$; hàm tựa lồi, tựa lõm, tựa tuyến tính (theo De Finetti); các ví dụ về hàm tựa tuyến tính như hàm $\log x$ trên $\mathbb{R}_{++}$ và hàm phân thức bậc nhất $(a^T x + b)/(c^T x + d)$; hàm nửa liên tục dưới và nửa liên tục trên; các khái niệm về tính đơn điệu của song hàm (đơn điệu mạnh, đơn điệu chặt, đơn điệu, giả đơn điệu, para-đơn điệu).
  • Mục 1.2 trình bày phát biểu bài toán cân bằng $EP(K, f)$ và chứng minh các mệnh đề đưa các bài toán quen thuộc về bài toán cân bằng: bài toán tối ưu, bài toán điểm yên ngựa, bài toán cân bằng Nash, bài toán điểm bất động, bài toán bất đẳng thức biến phân, bài toán bù và bài toán tối ưu Pareto yếu. Đồng thời, trình bày mệnh đề về tính duy nhất nghiệm của bài toán cân bằng khi song hàm đơn điệu mạnh.
  • Mục 1.3 giới thiệu bài toán chấp nhận tách (SFP) dạng tìm $x^* \in C$ sao cho $Ax^* \in Q$, phân tích tập nghiệm $\Gamma = C \cap A^{-1}Q$ và mối liên hệ quy bài toán chấp nhận tách về bài toán chấp nhận lồi (CFP).
  • Mục 1.4 trình bày các phương pháp lặp cơ bản tìm điểm bất động của ánh xạ không giãn: nguyên lý ánh xạ co Banach, phương pháp lặp Mann, phương pháp lặp Krasnoselskii và phương pháp lặp Mann-Krasnoselskii.
  • Mục 1.5 đưa ra điều kiện cần và đủ cho điểm cực tiểu của bài toán tối ưu ($0 \in \partial f(x^) + N_K(x^)$) và ba bổ đề bổ trợ quan trọng phục vụ chứng minh sự hội tụ:
    • Bổ đề 1.1: Bất đẳng thức chuẩn kết hợp lồi $|ax + (1-a)y - z|^2 \le a|x - z|^2 + (1-a)|y - z|^2$ với $a \in [0, 1]$.
    • Bổ đề 1.2: Dãy số thực không âm ${v_k}$ thỏa mãn $v_{k+1} \le v_k + \delta_k$ với $\sum_{k=1}^\infty \delta_k < +\infty$ thì ${v_k}$ hội tụ.
    • Bổ đề 1.3: Cho dãy ${a_k} \subset (a, b) \subset (0, 1)$ và hai dãy ${v_k}, {w_k}$ thỏa mãn $\limsup_{k \to \infty} |v_k| \le c$, $\limsup_{k \to \infty} |w_k| \le c$ và $\lim_{k \to \infty} |a_k v_k + (1-a_k)w_k| = c$ ($c > 0$), thì $\lim_{k \to \infty} |v_k - w_k| = 0$.

Chương 2: Thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii giải bài toán chấp nhận tách

Chương 2 (từ trang 26 đến trang 43) trình bày thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii để giải bài toán chấp nhận tách liên quan đến bài toán cân bằng và bài toán quy hoạch lồi (bài toán SEO): Tìm $x^* \in K$ sao cho: $$f(x^, y) \ge 0, \forall y \in K \quad \text{và} \quad g(Ax^) \le g(u), \forall u \in \mathbb{R}^m$$ trong đó $K \subset \mathbb{R}^n$ là tập lồi đóng, $A: \mathbb{R}^n \to \mathbb{R}^m$ là toán tử tuyến tính, $g: \mathbb{R}^m \to \mathbb{R}$ là hàm lồi chính thường nửa liên tục dưới.

Hàm mục tiêu phụ trợ được xác định qua toán tử gần kề: $$h(x) := \frac{1}{2}|(I - \text{prox}{\lambda g})Ax|^2$$ với đạo hàm tương ứng là $\nabla h(x) = A^*(I - \text{prox}{\lambda g})Ax$. Điểm $x$ thỏa mãn $h(x) = 0$ khi và chỉ khi $Ax$ là nghiệm của bài toán cực tiểu hóa hàm $g$ trên $\mathbb{R}^m$.

Các giả thiết hội tụ của bài toán bao gồm:

  • (A1) Với mỗi $x \in K$, $f(x, x) = 0$ và $f(x, \cdot)$ lồi, nửa liên tục dưới trên $K$.
  • (A2) $\partial_{2\varepsilon} f(x, x)$ bị chặn trên mỗi tập con bị chặn bất kỳ của $K$.
  • (A3) $f$ là song hàm para-đơn điệu trên $K$ đối với tập nghiệm $S(K, f)$ và $f(\cdot, x)$ nửa liên tục trên trên $K$.
  • (A4) Tập nghiệm $S$ của bài toán (SEO) khác rỗng.

Cấu trúc Thuật toán 2.1:

  • Chọn tham số $\delta, \xi > 0$, các dãy số thực ${a_k}, {\delta_k}, {\beta_k}, {\varepsilon_k}, {\rho_k}$ thỏa mãn: $0 < a < a_k < b < 1$; $0 < \xi \le \rho_k \le 4 - \xi$; $\sum_{k=1}^\infty \beta_k < +\infty$; $\sum_{k=1}^\infty \varepsilon_k < +\infty$; $\sum_{k=1}^\infty \frac{\beta_k}{\delta_k} = +\infty$; $\sum_{k=1}^\infty \frac{\beta_k \varepsilon_k}{\delta_k} < +\infty$; $\sum_{k=1}^\infty \beta_k^2 < +\infty$.
  • Bước 0: Chọn $x_1 \in K$, đặt $k := 1$.
  • Bước $k$: Có $x_k \in K$, lấy $g_k \in \partial_{2\varepsilon_k} f(x_k, x_k)$, tính bước dịch chuyển $\alpha_k = \frac{\beta_k}{\gamma_k}$ với $\gamma_k = \max{\delta_k, |g_k|}$.
    • Tính điểm chiếu một lần: $y_k = P_K(x_k - \alpha_k g_k)$, tức là điểm thỏa mãn $\langle y_k - x_k + \alpha_k g_k, x - y_k \rangle \ge 0, \forall x \in K$.
    • Xác định điểm lặp trung gian $z_k$:
      • Nếu $\nabla h(y_k) \ne 0$: $z_k = y_k - \rho_k \frac{h(y_k)}{|\nabla h(y_k)|^2} \nabla h(y_k)$.
      • Nếu $\nabla h(y_k) = 0$: $z_k = y_k$.
    • Tính điểm lặp tiếp theo theo cơ chế Mann-Krasnoselskii: $x_{k+1} = a_k x_k + (1 - a_k)z_k$.
    • Đặt $k := k + 1$ và lặp lại.

Định lý 2.1 chứng minh sự hội tụ mạnh của dãy ${x_k}$ sinh bởi Thuật toán 2.1 về nghiệm $x^* \in S$ thông qua 5 khẳng định logic:

  1. Dãy số thực ${|x_k - z|^2}$ hội tụ với mọi nghiệm $z \in S$, kéo theo các dãy ${x_k}$ và ${y_k}$ đều bị chặn.
  2. $\limsup_{k \to \infty} f(x_k, z) = 0$ với mỗi $z \in S$.
  3. Điểm tụ $x^$ của dãy con ${x_{k_j}}$ thỏa mãn $\lim_{j \to \infty} f(x_{k_j}, z) = \limsup_{k \to \infty} f(x_k, z)$ là một nghiệm của bài toán cân bằng ($x^ \in S(K, f)$) nhờ tính chất song hàm para-đơn điệu.
  4. Mọi điểm tụ $\bar{x}$ của dãy ${x_k}$ đều thỏa mãn $\bar{x} \in K$ và $A\bar{x} \in \arg\min_{y \in \mathbb{R}^m} g(y)$, do $h(y_k) \to 0$ và tính nửa liên tục dưới của $h$.
  5. Dãy hình chiếu ${P_S(x_{k_j})}$ là một dãy Cauchy trong không gian Euclid, dẫn tới $\lim_{k \to \infty} x_k = \lim_{k \to \infty} y_k = \lim_{k \to \infty} P_S(x_k) = x^* \in S$.

Ví dụ 2.5 trong chương chỉ ra tính xác đáng của giả thiết nghiệm: khi bài toán không có nghiệm ($S = K \cap Q = \emptyset$, với $K = {(u, v) \in \mathbb{R}^2 : u \ge 1, v \ge 1/u}$ và $Q = {(u, v) \in \mathbb{R}^2 : u \ge 1, v = 0}$), dãy lặp sinh bởi thuật toán không bị chặn, cụ thể tọa độ thứ nhất phân kỳ tới vô hạn: $\lim_{k \to \infty} u_k = +\infty$.

Mục 2.2 xây dựng ứng dụng cho mô hình cân bằng bán độc quyền Nash-Cournot trong sản xuất điện với chi phí môi trường thấp nhất (SEP). Mô hình xét $n$ nhà máy điện, nhà máy thứ $i$ có tập máy phát điện $I_i$, tổng số máy phát là $N$, sản lượng là véctơ $x = (x_1, \dots, x_N)$. Giá bán điện phụ thuộc hàm tổng sản lượng $s = \sum_{j=1}^N x_j$ theo hàm affin giảm $p_i(s) = \alpha - \beta_i s$. Hàm lợi nhuận của nhà máy $i$ là $f_i(x) = p_i(s)(\sum_{j \in I_i} x_j) - \sum_{j \in I_i} c_j(x_j)$, với $c_j$ là hàm chi phí sản xuất lồi tăng. Ma trận $A = (a_{l, j})$ biểu diễn định mức nguyên vật liệu $l$ ($l = 1, \dots, m$) cho một đơn vị điện của máy phát $j$. Toàn bộ phí môi trường do phát thải được mô tả bởi hàm lồi tăng $g(Ax)$. Bài toán tìm điểm cân bằng Nash tối đa hóa lợi nhuận đồng thời cực tiểu hóa phí phát thải môi trường được đưa về bài toán (SEP) và giải bằng Thuật toán 2.1.

Chương 3: Thuật toán dưới đạo hàm giải bài toán chấp nhận tách phi tuyến và ứng dụng cho mô hình cân bằng Nash có ràng buộc

Chương 3 (từ trang 44 đến trang 69) giải quyết bài toán chấp nhận tách phi tuyến (Nonlinear Split Feasibility Problem - NSEP) trong trường hợp toán tử chuyển là một phép biến đổi cấu thành từ các hàm số tựa tuyến tính:

  • Mô tả bài toán: Tìm $x^* \in C$ sao cho $F(x^*) \in Q$, trong đó $F: \mathbb{R}^n \to \mathbb{R}^m$ không phải là toán tử tuyến tính mà là toán tử phi tuyến được xác định bởi các thành phần $F(x) = (\phi_1(x), \dots, \phi_m(x))^T$ với $\phi_i$ là các hàm tựa tuyến tính trên tập lồi $C$.
  • Thiết kế thuật toán và phân tích sự hội tụ: Do $F$ phi tuyến, hàm khoảng cách mêtric không còn bảo toàn tính lồi, khiến các phương pháp đạo hàm thông thường không áp dụng được. Luận án đề xuất thuật toán dưới đạo hàm dựa trên việc sử dụng dưới vi phân Clarke cho bài toán tối ưu tựa lồi. Thuật toán sử dụng hướng giảm dưới đạo hàm kết hợp phép chiếu lên tập ràng buộc $C$. Sự hội tụ của dãy lặp được chứng minh chặt chẽ dựa trên các đặc trưng của hàm tựa lồi và nón pháp tuyến mà không cần đặt điều kiện lồi nhân tạo lên hàm khoảng cách mêtric như các công trình của Li và cộng sự.
  • Mô hình ứng dụng: Cuối chương giới thiệu mô hình cân bằng Nash với các ràng buộc chung (generalized Nash equilibrium model) nảy sinh trong kinh tế và quản lý kỹ thuật, trong đó chiến lược của mỗi người chơi bị chi phối bởi hành vi của các đối thủ qua các ràng buộc liên kết. Bài toán được chuyển hóa thành dạng bài toán chấp nhận tách phi tuyến tựa tuyến tính, được lập trình tính toán thử nghiệm trên máy tính và so sánh kết quả số với thuật toán đã công bố trước đó, khẳng định tính đúng đắn và khả thi của phương pháp.

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

Các đóng góp mới về mặt lý luận khoa học của luận án bao gồm:

  1. Xây dựng thuật toán chiếu một lần kết hợp kỹ thuật lặp Mann-Krasnoselskii thông qua toán tử gần kề để giải bài toán chấp nhận tách suy rộng (SEO) khi một tập ràng buộc là tập nghiệm của bài toán cân bằng và tập ràng buộc còn lại là tập nghiệm của bài toán tối ưu lồi. Thuật toán chỉ yêu cầu tính một phép chiếu lên tập ràng buộc ở mỗi bước lặp, giảm khối lượng tính toán so với các thuật toán dạng đạo hàm tăng cường (extragradient) hai phép chiếu.
  2. Thiết lập và chứng minh định lý hội tụ mạnh của dãy lặp trong Thuật toán 2.1 về một nghiệm của bài toán chấp nhận tách suy rộng dưới điều kiện song hàm cân bằng là para-đơn điệu, mở rộng phạm vi áp dụng so với các kết quả giả đơn điệu hoặc đơn điệu chặt truyền thống.
  3. Thiết lập thuật toán dưới đạo hàm giải bài toán chấp nhận tách phi tuyến khi toán tử chuyển được xác định bởi các hàm tựa tuyến tính. Đóng góp lý luận quan trọng ở đây là giải quyết được sự hội tụ của thuật toán bằng giải tích tựa lồi và dưới đạo hàm Clarke, loại bỏ hoàn toàn giả thiết nhân tạo về tính lồi của hàm khoảng cách mêtric mà các nghiên cứu trước đây (như công trình của Li và cộng sự) bắt buộc phải sử dụng.

Các đóng góp về mặt thực tiễn và ứng dụng:

  1. Mô hình hóa thành công bài toán cân bằng bán độc quyền Nash-Cournot của các nhà máy sản xuất điện có ràng buộc giảm thiểu chi phí phát thải môi trường thành bài toán chấp nhận tách suy rộng (SEP), cung cấp công cụ toán học hỗ trợ phân tích cân bằng thị trường năng lượng gắn với bài toán chi phí ngoại ứng môi trường.
  2. Ứng dụng thuật toán chấp nhận tách phi tuyến để giải mô hình cân bằng Nash có ràng buộc chung, tiến hành thử nghiệm số trên máy tính và đối chiếu hiệu quả tính toán với thuật toán có sẵn.

Các kết quả chính của luận án đã được công bố trong 2 công trình khoa học trên các tạp chí quốc tế thuộc danh mục ISI:

  • Bài báo trên tạp chí Mathematical Methods of Operations Research;
  • Bài báo trên tạp chí Journal of Global Optimization.

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

Về hạn chế, luận án xác định các phạm vi lý thuyết sau:

  • Không gian khảo sát hoàn toàn giới hạn trong không gian vectơ Euclid thực hữu hạn chiều ($\mathbb{R}^n$ và $\mathbb{R}^m$), chưa mở rộng sang không gian vô hạn chiều (như không gian Hilbert hay không gian Banach).
  • Trong Chương 2, sự hội tụ mạnh của thuật toán đòi hỏi song hàm cân bằng phải thỏa mãn tính chất para-đơn điệu và các điều kiện chính quy (A1)-(A4); chưa khảo sát trường hợp song hàm hoàn toàn không đơn điệu hoặc không thỏa mãn tính chất tự bức/para-đơn điệu.
  • Trong Chương 3, thuật toán dưới đạo hàm mới chỉ áp dụng cho toán tử chuyển cấu thành từ các hàm tựa tuyến tính; trường hợp toán tử phi tuyến tổng quát tùy ý chưa được giải quyết.
  • Luận án tập trung vào việc chứng minh sự hội tụ tiệm cận của thuật toán và thử nghiệm số minh họa, chưa phân tích định lượng chi tiết về độ phức tạp tính toán (computational complexity) và tốc độ hội tụ (rate of convergence) dưới dạng bậc O lớn.

Về hướng nghiên cứu tiếp:

  • Mở rộng các thuật toán chiếu và thuật toán dưới đạo hàm giải bài toán chấp nhận tách suy rộng từ không gian hữu hạn chiều sang không gian Hilbert vô hạn chiều.
  • Nghiên cứu nới lỏng điều kiện đơn điệu của song hàm cân bằng trong bài toán (SEO), tiếp cận các lớp bài toán cân bằng không đơn điệu hoặc bài toán cân bằng ngẫu nhiên.
  • Phát triển các thuật toán hiệu chỉnh cho bài toán chấp nhận tách phi tuyến với các lớp toán tử chuyển tổng quát hơn lớp hàm tựa tuyến tính.

Giá trị tham khảo

Luận án có giá trị tham khảo rõ ràng cho các nhóm đối tượng học thuật và ứng dụng sau:

  • Đối với nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Toán Giải tích, Toán Ứng dụng và Tối ưu hóa: Luận án là tài liệu tham khảo chuyên khảo về kỹ thuật kết hợp giữa phương pháp chiếu, toán tử gần kề và các dãy lặp tìm điểm bất động (Mann, Krasnoselskii). Kỹ thuật chứng minh 5 bước trong Định lý 2.1 và cách thức xử lý hàm không lồi bằng giải tích dưới đạo hàm Clarke trong Chương 3 là những mẫu mực phương pháp luận giải tích có thể vận dụng cho các bài toán liên quan.
  • Đối với các nhà nghiên cứu mô hình hóa kinh tế và kỹ thuật: Chương 2 (Mục 2.2) và Chương 3 (Mục 3.3) cung cấp phương pháp luận toán học cụ thể để mô hình hóa các bài toán cân bằng kinh tế thị trường (mô hình Cournot-Nash) có ràng buộc kỹ thuật và môi trường, chuyển hóa bài toán thực tế thành bài toán tối ưu và cân bằng giải được bằng thuật toán số.

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

  1. Bài toán (SEO) được nghiên cứu trong Chương 2 của luận án có cấu trúc như thế nào? Bài toán (SEO) là bài toán chấp nhận tách suy rộng dạng: Tìm $x^* \in K$ sao cho $f(x^, y) \ge 0$ với mọi $y \in K$ và $g(Ax^) \le g(u)$ với mọi $u \in \mathbb{R}^m$. Trong đó $K \subset \mathbb{R}^n$ là tập lồi đóng khác rỗng, $f$ là song hàm cân bằng para-đơn điệu, $A: \mathbb{R}^n \to \mathbb{R}^m$ là toán tử tuyến tính và $g: \mathbb{R}^m \to \mathbb{R}$ là hàm lồi chính thường nửa liên tục dưới. Cấu trúc này đồng nghĩa với việc tìm một điểm thuộc tập nghiệm của bài toán cân bằng sao cho ảnh tuyến tính của nó qua $A$ rơi vào tập nghiệm của bài toán tối ưu lồi trên $\mathbb{R}^m$.

  2. Song hàm para-đơn điệu (paramonotone) có ý nghĩa gì đối với sự hội tụ của Thuật toán 2.1? Song hàm $f$ được gọi là para-đơn điệu trên $K$ đối với tập nghiệm $S(K, f)$ nếu $f$ là đơn điệu và với mọi $x \in S(K, f), y \in K$ thỏa mãn $f(x, y) = f(y, x) = 0$ thì kéo theo $y \in S(K, f)$. Tính chất này là điều kiện then chốt trong Khẳng định 3 của Định lý 2.1, cho phép chứng minh điểm tụ $x^$ của dãy con lặp sinh bởi thuật toán thực sự là nghiệm của bài toán cân bằng ($x^ \in S(K, f)$).

  3. Luận án đã sử dụng công cụ toán học nào để xử lý bài toán tối ưu lồi trong cấu trúc bài toán chấp nhận tách ở Chương 2? Luận án sử dụng toán tử gần kề (proximal operator) định nghĩa bởi $\text{prox}{\lambda g}(u) = \arg\min{v \in \mathbb{R}^m} {g(v) + \frac{1}{2\lambda}|v - u|^2}$ với $\lambda > 0$. Từ đó, hàm khoảng cách $h(x) = \frac{1}{2}|(I - \text{prox}{\lambda g})Ax|^2$ được thiết lập. Hàm $h(x)$ luôn khả vi với gradient $\nabla h(x) = A^*(I - \text{prox}{\lambda g})Ax$, giúp chuyển điều kiện $Ax \in \arg\min g$ về điều kiện giải tích $h(x) = 0$ để tích hợp vào bước lặp $z_k$ của thuật toán.

  4. Điểm cốt lõi giúp khắc phục hạn chế của các nghiên cứu trước đây về bài toán chấp nhận tách phi tuyến trong Chương 3 là gì? Các nghiên cứu trước (tiêu biểu là Li và cộng sự) khi giải bài toán chấp nhận tách phi tuyến buộc phải đặt giả thiết phụ rằng hàm khoảng cách mêtric là hàm lồi để chứng minh sự hội tụ. Luận án khắc phục rào cản này bằng cách tiếp cận qua lý thuyết hàm tựa lồi và sử dụng dưới đạo hàm Clarke, cho phép thiết lập thuật toán dưới đạo hàm hội tụ trực tiếp đối với toán tử chuyển tựa tuyến tính mà không cần đòi hỏi bất kỳ tính lồi nhân tạo nào của hàm khoảng cách.

  5. Trong trường hợp bài toán chấp nhận tách không có nghiệm thì thuật toán của luận án thể hiện trạng thái gì? Luận án chỉ ra qua Ví dụ 2.5 rằng khi tập nghiệm của bài toán rỗng ($S = K \cap Q = \emptyset$), dãy lặp sinh bởi Thuật toán 2.1 có thể không bị chặn. Cụ thể, trong phản ví dụ trên không gian $\mathbb{R}^2$ với hai tập lồi không giao nhau, tọa độ thứ nhất của dãy lặp thỏa mãn bất đẳng thức đệ quy $u_{k+1} \ge u_k + \frac{1}{32 u_k^3}$ và phân kỳ ra dương vô cùng ($\lim_{k \to \infty} u_k = +\infty$), chứng minh tính cần thiết của giả thiết tập nghiệm khác rỗng đối với sự hội tụ.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Thị Thanh Huyền đã nghiên cứu có hệ thống bài toán chấp nhận tách suy rộng liên quan đến bài toán cân bằng và bài toán quy hoạch lồi, cũng như trường hợp toán tử chuyển phi tuyến tựa tuyến tính. Tác giả đã đề xuất hai thuật toán lặp số học mới (thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii và thuật toán dưới đạo hàm Clarke), thiết lập các định lý chứng minh sự hội tụ mạnh dưới các điều kiện chính quy giải tích xác định. Đồng thời, luận án đã ứng dụng các cấu trúc toán học này để giải quyết mô hình cân bằng bán độc quyền Nash-Cournot trong sản xuất điện có ràng buộc chi phí môi trường và mô hình cân bằng Nash có ràng buộc chung, với các kết quả nghiên cứu đã được công bố trên các tạp chí quốc tế uy tín thuộc danh mục ISI.