Tổng quan luận án

Luận án tiến sĩ toán học "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" do nghiên cứu sinh Nguyễn Thị Thanh Huyền thực hiện dưới sự hướng dẫn khoa học của GS. Lê Dũng Mưu, chuyên ngành Toán Giải tích (mã số: 946 01 02), bảo vệ tại Trường Đại học Sư phạm – Đại học Thái Nguyên năm 2020.

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 - kí hiệu là EP), còn được 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 bài toán quen thuộc như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán bù, bài toán cân bằng Nash trong lý thuyết trò chơi không hợp tác và bài toán tối ưu Pareto yếu. Cùng với đó, bài toán chấp nhận tách (Split Feasibility Problem - kí hiệu là SFP) xuất phát từ các bài toán thực tế 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ị trong điều trị ung thư.

Trong lý thuyết tối ưu và giải tích phi tuyến, phần lớn các phương pháp giải bài toán chấp nhận tách trước đây chỉ tập trung vào trường hợp toán tử chuyển là toán tử tuyến tính và hai tập ràng buộc được cho tường minh hoặc là tập điểm bất động, tập nghiệm của bài toán bất đẳng thức biến phân. Khi các tập ràng buộc được cho dưới dạng ẩn là tập nghiệm của bài toán cân bằng và tập nghiệm của bài toán tối ưu lồi, hoặc khi toán tử chuyển là toán tử phi tuyến (chẳng hạn toán tử cho bởi các hàm tựa tuyến tính), các phương pháp truyền thống gặp nhiều trở ngại:

  • Các thuật toán chiếu cổ điển đòi hỏi phải tính toán toán tử chuyển vị hoặc toán tử nghịch đảo của ma trận chuyển, điều này không thực hiện được khi toán tử chuyển là phi tuyến.
  • Các phương pháp giải bài toán cân bằng thông thường (như phương pháp đạo hàm tăng cường Korpelevich-Antipin) đòi hỏi hai phép chiếu lên tập ràng buộc ở mỗi bước lặp, gây tốn kém khối lượng tính toán khi cấu trúc tập ràng buộc phức tạp.
  • Thiếu các thuật toán giải bài toán chấp nhận tách phi tuyến khi hàm mục tiêu không đảm bảo tính lồi toàn cục.

Mục tiêu và câu hỏi nghiên cứu

Luận án tập trung giải quyết hai mục tiêu nghiên cứu cụ thể:

  1. Xây dựng thuật toán chiếu một lần kết hợp với kỹ thuật lặp Mann-Krasnoselskii và toán tử gần kề để giải bài toán chấp nhận tách suy rộng, trong đó tập ràng buộc thứ nhất là tập nghiệm của bài toán cân bằng para-đơn điệu và tập ràng buộc thứ hai là tập nghiệm của bài toán tối ưu lồi trong không gian hữu hạn chiều; thiết lập các điều kiện hội tụ mạnh của dãy lặp sinh bởi thuật toán.
  2. Xây dựng thuật toán dưới đạo hàm dựa trên xấp xỉ dưới vi phân Clarke cho bài toán tối ưu tựa lồi nhằm giải bài toán chấp nhận tách phi tuyến với toán tử chuyển tựa tuyến tính; áp dụng giải mô hình cân bằng Nash có ràng buộc chung phát sinh từ các bài toán thực tế.

Đố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, bài toán tối ưu lồi, bài toán chấp nhận tách suy rộng tuyến tính và phi tuyến, các phương pháp lặp điểm bất động (Mann, Krasnoselskii, Mann-Krasnoselskii), phép chiếu mêtric, toán tử gần kề và giải tích dưới vi phân của hàm lồi và hàm tựa lồi.
  • Phạm vi không gian: Không gian véctơ Euclid thực hữu hạn chiều $\mathbb{R}^n$ và $\mathbb{R}^m$.
  • Phạm vi ứng dụng: Mô hình cân bằng bán độc quyền Nash-Cournot trong bài toán sản xuất điện năng gắn với chi phí ô nhiễm môi trường và mô hình cân bằng Nash có ràng buộc chung.

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

