Tổng quan luận án

Bản luận án tiến sĩ toán học với đề tài "Thuật toán giải một số lớp bài toán cân bằng và điểm bất động" được thực hiện bởi nghiên cứu sinh Nguyễn Thị Thanh Hà, dưới sự hướng dẫn khoa học của TS. Bùi Văn Định và TS. Đào Trọng Quyết, tại Bộ môn Toán, Khoa Công nghệ Thông tin, Học viện Kỹ thuật Quân sự (Hà Nội, 2021). Luận án thuộc chuyên ngành Toán ứng dụng, mã số đào tạo 9 46 01 12.

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

Thuật ngữ "cân bằng" (equilibrium) giữ vai trò trung tâm trong nhiều ngành khoa học tự nhiên, kỹ thuật và kinh tế học: từ cân bằng cơ học, cân bằng thủy tĩnh trong vật lý; cân bằng động lực phản ứng thuận nghịch trong hóa học; cân bằng di truyền quần thể trong sinh học; đến phân bố lưu lượng mạng giao thông - viễn thông trong kỹ thuật và lý thuyết cân bằng cung - cầu - giá cả (cân bằng riêng, cân bằng chung) trong kinh tế học. Đặc biệt, sự ra đời của lý thuyết trò chơi và khái niệm cân bằng Nash đã mở rộng phạm vi của lý thuyết cân bằng sang vận trù học và quy hoạch toán học.

Về mặt toán học, bài toán cân bằng tổng quát theo nghĩa Blum - Oettli hay bất đẳng thức Ky Fan, ký hiệu $EP(C, f)$, có dạng: $$\text{Tìm } x^* \in C \text{ sao cho } f(x^*, y) \ge 0, \quad \forall y \in C$$ trong đó $H$ là không gian Hilbert thực, $C \subset H$ là tập lồi đóng khác rỗng, và $f: C \times C \to \mathbb{R}$ là song hàm cân bằng thỏa mãn $f(x, x) = 0, \forall x \in C$. Cấu trúc này hợp nhất nhiều lớp bài toán quan trọng như: bài toán tối ưu hóa ($OP$), bất đẳng thức biến phân đơn trị ($VIP$) và đa trị ($MVIP$), bài toán điểm bất động ($FP, MFP$), bài toán điểm yên ngựa, và mô hình cân bằng Nash ($NEP$) trong trò chơi không hợp tác.

Qua khảo cứu tài liệu chuyên ngành, tác giả xác định ba khoảng trống nghiên cứu lý thuyết và giải thuật thực tế:

  1. Bài toán cân bằng không đơn điệu: Phần lớn các thuật toán giải bài toán cân bằng hiện có (phương pháp hàm đánh giá, phương pháp nguyên lý bài toán phụ, điểm gần kề, hiệu chỉnh Tikhonov, đạo hàm tăng cường...) đều đòi hỏi song hàm $f$ phải thỏa mãn tính đơn điệu hoặc đơn điệu suy rộng (đơn điệu mạnh, đơn điệu chặt, giả đơn điệu). Tuy nhiên, nhiều bài toán cân bằng nảy sinh trong thực tế kinh tế (như mô hình thị trường điện Nash-Cournot) có song hàm không đơn điệu. Các thuật toán kiểu chiếu giải bài toán không đơn điệu còn rất hạn chế.
  2. Mối quan hệ giữa hệ bài toán cân bằng và bài toán cân bằng tổ hợp: Để giải bài toán tìm nghiệm chung của một họ bài toán cân bằng $CSEP(C, f_i)$, một số công trình quốc tế gần đây (tiêu biểu như S. Kangtunyakarn và cộng sự) đã chuyển về bài toán cân bằng tổ hợp $CEP(C, \sum \alpha_i f_i)$ dựa trên khẳng định rằng tập nghiệm của hai bài toán này trùng nhau khi các song hàm $f_i$ đơn điệu. Luận án phát hiện giả thiết tính đơn điệu là chưa đủ để thiết lập đẳng thức tập nghiệm và cần xác lập lại điều kiện đủ chính xác.
  3. Bài toán tìm nghiệm chung của bài toán cân bằng và điểm bất động: Các thuật toán hiện hành (chẳng hạn thuật toán HSEM của D. Hieu) kết hợp phương pháp đạo hàm tăng cường với phép lặp Halpern/Mann đòi hỏi tham số bước $\lambda$ phải thỏa mãn $0 < \lambda < \min{\frac{1}{2c_1}, \frac{1}{2c_2}}$, phụ thuộc trực tiếp vào các hằng số kiểu Lipschitz $c_1, c_2$ của song hàm $f$. Khi các hằng số này không biết hoặc khó ước lượng, thuật toán không thể áp dụng trực tiếp.

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

