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 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 bởi nghiên cứu sinh Nguyễn Thị Thanh Huyề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 (bảo vệ năm 2020), thuộc chuyên ngành Toán Giải tích (mã số: 946 01 02).

+---------------------------------------------------------------------------------------------------+
| THÔNG TIN ĐỊNH DANH CÔNG TRÌNH                                                                    |
+------------------------------------+--------------------------------------------------------------+
| Tác giả:                           | Nguyễn Thị Thanh Huyền                                       |
| Người hướng dẫn khoa học:          | GS. Lê Dũng Mưu                                              |
| Cơ sở đào tạo:                     | Trường Đại học Sư phạm – Đại học Thái Nguyên                 |
| Chuyên ngành:                      | Toán Giải tích (Mã số: 946 01 02)                            |
| Năm hoàn thành:                    | 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$) và bài toán chấp nhận tách (Split Feasibility Problem - kí hiệu là $SFP$) là hai mô hình toán học tổng quát, chứa đựng nhiều lớp bài toán quan trọng như bài toán tối ưu, bất đẳng thức biến phân, điểm bất động, bài toán bù và bài toán cân bằng Nash trong lý thuyết trò chơi phi hợp tác.

Trong thực tiễn tính toán, bài toán chấp nhận tách kinh điển tìm một điểm $x \in C$ sao cho $Ax \in Q$ (với $A$ là toán tử tuyến tính chuyển giữa hai không gian Euclid hữu hạn chiều $\mathbb{R}^n$ và $\mathbb{R}^m$). Tuy nhiên, phần lớn các công trình nghiên cứu trước đây chỉ tập trung vào trường hợp các tập ràng buộc $C$ và $Q$ được cho tường minh, hoặc toán tử chuyển $A$ thuần nhất là toán tử tuyến tính.

Khoảng trống nghiên cứu then chốt mà luận án xác định và giải quyết bao gồm:

  1. Thiếu vắng các thuật toán hiệu quả giải bài toán chấp nhận tách suy rộng khi tập $C$ và/hoặc $Q$ cho dưới dạng ẩn, cụ thể $C$ là tập nghiệm của một bài toán cân bằng phi tuyến (với song hàm para-đơn điệu) và $Q$ là tập nghiệm của một bài toán tối ưu lồi.
  2. Hạn chế của các thuật toán hiện hành khi xử lý bài toán chấp nhận tách có toán tử chuyển $A$ mang bản chất phi tuyến (toán tử tựa tuyến tính), nơi các kỹ thuật chiếu đối ngẫu $A^*$ hoặc toán tử nghịch đảo $A^{-1}$ truyền thống không còn khả thi.

Mục tiêu và nhiệm vụ nghiên cứu

Luận án tập trung thực hiện 4 nhiệm vụ cốt lõi:

  1. Xây dựng thuật toán lặp giải bài toán chấp nhận tách suy rộng (SEO) kết hợp giữa bài toán cân bằng para-đơn điệu và bài toán quy hoạch lồi thông qua phép chiếu một lần và toán tử gần kề (proximal operator).
  2. Thiết lập và chứng minh sự hội tụ của dãy lặp sinh bởi thuật toán kết hợp phép lặp Mann-Krasnoselskii dưới các điều kiện chính quy phù hợp.
  3. Nghiên cứu thuật toán dưới đạo hàm (subgradient method) dựa trên xấp xỉ dưới vi phân Clarke để giải bài toán chấp nhận tách phi tuyến (NSEP) với toán tử chuyển tựa tuyến tính.
  4. Xây dựng mô hình ứng dụng thực tế và thực nghiệm tính toán số trên máy tính cho mô hình cân bằng bán độc quyền Nash-Cournot sản xuất điện gắn với chi phí môi trường và mô hình cân bằng Nash có ràng buộc chung.

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

  • Đối tượng nghiên cứu: Các bài toán chấp nhận tách suy rộng tuyến tính và phi tuyến, bài toán cân bằng Ky Fan, bài toán tối ưu lồi, toán tử gần kề, phép chiếu mêtric, phép lặp Mann-Krasnoselskii, dưới đạo hàm và hàm tựa lồi/tựa tuyến tính.
  • 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$ trang bị tích vô hướng chuẩn tắc $\langle \cdot, \cdot \rangle$ và chuẩn Euclid $|\cdot|$.
  • Phạm vi cấu trúc hàm: Song hàm cân bằng $f$ thỏa mãn tính chất para-đơn điệu, nửa liên tục; hàm mục tiêu $g$ lồi chính thường, nửa liên tục dưới; các toán tử chuyển phi tuyến cấu thành từ các hàm tựa tuyến tính.

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