Các hướng nghiên cứu liên quan trong y văn

Văn bản luận án điểm lại có hệ thống các mốc phát triển chính của bài toán cân bằng và bài toán chấp nhận tách:

  • Nguồn gốc 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 khi nghiên cứu trò chơi không hợp tác. Năm 1972, Ky Fan khảo sát bài toán dưới tên gọi bất đẳng thức minimax và chứng minh các định lý về sự tồn tại nghiệm. Thuật ngữ "bài toán cân bằng" (Equilibrium Problem) được L. Blum và W. Oettli định hình và phát triển có hệ thống từ năm 1994, sau đó được E. Blum và W. Oettli cùng nhóm tác giả G. Bigi tổng hợp trong các chuyên khảo tiêu biểu.
  • Phương pháp giải bài toán cân bằng:
    • Phương pháp điểm bất động và nguyên lý bài toán phụ: G. Cohen đề xuất 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; G. Mastroeni mở rộng cho bài toán cân bằng vào năm 2003; P. L. Combettes đề xuất ánh xạ dựa trên phương pháp hiệu chỉnh gần kề năm 2004.
    • Phương pháp hàm đánh giá (gap function): Được phát triển bởi A. Auslender, M. Fukushima, P. Q. Khanh và N. H. Quoc nhằm chuyển đổi bài toán cân bằng về bài toán tối ưu tương đương.
    • Phương pháp hiệu chỉnh Tikhonov và điểm gần kề: Được nghiên cứu cho bài toán cân bằng đơn điệu và giả đơn điệu trong các công trình của L. D. Muu, N. V. Quy, P. T. Kien và V. V. Hien.
    • Phương pháp đạo hàm tăng cường (extragradient): Do A. S. Antipin đề xuất năm 1995 cho bài toán cân bằng với tập lồi compac; S. Langenberg mở rộng cho tập không bị chặn; sau đó được hoàn thiện và cải tiến bởi B. V. Định (2011), T. N. Hải (2015), P. G. Hưng (2017).
  • Nguồn gốc bài toán chấp nhận tách: Do Y. Censor và T. Elfving giới thiệu năm 1994 cho mô hình bài toán ngược; C. Byrne (2002) đưa ra thuật toán CQ ứng dụng trong tái tạo hình ảnh y tế; Y. Censor (2005) mở rộng sang điều khiển xạ trị ung thư (IMRT); T. V. Anh (2013) nghiên cứu cho trường hợp liên quan đến bất đẳng thức biến phân và điểm bất động; B. S. Thakur (2013) chuyển bài toán chấp nhận tách về bài toán tối ưu lồi không ràng buộc dựa trên toán tử chiếu.
Hướng nghiên cứu Tác giả tiêu biểu được trích dẫn Hạn chế hoặc đặc điểm kỹ thuật
Bài toán cân bằng tổng quát H. Isoda (1955), Ky Fan (1972), E. Blum & W. Oettli (1994), G. Bigi (2013) Đặt nền tảng lý thuyết và điều kiện tồn tại nghiệm.
Phương pháp đạo hàm tăng cường A. S. Antipin (1995), S. Langenberg, P. Scheimberg (2008) Cần 2 phép chiếu ở mỗi bước lặp, chi phí tính toán cao.
Bài toán chấp nhận tách tuyến tính Y. Censor & T. Elfving (1994), C. Byrne (2002), B. S. Thakur (2013) Yêu cầu toán tử $A$ tuyến tính và tính được ma trận chuyển vị $A^*$.
Chấp nhận tách phi tuyến Li và các cộng sự Phải giả thiết tính lồi ngặt của hàm khoảng cách chiếu.

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