Luận án tập trung giải quyết 3 mục tiêu nghiên cứu cụ thể sau đây (được đánh số theo nguyên văn tác giả):

  • (i) Xây dựng thuật toán giải bài toán cân bằng không đơn điệu.
  • (ii) Nghiên cứu mối quan hệ giữa tập nghiệm của bài toán cân bằng tổ hợp với giao các tập nghiệm của các bài toán cân bằng.
  • (iii) Thiết lập phương pháp tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động.

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

  • Đối tượng nghiên cứu:
    • Lớp bài toán cân bằng $EP(C, f)$ với song hàm không đơn điệu.
    • Họ bài toán cân bằng $CSEP(C, f_i)$ và bài toán cân bằng tổ hợp $CEP(C, \sum \alpha_i f_i)$ với họ chỉ số hữu hạn hoặc vô hạn đếm được.
    • Bài toán tìm nghiệm chung $S = Sol(C, f) \cap Fix(T)$ của bài toán cân bằng $EP(C, f)$ với song hàm giả đơn điệu kiểu Lipschitz và bài toán điểm bất động $FP(C, T)$ của ánh xạ tựa không giãn $T$.
  • Phạm vi không gian và thời gian: Không gian Hilbert thực $H$ (bao gồm không gian Euclide hữu hạn chiều $\mathbb{R}^n$ và không gian Hilbert vô hạn chiều), trên tập con lồi, đóng, khác rỗng $C \subset H$. Các kết quả và thực nghiệm số được hoàn thành và bảo vệ trong năm 2021.

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

Các hướng nghiên cứu tiền đề

Luận án tiến hành phân loại và điểm lại các hệ thống công trình nghiên cứu đi trước:

  • Về lý thuyết nền tảng và tính tồn tại nghiệm của bài toán cân bằng: Dựa trên các công trình khởi xướng của Blum và Oettli [14], bất đẳng thức Ky Fan [27], cùng các nghiên cứu về cấu trúc và tính ổn định nghiệm của M. Bigi và cộng sự [12, 13], B. T. Kien, L. D. Muu [62], P. Q. Khanh, N. X. Tan.
  • Về các phương pháp giải bài toán cân bằng lồi và đơn điệu: Các thuật toán hàm đánh giá (gap function) của M. Fukushima, I. V. Konnov [53]; phương pháp nguyên lý bài toán phụ (auxiliary subproblem principle) [54]; phương pháp điểm gần kề (proximal point method) của A. Moudafi [55]; phương pháp hiệu chỉnh Tikhonov [25, 73]; phương pháp chiếu (projection methods) [24]; và phương pháp đạo hàm tăng cường (extragradient method) của P. Santos, S. Scheimberg [8].
  • Về bài toán cân bằng không đơn điệu: Các nghiên cứu bước đầu về thuật toán kiểu chiếu của Y. Censor, A. Gibali, S. Reich [21], L. C. Ceng [65], và Y. Yao [85]. Trong không gian $\mathbb{R}^n$, D. Tran và cộng sự [62, Algorithm 2a] kết hợp thuật toán đạo hàm tăng cường [43] với quy tắc tìm kiếm tia Armijo [9] để giải bài toán giả đơn điệu không kiểu Lipschitz.
  • Về phương pháp chiếu nhúng (shrinking projection method): Được W. Takahashi, Y. Takeuchi, R. Kubota [70] đề xuất để tìm điểm bất động của ánh xạ không giãn trong không gian Hilbert.
  • Về bài toán tìm nghiệm chung của họ bài toán cân bằng: Các công trình của S. Kangtunyakarn và cộng sự [41, 42, 66, 67, 68], cùng các bài báo [5, 6, 30, 78], nghiên cứu sự liên hệ giữa $CSEP$ và $CEP$.
  • Về các phương pháp lặp tìm điểm bất động: Định lý điểm bất động Banach cho ánh xạ co; phép lặp Mann [52] cho ánh xạ không giãn; phép lặp Ishikawa [34] cho ánh xạ Lipschitz giả co; và phép lặp Halpern [29] đảm bảo tính hội tụ mạnh cho ánh xạ không giãn.
  • Về bài toán tìm nghiệm chung của bài toán cân bằng và điểm bất động: Các công trình của L. C. Ceng [16], B. Dinh và cộng sự [23], T. Thuy và cộng sự [75], N. Vuong và cộng sự [78]. Đặc biệt, công trình của D. Hieu [31] đề xuất thuật toán dưới đạo hàm tăng cường Halpern (HSEM) cho song hàm giả đơn điệu kiểu Lipschitz và ánh xạ $\kappa$-nửa co.