Luận án đã hệ thống hóa lịch sử phát triển của bài toán cân bằng và bài toán chấp nhận tách qua các mốc nghiên cứu chính:

Lịch sử nghiên cứu bài toán cân bằng (EP)

  • Khởi nguồn và định danh: H. Isoda (1955) sử dụng dạng bất đẳng thức cân bằng đầu tiên trong trò chơi không hợp tác. Năm 1972, Ky Fan giới thiệu bất đẳng thức minimax và chứng minh các định lý 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 xác lập năm 1994, sau đó được G. Bigi và các cộng sự tổng kết hệ thống trong chuyên khảo năm 2013.
  • Các hướng phương pháp giải bài toán EP:
    • Phương pháp điểm bất động và nguyên lý bài toán phụ: G. Cohen (1980, 1988) đề xuất cho tối ưu và bất đẳng thức biến phân; G. Mastroeni (2003) mở rộng cho bài toán cân bằng với hàm khoảng cách Bregman; Combettes đề xuất phương pháp hiệu chỉnh gần kề đơn điệu mạnh.
    • Phương pháp hàm đánh giá (Gap functions): Hàm đánh giá Auslender, Fukushima và hàm đánh giá đối ngẫu Minty được G. Mastroeni, L. D. Muu, N. V. Quy và V. H. Nguyen nghiên cứu chuyển EP 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ề (Proximal Point): Ứng dụng giải các bài toán đặt không chỉnh (ill-posed), mở rộng bởi P. T. Kien, L. D. Muu (2009) cho bài toán giả đơn điệu thông qua kỹ thuật tối ưu hai cấp (bilevel optimization).
    • Phương pháp đạo hàm tăng cường (Extragradient): A. S. Antipin (1995), K. O. Langenberg (2012), kết hợp các cải tiến chiếu trên siêu phẳng trong các công trình của Bùi Văn Định (2013), Trịnh Ngọc Hải (2014), Phạm Gia Hưng (2015).

Lịch sử nghiên cứu bài toán chấp nhận tách (SFP)

  • Khởi nguồn và ứng dụng: Y. Censor và T. Elfving (1994) đưa ra bài toán SFP đầu tiên ứng dụng trong bài toán ngược (inverse problems). C. Byrne (2002) đề xuất thuật toán CQ ứng dụng trong khôi phục và tái tạo hình ảnh y tế. Y. Censor (2005, 2006) ứng dụng điều khiển cường độ xạ trị trong điều trị ung thư.
  • Tiếp cận tối ưu hóa: A. Moudafi và Thakur (2013) chứng minh việc giải SFP tương đương với cực tiểu hóa hàm khoảng cách lồi khả vi $h(x) = \frac{1}{2\lambda}|(I - P_Q)Ax|^2$.
  • Mở rộng suy rộng và phi tuyến: Trần Việt Anh (2016) nghiên cứu SFP khi các tập ràng buộc là tập nghiệm của bất đẳng thức biến phân hoặc điểm bất động của ánh xạ không giãn. Li và các cộng sự xét trường hợp toán tử $A$ phi tuyến nhưng phải đặt giả thiết lồi nghiêm ngặt lên hàm khoảng cách $p(x) = \frac{1}{2}|P_Q(F(x)) - F(x)|^2$.

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

Luận án định vị trọng tâm nghiên cứu vào hai bài toán chưa có lời giải hoàn chỉnh:

  1. Giải bài toán chấp nhận tách (SEO) với $C = S(K, f)$ là tập nghiệm bài toán cân bằng với song hàm $f$ para-đơn điệu và $Q = \text{argmin}_{u \in \mathbb{R}^m} g(u)$ là tập nghiệm tối ưu lồi, kết hợp thuật toán chiếu một lần của P. Scheimberg với toán tử gần kề và phép lặp Mann-Krasnoselskii.
  2. Giải bài toán chấp nhận tách phi tuyến (NSEP) khi toán tử chuyển $F$ là phép biến đổi tựa tuyến tính, khắc phục triệt để yêu cầu toán tử tuyến tính hoặc giả thiết hàm khoảng cách lồi của các nghiên cứu đi trước.

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

