Tổng quan luận án

Quy hoạch thương (Fractional Programming) là phân ngành của lý thuyết tối ưu hóa, nghiên cứu các bài toán mà hàm mục tiêu là tỉ số của hai hàm số. Trong thực tiễn kinh tế và kỹ thuật, các bài toán quy hoạch thương nảy sinh một cách tự nhiên từ các yêu cầu tối ưu hóa hiệu suất như: cực đại hóa lợi nhuận trên chi phí, cực đại hóa giá trên thời gian, cực đại hóa đầu ra trên đầu vào, cực tiểu hóa chi phí trên thời gian, cực đại hóa tỷ lệ tín hiệu trên tạp âm của bộ lọc quang phổ trong vật lý, cũng như trong bài toán lên kế hoạch hay lập trình quy mô lớn.

Phần lớn các công trình nghiên cứu trước đây về quy hoạch thương chủ yếu tập trung vào bài toán đơn mục tiêu và xét trên các tập chấp nhận được là tập lồi hoặc khối đa diện lồi, hoặc các hàm mục tiêu thỏa mãn điều kiện trơn (khả vi) hay lồi/lõm cổ điển. Tuy nhiên, nhiều mô hình thực tế đòi hỏi việc ra quyết định phải tối ưu hóa đồng thời nhiều tỉ số khác nhau trong điều kiện không trơn (không khả vi), đồng thời chịu sự chi phối của hệ ràng buộc hỗn hợp gồm cả bất đẳng thức, đẳng thức và ràng buộc tập. Các kết quả nghiên cứu về điều kiện tối ưu và lý thuyết đối ngẫu cho bài toán quy hoạch thương đa mục tiêu tổng quát không trơn dưới ngôn ngữ dưới vi phân suy rộng còn rất ít. Đồng thời, việc khảo sát nghiệm xấp xỉ (tựa nghiệm hữu hiệu) là một nhu cầu cấp thiết, xuất phát từ thực tế tính toán số: khi thực hiện các thuật toán giải bài toán tối ưu, sau một số hữu hạn bước lặp, người tính toán chỉ có thể nhận được nghiệm gần đúng chứ khó đạt tới nghiệm chính xác tuyệt đối.

Luận án xác định các mục tiêu và câu hỏi nghiên cứu cụ thể như sau:

  1. Thiết lập các định lý điều kiện cần dạng Fritz John và dạng Kuhn-Tucker cho nghiệm hữu hiệu yếu địa phương của bài toán quy hoạch thương đa mục tiêu không trơn có ràng buộc hỗn hợp thông qua dưới vi phân suy rộng Jeyakumar-Luc kết hợp điều kiện chính quy Mangasarian-Fromovitz tổng quát.
  2. Xây dựng các khái niệm hàm lồi suy rộng (giả lồi bất biến tiệm cận và tựa lồi bất biến tiệm cận) nhằm thiết lập và chứng minh định lý điều kiện đủ cho nghiệm hữu hiệu yếu của bài toán.
  3. Thiết lập công thức tính dưới vi phân suy rộng cho hàm thương; từ đó xây dựng các điều kiện cần Fritz John, Kuhn-Tucker và điều kiện đủ cho tựa nghiệm hữu hiệu yếu địa phương của bài toán.
  4. Xây dựng các mô hình bài toán đối ngẫu kiểu Mond-Weir và kiểu Wolfe, đồng thời chứng minh các định lý đối ngẫu yếu, đối ngẫu mạnh và đối ngẫu ngược cho cả hai lớp nghiệm: nghiệm hữu hiệu yếu và tựa nghiệm hữu hiệu yếu thông qua dưới vi phân suy rộng.

Đối tượng nghiên cứu của luận án là bài toán quy hoạch thương đa mục tiêu (MFP) có dạng: $$ \begin{aligned} \min & \left( \frac{f_1(x)}{g_1(x)}, \dots, \frac{f_p(x)}{g_p(x)} \right) \ \text{với các ràng buộc:} \quad & h_j(x) \le 0, \quad j \in I := {1, \dots, m}, \ & \ell_k(x) = 0, \quad k \in L := {1, \dots, r}, \ & x \in D, \end{aligned} $$ trong đó $D$ là tập con đóng của không gian định chuẩn $X$; $f_i, g_i, h_j, \ell_k$ là các hàm liên tục trên $X$ với mọi $i = 1, \dots, p$; $j \in I$; $k \in L$; mẫu số thỏa mãn $g_i(x) > 0$ với mọi $x \in X$ và $i = 1, \dots, p$. Tập chấp nhận được của bài toán ký hiệu là $M := {x \in D : h_j(x) \le 0, j \in I \text{ và } \ell_k(x) = 0, k \in L}$.

Phạm vi nghiên cứu của đề tài là không gian định chuẩn và không gian Banach trừu tượng trong giải tích biến phân và tối ưu hóa không trơn. Công trình được hoàn thành năm 2022 tại Viện Công nghệ Thông tin trực thuộc Học viện Khoa học và Công nghệ – Viện Hàn lâm Khoa học và Công nghệ Việt Nam.

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