Vị trí và đóng góp học thuật của luận án

  1. Mở rộng hướng giải bài toán cân bằng không đơn điệu bằng cách kết hợp kỹ thuật chiếu nhúng với tìm kiếm theo tia kiểu Armijo, thiết lập tính hội tụ mạnh trong không gian Hilbert thực vô hạn chiều.
  2. Đóng vai trò phản biện học thuật đối với các kết quả trong [41, 42, 66, 67, 68]: Luận án chỉ ra bằng phản ví dụ rằng điều kiện tính đơn điệu là chưa đủ để có $\bigcap_{i=1}^N Sol(C, f_i) = Sol(C, \sum_{i=1}^N \alpha_i f_i)$, đồng thời xây dựng bổ sung điều kiện đủ chuẩn xác cho cả trường hợp hữu hạn và vô hạn các song hàm.
  3. Cải tiến cấu trúc thuật toán giải bài toán nghiệm chung $Sol(C, f) \cap Fix(T)$: Khắc phục triệt để nhược điểm phải biết trước hằng số Lipschitz $c_1, c_2$ của thuật toán HSEM [31] bằng cách kết hợp phương pháp dưới đạo hàm tăng cường với quy tắc lặp Ishikawa cho lớp ánh xạ tựa không giãn.

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

Luận án vận dụng hệ thống giải tích lồi, giải tích hàm, lý thuyết tối ưu và lý thuyết điểm bất động trong không gian Hilbert thực $H$:

  • Tập hợp và phép chiếu: Nón pháp tuyến ngoài của tập lồi $C$ tại $x_0 \in C$ là $N_C(x_0) = {w \in H : \langle w, x - x_0 \rangle \le 0, \forall x \in C}$. Phép chiếu vuông góc $P_C(x) = \arg\min{|x - y| : y \in C}$ có tính chất đặc trưng: $z = P_C(x) \Leftrightarrow \langle x - z, y - z \rangle \le 0, \forall y \in C$.
  • Hàm số và dưới vi phân: Khái niệm hàm lồi, lồi chặt, lồi mạnh hệ số $\beta > 0$, tựa lồi, hàm chính thường, nửa liên tục dưới/trên, và liên tục yếu đồng thời trên tích Descartes. Dưới vi phân của hàm lồi chính thường $f$ tại $x$ là $\partial f(x) = {w \in H : f(y) \ge f(x) + \langle w, y - x \rangle, \forall y \in H}$. Điều kiện cực tiểu hóa: $x_0 \in \arg\min_{x \in C} f(x) \Leftrightarrow 0 \in \partial f(x_0) + N_C(x_0)$.
  • Phân loại tính đơn điệu của song hàm cân bằng $f$:
    • Đơn điệu mạnh hệ 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$ với mọi $x \neq y$.
    • Đơn điệu: $f(x, y) + f(y, x) \le 0$.
    • Giả đơn điệu: $f(x, y) \ge 0 \Rightarrow f(y, x) \le 0$.
    • Điều kiện kiểu Lipschitz: tồn tại $c_1 > 0, 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$.
  • Phân loại ánh xạ $T: C \to H$: Ánh xạ co (hệ số $\tau \in (0, 1)$), ánh xạ không giãn ($|T(x) - T(y)| \le |x - y|$), ánh xạ Lipschitz (hằng số $L > 0$), ánh xạ tựa không giãn ($|T(x) - y| \le |x - y|, \forall x \in C, y \in Fix(T)$), ánh xạ giả co và ánh xạ $\kappa$-nửa co ($\kappa \in [0, 1)$).

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

  • Phương pháp chiếu nhúng kết hợp tìm kiếm theo tia (Armijo linesearch): Sử dụng để giải bài toán cân bằng không đơn điệu. Thay vì chiếu trực tiếp lên tập ràng buộc $C$, thuật toán xây dựng các nửa không gian thu hẹp $C_{k+1} \subset C_k$ và chiếu điểm ban đầu $x_g$ lên $C_{k+1}$ nhằm ép dãy lặp hội tụ mạnh.
  • Phương pháp phản ví dụ và kỹ thuật giải tích lồi: Xây dựng phản ví dụ tường minh để bác bỏ các định lý chưa đủ điều kiện trong y văn; vận dụng giải tích đa trị và nón pháp tuyến để thiết lập các điều kiện đủ mới.
  • Phương pháp dưới đạo hàm tăng cường (subgradient extragradient) kết hợp lặp Ishikawa: Cho phép giảm khối lượng tính toán (chỉ giải 1 bài toán tối ưu trên $C$ thay vì 2 bài toán như thuật toán đạo hàm tăng cường cổ điển) và thích ứng tự động với các bước lặp không cần biết trước hằng số Lipschitz.
  • Phương pháp mô phỏng số và thực nghiệm tính toán: Lập trình trên môi trường MATLAB R2014a chạy trên máy tính xách tay cấu hình CPU Intel(R) Core(TM) i5-3230M @ 2.60 GHz, RAM 4GB.

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 này hệ thống hóa các khái niệm, bổ đề và định lý nền tảng làm công cụ cho các chương sau:

  • Mục 1.1 (Một số khái niệm và kết quả cơ bản): Trình bày cấu trúc không gian Hilbert thực, khái niệm hội tụ mạnh ($x^k \to x^$), hội tụ yếu ($x^k \rightharpoonup x^$), nón lồi, nón pháp tuyến ngoài $N_C(x)$, tính chất duy nhất và tính chất biến phân của phép chiếu $P_C(x)$, cùng các định lý về dưới vi phân và điều kiện tối ưu Fermat.
  • Mục 1.2 (Bài toán cân bằng và sự tồn tại nghiệm): Thiết lập dạng thức của bài toán $EP(C, f)$ và bài toán Minty $MEP(C, f)$. Trình bày chi tiết cách quy đổi 5 bài toán chuyên biệt về bài toán cân bằng:
    1. Bài toán tối ưu: $f(x, y) = \phi(y) - \phi(x)$.
    2. Bất đẳng thức biến phân đơn trị: $f(x, y) = \langle F(x), y - x \rangle$.
    3. Bất đẳng thức biến phân đa trị: $f(x, y) = \max_{u \in F(x)} \langle u, y - x \rangle$.
    4. Bài toán điểm bất động đơn trị và đa trị: $f(x, y) = \langle x - F(x), y - x \rangle$ hoặc $f(x, y) = \max_{u \in F(x)} \langle x - u, y - x \rangle$.
    5. Mô hình cân bằng Nash: $f(x, y) = \sum_{i \in I} [f_i(x[y_i]) - f_i(x)]$. Trình bày các điều kiện tồn tại nghiệm dưới các giả thiết $(G_1)$ (nửa liên tục trên theo biến 1), $(G_2)$ (tựa lồi theo biến 2), $(G_3)$ (nửa liên tục dưới theo biến 2) và tính com-pắc của $C$ hoặc điều kiện bức bức (coercivity).
  • Mục 1.3 (Bài toán điểm bất động và một số phương pháp tìm điểm bất động): Nhắc lại định lý Banach; phân tích sự thất bại của phép lặp đơn $x^{n+1} = T(x^n)$ qua ví dụ phép quay $Q_O^\alpha$ trên $\mathbb{R}^2$; giới thiệu lược đồ lặp Mann ($x^{k+1} = (1 - \alpha_k)x^k + \alpha_k T(x^k)$), lược đồ Ishikawa ($x^{k+1} = \alpha_k T(\beta_k T(x^k) + (1 - \beta_k)x^k) + (1 - \alpha_k)x^k$), và lược đồ Halpern ($x^{k+1} = \alpha_k x_0 + (1 - \alpha_k)T(x^k)$).