Luận án sử dụng bộ công cụ toán học giải tích lồi, giải tích biến phân và lý thuyết tối ưu hóa:

+---------------------------------------------------------------------------------------------------+
| HỆ THỐNG CÔNG CỤ VÀ KHUNG LÝ THUYẾT TRONG LUẬN ÁN                                                 |
+------------------------------+--------------------------------------------------------------------+
| Công cụ giải tích lồi:       | Phép chiếu mêtric P_K, nón pháp tuyến ngoài N_K, dưới vi phân \partial|
|                              | và \epsilon-dưới vi phân \partial_\epsilon, toán tử gần kề prox_{\lambda g}        |
+------------------------------+--------------------------------------------------------------------+
| Khái niệm đơn điệu song hàm: | Đơn điệu mạnh, đơn điệu chặt, đơn điệu, giả đơn điệu, para-đơn điệu|
+------------------------------+--------------------------------------------------------------------+
| Công cụ hàm suy rộng:        | Hàm tựa lồi, tựa lõm, tựa tuyến tính (De Finetti 1949),           |
|                              | dưới vi phân Clarke cho hàm Lipschitz địa phương                  |
+------------------------------+--------------------------------------------------------------------+
| Sơ đồ lặp điểm bất động:     | Phép lặp Picard, Mann, Krasnoselskii, Mann-Krasnoselskii           |
+------------------------------+--------------------------------------------------------------------+

Các khái niệm và mệnh đề giải tích cơ sở

  • Phép chiếu mêtric: Cho $K \subset \mathbb{R}^n$ lồi, đóng, khác rỗng. $P_K(x) = \text{argmin}_{z \in K} |z - x|$. Điểm $z = P_K(x) \iff \langle x - z, y - z \rangle \le 0, \forall y \in K$.
  • 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: \mathbb{R}^m \to \mathbb{R} \cup {+\infty}$, với $\lambda > 0$: $$\text{prox}{\lambda g}(u) = \text{argmin}{v \in \mathbb{R}^m} \left{ g(v) + \frac{1}{2\lambda} |v - u|^2 \right}$$
  • Hàm đánh giá khoảng cách khả vi: Luận án định nghĩa hàm: $$h(x) := \frac{1}{2}|(I - \text{prox}{\lambda g})Ax|^2$$ Hàm $h(x)$ luôn khả vi trên $\mathbb{R}^n$ với gradient $\nabla h(x) = A^*(I - \text{prox}{\lambda g})Ax$, và $h(x) = 0 \iff Ax \in \text{argmin}_{u \in \mathbb{R}^m} g(u)$.
  • Tính chất para-đơn điệu (Paramonotone): 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 với mọi $x \in S, y \in K$ thỏa mãn $f(x, y) = f(y, x) = 0$ thì kéo theo $y \in S$. Khái niệm này bao hàm tính chất đơn điệu chuẩn và được xây dựng bởi A. N. Iusem (1998, 2002).