Luận án giải quyết hai khoảng trống kỹ thuật:

  1. Thiết kế thuật toán giải bài toán chấp nhận tách khi tập nghiệm thứ nhất là tập nghiệm của bài toán cân bằng $EP(K, f)$ và tập nghiệm thứ hai là tập cực tiểu của hàm lồi $g(u)$, trong đó chỉ sử dụng duy nhất một phép chiếu lên tập $K$ kết hợp ánh xạ gần kề $\text{prox}_{\lambda g}$, khắc phục sự tốn kém tính toán của phương pháp chiếu hai lần.
  2. Xây dựng thuật toán giải bài toán chấp nhận tách khi toán tử chuyển $A$ là toán tử phi tuyến được tạo thành từ các hàm tựa tuyến tính, khắc phục giới hạn của các phương pháp cũ vốn chỉ áp dụng cho toán tử tuyến tính.

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

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

  • Giải tích lồi trong không gian $\mathbb{R}^n$: Sử dụng tích vô hướng $\langle x, y \rangle = \sum_{i=1}^n x_i y_i$, chuẩn Euclid $|x| = \sqrt{\langle x, x \rangle}$, tập lồi, phép chiếu mêtric $P_K(x) = \arg\min_{z \in K} |z - x|$, nón pháp tuyến ngoài $N_K(x) = {w \in \mathbb{R}^n : \langle w, y - x \rangle \le 0, \forall y \in K}$.
  • Giải tích dưới vi phân: Dưới vi phân $\partial f(x_0)$ và $\varepsilon$-dưới vi phân $\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 với song hàm $f(x, y)$, ký hiệu $\partial_2^\varepsilon f(x, x)$ là $\varepsilon$-dưới vi phân theo biến thứ hai tại điểm $x$.
  • Lý thuyết hàm tựa lồi (De Finetti, 1949): Hàm $\phi: X \to \mathbb{R}$ được gọ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}$; $\phi$ là tựa lõm nếu $-\phi$ tựa lồi; $\phi$ là tựa tuyến tính nếu nó vừa tựa lồi vừa tựa lõm.
  • Tính chất đơn điệu của song hàm cân bằng:
    • Đơn điệu mạnh với hằng số $\tau > 0$: $f(x, y) + f(y, x) \le -\tau |x - y|^2$.
    • Đơn điệu chặt: $f(x, y) + f(y, x) < 0, \forall x \ne y$.
    • Đơn điệu: $f(x, y) + f(y, x) \le 0$.
    • Giả đơn điệu: $f(x, y) \ge 0 \Rightarrow f(y, x) \le 0$.
    • Para-đơn điệu (paramonotone) đối với tập $S$: $f$ là giả đơn điệu và nếu $x \in S, y \in K$ thỏa mãn $f(x, y) = f(y, x) = 0$ thì $y \in S$.
  • Toán tử gần kề (Proximal Operator): Với hàm lồi chính thường, nửa liên tục dưới $g: \mathbb{R}^m \to \mathbb{R} \cup {+\infty}$ và tham số $\lambda > 0$, toán tử gần kề được định nghĩa là: $$\text{prox}{\lambda g}(u) := \arg\min{v \in \mathbb{R}^m} \left{ g(v) + \frac{1}{2\lambda} |v - u|^2 \right}$$ Hàm đánh giá liên kết $h(x) := \frac{1}{2} |(I - \text{prox}{\lambda g})Ax|^2$ là hàm khả vi trên toàn không gian và có gradient $\nabla h(x) = A^*(I - \text{prox}{\lambda g})Ax$.

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

  • Phương pháp giải tích và lý thuyết toán tử lồi: Xây dựng sơ đồ lặp kết hợp giữa kỹ thuật xấp xỉ $\varepsilon$-dưới vi phân, phép chiếu mêtric một lần lên tập lồi và phép lặp Mann-Krasnoselskii dạng $x^{k+1} = a_k x^k + (1 - a_k)z^k$.
  • Phương pháp xấp xỉ dưới đạo hàm Clarke: Sử dụng các công cụ giải tích không trơn để xử lý tính tựa lồi và cấu trúc phi tuyến của toán tử chuyển.
  • Phương pháp thực nghiệm tính toán số: Thiết lập thuật toán trên máy tính, thực hiện các thử nghiệm kiểm chứng sự hội tụ trên các bài toán mẫu và mô hình kinh tế năng lượng, so sánh số bước lặp và thời gian tính 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 hệ thống hóa các định nghĩa, ký hiệu và kết quả bổ trợ nền tảng của giải tích lồi, lý thuyết bài toán cân bằng, bài toán chấp nhận tách và các phương pháp lặp cơ bản.

  • Các khái niệm giải tích lồi và song hàm: Định nghĩa và các tính chất cơ bản của phép chiếu mêtric $P_K$, nón pháp tuyến ngoài $N_K$, dưới vi phân $\partial f$, $\varepsilon$-dưới vi phân $\partial^\varepsilon f$, hàm tựa lồi, tựa lõm và tựa tuyến tính. Phân cấp mối quan hệ giữa các lớp song hàm đơn điệu: đơn điệu mạnh $\Rightarrow$ đơn điệu chặt $\Rightarrow$ đơn điệu $\Rightarrow$ giả đơn điệu; para-đơn điệu $\Rightarrow$ đơn điệu.
  • Mối quan hệ giữa bài toán cân bằng $EP(K, f)$ và các bài toán liên quan:
    • Bài toán tối ưu lồi: Đặt $f(x, y) := \phi(y) - \phi(x)$.
    • Bài toán điểm yên ngựa: Đặt $f((x_1, x_2), (y_1, y_2)) := \phi(y_1, x_2) - \phi(x_1, y_2)$.
    • Bài toán cân bằng Nash: Đặt $f(x, y) := \sum_{i \in I} (f_i(x[y_i]) - f_i(x))$.
    • Bài toán điểm bất động: Đặt $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ù: Đặt $f(x, y) := \langle Tx, y - x \rangle$ hoặc $f(x, y) := \langle F(x), y - x \rangle$.
    • Bài toán tối ưu Pareto yếu: Đặt $f(x, y) := \max_{1 \le i \le m} [\psi_i(y) - \psi_i(x)]$.
  • Các phương pháp lặp tìm điểm bất động kinh điển:
    • Nguyên lý ánh xạ co Banach (lặp Picard): $x_{n+1} = Tx_n$.
    • Phép lặp Mann: $x_{n+1} = (1 - \alpha_n)x_n + \alpha_n Tx_n$ với $\sum \alpha_n = \infty$.
    • Phép lặp Krasnoselskii: $x_{n+1} = \frac{1}{2}(x_n + Tx_n)$.
    • Phép lặp Mann-Krasnoselskii: $x_{n+1} = (1 - \alpha_n)x_n + \alpha_n Tx_n$ với $\alpha_n \in (0, 1)$.
  • Các bổ đề bổ trợ:
    • Bổ đề 1.1: Với $x, y, z \in \mathbb{R}^n$ và $a \in [0, 1]$: $|ax + (1-a)y - z|^2 \le a|x - z|^2 + (1-a)|y - z|^2$.
    • Bổ đề 1.2 (hội tụ dãy số không âm): Cho dãy ${v_k}, {\delta_k}$ không âm thỏa $v_{k+1} \le v_k + \delta_k$ và $\sum_{k=1}^\infty \delta_k < +\infty$, khi đó ${v_k}$ hội tụ.
    • Bổ đề 1.3: Bổ đề kỹ thuật về giới hạn dãy véctơ trong $\mathbb{R}^n$ để suy ra $\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 trình bày bài toán chấp nhận tách dạng (SEO): $$\text{Tìm } x^* \in K \text{ 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 khác rỗng, $A: \mathbb{R}^n \to \mathbb{R}^m$ là toán tử tuyến tính, $f: K \times K \to \mathbb{R}$ là song hàm cân bằng 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.

Hệ giả thiết kỹ thuật (A1)–(A4)

  • (A1): Với mỗi $x \in K$, $f(x, x) = 0$ và $f(x, \cdot)$ là hàm 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 của $K$.
  • (A3): Song hàm $f$ là para-đơn điệu trên $K$ đối với tập nghiệm $S(K, f)$.
  • (A4): Với mỗi $x \in K$, hàm $f(\cdot, x)$ nửa liên tục trên trên $K$.

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

  • Thông số ban đầu: Lấy $\delta > 0, \xi > 0$ và 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; \quad 0 < \xi \le \rho_k \le 4 - \xi; \quad \sum_{k=1}^\infty \beta_k < +\infty; \quad \sum_{k=1}^\infty \varepsilon_k < +\infty; \quad \sum_{k=1}^\infty \frac{\beta_k}{\delta_k} = +\infty$$
  • Bước 0: Chọn điểm khởi tạo $x^1 \in K$, đặt $k := 1$.
  • Bước $k$: Đã có $x^k \in K$:
    1. Lấy dưới vi phân $g_k \in \partial_2^{\varepsilon_k} f(x^k, x^k)$, xác định $\gamma_k = \max{\delta_k, |g_k|}$ và bước nhảy $\alpha_k = \frac{\beta_k}{\gamma_k}$.
    2. Tính điểm chiếu: $y^k = P_K(x^k - \alpha_k g_k)$.
    3. Xác định $z^k$: $$z^k = \begin{cases} P_K \left( y^k - \rho_k \dfrac{h(y^k)}{|\nabla h(y^k)|^2} \nabla h(y^k) \right) & \text{nếu } \nabla h(y^k) \ne 0 \ y^k & \text{nếu } \nabla h(y^k) = 0 \end{cases}$$
    4. Cập nhật nghiệm theo sơ đồ Mann-Krasnoselskii: $x^{k+1} = a_k x^k + (1 - a_k)z^k$.
    5. Tăng $k := k + 1$ và lặp lại.

Định lý hội tụ 2.1

Giả sử bài toán (SEO) có tập nghiệm $S \ne \emptyset$ và thỏa mãn các giả thiết (A1)–(A4). Khi đó dãy ${x^k}$ sinh bởi Thuật toán 2.1 hội tụ mạnh về một nghiệm $x^* \in S$. Quá trình chứng minh được chia thành 5 khẳng định giải tích:

  1. Khẳng định 1: Dãy ${|x^k - z|^2}$ hội tụ với mọi $z \in S$, suy ra các dãy ${x^k}$ và ${y^k}$ đều bị chặn.
  2. Khẳng định 2: $\limsup_{k \to +\infty} f(x^k, z) = 0$ với mọi $z \in S$.
  3. Khẳng định 3: Mọi điểm tụ $x^*$ của dãy con ${x^{k_j}}$ đều thuộc tập nghiệm $S(K, f)$ của bài toán cân bằng.
  4. Khẳng định 4: Mọi điểm tụ $x$ của dãy ${x^k}$ thỏa mãn $x \in K$ và $Ax \in \arg\min_{u \in \mathbb{R}^m} g(u)$ nhờ tính chất nửa liên tục dưới của hàm khoảng cách $h$.
  5. Khẳng định 5: Dãy hình chiếu ${P_S(x^{k_j})}$ là một dãy Cauchy trong $\mathbb{R}^n$, do đó $\lim_{k \to \infty} x^k = \lim_{k \to \infty} y^k = x^* \in S$.

Trường hợp bài toán vô nghiệm và Mô hình ứng dụng

  • Ví dụ phân kỳ khi $S = \emptyset$: Luận án chứng minh nếu $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 thỏa mãn $u_{k+1} \ge u_k + \frac{1}{32 u_k^3}$, dẫn đến $\lim_{k \to \infty} u_k = +\infty$ (dãy phân kỳ).
  • Ứng dụng sản xuất điện cân bằng Nash-Cournot: Xét $n$ nhà máy điện, mỗi nhà máy $i$ sở hữu tập máy phát $I_i$. Véctơ sản lượng điện là $x = (x_j)$, tổng sản lượng $s = \sum_{j=1}^N x_j$. Giá bán điện là hàm giảm $p_i(s) = \alpha - \beta_i s$. Hàm lợi nhuận của nhà máy $i$: $$f_i(x) = p_i(s) \left( \sum_{j \in I_i} x_j \right) - \sum_{j \in I_i} c_j(x_j)$$ Hàm chi phí $c_j(x_j)$ là hàm lồi. Để sản xuất, nhà máy sử dụng $m$ loại nguyên vật liệu xác định bởi ma trận $A = (a_{l, j})$. Phí ô nhiễm môi trường là hàm lồi tăng $g(Ax)$. Bài toán tìm điểm cân bằng Nash có tổng phí môi trường thấp nhất được quy về dạng (SEP): $$\text{Tìm } x^* \in K : f(x^, x) \ge 0, \forall x \in K \quad \text{và} \quad g(Ax^) \le g(Ax), \forall x \in K$$

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 mở rộng bài toán chấp nhận tách sang trường hợp toán tử chuyển phi tuyến (NSEP): $$\text{Tìm } x^* \in C \text{ 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à được cấu thành từ các hàm thành phần tựa tuyến tính $\phi_i(x)$.

  • Thuật toán dưới đạo hàm Clarke: Sử dụng kỹ thuật tối ưu hóa cho hàm tựa lồi không trơn, thay thế gradient thông thường bằng dưới vi phân Clarke $\partial^C \phi(x)$. Thuật toán xác định hướng giảm dựa trên dưới đạo hàm của hàm khoảng cách mức và thực hiện các bước chiếu xấp xỉ liên tiếp.
  • Chứng minh sự hội tụ: Thiết lập điều kiện đủ để dãy lặp hội tụ về nghiệm của bài toán chấp nhận tách phi tuyến mà không đòi hỏi giả thiết về tính lồi toàn cục của hàm khoảng cách.
  • Ứng dụng cho mô hình cân bằng Nash có ràng buộc chung (GNEP): Mô hình hóa bài toán cạnh tranh thị trường khi các đấu thủ không chỉ cạnh tranh về hàm mục tiêu mà còn chịu ràng buộc chung về hạn ngạch tài nguyên, xả thải hoặc năng lực truyền tải của mạng lưới. Dữ liệu thử nghiệm số khẳng định thuật toán giải quyết hiệu quả bài toán với số bước lặp ổn định.

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 bao gồm:

  1. Về mặt lý luận và thuật toán cho bài toán (SEO):

    • Đề xuất thuật toán chiếu một lần kết hợp kỹ thuật lặp Mann-Krasnoselskii và toán tử gần kề giải bài toán chấp nhận tách liên quan đến bài toán cân bằng para-đơn điệu và bài toán tối ưu lồi.
    • Thuật toán chỉ sử dụng duy nhất một phép chiếu lên tập ràng buộc $K$ ở mỗi bước lặp, loại bỏ bước chiếu phụ thứ hai vốn có trong các phương pháp đạo hàm tăng cường dạng extragradient, qua đó giảm chi phí tính toán.
    • Thiết lập và chứng minh định lý hội tụ mạnh của dãy lặp trong không gian hữu hạn chiều mà không đòi hỏi toán tử tuyến tính $A$ phải khả nghịch.

  2. Về mặt lý luận và thuật toán cho bài toán (NSEP):

    • Mở rộng bài toán chấp nhận tách sang trường hợp toán tử chuyển phi tuyến cấu thành từ các hàm tựa tuyến tính.
    • Xây dựng thuật toán dưới đạo hàm Clarke cho bài toán tối ưu tựa lồi và chứng minh sự hội tụ của phương pháp.

  3. Về mặt ứng dụng thực tiễn:

    • Xây dựng mô hình toán học tích hợp bài toán cân bằng bán độc quyền Nash-Cournot trong sản xuất điện năng với bài toán tối thiểu hóa hàm chi phí ô nhiễm môi trường.
    • Mô hình hóa và giải bài toán cân bằng Nash có ràng buộc chung (GNEP) nảy sinh trong thực tế.

  4. Công bố khoa học:

    • Các kết quả chính của luận án đã được công bố trong 02 bài báo khoa học trên các tạp chí quốc tế thuộc danh mục ISI:
      • Mathematical Methods of Operations Research (nội dung Chương 2).
      • Journal of Global Optimization (nội dung Chương 3).

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

Hạn chế được ghi nhận từ phạm vi nghiên cứu

  • Các thuật toán và định lý hội tụ trong luận án được thiết lập trong không gian véctơ Euclid hữu hạn chiều $\mathbb{R}^n$ và $\mathbb{R}^m$, chưa mở rộng hoàn chỉnh sang không gian vô hạn chiều (như không gian Hilbert hay Banach tổng quát).
  • Đối với bài toán (SEO), song hàm cân bằng $f$ bắt buộc phải thỏa mãn tính chất para-đơn điệu; đối với bài toán (NSEP), toán tử chuyển phi tuyến bị giới hạn trong lớp các hàm tựa tuyến tính.
  • Khi bài toán không tồn tại nghiệm ($S = \emptyset$), thuật toán chưa tích hợp tiêu chuẩn dừng nhận biết tự động mà dãy lặp sẽ phân kỳ ra vô cùng.

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

  • Mở rộng thuật toán giải bài toán chấp nhận tách suy rộng sang không gian Hilbert vô hạn chiều phục vụ các bài toán điều khiển tối ưu và phương trình đạo hàm riêng.
  • Nghiên cứu nới lỏng giả thiết đơn điệu của song hàm cân bằng sang các lớp hàm tổng quát hơn như song hàm giả đơn điệu yếu hoặc song hàm không đơn điệu.
  • Phát triển kỹ thuật chọn độ dài bước lặp tự điều chỉnh (adaptive stepsize) không phụ thuộc vào hằng số Lipschitz hoặc tham số chặn dưới vi phân.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên khảo hữu ích cho:

  • 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 Tối ưu và Toán Ứng dụng: Tham khảo phương pháp xây dựng thuật toán lặp giải tích, kỹ thuật kết hợp toán tử gần kề prox với phép lặp Mann-Krasnoselskii, và giải tích hàm tựa lồi không trơn.
  • Các nhà nghiên cứu trong lĩnh vực Kinh tế lượng, Kỹ thuật hệ thống điện và Môi trường: Tham khảo phương pháp mô hình hóa bài toán thị trường điện cạnh tranh Nash-Cournot có ràng buộc chi phí phát thải môi trường và bài toán cân bằng Nash có ràng buộc chung.

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

1. Bài toán chấp nhận tách suy rộng (SEO) trong Chương 2 được phát biểu như thế nào?

Bài toán (SEO) là bài toán tìm một điểm $x^* \in K$ sao cho: $$f(x^, y) \ge 0, \quad \forall y \in K \quad \text{và} \quad g(Ax^) \le g(u), \quad \forall u \in \mathbb{R}^m$$ trong đó $K \subset \mathbb{R}^n$ là tập lồi đóng khác rỗng, $A: \mathbb{R}^n \to \mathbb{R}^m$ là toán tử tuyến tính, $f$ là song hàm cân bằng thỏa mãn $f(x, x) = 0$ 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. Đây là bài toán chấp nhận tách với tập ràng buộc thứ nhất là tập nghiệm của bài toán cân bằng $EP(K, f)$ và tập ràng buộc thứ hai là tập nghiệm của bài toán quy hoạch lồi $\min_{u \in \mathbb{R}^m} g(u)$.

2. Ưu điểm kỹ thuật chính của Thuật toán 2.1 so với phương pháp đạo hàm tăng cường truyền thống là gì?

Phương pháp đạo hàm tăng cường truyền thống (như thuật toán Korpelevich hoặc Antipin) đòi hỏi thực hiện hai phép chiếu mêtric lên tập ràng buộc $K$ ở mỗi bước lặp. Thuật toán 2.1 của luận án kết hợp phép chiếu một lần $y^k = P_K(x^k - \alpha_k g_k)$ với toán tử gần kề $\text{prox}{\lambda g}$ của hàm lồi $g$ thông qua hàm đánh giá khả vi $h(x) = \frac{1}{2}|(I - \text{prox}{\lambda g})Ax|^2$. Nhờ đó, thuật toán giảm thiểu số lần chiếu lên tập $K$, tiết kiệm chi phí tính toán khi cấu trúc hình học của $K$ phức tạp.

3. Song hàm para-đơn điệu (paramonotone) là gì và có vai trò như thế nào trong chứng minh hội tụ?

Một song hàm $f: K \times K \to \mathbb{R}$ được gọi là para-đơn điệu trên $K$ đối với tập nghiệm $S$ nếu nó là giả đơn điệu và thỏa mãn điều kiện: nếu $x \in S, y \in K$ sao cho $f(x, y) = 0$ và $f(y, x) = 0$ thì $y \in S$. Tính chất này đóng vai trò quyết định trong Khẳng định 3 của Định lý 2.1, bảo đảm rằng mọi điểm tụ $x^*$ của dãy lặp đều thuộc tập nghiệm $S(K, f)$ của bài toán cân bằng.

4. Thuật toán 2.1 hoạt động như thế nào trong trường hợp bài toán vô nghiệm?

Trong trường hợp tập nghiệm của bài toán rỗng ($S = K \cap Q = \emptyset$), luận án đã chứng minh bằng ví dụ phản chứng cụ thể rằng dãy lặp ${x^k}$ sinh bởi Thuật toán 2.1 sẽ không bị chặn và phân kỳ ra vô cùng ($\lim_{k \to \infty} |x^k| = +\infty$). Điều này khẳng định tính đúng đắn của giả thiết tập nghiệm $S \ne \emptyset$ trong định lý hội tụ.

5. Mô hình sản xuất điện trong Chương 2 tích hợp bài toán cân bằng Nash và bài toán môi trường ra sao?

Mô hình giả định có $n$ nhà máy điện cạnh tranh theo cơ chế Nash-Cournot với hàm giá giảm tuyến tính $p_i(s) = \alpha - \beta_i s$ và hàm chi phí sản xuất $c_j(x_j)$. Để sản xuất, các nhà máy tiêu thụ nguyên vật liệu xác định bởi ma trận $A$, dẫn đến phát thải ô nhiễm với chi phí toàn hệ thống là $g(Ax)$. Bài toán đặt ra là tìm véctơ sản lượng $x^*$ vừa là điểm cân bằng Nash giữa các nhà máy, vừa tối thiểu hóa chi phí ô nhiễm môi trường $g(Ax)$, được mô hình hóa chính xác dưới dạng bài toán chấp nhận tách (SEO).

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Thị Thanh Huyền đã giải quyết trọn vẹn việc xây dựng các thuật toán lặp hiệu quả cho hai lớp 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 trong không gian Euclid hữu hạn chiều. Bằng việc kết hợp sáng tạo phép chiếu một lần, toán tử gần kề, kỹ thuật lặp Mann-Krasnoselskii và dưới đạo hàm Clarke cho hàm tựa lồi, công trình đã thiết lập các định lý hội tụ mạnh với giả thiết hợp lý và kiểm chứng tính khả thi qua các mô hình thực tế về cân bằng sản xuất điện năng gắn với bảo vệ môi trường và cân bằng Nash có ràng buộc chung. Các kết quả lý thuyết cốt lõi của luận án đã được công bố trên hai tạp chí quốc tế uy tín thuộc danh mục ISI là Mathematical Methods of Operations Research và Journal of Global Optimization.