Chương 2. Một số thuật toán giải bài toán cân bằng không đơn điệu

Chương này giải quyết bài toán $EP(C, f)$ khi $f$ không thỏa mãn tính đơn điệu trên tập lồi mở $\Omega \supset C$, chỉ cần đáp ứng hai giả thiết:

  • $(B_1)$ $f(x, \cdot)$ lồi trên $\Omega$ với mọi $x \in C$.
  • $(B_2)$ $f$ liên tục yếu đồng thời trên $\Omega \times \Omega$.

Tác giả đề xuất hai thuật toán hội tụ mạnh dựa trên sự kết hợp giữa thuật toán đạo hàm tăng cường [62] và phương pháp chiếu nhúng [70]:

Thuật toán 2.1

  1. Khởi tạo: Chọn $x^0 = x_g \in C$, tham số $\eta, \mu \in (0, 1)$, $0 < \underline{\rho} \le \bar{\rho}$, dãy ${\rho_k} \subset [\underline{\rho}, \bar{\rho}]$, $\gamma_k \in [\underline{\gamma}, \bar{\gamma}] \subset (0, 2)$, và đặt $C_0 = C$.
  2. Bước 1: Giải bài toán quy hoạch lồi mạnh tìm nghiệm duy nhất: $$y^k = \arg\min \left{ f(x^k, y) + \frac{1}{2\rho_k} |y - x^k|^2 : y \in C \right}$$ Nếu $y^k = x^k$, dừng thuật toán ($x^k \in Sol(C, f)$). Nếu không, chuyển Bước 2.
  3. Bước 2 (Tìm kiếm tia kiểu Armijo): Tìm số nguyên không âm nhỏ nhất $m_k$ thỏa mãn: $$f(z^{k, m_k}, x^k) - f(z^{k, m_k}, y^k) \ge \frac{\mu}{2\rho_k} |y^k - x^k|^2$$ với $z^{k, m_k} = (1 - \eta^{m_k})x^k + \eta^{m_k} y^k$. Đặt $\eta_k = \eta^{m_k}, z^k = z^{k, m_k}$.
  4. Bước 3: Lấy $w^k \in \partial_2 f(z^k, x^k)$, tính $\sigma_k = \frac{f(z^k, x^k)}{|w^k|^2}$, và tính: $$u^k = P_C(x^k - \gamma_k \sigma_k w^k)$$
  5. Bước 4 (Chiếu nhúng): Xây dựng tập thu hẹp: $$C_{k+1} = {x \in C_k : |x - u^k| \le |x - x^k|}$$ Tính $x^{k+1} = P_{C_{k+1}}(x_g)$. Tăng $k := k + 1$ và quay lại Bước 1.