Bổ đề bổ trợ chứng minh hội tụ

  • Bổ đề 1.1: Cho $x, y, z \in \mathbb{R}^n$ và $0 \le a \le 1$, ta có bất đẳng thức: $$|ax + (1-a)y - z|^2 \le a|x - z|^2 + (1-a)|y - z|^2$$
  • Bổ đề 1.2 (P. Scheimberg 2000): Cho ${v_k}$ và ${\delta_k}$ là các dãy số thực không âm thỏa mãn $v_{k+1} \le v_k + \delta_k$ với $\sum_{k=1}^{\infty} \delta_k < +\infty$. Khi đó dãy ${v_k}$ hội tụ.
  • Bổ đề 1.3 (L. D. Muu et al. 2008): Cho dãy số ${a_k} \subset (a, b) \subset (0, 1)$ và hai dãy ${v_k}, {w_k} \subset \mathbb{R}^n$ 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$ với $c > 0$. Khi đó $\lim_{k \to \infty} |v_k - w_k| = 0$.

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 gồm 5 phần cung cấp nền tảng lý thuyết cho toàn bộ luận án:

  1. Các khái niệm và kết quả cơ bản: Định nghĩa không gian Euclid $\mathbb{R}^n$, tích vô hướng, chuẩn, tập lồi, phép chiếu mêtric $P_K(x)$, nón pháp tuyến ngoài $N_K(x_0) = {w \in \mathbb{R}^n: \langle w, y - x_0 \rangle \le 0, \forall y \in K}$, hàm lồi, dưới vi phân $\partial f(x)$, $\epsilon$-dưới vi phân $\partial_\epsilon f(x)$, hàm tựa lồi (tập mức dưới lồi), hàm tựa tuyến tính (vừa tựa lồi vừa tựa lõm theo De Finetti 1949), tính nửa liên tục trên/dưới và các cấp độ đơ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).
  2. Bài toán cân bằng và các bài toán liên quan: Mô tả bài toán $EP(K, f)$ tìm $x^* \in K$ sao cho $f(x^*, y) \ge 0, \forall y \in K$. Phân tích chi tiết quy dẫn từ 6 lớp bài toán về bài toán cân bằng: bài toán tối ưu quy hoạch toán học ($f(x, y) = \phi(y) - \phi(x)$), bài toán điểm yên ngựa ($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 ($f(x, y) = \sum_{i \in I} (f_i(x[y_i]) - f_i(x))$), 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)]$).
  3. Bài toán chấp nhận tách: Định dạng bài toán SFP tìm $x^* \in C$ sao cho $Ax^* \in Q$, tập nghiệm $\Gamma = C \cap A^{-1}Q$, mối liên hệ với bài toán chấp nhận lồi (CFP), các mở rộng chấp nhận tách suy rộng (GSFP).
  4. Một số phương pháp lặp cơ bản tìm điểm bất động: Trình bày nguyên lý ánh xạ co Banach (lặp Picard), phương pháp lặp Mann ($x_{n+1} = (1 - \alpha_n)x_n + \alpha_n T x_n$), phương pháp lặp Krasnoselskii ($x_{n+1} = \frac{1}{2}(x_n + T x_n)$), và phương pháp lặp Mann-Krasnoselskii ($x_{n+1} = (1 - \alpha_n)x_n + \alpha_n T x_n$ với $0 < \alpha_n < 1$).
  5. Các kết quả bổ trợ: Thiết lập điều kiện cần và đủ cho cực tiểu bài toán tối ưu lồi $0 \in \partial f(x^) + N_K(x^)$ cùng hệ thống 3 bổ đề giải tích quan trọng.

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 giải quyết bài toán chấp nhận tách suy rộ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ồi đó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, $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ác giả thiết kỹ thuật

  • (A1): Với mỗi $x \in K$, $f(x, x) = 0$ và hàm $f(x, \cdot)$ lồi, nửa liên tục dưới trên $K$.
  • (A2): Tập $\partial_{2\epsilon} 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): Song hàm $f(\cdot, x)$ là nửa liên tục trên trên $K$ với mỗi $x \in K$.

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

  • Tham số và dãy số khởi tạo: Chọn $\delta, \xi > 0$ và các dãy số thực ${a_k}, {\delta_k}, {\beta_k}, {\epsilon_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^2 < +\infty, \quad \sum_{k=1}^{\infty} \epsilon_k < +\infty, \quad \sum_{k=1}^{\infty} \frac{\beta_k}{\delta_k} = +\infty$$
  • Bước 0: Chọn điểm xuất phát $x_1 \in K$, đặt $k := 1$.
  • Bước $k$ ($k \ge 1$): Đã có $x_k \in K$:
    1. Lấy $g_k \in \partial_{2\epsilon_k} f(x_k, x_k)$, đặt $\gamma_k = \max{\delta_k, |g_k|}$ và tính bước $\alpha_k = \frac{\beta_k}{\gamma_k}$.
    2. Thực hiện phép chiếu giải bài toán cân bằng: $$y_k = P_K(x_k - \alpha_k g_k) \iff \langle y_k - x_k + \alpha_k g_k, x - y_k \rangle \ge 0, \forall x \in K$$
    3. Thực hiện bước lặp hiệu chỉnh theo bài toán tối ưu lồi:
      • Nếu $\nabla h(y_k) \ne 0$: $z_k = P_K\left(y_k - \rho_k \frac{h(y_k)}{|\nabla h(y_k)|^2} \nabla h(y_k)\right)$
      • Nếu $\nabla h(y_k) = 0$: $z_k = y_k$
    4. Cập nhật điểm lặp theo sơ đồ Mann-Krasnoselskii: $$x_{k+1} = a_k x_k + (1 - a_k)z_k$$
    5. Đặt $k := k + 1$ và lặp lại.

Bổ đề đánh giá sai số (Bổ đề 2.3)

Với $z \in S$ (tập nghiệm của bài toán SEO):

  • Khi $\nabla h(y_k) \ne 0$: $$|x_{k+1} - z|^2 \le |x_k - z|^2 - (1 - a_k)\rho_k(4 - \rho_k)\frac{h^2(y_k)}{|\nabla h(y_k)|^2} + 2(1 - a_k)\alpha_k f(x_k, z) + A_k$$
  • Khi $\nabla h(y_k) = 0$: $$|x_{k+1} - z|^2 \le |x_k - z|^2 + 2(1 - a_k)\alpha_k f(x_k, z) + A_k$$ với $A_k = 2(1 - a_k)(\alpha_k \epsilon_k + \beta_k^2)$.

Định lý hội tụ (Định lý 2.1)

Luận án chứng minh dãy ${x_k}$ sinh bởi Thuật toán 2.1 hội tụ tới một nghiệm $x^* \in S$ thông qua chuỗi 5 khẳng định logic:

  • Khẳng định 1: Dãy số thực ${|x_k - z|^2}$ hội tụ với mọi $z \in S$, kéo theo ${x_k}$ và ${y_k}$ bị chặn trong $\mathbb{R}^n$.
  • Khẳng định 2: $\limsup_{k \to +\infty} f(x_k, z) = 0$ với mọi $z \in S$ nhờ tính chất phân kỳ $\sum \frac{\beta_k}{\delta_k} = +\infty$.
  • 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 bài toán cân bằng $S(K, f)$ (sử dụng tính para-đơn điệu và nửa liên tục trên của song hàm).
  • Khẳng định 4: Mọi điểm tụ $x^$ đều thỏa mãn $Ax^ \in \text{argmin}_{y \in \mathbb{R}^m} g(y)$ do $h(y_k) \to 0$.
  • 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$, dẫn đến $\lim_{k \to \infty} x_k = \lim_{k \to \infty} y_k = \lim_{k \to \infty} P_S(x_k) = x^* \in S$.

Phản ví dụ trường hợp vô nghiệm (Ví dụ 2.5)

Luận án chỉ ra rằng nếu tập nghiệm $S = K \cap Q = \emptyset$, dãy lặp có thể phân kỳ ra vô hạn:

  • Chọn $K = {(u, v) \in \mathbb{R}^2: u \ge 1, v \ge 1/u}$, $Q = {(u, v) \in \mathbb{R}^2: u \ge 1, v = 0}$, $A = I$, $f(x, y) = \delta_K(y) - \delta_K(x)$, $g(x) = \delta_Q(x)$.
  • Thiết lập tham số $\epsilon_k = 0, \beta_k = 1/k, \delta_k = 1, \rho_k = 2, a_k = 1/2$.
  • Dãy tọa độ thứ nhất thỏa mãn bất đẳng thức đệ quy $u_{k+1} \ge u_k + \frac{1}{32 u_k^3}$, dẫn đến $\lim_{k \to \infty} u_k = +\infty$ (dãy lặp không bị chặn).

Ứng dụng mô hình kinh tế năng lượng

Mô hình cân bằng bán độc quyền Nash-Cournot mở rộng cho hệ thống $n$ nhà máy phát điện (mỗi nhà máy $i$ có $I_i$ tổ máy phát, tổng số $N$ máy).

  • Giá điện phụ thuộc tổng sản lượng $s = \sum_{j=1}^N x_j$: $p_i(s) = \alpha - \beta_i s$.
  • 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)$, với $c_j$ là hàm chi phí sản xuất lồi tăng.
  • Ma trận $A = (a_{l, j})_{m \times N}$ quy định định mức tiêu hao nguyên vật liệu loại $l$ trên mỗi đơn vị điện của máy $j$.
  • Hàm $g(Ax)$ là tổng phí tổn ô nhiễm môi trường phát thải từ lượng vật liệu $Ax$.
  • Bài toán tìm phương án sản xuất $x^* \in K$ đạt cân bằng Nash đồng thời tối thiểu hóa phí môi trường $g(Ax^*)$ được mô hình hóa chính xác thành bài toán (SEO) và giải thành công 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 mở rộng bài toán chấp nhận tách sang trường hợp phi tuyến (NSEP): $$\text{Tìm } x^* \in C \text{ sao cho } F(x^*) \in Q$$ trong đó toán tử chuyển $F: \mathbb{R}^n \to \mathbb{R}^m$ không tuyến tính mà được cấu thành từ các hàm tựa tuyến tính $F(x) = (\phi_1(x), \phi_2(x), \dots, \phi_m(x))^T$.