Quy hoạch thương được Charnes và Cooper khởi xướng từ năm 1962 với công trình kinh điển [1], đề xuất phép biến đổi đưa bài toán quy hoạch thương tuyến tính về bài toán quy hoạch tuyến tính tương đương. Sau đó, hướng nghiên cứu này mở rộng sang nhiều ứng dụng thực tiễn:

  • Gilmore và Gomory [16] phân tích bài toán chia cổ phần trong ngành công nghiệp giấy dưới dạng quy hoạch thương tuyến tính, chứng minh việc giảm tỉ lệ nguyên liệu thô tối ưu hơn việc giảm thiểu hao hụt nguyên liệu.
  • Hoskins và Blom [17] sử dụng quy hoạch thương một mục tiêu để phân tích giảm chi phí lao động.
  • Trong lĩnh vực tài chính và danh mục đầu tư, Ziemba, Parkan và Brooks-Hill [18], Ohlson và Ziemba [19], Mao [23], Faaland và Jacobs [24] đã nghiên cứu các bài toán lựa chọn danh mục đầu tư dẫn đến các quy hoạch thương tuyến tính hoặc phi tuyến bậc hai.
  • Uberti [25] nghiên cứu bài toán cho thuê; Konno và Inori [26] tối ưu hóa kỳ hạn hoặc năng suất trung bình trong giao dịch trái phiếu.
  • Trong giao thông và vận tải, Dantzig, Blattner và Rao [27] tối ưu hóa hành trình mạng lưới để giảm tỷ lệ chi phí theo thời gian; Kydland [28] nghiên cứu vận chuyển hàng hóa với mục tiêu tối ưu hóa lợi nhuận trên đơn vị thời gian; Derman [29] và Klein [30] phân tích các quy trình ngẫu nhiên để cực tiểu chi phí trên thời gian.
  • Charnes, Cooper và Rhodes [31] dùng quy hoạch thương tuyến tính đánh giá hoạt động của các tổ chức phi lợi nhuận qua tỉ số đầu ra trên đầu vào; Stancu-Minasian [32] áp dụng trong kinh tế vĩ mô nhằm cực đại tăng trưởng thu nhập quốc dân trên đầu tư và tiêu dùng; Eichhorn [33, 34] nghiên cứu về mặt lý thuyết kinh tế.
  • Trong giải tích số và vật lý, bài toán giá trị ban đầu [35] đưa về bài toán cực đại thương Rayleigh (quy hoạch thương bậc hai không lõm); Falk [36] giải bài toán cực đại tỷ lệ tín hiệu trên tạp âm của bộ lọc quang phổ; bài toán lý thuyết định vị [37] xuất hiện như đối ngẫu của bài toán cực tiểu định vị; Charnes và Cooper [38] cùng Bereanu [39] phát triển các mô hình quy hoạch ngẫu nhiên đưa về dạng thương.
  • Về phương pháp tính và thuật toán, Isbell và Marlow [57] áp dụng phương pháp Newton cho bài toán quy hoạch thương tuyến tính; Dinkelbach [55] mở rộng thành phương pháp tham số Dinkelbach cho bài toán phi tuyến; Pardalos và Phillip [58] đề xuất một biến thể khác của phương pháp Newton; Martos [50] và Swarup [51] xây dựng phương pháp tựa đơn hình.

Đối với bài toán cực đại tỷ số nhỏ nhất và bài toán tổng các tỷ số:

  • Neumann [62, 63] thiết lập bài toán đối ngẫu cho bài toán cực đại tỷ số nhỏ nhất phát sinh từ mô hình tỷ lệ tăng trưởng của nền kinh tế mở bằng phương pháp vi phân.
  • Scott và Jefferson [66], Bector và Suneja [67], Boncompte và Martinez-Legaz [68], Chandra, Craven và Mond [3] đưa ra các phương pháp đối ngẫu liên hợp và đối ngẫu khác cho bài toán cực đại tỷ số nhỏ nhất.
  • Đối với bài toán tổng các tỷ số, Almogy và Levin [71] phân tích bài toán vận chuyển ngẫu nhiên nhiều tầng; Colantoni, Manes và Whinston [72] cải biên bài toán cực đại lợi nhuận có chi phí cố định; Drezner, Schaible và Simchi-Levi [73] tìm cực tiểu thời gian chờ trung bình trong bài toán xếp hàng; Craven [15], Cambini, Martein và Schaible [74], Martein [75], Falk và Palocsay [76] nghiên cứu các thuật toán và tính chất nghiệm nằm trên biên của đa diện lồi.

Đối với bài toán đa mục tiêu và các tiếp cận giải tích không trơn:

  • N. Gadhi [5] nghiên cứu điều kiện tối ưu cho bài toán quy hoạch thương đa mục tiêu qua dưới vi phân suy rộng, nhưng cấu trúc bài toán chỉ bao gồm ràng buộc bất đẳng thức, chưa xét tới các ràng buộc đẳng thức và ràng buộc tập.
  • Golestani và các cộng sự [81] thiết lập các điều kiện cần và đủ cho tựa nghiệm hữu hiệu yếu của bài toán quy hoạch đa mục tiêu không trơn nhưng chỉ sử dụng công cụ dưới vi phân Clarke.
  • Căpăţână [84] thiết lập điều kiện tối ưu cho $\epsilon$-tựa nghiệm của bài toán tối ưu vô hướng qua $\epsilon$-dưới vi phân suy rộng.
  • Gong [91] công bố các kết quả vô hướng hóa cho nghiệm hữu hiệu yếu của bài toán cân bằng vectơ (VEP).
  • Jeyakumar và Luc [92] phát triển lý thuyết dưới vi phân suy rộng và quy tắc tính vi phân hàm hợp.