Thuật toán 2.2

Thay đổi quy tắc tìm kiếm tia tại Bước 2: Tìm $m_k$ sao cho $f(z^{k, m_k}, y^k) \le -\frac{\mu}{2\rho_k} |y^k - x^k|^2$. Nếu $0 \in \partial_2 f(z^k, z^k)$ thì $z^k \in Sol(C, f)$ và dừng lại. Ngược lại, chọn $w^k \in \partial_2 f(z^k, z^k)$, đặt $\sigma_k = -\frac{f(z^k, y^k)}{|w^k|^2}$, tính $u^k = P_C(x^k - \gamma_k \sigma_k w^k)$ và cập nhật tập $C_{k+1}$ tương tự.

Định lý hội tụ (Định lý 2.9 và Định lý 2.12): Dưới các giả thiết $(B_1), (B_2)$ và giả thiết tập nghiệm Minty $S_M \neq \emptyset$, các dãy ${x^k}$ và ${u^k}$ sinh bởi Thuật toán 2.1 và Thuật toán 2.2 hội tụ mạnh trong không gian Hilbert tới nghiệm $x^* = P_{\bigcap_{k=0}^\infty C_k}(x_g) \in Sol(C, f)$.

Ứng dụng mô phỏng số: Mô hình cân bằng thị trường điện bán độc quyền Nash-Cournot

Mô hình gồm $n_c = 3$ công ty sản xuất điện và $n_g = 6$ đơn vị phát điện:

  • Công ty 1 sở hữu đơn vị ${1}$.
  • Công ty 2 sở hữu đơn vị ${2, 3}$.
  • Công ty 3 sở hữu đơn vị ${4, 5, 6}$.

Hàm giá điện affine giảm: $p(x) = 378 - \sum_{i=1}^{n_g} x_i$. Lợi nhuận của công ty $i$ là $f_i(x) = p(\sigma) \sum_{j \in I_i} x_j - \sum_{j \in I_i} c_j(x_j)$, với hàm chi phí phi tuyến $c_j(x_j) = \max{c_{0j}(x_j), c_{1j}(x_j)}$, trong đó: $$c_{0j}(x_j) = \frac{\alpha_{j0}}{2} x_j^2 + \beta_{j0} x_j + \gamma_{j0}, \quad c_{1j}(x_j) = \alpha_{j1} x_j + \frac{\beta_{j1}}{\beta_{j1}+1} \gamma_{j1}^{-1/\beta_{j1}} (x_j)^{(\beta_{j1}+1)/\beta_{j1}}$$

Khi biểu diễn dưới dạng bài toán cân bằng $EP(C, f)$, song hàm có dạng: $$f(x, y) = [(A + B)x + By + a]^T (y - x) + c(y) - c(x)$$ với $f(x, y) + f(y, x) = -(y - x)^T A (y - x)$. Do ma trận $A$ không nửa xác định dương nên song hàm $f$ không đơn điệu.

Bảng dữ liệu giới hạn sản lượng của các đơn vị phát điện (Bảng 2.1 trong văn bản):

Công ty (Com.) Đơn vị phát (Gen.) $x_{g\min}$ $x_{g\max}$ $x_{c\min}$ $x_{c\max}$
1 1 0 80 0 80
2 2 0 80 0 130
2 3 0 50 0 130
3 4 0 55 0 125
3 5 0 30 0 125
3 6 0 40 0 125

Thuật toán 2.1 được thực thi trên MATLAB R2014a, tiêu chuẩn dừng kiểm tra: $$\frac{|x^{k+1} - x^k|}{\max{1, |x^k|}} \le 10^{-3}$$ Kết quả chứng minh thuật toán hội tụ ổn định về điểm cân bằng sản lượng điện với các điểm khởi tạo và tham số khác nhau.

Chương 3. Hệ bài toán cân bằng và bài toán cân bằng tổ hợp