Nội dung và đóng góp của chương

  1. Mô tả bài toán và phương pháp giải: Luận án chuyển bài toán NSEP về bài toán tối ưu tựa lồi không trơn. Bằng cách sử dụng dưới đạo hàm Clarke, tác giả xây dựng thuật toán dưới đạo hàm thích nghi cho phép xử lý trực tiếp tính phi tuyến của $F$ mà không cần tính đạo hàm Fréchet hay ma trận Jacobi chuyển vị $F'(x)^*$.
  2. Chứng minh sự hội tụ: Luận án thiết lập định lý hội tụ toàn cục cho dãy lặp dưới các điều kiện giảm dần của độ dài bước và tính chất tựa lồi của các hàm thành phần.
  3. Ứng dụng mô hình cân bằng Nash có ràng buộc chung (Joint Constraints): Mô hình hóa bài toán cạnh tranh thị trường nơi các chiến lược của các đấu thủ bị ràng buộc bởi giới hạn tài nguyên chia sẻ chung. Luận án thực hiện các thử nghiệm số trên máy tính, phân tích tốc độ hội tụ và so sánh hiệu năng trực tiếp với các thuật toán tối ưu hóa đã có.

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

Luận án đạt được các kết quả khoa học nguyên gốc đã được công bố trên các tạp chí quốc tế chuyên ngành (gồm 2 bài báo ISI trên Mathematical Methods of Operations Research và Journal of Global Optimization):