Khoảng trống nghiên cứu được luận án lựa chọn giải quyết: Mặc dù bài toán quy hoạch thương đã được nghiên cứu đa dạng, các công trình đi trước chưa xử lý trọn vẹn bài toán quy hoạch thương đa mục tiêu không trơn đồng thời chứa cả ba loại ràng buộc: bất đẳng thức, đẳng thức và ràng buộc tập. Hơn nữa, việc sử dụng công cụ dưới vi phân suy rộng Jeyakumar-Luc (vốn bao quát hơn dưới vi phân Clarke và Michel-Penot) để nghiên cứu điều kiện tối ưu cho cả nghiệm hữu hiệu yếu lẫn tựa nghiệm hữu hiệu yếu, cũng như xây dựng hoàn chỉnh hệ thống lý thuyết đối ngẫu kiểu Mond-Weir và kiểu Wolfe cho bài toán này, vẫn là một bài toán mở. Luận án đặt vị trí nghiên cứu vào việc hoàn thiện khoảng trống lý thuyết này.

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

Luận án dựa trên nền tảng lý thuyết tối ưu hóa và giải tích không trơn trong không gian Banach và không gian định chuẩn $X$:

  • Các lớp đạo hàm cổ điển và mở rộng: Đạo hàm theo phương $F'(x; v)$, đạo hàm Gâteaux $\nabla_G f(x)$, đạo hàm Fréchet $\nabla f(x)$, đạo hàm theo phương Dini dưới $f^-(x; v) = \liminf_{t \downarrow 0} \frac{f(x + tv) - f(x)}{t}$ và Dini trên $f^+(x; v) = \limsup_{t \downarrow 0} \frac{f(x + tv) - f(x)}{t}$.
  • Hàm Lipschitz địa phương, đạo hàm theo phương Clarke $f^\circ(x; v) = \limsup_{x' \to x, t \downarrow 0} \frac{f(x' + tv) - f(x')}{t}$ và dưới vi phân Clarke: $$\partial^C f(x) = {x^* \in X^* : f^\circ(x; v) \ge \langle x^*, v \rangle, \forall v \in X}.$$
  • Đạo hàm theo phương Michel-Penot $f^\diamond(x; v) = \sup_{w \in X} \limsup_{t \downarrow 0} \frac{f(x + t(v + w)) - f(x + tw)}{t}$ và dưới vi phân Michel-Penot: $$\partial^{MP} f(x) = {x^* \in X^* : f^\diamond(x; v) \ge \langle x^*, v \rangle, \forall v \in X}.$$ Nếu $f$ Lipschitz địa phương thì $\partial^{MP} f(x) \subseteq \partial^C f(x)$.
  • Dưới vi phân suy rộng Jeyakumar-Luc $\partial^* f(x) \subset X^$: Không nhất thiết lồi hay compact yếu. Ví dụ, hàm $f(x) = \sqrt{x}$ (với $x > 0$) và $-\sqrt{-x}$ (với $x < 0$) có dưới vi phân suy rộng không compact tại 0 là $[\alpha, \infty)$; hàm $f(x) = -|x|$ có dưới vi phân suy rộng không lồi tại 0 là ${-1, 1}$; hàm $f(x) = x^2 \sin(1/x)$ (với $x \neq 0$) và $f(0) = 0$ có dưới vi phân suy rộng tại 0 là ${-1, 1}$.
  • Quy tắc hàm hợp của Jeyakumar và Luc [92]: Nếu $f = (f_1, \dots, f_n): X \to \mathbb{R}^n$ và $g: \mathbb{R}^n \to \mathbb{R}$ liên tục, có dưới vi phân suy rộng bị chặn và nửa liên tục trên, thì $\partial^* g(f(x))(\partial^* f_1(x), \dots, \partial^* f_n(x))$ là dưới vi phân suy rộng của $g \circ f$ tại $x$.
  • Nón tiếp tuyến Clarke $T(D; x)$ và nón pháp tuyến Clarke $N(D; x) = {\xi \in X^* : \langle \xi, v \rangle \le 0, \forall v \in T(D; x)}$.
  • Điểm chính quy theo nghĩa Ioffe của ánh xạ ràng buộc đẳng thức $\ell$ theo tập $D$.
  • Điều kiện chính quy kiểu Mangasarian-Fromovitz (CQ): Tồn tại $v_0 \in T(D; \bar{x})$ và các số $a_j > 0$ ($j \in I(\bar{x})$) sao cho $\langle \xi, v_0 \rangle \le -a_j$ với mọi $\xi \in \text{conv},\partial^* h_j(\bar{x})$ và $\langle \eta_k, v_0 \rangle = 0$ với mọi $\eta_k \in \text{conv},\partial^* \ell_k(\bar{x})$.
  • Các khái niệm lồi suy rộng theo ánh xạ $\eta: X \times X \to X$:
    • Hàm $f$ giả lồi bất biến tiệm cận (asymptotic pseudoinvex) tại $\bar{x}$ theo $(\eta, D)$ nếu với mọi $x \in D$, tồn tại $x^_n \in \text{conv},\partial^ f(\bar{x})$ sao cho $\lim_{n \to \infty} \langle x^*_n, \eta(x, \bar{x}) \rangle \ge 0 \implies f(x) \ge f(\bar{x})$.
    • Hàm $f$ giả lồi bất biến tiệm cận chặt (asymptotic strict pseudoinvex) tại $\bar{x}$ theo $(\eta, D)$ nếu với mọi $x \in D, x \neq \bar{x}$, tồn tại $x^_n \in \text{conv},\partial^ f(\bar{x})$ sao cho $\lim_{n \to \infty} \langle x^*_n, \eta(x, \bar{x}) \rangle \ge 0 \implies f(x) > f(\bar{x})$.
    • Hàm $f$ tựa lồi bất biến tiệm cận (asymptotic quasiinvex) tại $\bar{x}$ theo $(\eta, D)$ nếu với mọi $x \in D$, $f(x) \le f(\bar{x}) \implies$ tồn tại $x^_n \in \text{conv},\partial^ f(\bar{x})$ thỏa mãn $\lim_{n \to \infty} \langle x^*_n, \eta(x, \bar{x}) \rangle \le 0$.

Phương pháp nghiên cứu thực tế của luận án:

  • Tiếp cận định tính thuần túy thuộc toán học lý thuyết và giải tích biến phân.
  • Kỹ thuật vô hướng hóa: Áp dụng kết quả vô hướng hóa của Gong [91] cho bài toán cân bằng vectơ (VEP). Sử dụng phiếm hàm khoảng cách $P(y) = \inf{t \in \mathbb{R} : y \in te - D}$ liên tục, thuần nhất dương, dưới cộng tính trên không gian vectơ tôpô Hausdorff để quy bài toán vector về bài toán tối ưu vô hướng, từ đó dẫn xuất các điều kiện tối ưu.
  • Kỹ thuật tính toán vi phân suy rộng: Biến đổi hàm thương $f_i/g_i$ thành hàm sai phân phụ trợ $\phi_i(x) = f_i(x) - \varphi_i(\bar{x}) g_i(x)$ (với $\varphi_i(\bar{x}) = f_i(\bar{x})/g_i(\bar{x})$), sau đó sử dụng quy tắc hàm hợp của Jeyakumar-Luc để xác định cấu trúc đạo hàm suy rộng.
  • Phương pháp đối ngẫu: Thiết lập các bài toán đối ngẫu dạng Mond-Weir và Wolfe qua việc phân tách các ràng buộc đẳng thức, bất đẳng thức và hàm mục tiêu, sau đó sử dụng tính lồi suy rộng tiệm cận để chứng minh tính không vượt trội (đối ngẫu yếu) và sự trùng khớp giá trị mục tiêu (đối ngẫu mạnh, đối ngẫu ngược).

Nguồn tư liệu sử dụng hoàn toàn là các tài liệu học thuật lý thuyết gồm sách chuyên khảo, bài báo trên các tạp chí toán học chuyên ngành trong và ngoài nước; không sử dụng bộ dữ liệu số thực nghiệm hay phần mềm thống kê.

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à bổ đề nền tảng được dùng xuyên suốt luận án:

  • Trình bày định nghĩa ánh xạ khả vi Gâteaux, khả vi Fréchet, khả vi chặt, đạo hàm theo phương Dini dưới và Dini trên.
  • Trình bày định nghĩa nón lồi đóng $D \subset \mathbb{R}^p$, vectơ cực tiểu hữu hiệu và vectơ cực tiểu hữu hiệu yếu của tập $A$ theo nón $D$.
  • Trình bày đạo hàm theo phương Clarke, dưới vi phân Clarke $\partial^C f(x)$, khái niệm hàm chính quy Clarke, đạo hàm theo phương Michel-Penot và dưới vi phân Michel-Penot $\partial^{MP} f(x)$.
  • Trình bày chi tiết phương pháp vô hướng hóa của Gong cho bài toán cân bằng vectơ (VEP) với nón lồi nhọn $D$: Chứng minh hàm $P(y) = \inf{t \in \mathbb{R} : y \in te - D}$ là hàm liên tục, thuần nhất dương, dưới cộng tính trên $Y$ khi $e \in \text{int} D$. Khẳng định định lý tương đương: $\bar{x} \in A$ là nghiệm hữu hiệu yếu của (VEP) khi và chỉ khi tồn tại hàm liên tục, thuần nhất dương, dưới cộng tính $\Lambda$ sao cho $y_2 - y_1 \in \text{int} D \implies \Lambda(y_1) < \Lambda(y_2)$ và $\Lambda(F(\bar{x}, y)) \ge 0$ với mọi $y \in A$.
  • Giới thiệu khái niệm dưới vi phân suy rộng Jeyakumar-Luc $\partial^* f(x)$, minh họa tính không lồi, không compact qua các ví dụ giải tích; nhắc lại quy tắc hàm hợp Jeyakumar-Luc; định nghĩa nón tiếp tuyến Clarke $T(D; x)$ và nón pháp tuyến Clarke $N(D; x)$.

Chương 2. Điều kiện cần và điều kiện đủ cho nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục tiêu

Chương 2 nghiên cứu trực tiếp nghiệm hữu hiệu yếu của bài toán (MFP). Các luận điểm và kết quả chính bao gồm:

  • Thiết lập Điều kiện cần Fritz John (Định lý 2.1): Cho $\bar{x} \in M$ là nghiệm hữu hiệu yếu địa phương của bài toán (MFP). Dưới các giả thiết: các hàm $f_i, g_i, h_j, \ell_k$ liên tục, có dưới vi phân suy rộng bị chặn và nửa liên tục trên tại lân cận của $\bar{x}$; $\ell_k$ Lipschitz địa phương và $|\ell_k|$ chính quy Clarke tại $\bar{x}$; $\bar{x}$ chính quy Ioffe đối với $\ell$ theo $D$; $D$ lồi. Khi đó tồn tại các vectơ nhân tử $(\lambda^_1, \dots, \lambda^p) \in \mathbb{R}^p+ \setminus {0}$, $(\mu^_0, \mu^1, \dots, \mu^m) \in \mathbb{R}^{m+1}+$ và $(\nu^1, \dots, \nu^_r) \in \mathbb{R}^r$ thỏa mãn: $$0 \in \text{cl} \left[ \mu^0 \sum{i=1}^p \lambda^_i \left( \text{conv},\partial^ f_i(\bar{x}) - \varphi_i(\bar{x}) \text{conv},\partial^* g_i(\bar{x}) \right) + \sum{j=1}^m \mu^_j \text{conv},\partial^ h_j(\bar{x}) + \sum{k=1}^r \nu^_k \text{conv},\partial^ \ell_k(\bar{x}) + N(D; \bar{x}) \right].$$
  • Thiết lập Điều kiện cần Kuhn-Tucker (Định lý 2.2): Bổ sung điều kiện chính quy Mangasarian-Fromovitz (CQ). Luận án chứng minh bằng phản chứng rằng nếu nhân tử $\mu^0 = 0$ thì dẫn tới mâu thuẫn $\sum{j \in I(\bar{x})} \mu^_j a_j < 0$, do đó bắt buộc $\mu^_0 > 0$. Điều này cho phép chuẩn hóa nhân tử và suy ra tồn tại $(\alpha^_1, \dots, \alpha^p) \in \mathbb{R}^p+ \setminus {0}$, $(\mu^_1, \dots, \mu^m) \in \mathbb{R}^m+$ và $(\nu^1, \dots, \nu^r) \in \mathbb{R}^r$ sao cho: $$0 \in \text{cl} \left[ \sum{i=1}^p \alpha^i \left( \text{conv},\partial^* f_i(\bar{x}) - \varphi_i(\bar{x}) \text{conv},\partial^* g_i(\bar{x}) \right) + \sum{j=1}^m \mu^_j \text{conv},\partial^ h_j(\bar{x}) + \sum{k=1}^r \nu^_k \text{conv},\partial^ \ell_k(\bar{x}) + N(D; \bar{x}) \right].$$
  • Minh họa lý thuyết bằng Ví dụ bài toán $(P_4)$ trong không gian $\mathbb{R}^2$: Xét 3 hàm mục tiêu thương, 2 ràng buộc bất đẳng thức, 1 ràng buộc đẳng thức trên tập lồi $D = \mathbb{R}^2_+$. Tập chấp nhận được là đoạn thẳng $M = {x = (x_1, x_2) : x_2 = 2x_1, 0 \le x_1 \le 1}$. Tại điểm tối ưu $\bar{x}$, điều kiện chính quy (CQ) thỏa mãn với vectơ hướng $v_0 = (1, 2) \in T(D; \bar{x})$, và điều kiện cần Kuhn-Tucker được kiểm chứng chính xác với bộ nhân tử cụ thể: $\alpha^_1 = 2, \alpha^_2 = 1, \alpha^_3 = 2, \mu^_1 = 2, \mu^_2 = 1, \nu^ = 1$.
  • Thiết lập Điều kiện đủ (Định lý 2.3): Luận án chứng minh rằng nếu tổ hợp hàm mục tiêu $\sum_{i=1}^p \alpha^_i (f_i - \varphi_i(\bar{x})g_i)$ thỏa mãn tính chất giả lồi bất biến tiệm cận tại $\bar{x}$ theo $(\eta, D)$, các ràng buộc bất đẳng thức tích cực $h_j$ và các ràng buộc đẳng thức $\pm \nu^_k \ell_k$ thỏa mãn tính chất tựa lồi bất biến tiệm cận tại $\bar{x}$ theo $(\eta, D)$, thì điểm thỏa mãn điều kiện Kuhn-Tucker chính là nghiệm hữu hiệu yếu của bài toán (MFP). Kết quả này tổng quát hóa Định lý 7 của Gadhi [5].

Chương 3. Điều kiện cần và điều kiện đủ cho tựa nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục tiêu

Chương 3 mở rộng bài toán từ nghiệm chính xác sang tựa nghiệm hữu hiệu yếu (nghiệm hữu hiệu xấp xỉ địa phương) theo vectơ tham số sai số $\alpha = (\alpha_1, \dots, \alpha_p) \in \mathbb{R}^p_{++}$. Nội dung trọng tâm bao gồm:

  • Thiết lập Mệnh đề 3.1 (Quy tắc dưới vi phân suy rộng cho hàm thương): Cho $f, g$ liên tục trên $D \subset X$, $g(x) > 0$. Giả sử $\partial^* f(x), \partial^* g(x)$ bị chặn và nửa liên tục trên tại $\bar{x}$. Luận án chứng minh tập: $$\frac{g(\bar{x})\partial^* f(\bar{x}) - f(\bar{x})\partial^* g(\bar{x})}{g^2(\bar{x})}$$ chính là dưới vi phân suy rộng của hàm thương $f/g$ tại $\bar{x}$.
  • Thiết lập Điều kiện cần Fritz John cho tựa nghiệm hữu hiệu yếu (Định lý 3.1): Cho $\bar{x}$ là tựa nghiệm hữu hiệu yếu địa phương theo $\alpha \in \mathbb{R}^p_{++}$ của (MFP). Chuyển đổi bài toán qua hàm mục tiêu phụ trợ $\tilde{\varphi}_i(x) = \frac{f_i(x)}{g_i(x)} + \alpha_i |x - \bar{x}|$, kết hợp định lý vô hướng hóa Gong và dưới vi phân hàm khoảng cách, chứng minh tồn tại các nhân tử $(\theta^_1, \dots, \theta^p) \in \mathbb{R}^p+ \setminus {0}$, $(\mu^_0, \dots, \mu^m) \in \mathbb{R}^{m+1}+$ và $(\nu^_1, \dots, \nu^r) \in \mathbb{R}^r$ thỏa mãn: $$0 \in \text{cl} \left[ \mu^0 \sum{i=1}^p \theta^i \left( \text{conv},\partial^* f_i(\bar{x}) - \varphi_i(\bar{x})\text{conv},\partial^* g_i(\bar{x}) + \alpha_i g_i(\bar{x}) B^* \right) + \sum{j=1}^m \mu^_j \text{conv},\partial^ h_j(\bar{x}) + \sum{k=1}^r \nu^_k \text{conv},\partial^ \ell_k(\bar{x}) + N(D; \bar{x}) \right],$$ trong đó $B^$ là hình cầu đơn vị đóng trong không gian đối ngẫu $X^$.
  • Dưới điều kiện chính quy phù hợp, dẫn xuất Điều kiện cần Kuhn-Tucker cho tựa nghiệm hữu hiệu yếu với $\mu^*_0 > 0$.
  • Thiết lập Điều kiện đủ cho tựa nghiệm hữu hiệu yếu dựa trên các giả thiết giả lồi tiệm cận của hàm mục tiêu mở rộng và tựa lồi tiệm cận của các ràng buộc. Kết quả này mở rộng công trình của Golestani và cộng sự [81] và Căpăţână [84].

Chương 4. Đối ngẫu cho bài toán quy hoạch thương đa mục tiêu với nghiệm hữu hiệu yếu

Chương 4 thiết lập lý thuyết đối ngẫu cho bài toán (MFP) đối với nghiệm hữu hiệu yếu:

  • Xây dựng Bài toán đối ngẫu kiểu Mond-Weir: Tách biệt hoàn toàn các hàm ràng buộc bất đẳng thức và đẳng thức khỏi hàm mục tiêu, chuyển chúng vào tập chấp nhận được của bài toán đối ngẫu thông qua hệ thức triệt tiêu dưới vi phân suy rộng kết hợp nón pháp tuyến $N(D; y)$.
  • Xây dựng Bài toán đối ngẫu kiểu Wolfe: Đưa các thành phần nhân tử Lagrange của các ràng buộc trực tiếp vào hàm mục tiêu đối ngẫu.
  • Chứng minh Định lý đối ngẫu yếu: Khẳng định rằng dưới các giả thiết về tính giả lồi bất biến tiệm cận của hàm mục tiêu và tựa lồi bất biến tiệm cận của các ràng buộc, giá trị hàm mục tiêu tại mọi điểm chấp nhận được của bài toán gốc không thể bị vượt trội theo nghĩa nón bởi giá trị hàm mục tiêu của bài toán đối ngẫu (kiểu Mond-Weir hoặc kiểu Wolfe).
  • Chứng minh Định lý đối ngẫu mạnh: Nếu $\bar{x}$ là nghiệm hữu hiệu yếu của bài toán (MFP) và thỏa mãn điều kiện chính quy (CQ), thì tồn tại các nhân tử đối ngẫu sao cho bộ biến - nhân tử tương ứng là nghiệm của bài toán đối ngẫu, và giá trị mục tiêu của hai bài toán trùng nhau.
  • Chứng minh Định lý đối ngẫu ngược: Khẳng định các điều kiện để từ nghiệm của bài toán đối ngẫu khôi phục lại nghiệm hữu hiệu yếu của bài toán gốc ban đầu.

Chương 5. Đối ngẫu cho bài toán quy hoạch thương đa mục tiêu với tựa nghiệm hữu hiệu yếu

Chương 5 mở rộng toàn bộ khung lý thuyết đối ngẫu sang trường hợp tựa nghiệm hữu hiệu yếu (nghiệm xấp xỉ):

  • Xây dựng mô hình bài toán đối ngẫu xấp xỉ kiểu Mond-Weir và kiểu Wolfe cho tựa nghiệm hữu hiệu yếu, trong đó cấu trúc hàm mục tiêu và các điều kiện dưới vi phân tích hợp thêm số hạng hiệu chỉnh sai số dạng $\alpha_i g_i(y) B^*$.
  • Chứng minh hệ thống Định lý đối ngẫu yếu kiểu Mond-Weir và kiểu Wolfe: Thiết lập ranh giới đánh giá sai số giữa giá trị xấp xỉ của bài toán gốc và bài toán đối ngẫu dưới các điều kiện lồi suy rộng tiệm cận.
  • Chứng minh Định lý đối ngẫu mạnh kiểu Mond-Weir và kiểu Wolfe: Khẳng định sự tồn tại của tựa nghiệm đối ngẫu tương ứng khi bài toán gốc đạt tựa nghiệm hữu hiệu yếu và thỏa mãn điều kiện chính quy.
  • Chứng minh Định lý đối ngẫu ngược: Đảm bảo tính khép kín và đối xứng lý thuyết giữa bài toán gốc xấp xỉ và bài toán đối ngẫu xấp xỉ.

Bảng tổng hợp phạm vi khảo sát lý thuyết qua các chương của luận án:

Chương Đối tượng nghiệm Công cụ vi phân Loại ràng buộc khảo sát Khung lý thuyết thiết lập
Chương 1 Chuẩn bị cơ sở Clarke, Michel-Penot, Jeyakumar-Luc Không gian $X$, nón $D$ Vô hướng hóa Gong, nón $T(D; x)$, $N(D; x)$
Chương 2 Nghiệm hữu hiệu yếu Dưới vi phân suy rộng $\partial^*$ Bất đẳng thức, đẳng thức, tập Điều kiện cần Fritz John, Kuhn-Tucker, điều kiện đủ
Chương 3 Tựa nghiệm hữu hiệu yếu Dưới vi phân suy rộng $\partial^*$ Bất đẳng thức, đẳng thức, tập Vi phân hàm thương, điều kiện cần, điều kiện đủ
Chương 4 Nghiệm hữu hiệu yếu Dưới vi phân suy rộng $\partial^*$ Bất đẳng thức, đẳng thức, tập Đối ngẫu Mond-Weir, Wolfe (yếu, mạnh, ngược)
Chương 5 Tựa nghiệm hữu hiệu yếu Dưới vi phân suy rộng $\partial^*$ Bất đẳng thức, đẳng thức, tập Đối ngẫu Mond-Weir, Wolfe xấp xỉ (yếu, mạnh, ngược)

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

Các đóng góp mới về mặt lý luận được luận án tự xác định bao gồm:

  1. Mở rộng bài toán quy hoạch thương đa mục tiêu từ bài toán chỉ có ràng buộc bất đẳng thức (trong công trình của Gadhi [5]) thành bài toán tổng quát chứa đồng thời cả ba loại ràng buộc: bất đẳng thức, đẳng thức và ràng buộc tập trong không gian định chuẩn trừu tượng.
  2. Xây dựng và chứng minh định lý điều kiện cần Fritz John và Kuhn-Tucker cho nghiệm hữu hiệu yếu của bài toán (MFP) qua dưới vi phân suy rộng Jeyakumar-Luc, sử dụng kỹ thuật vô hướng hóa Gong và điều kiện chính quy Mangasarian-Fromovitz.
  3. Thiết lập các khái niệm giả lồi bất biến tiệm cận và tựa lồi bất biến tiệm cận theo $(\eta, D)$, qua đó chứng minh định lý điều kiện đủ cho bài toán (MFP).
  4. Thiết lập công thức giải tích tính dưới vi phân suy rộng cho thương của hai hàm số (Mệnh đề 3.1): $\partial^(f/g)(\bar{x}) = \frac{g(\bar{x})\partial^ f(\bar{x}) - f(\bar{x})\partial^* g(\bar{x})}{g^2(\bar{x})}$.
  5. Thiết lập và chứng minh hệ thống điều kiện cần Fritz John, Kuhn-Tucker và điều kiện đủ cho tựa nghiệm hữu hiệu yếu của bài toán quy hoạch thương đa mục tiêu không trơn, mở rộng các kết quả của Golestani và cộng sự [81] (vốn chỉ xét dưới vi phân Clarke) và Căpăţână [84] (chỉ xét bài toán vô hướng).
  6. Xây dựng hai lớp bài toán đối ngẫu kiểu Mond-Weir và kiểu Wolfe qua dưới vi phân suy rộng; chứng minh hoàn chỉnh các định lý đối ngẫu yếu, đối ngẫu mạnh và đối ngẫu ngược cho cả hai trường hợp: nghiệm hữu hiệu yếu và tựa nghiệm hữu hiệu yếu.

Kiến nghị và giải pháp đề xuất:

  • Luận án cung cấp cơ sở lý thuyết giải tích biến phân cho việc nghiên cứu thuật toán tính toán nghiệm. Việc đưa vào nghiên cứu tựa nghiệm hữu hiệu yếu giải quyết trực tiếp bài toán thực tế: khi các thuật toán tối ưu số dừng lại sau một số hữu hạn bước lặp, kết quả thu được là một nghiệm xấp xỉ; các định lý trong luận án cung cấp tiêu chuẩn kiểm tra toán học xem nghiệm xấp xỉ đó có thỏa mãn điều kiện tối ưu hay không.
  • Các mô hình đối ngẫu Mond-Weir và Wolfe đề xuất một hướng tiếp cận gián tiếp để giải bài toán (MFP) thông qua bài toán đối ngẫu trong trường hợp bài toán đối ngẫu có cấu trúc dễ xử lý hơn bài toán gốc.

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

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

  • Toàn bộ công trình tập trung giải quyết các bài toán lý thuyết giải tích biến phân và điều kiện tối ưu thuần túy; luận án chưa thực hiện việc thiết kế thuật toán số cụ thể và chưa có các kết quả thực nghiệm lập trình tính toán kiểm chứng trên máy tính.
  • Khái niệm nghiệm trong luận án tập trung chủ yếu vào nghiệm hữu hiệu yếu và tựa nghiệm hữu hiệu yếu (weak / weak quasi-efficient solutions); chưa bao quát tới các khái niệm nghiệm hữu hiệu Pareto chặt hoặc nghiệm hữu hiệu chính quy (proper efficient solutions) cho bài toán thương đa mục tiêu không trơn với hệ ràng buộc hỗn hợp.

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

  • Tiếp tục mở rộng nghiên cứu điều kiện tối ưu và lý thuyết đối ngẫu cho các dạng nghiệm hữu hiệu khác (như nghiệm hữu hiệu, nghiệm hữu hiệu chính quy) của bài toán quy hoạch thương đa mục tiêu không trơn.
  • Xây dựng và triển khai các thuật toán số xấp xỉ nghiệm dựa trên các điều kiện tối ưu và mô hình đối ngẫu đã thiết lập, đồng thời phân tích tốc độ hội tụ và độ phức tạp tính toán của thuật toán.

Giá trị tham khảo

Nội dung luận án có giá trị tham khảo chuyên môn đối với các nhóm đối tượng:

  • 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, Lý thuyết tối ưu và Điều khiển học: Tài liệu tham khảo sâu về giải tích không trơn, kỹ thuật vô hướng hóa bài toán vector, kỹ thuật ước lượng dưới vi phân suy rộng Jeyakumar-Luc và lý thuyết đối ngẫu.
  • Các nhà nghiên cứu trong lĩnh vực mô hình hóa kinh tế, tài chính và kỹ thuật: Cung cấp khung lý thuyết toán học chặt chẽ khi xử lý các mô hình tối ưu hóa chứa đồng thời nhiều hàm mục tiêu dạng hiệu suất/tỉ số trong điều kiện hàm số không khả vi.

Phần nội dung đáng tham khảo nhất:

  • Kỹ thuật kết hợp định lý vô hướng hóa Gong với hàm dưới cộng tính để chuyển đổi bài toán đa mục tiêu không trơn thành bài toán vô hướng ở Chương 2 và Chương 3.
  • Mệnh đề 3.1 về công thức tính dưới vi phân suy rộng cho hàm thương.
  • Cách thiết lập không gian bài toán và kỹ thuật chứng minh hệ thống đối ngẫu Mond-Weir và Wolfe cho tựa nghiệm hữu hiệu yếu ở Chương 5.

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

1. Bài toán quy hoạch thương đa mục tiêu (MFP) trong luận án được phát biểu toán học như thế nào?
Bài toán (MFP) được định nghĩa là bài toán tìm cực tiểu đồng thời của $p$ tỉ số: $$\min \left( \frac{f_1(x)}{g_1(x)}, \dots, \frac{f_p(x)}{g_p(x)} \right)$$ thỏa mãn hệ ràng buộc bất đẳng thức $h_j(x) \le 0$ ($j = 1, \dots, m$), ràng buộc đẳng thức $\ell_k(x) = 0$ ($k = 1, \dots, r$) và ràng buộc tập $x \in D$, trong đó $D$ là tập con đóng của không gian định chuẩn $X$, các hàm $f_i, g_i, h_j, \ell_k$ liên tục trên $X$ và $g_i(x) > 0$.

2. Dưới vi phân suy rộng Jeyakumar-Luc có đặc điểm gì khác biệt so với dưới vi phân Clarke và Michel-Penot?
Dưới vi phân suy rộng $\partial^* f(x)$ không nhất thiết phải là tập lồi hoặc tập compact yếu*. Bao lồi của dưới vi phân suy rộng có thể nằm hoàn toàn bên trong dưới vi phân Clarke và dưới vi phân Michel-Penot. Do đó, các điều kiện tối ưu thiết lập qua dưới vi phân suy rộng có thể áp dụng cho các lớp hàm liên tục không trơn rộng hơn mà dưới vi phân cổ điển khó bao quát (chẳng hạn các hàm có bước nhảy đạo hàm như hàm $-|x|$ hoặc hàm dao động $x^2 \sin(1/x)$ tại điểm 0).

3. Điều kiện chính quy Mangasarian-Fromovitz (CQ) trong Chương 2 đóng vai trò gì?
Điều kiện chính quy (CQ) đòi hỏi sự tồn tại của một vectơ hướng $v_0 \in T(D; \bar{x})$ sao cho tích vô hướng giữa $v_0$ và mọi phần tử thuộc bao lồi dưới vi phân suy rộng của các ràng buộc bất đẳng thức tích cực đều nhỏ hơn hoặc bằng một số âm xác định, đồng thời trực giao với mọi phần tử thuộc bao lồi dưới vi phân suy rộng của các ràng buộc đẳng thức. Điều kiện này đảm bảo nhân tử mục tiêu $\mu^_0$ trong điều kiện Fritz John bắt buộc phải dương tuyệt đối ($\mu^_0 > 0$), từ đó cho phép chuẩn hóa hệ số để chuyển điều kiện Fritz John thành điều kiện Kuhn-Tucker.

4. Vì sao luận án dành riêng Chương 3 và Chương 5 để nghiên cứu tựa nghiệm hữu hiệu yếu?
Vì trong thực tế tính toán tối ưu số, các thuật toán lặp sau một số hữu hạn bước chỉ thu được nghiệm gần đúng chứ không thể đạt nghiệm chính xác. Khái niệm tựa nghiệm hữu hiệu yếu (local weak quasi-efficient solution) với tham số dung sai $\alpha \in \mathbb{R}^p_{++}$ cho phép đưa ra tiêu chuẩn mềm dẻo để đánh giá tính tối ưu của nghiệm xấp xỉ trong tính toán thực tế.

5. Luận án xây dựng những mô hình đối ngẫu nào cho bài toán (MFP)?
Luận án xây dựng hai mô hình đối ngẫu kinh điển trong tối ưu hóa: mô hình đối ngẫu kiểu Mond-Weir và mô hình đối ngẫu kiểu Wolfe thông qua ngôn ngữ dưới vi phân suy rộng Jeyakumar-Luc. Hai mô hình này được thiết lập độc lập cho cả trường hợp nghiệm hữu hiệu yếu (Chương 4) và tựa nghiệm hữu hiệu yếu (Chương 5), đi kèm các chứng minh đầy đủ về đối ngẫu yếu, đối ngẫu mạnh và đối ngẫu ngược.

Kết luận

Luận án tiến sĩ của tác giả Phạm Thị Linh là công trình nghiên cứu lý thuyết hoàn chỉnh thuộc chuyên ngành Toán ứng dụng, tập trung giải quyết bài toán quy hoạch thương đa mục tiêu không trơn chứa đồng thời ràng buộc bất đẳng thức, đẳng thức và ràng buộc tập. Bằng việc kết hợp phương pháp vô hướng hóa Gong với công cụ dưới vi phân suy rộng Jeyakumar-Luc, tác giả đã thiết lập thành công hệ thống điều kiện cần Fritz John, Kuhn-Tucker và điều kiện đủ cho cả nghiệm hữu hiệu yếu lẫn tựa nghiệm hữu hiệu yếu. Đồng thời, luận án đã xây dựng hoàn chỉnh lý thuyết đối ngẫu kiểu Mond-Weir và kiểu Wolfe tương ứng, giải quyết trọn vẹn các định lý đối ngẫu yếu, đối ngẫu mạnh và đối ngẫu ngược. Các kết quả này mở rộng các nghiên cứu trước đó trong giải tích biến phân và tạo cơ sở lý thuyết toán học quan trọng cho việc nghiên cứu thuật toán tính toán tối ưu xấp xỉ.