Chương này tập trung làm rõ mối quan hệ cấu trúc giữa tập nghiệm của bài toán tìm nghiệm chung $CSEP(C, f_i)$: $$\text{Tìm } x^* \in C \text{ sao cho } f_i(x^, y) \ge 0, \quad \forall y \in C, \forall i \in I$$ và bài toán cân bằng tổ hợp $CEP(C, \sum_{i \in I} \alpha_i f_i)$: $$\text{Tìm } x^ \in C \text{ sao cho } \sum_{i \in I} \alpha_i f_i(x^*, y) \ge 0, \quad \forall y \in C$$ với $\alpha_i \in (0, 1)$ và $\sum_{i \in I} \alpha_i = 1$.

  • Phản biện khoa học (Mục 3.1): Luận án phân tích khẳng định trong công trình [66] của S. Kangtunyakarn và các bài báo liên quan [41, 42, 67, 68] cho rằng khi $I = {1, 2, \dots, N}$ hữu hạn và các $f_i$ đơn điệu thì $\bigcap_{i=1}^N Sol(C, f_i) = Sol(C, \sum_{i=1}^N \alpha_i f_i)$. Bằng cách đưa ra phản ví dụ cụ thể trong không gian $\mathbb{R}^n$, tác giả chỉ ra rằng tính đơn điệu không đủ để suy ra sự bằng nhau của hai tập nghiệm (tập nghiệm tổ hợp có thể chứa các điểm không thuộc giao các tập nghiệm thành phần).
  • Thiết lập điều kiện đủ mới (Mục 3.2): Bằng các kỹ thuật giải tích lồi, tác giả thiết lập hệ điều kiện đủ để đẳng thức tập nghiệm $\bigcap_{i \in I} Sol(C, f_i) = Sol(C, \sum_{i \in I} \alpha_i f_i)$ xảy ra, mở rộng thành công từ trường hợp hữu hạn ($N$ song hàm) sang trường hợp vô hạn đếm được các song hàm $f_i$ ($i = 1, 2, \dots$).

Chương 4. Một thuật toán tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động

Chương này xây dựng phương pháp lặp giải bài toán tìm điểm chung: $$x^* \in S = Sol(C, f) \cap Fix(T)$$ trong đó $f$ là song hàm giả đơn điệu, liên tục yếu đồng thời, thỏa mãn điều kiện kiểu Lipschitz với các hằng số $c_1, c_2 > 0$, và $T: C \to C$ là ánh xạ tựa không giãn (quasinonexpansive).

  • Phân tích hạn chế của thuật toán HSEM [31] (Mục 4.1): Thuật toán Halpern subgradient extragradient của D. Hieu đòi hỏi bước nhảy $\lambda$ cố định thỏa mãn $0 < \lambda < \min{\frac{1}{2c_1}, \frac{1}{2c_2}}$. Nếu $c_1, c_2$ không thể ước lượng được thì thuật toán không khả thi.
  • Thuật toán đề xuất và chứng minh hội tụ (Mục 4.2): Kết hợp phương pháp dưới đạo hàm tăng cường (subgradient extragradient) với phép lặp Ishikawa. Thuật toán mới loại bỏ sự phụ thuộc vào các hằng số $c_1, c_2$ chưa biết, thực hiện giải duy nhất 1 bài toán tối ưu lồi mạnh trên $C$ tại mỗi bước lặp, kết hợp với các bước lặp kiểu Ishikawa đối với ánh xạ tựa không giãn $T$. Luận án chứng minh định lý hội tụ mạnh của dãy lặp về hình chiếu vuông góc của điểm ban đầu lên tập nghiệm chung $S$. Đồng thời, các thuật toán hệ quả cho các trường hợp riêng biệt được suy biến một cách chặt chẽ.
  • Thực nghiệm tính toán (Mục 4.3): Trình bày các ví dụ số minh họa tốc độ hội tụ và độ chính xác của thuật toán trong không gian hữu hạn chiều và đặc biệt là trong không gian Hilbert vô hạn chiều.

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

Các kết quả đạt được của luận án được thể hiện qua 3 đóng góp khoa học chính:

  1. Về bài toán cân bằng không đơn điệu: Đề xuất thành công 2 thuật toán kiểu chiếu nhúng kết hợp tìm kiếm theo tia Armijo (Thuật toán 2.1 và Thuật toán 2.2). Chứng minh toán học chặt chẽ tính hội tụ mạnh của các dãy lặp trong không gian Hilbert thực mà không cần giả thiết về tính đơn điệu hay giả đơn điệu của song hàm. Ứng dụng giải quyết bài toán mô phỏng cân bằng thị trường điện bán độc quyền Nash-Cournot. Kết quả công bố trong công trình [CT1] (Journal of Nonlinear Analysis and Optimization, 2018).
  2. Về quan hệ giữa bài toán cân bằng tổ hợp và hệ bài toán cân bằng: Chỉ ra thiếu sót trong các công trình quốc tế công bố trước đó bằng phản ví dụ cụ thể, chứng minh tính đơn điệu chưa đủ để đồng nhất tập nghiệm của $CEP$ và $CSEP$. Thiết lập và chứng minh hệ điều kiện đủ mới để đẳng thức tập nghiệm được bảo toàn cho cả trường hợp hữu hạn và vô hạn đếm được. Kết quả công bố trong công trình [CT2].
  3. Về bài toán nghiệm chung của cân bằng và điểm bất động: Đề xuất thuật toán mới kết hợp phương pháp dưới đạo hàm tăng cường với phép lặp Ishikawa. Thuật toán giải quyết bài toán khi không biết trước hằng số Lipschitz $c_1, c_2$ và áp dụng cho lớp ánh xạ tựa không giãn, giảm thiểu chi phí tính toán khi chỉ giải 1 bài toán quy hoạch lồi mạnh trên $C$ mỗi bước lặp. Kết quả công bố trong công trình [CT3].