+---------------------------------------------------------------------------------------------------+
| TỔNG HỢP NHỮNG ĐÓNG GÓP MỚI CỦA LUẬN ÁN                                                           |
+----------------------+----------------------------------------------------------------------------+
| Đóng góp lý luận 1:  | Đề xuất thuật toán chiếu một lần 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 (SEO) giữa bài toán cân bằng para-đơn điệu|
|                      | và bài toán tối ưu lồi.                                                    |
+----------------------+----------------------------------------------------------------------------+
| Đóng góp lý luận 2:  | Chứng minh định lý hội tụ mạnh/yếu mà không đòi hỏi đơn điệu mạnh của song |
|                      | hàm hay tính khả vi của hàm mục tiêu g, vượt qua giới hạn của phương pháp  |
|                      | đạo hàm tăng cường hai lần chiếu.                                          |
+----------------------+----------------------------------------------------------------------------+
| Đóng góp lý luận 3:  | Xây dựng thuật toán dưới đạo hàm Clarke giải bài toán chấp nhận tách       |
|                      | phi tuyến (NSEP) cho toán tử tựa tuyến tính.                               |
+----------------------+----------------------------------------------------------------------------+
| Đóng góp thực tiễn:  | Ứng dụng thành công vào mô hình cân bằng Nash-Cournot sản xuất điện gắn với |
|                      | chi phí môi trường và mô hình trò chơi Nash có ràng buộc chung.            |
+----------------------+----------------------------------------------------------------------------+

Chi tiết các đóng góp mới

  1. Về mặt thuật toán tuyến tính suy rộng: Thiết kế thành công sơ đồ lặp chỉ yêu cầu một phép chiếu mêtric lên tập ràng buộc $K$ ở mỗi bước lặp bài toán cân bằng, kết hợp với phép chiếu hiệu chỉnh theo hướng gradient của hàm khoảng cách $h(x)$ tạo bởi toán tử gần kề $\text{prox}_{\lambda g}$. Điều này giảm đáng kể khối lượng tính toán so với các phương pháp đạo hàm tăng cường truyền thống vốn đòi hỏi hai phép chiếu tốn kém trên tập nghiệm ẩn.
  2. Về mặt giải tích hội tụ: Mở rộng lớp song hàm cân bằng từ giả đơn điệu sang para-đơn điệu. Sử dụng kỹ thuật xấp xỉ $\epsilon$-dưới vi phân và dãy tham số bước triệt tiêu linh hoạt, luận án chứng minh sự hội tụ của thuật toán mà không cần giả thiết tập nghiệm bị chặn tiên nghiệm.
  3. Về mặt bài toán phi tuyến: Thiết lập khung 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ử tựa tuyến tính, phá vỡ thế bế tắc của các nghiên cứu trước vốn phụ thuộc hoàn toàn vào cấu trúc tuyến tính của toán tử chuyển.

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