Các kết quả nghiên cứu đã được báo cáo và thẩm định tại:

  • Xê-mi-na Bộ môn Toán và Xê-mi-na Khoa Công nghệ Thông tin, Học viện Kỹ thuật Quân sự.
  • Hội nghị Khoa học các nhà nghiên cứu trẻ lần thứ XV (20/02/2020), Học viện Kỹ thuật Quân sự.
  • Hội thảo Tối ưu và Tính toán Khoa học lần thứ 18 (20-22/8/2020), Hòa Lạc, Hà Nội.
  • Hội nghị các cựu học viên Viện Toán học - Một số vấn đề trong Toán học đương đại (11-12/9/2020), Hà Nội.

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

Hạn chế

Theo các giới hạn lý thuyết và phạm vi nghiên cứu được nêu trong văn bản:

  • Thuật toán giải bài toán cân bằng không đơn điệu ở Chương 2 đòi hỏi tại mỗi bước lặp phải tính toán hình chiếu lên nửa không gian thu hẹp $C_{k+1}$ và thực hiện quy tắc tìm kiếm tia Armijo, điều này có thể làm tăng số lần đánh giá hàm mục tiêu khi quy mô bài toán tăng cao.
  • Thuật toán ở Chương 4 giới hạn trên lớp ánh xạ tựa không giãn và song hàm giả đơn điệu kiểu Lipschitz; việc mở rộng cho các lớp ánh xạ tổng quát hơn (như ánh xạ nửa co, ánh xạ giả co) chưa được bao quát hoàn toàn trong khuôn khổ luận án.

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

Văn bản luận án xác định các hướng nghiên cứu tiếp tục phát triển (trang 89):

  • Tiếp tục nghiên cứu, mở rộng các thuật toán giải bài toán cân bằng cho các lớp song hàm tổng quát hơn (chẳng hạn không liên tục yếu đồng thời, hoặc trên các tập ràng buộc không lồi).
  • Cải tiến quy tắc tìm kiếm bước nhảy và tối ưu hóa cấu trúc của các phép chiếu nhúng nhằm nâng cao tốc độ hội tụ và giảm chi phí tính toán cho các bài toán ứng dụng quy mô lớn trong kinh tế và kỹ thuật.

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 ứng dụng, Toán giải tích, Tối ưu hóa: Tham khảo khung lý thuyết giải tích lồi hiện đại, kỹ thuật xử lý tính không đơn điệu qua phép chiếu nhúng, và phương pháp kết hợp thuật toán dưới đạo hàm tăng cường với các lược đồ lặp điểm bất động (Mann, Ishikawa, Halpern).
  • Các nhà nghiên cứu mô hình hóa kinh tế và vận trù học: Tham khảo cách thiết lập mô hình bài toán cân bằng tổng quát Blum - Oettli từ các bài toán thực tiễn như trò chơi Nash không hợp tác, bất đẳng thức biến phân và mô hình cân bằng thị trường điện bán độc quyền Nash-Cournot phân tích tại Chương 2.
  • Phần giá trị chuyên sâu đáng trích dẫn:
    • Kỹ thuật chứng minh định lý hội tụ mạnh sử dụng nửa không gian thu hẹp $C_{k+1}$ (Chương 2).
    • Phương pháp xây dựng phản ví dụ bác bỏ đẳng thức tập nghiệm trong bài toán cân bằng tổ hợp (Chương 3).
    • Lược đồ tính toán tự thích nghi bước nhảy không phụ thuộc hằng số kiểu Lipschitz (Chương 4).

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

1. Luận án nghiên cứu những dạng bài toán cụ thể nào và bài toán cân bằng bao hàm các bài toán quen thuộc nào?

Luận án nghiên cứu bài toán cân bằng tổng quát $EP(C, f)$ với song hàm không đơn điệu, hệ bài toán cân bằng $CSEP$, bài toán cân bằng tổ hợp $CEP$, và bài toán tìm nghiệm chung $S = Sol(C, f) \cap Fix(T)$ giữa bài toán cân bằng và điểm bất động. Văn bản chỉ ra rằng bài toán cân bằng bao hàm 5 lớp bài toán quen thuộc: bài toán tối ưu ($OP$), bài toán bất đẳng thức biến phân đơn trị ($VIP$) và đa trị ($MVIP$), bài toán điểm bất động đơn trị ($FP$) và đa trị ($MFP$), cùng mô hình cân bằng Nash ($NEP$) trong lý thuyết trò chơi không hợp tác.

2. Tại sao giả thiết tính đơn điệu trong các công trình của S. Kangtunyakarn và cộng sự bị luận án phản bác?

Trong các công trình [41, 42, 66, 67, 68], nhóm tác giả cho rằng khi các song hàm $f_i$ ($i = 1, \dots, N$) là đơn điệu thì giao các tập nghiệm $\bigcap_{i=1}^N Sol(C, f_i)$ luôn trùng với tập nghiệm của bài toán cân bằng tổ hợp $Sol(C, \sum_{i=1}^N \alpha_i f_i)$. Tác giả Nguyễn Thị Thanh Hà đã chỉ ra rằng giả thiết tính đơn điệu đơn thuần là chưa đủ thông qua việc xây dựng một phản ví dụ toán học tường minh, chứng minh tập nghiệm tổ hợp có thể rộng hơn giao các tập nghiệm thành phần nếu thiếu các điều kiện ràng buộc bổ sung.

3. Điểm cải tiến kỹ thuật chính của thuật toán đề xuất ở Chương 4 so với thuật toán HSEM của D. Hieu [31] là gì?

Thuật toán HSEM trong [31] yêu cầu tham số bước $\lambda$ phải thỏa mãn điều kiện $0 < \lambda < \min{\frac{1}{2c_1}, \frac{1}{2c_2}}$, buộc người giải phải biết trước các hằng số kiểu Lipschitz $c_1, c_2$. Thuật toán đề xuất trong luận án khắc phục điểm này bằng cách kết hợp phương pháp dưới đạo hàm tăng cường với phép lặp Ishikawa, cho phép thuật toán tự thích nghi và thực thi thành công ngay cả khi các hằng số Lipschitz $c_1, c_2$ hoàn toàn không xác định được.

4. Mô hình kinh tế thực tế nào được tác giả sử dụng để kiểm chứng thuật toán và tại sao nó lại dẫn đến bài toán không đơn điệu?

Tác giả sử dụng mô hình cân bằng thị trường điện bán độc quyền Nash-Cournot gồm $n_c = 3$ công ty sản xuất điện và $n_g = 6$ đơn vị phát điện, với hàm giá điện $p(x) = 378 - \sum x_i$ và hàm chi phí phi tuyến $c_j(x_j) = \max{c_{0j}(x_j), c_{1j}(x_j)}$. Khi chuyển mô hình về bài toán cân bằng $EP(C, f)$, ma trận $A$ xuất hiện trong biểu thức song hàm không phải là ma trận nửa xác định dương, dẫn đến $f(x, y) + f(y, x) = -(y - x)^T A (y - x)$ không thỏa mãn điều kiện đơn điệu.

5. Cấu hình phần mềm và phần cứng được sử dụng trong các thực nghiệm số của luận án gồm những gì?

Các thuật toán được lập trình và tính toán trên phần mềm MATLAB phiên bản R2014a, chạy trên máy tính xách tay trang bị vi xử lý Intel(R) Core(TM) i5-3230M CPU @ 2.60 GHz, bộ nhớ trong RAM 4GB. Tiêu chuẩn dừng thuật toán sử dụng sai số tương đối $\frac{|x^{k+1} - x^k|}{\max{1, |x^k|}} \le 10^{-3}$.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Thị Thanh Hà đã giải quyết trọn vẹn ba vấn đề lý thuyết và giải thuật trọng tâm trong lý thuyết tối ưu và giải tích phi tuyến: xây dựng thuật toán hội tụ mạnh cho bài toán cân bằng không đơn điệu, xác lập điều kiện đủ chuẩn xác cho mối liên hệ tập nghiệm giữa hệ bài toán cân bằng và bài toán cân bằng tổ hợp, và thiết lập thuật toán tìm nghiệm chung của bài toán cân bằng giả đơn điệu với điểm bất động tựa không giãn không đòi hỏi biết trước hằng số Lipschitz. Các kết quả nghiên cứu được chứng minh chặt chẽ trong không gian Hilbert thực, kiểm chứng hiệu quả qua mô hình cân bằng thị trường điện bán độc quyền Nash-Cournot và các ví dụ số vô hạn chiều, đồng thời đã được công bố trên các tạp chí chuyên ngành. Đây là công trình nghiên cứu hoàn chỉnh, có ý nghĩa học thuật vững chắc và giá trị ứng dụng rõ ràng trong chuyên ngành Toán ứng dụng.