Dựa trên nội dung văn bản và phạm vi nghiên cứu, luận án ghi nhận một số giới hạn và định hướng mở rộng:

Hạn chế

  • Không gian khảo sát: Các kết quả chính và thuật toá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$.
  • Cấu trúc tính toán: Thuật toán ở Chương 2 đòi hỏi phải tính chính xác phép chiếu mêtric $P_K$ lên tập lồi $K$ tại mỗi bước lặp; khi $K$ có cấu trúc hình học phức tạp, chi phí tính toán hình chiếu có thể tăng cao.
  • Phạm vi toán tử phi tuyến: Thuật toán phi tuyến trong Chương 3 tập trung chủ yếu vào lớp ánh xạ tựa tuyến tính cấu thành từ các hàm tựa lồi/tựa lõm.

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

  • Mở rộ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 sang không gian Hilbert vô hạn chiều hoặc không gian Banach lồi đều.
  • Nghiên cứu các thuật toán dạng chiếu dưới siêu phẳng hoặc phương pháp chiếu không khớp (inexact projection) để giảm thiểu chi phí tính toán phép chiếu mêtric $P_K$.
  • Mở rộng nghiên cứu cho các lớp bài toán chấp nhận tách phi tuyến với toán tử chuyển tổng quát hơn (như toán tử đơn điệu đa trị, toán tử nửa liên tục yếu).

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên khảo có giá trị cao đối với nhiều đối tượng trong nghiên cứu và đào tạo:

+---------------------------------------------------------------------------------------------------+
| ĐỐI TƯỢNG VÀ ĐỊA CHỈ THAM KHẢO CHUYÊN MÔN                                                         |
+------------------------------------+--------------------------------------------------------------+
| Nghiên cứu sinh & Học viên Cao học:| Nguồn tài liệu chuẩn mực về kỹ thuật chứng minh hội tụ giải  |
| chuyên ngành Toán Giải tích/Tối ưu:| tích lồi, phép lặp Mann-Krasnoselskii, kỹ thuật xấp xỉ dãy   |
|                                    | Cauchy trong không gian Euclid (Chương 1 và Chương 2).        |
+------------------------------------+--------------------------------------------------------------+
| Giảng viên & Nhà nghiên cứu        | Tham khảo phương pháp xây dựng toán tử gần kề kết hợp bài toán|
| Toán Ứng dụng:                     | cân bằng và kỹ thuật dưới đạo hàm Clarke cho bài toán phi    |
|                                    | tuyến (Chương 2 và Chương 3).                                |
+------------------------------------+--------------------------------------------------------------+
| Chuyên gia Kinh tế Năng lượng &    | Khung mô hình hóa bài toán cân bằng thị trường điện cạnh     |
| Hoạch định Chính sách Môi trường:  | tranh gắn với giới hạn phát thải và tối ưu hóa chi phí môi   |
|                                    | trường (Mục 2.2 Chương 2 và Mục 3.3 Chương 3).               |
+------------------------------------+--------------------------------------------------------------+

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

1. Bài toán (SEO) trong Chương 2 của luận án được phát biểu như thế nào và có cấu trúc gì đặc thù?

Trả lời: Bài toán (SEO) là bài toán chấp nhận tách suy rộng tìm điểm $x^* \in K \subset \mathbb{R}^n$ thỏa mãn đồng thời hai điều kiện:

  1. $x^$ là nghiệm của bài toán cân bằng: $f(x^, y) \ge 0, \forall y \in K$.
  2. Ảnh của $x^$ qua toán tử tuyến tính $A$ là nghiệm của bài toán tối ưu lồi trong $\mathbb{R}^m$: $g(Ax^) \le g(u), \forall u \in \mathbb{R}^m$.

Đặc thù của bài toán là hai tập ràng buộc đều được cho dưới dạng ẩn (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 quy hoạch lồi).

2. Thuật toán 2.1 kết hợp các kỹ thuật lặp nào để giải bài toán (SEO)?

Trả lời: Thuật toán 2.1 tích hợp 3 kỹ thuật cốt lõi trong một vòng lặp duy nhất:

  1. Phép chiếu mêtric một lần giải bài toán cân bằng: $y_k = P_K(x_k - \alpha_k g_k)$ với $g_k \in \partial_{2\epsilon_k} f(x_k, x_k)$.
  2. Phép chiếu hiệu chỉnh giải bài toán tối ưu lồi thông qua gradient của hàm khoảng cách khả vi $h(y) = \frac{1}{2}|(I - \text{prox}_{\lambda g})Ay|^2$.
  3. Sơ đồ cập nhật điểm lặp Mann-Krasnoselskii: $x_{k+1} = a_k x_k + (1 - a_k)z_k$ với $a_k \in (a, b) \subset (0, 1)$.

3. Song hàm cân bằng $f$ trong Chương 2 cần thỏa mãn những giả thiết gì để đảm bảo sự hội tụ của thuật toán?

Trả lời: Theo văn bản luận án, song hàm $f$ cần thỏa mãn 4 giả thiết (A1)-(A4):

  • (A1): $f(x, x) = 0$ và $f(x, \cdot)$ lồi, nửa liên tục dưới trên $K$ với mọi $x \in K$.
  • (A2): $\partial_{2\epsilon} f(x, x)$ bị chặn trên mọi tập con bị chặn của $K$.
  • (A3): $f$ là para-đơn điệu trên $K$ đối với tập nghiệm $S(K, f)$ (tức nếu $x \in S(K, f), y \in K$ và $f(x, y) = f(y, x) = 0$ thì $y \in S(K, f)$).
  • (A4): $f(\cdot, x)$ nửa liên tục trên trên $K$ với mọi $x \in K$.

4. Tại sao các thuật toán chiếu giải bài toán chấp nhận tách truyền thống không áp dụng được cho trường hợp toán tử chuyển phi tuyến trong Chương 3?

Trả lời: Các thuật toán chiếu kinh điển (như thuật toán CQ của Byrne) đòi hỏi phải tính được toán tử chuyển vị $A^*$ hoặc ma trận nghịch đảo $A^{-1}$, điều này chỉ thực hiện được khi $A$ là toán tử tuyến tính. Khi chuyển bài toán về dạng tối ưu hóa cực tiểu hàm khoảng cách $\frac{1}{2\lambda}|(I - P_Q)(Ax)|^2$, hàm này chỉ đảm bảo tính lồi và khả vi khi $A$ tuyến tính. Với toán tử phi tuyến, hàm khoảng cách mất tính lồi và khả vi thông thường, buộc luận án phải xây dựng thuật toán dưới đạo hàm Clarke cho hàm tựa lồi/tựa tuyến tính.

5. Yếu tố chi phí môi trường được tích hợp vào mô hình sản xuất điện Nash-Cournot ở Chương 2 như thế nào?

Trả lời: Trong mô hình mở rộng của luận án, để sản xuất lượng điện $x$, các nhà máy phải tiêu thụ lượng nguyên vật liệu được biểu diễn qua ma trận chuyển $Ax$ (với hàng $l$ là tổng lượng vật liệu loại $l$). Việc sử dụng vật liệu gây phát thải ô nhiễm và các nhà máy phải nộp khoản phí môi trường $g(Ax)$, trong đó $g$ là hàm lồi tăng. Mô hình đưa về việc tìm sản lượng $x^$ vừa là điểm cân bằng Nash giữa các nhà máy điện, vừa đạt mức chi phí môi trường thấp nhất toàn hệ thống ($g(Ax^) \le g(Ax), \forall x \in K$).

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 thành công bài toán chấp nhận tách suy rộng kết hợp giữa bài toán cân bằng para-đơn điệu và bài toán quy hoạch lồi thông qua thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii. Công trình cũng mở rộng phạm vi nghiên cứu sang bài toán chấp nhận tách phi tuyến với toán tử tựa tuyến tính bằng phương pháp dưới đạo hàm Clarke. Toàn bộ các định lý hội tụ đều được chứng minh chặt chẽ về mặt toán học và được minh họa tính khả thi thông qua các mô hình cân bằng kinh tế năng lượng và môi trường thực tiễn.