Tổng quan luận án

Luận án tiến sĩ toán học với đề tài "Một số lớp bài toán tối ưu không lồi: Thuật toán và ứng dụng", chuyên ngành Toán học (Mã số: 9460101), được thực hiện bởi nghiên cứu sinh Phạm Thị Hoài dưới sự hướng dẫn khoa học của TS. Nguyễn Cảnh Nam và GS. Lê Thị Hoài An tại Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội (năm 2019).

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

Tối ưu không lồi và tối ưu toàn cục là các lĩnh vực nghiên cứu cốt lõi của lý thuyết tối ưu với nhiều ứng dụng thực tiễn. Kể từ công trình đặt nền móng của GS. Hoàng Tụy năm 1964 về việc tìm nghiệm tối ưu toàn cục cho bài toán cực tiểu hàm lõm với ràng buộc tuyến tính, lý thuyết tối ưu không lồi đã phát triển qua hơn nửa thế kỷ. Tuy nhiên, khó khăn căn bản của tối ưu không lồi là không có tiêu chuẩn đặc trưng tổng quát cho nghiệm tối ưu toàn cục; nghiệm tối ưu địa phương nói chung không trùng với nghiệm toàn cục, khiến cho việc giải bài toán quy mô lớn gặp nhiều thách thức.

Trong thực tế tính toán, việc giải toàn cục các bài toán tối ưu rời rạc bằng các phương pháp truyền thống như nhánh cận (Branch and Bound - BB), nhánh cắt hay siêu phẳng cắt thường gặp khó khăn lớn về thời gian tính toán. Tuy nhiên, khi chuyển đổi bài toán rời rạc về dạng bài toán tối ưu liên tục (như bài toán hiệu hai hàm lồi - DC), việc áp dụng các thuật toán chuyên dụng như DCA (DC Algorithm) đem lại hiệu quả cao. Ngược lại, một số bài toán tối ưu không lồi liên tục phức tạp cũng có thể chuyển đổi tương đương về bài toán tối ưu đơn điệu rời rạc để giải quyết bằng các kỹ thuật nhánh-giảm-cận (Branch-Reduce-Bound - BRB). Khoảng trống nghiên cứu đặt ra là:

  1. Xây dựng mô hình toán học và thuật toán toàn cục hiệu quả cho bài toán phân bổ tài nguyên trong mạng không dây OFDMA/TDD vốn trước đây chỉ được tiếp cận theo kinh nghiệm hoặc phương pháp heuristic.
  2. Thiết lập thuật toán toàn cục cho bài toán năng lượng phủ cảm biến (SCEP) trong mạng cảm biến vô tuyến, khắc phục hạn chế của các phương pháp địa phương trước đó vốn không kiểm tra được tính toàn cục của nghiệm.
  3. Nghiên cứu cấu trúc miền tìm kiếm bằng công cụ đa khối nửa mở trong không gian ảnh và đánh giá vai trò quản lý bài toán con trong quy hoạch đa mục tiêu rời rạc.
  4. Xây dựng thuật toán toàn cục cho bài toán tối ưu trên tập hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc khi hàm mục tiêu tựa lõm và đơn điệu tăng trên tập chấp nhận được hữu hạn điểm.

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

Luận án xác định 4 mục tiêu nghiên cứu cụ thể được đánh số theo văn bản:

  1. Mô hình hóa bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD dưới dạng bài toán tối ưu rời rạc, đưa bài toán này về bài toán tối ưu DC và đề xuất thuật toán toàn cục (nhánh cận kết hợp DCA) để giải.
  2. Nghiên cứu bài toán năng lượng phủ cảm biến cho mạng cảm biến vô tuyến (SCEP); đưa bài toán về dạng tối ưu đơn điệu rời rạc, xây dựng thuật toán toàn cục dựa trên lược đồ nhánh-giảm-cận cải tiến và đề xuất thêm thuật toán tìm nghiệm địa phương.
  3. Sử dụng khái niệm đa khối nửa mở để biểu diễn miền tìm kiếm của bài toán tối ưu đa mục tiêu rời rạc; đề xuất thủ tục mới cập nhật miền tìm kiếm cho lược đồ chung (Generic Method - GM) và nghiên cứu sự ảnh hưởng của việc quản lý bài toán con lưu trữ trong quá trình tìm kiếm đến hiệu quả của lược đồ GM.
  4. Nghiên cứu lớp bài toán tối ưu trên tập hữu hiệu với hàm mục tiêu đơn điệu tăng tựa lõm và tập ràng buộc là tập nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc có miền ràng buộc gồm hữu hạn điểm cho trước; đề xuất thuật toán toàn cục để giải bài toán.

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

  • Đối tượng nghiên cứu: Bốn bài toán toán học và ứng dụng bao gồm: (1) Bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD; (2) Bài toán năng lượng phủ cảm biến cho mạng cảm biến vô tuyến; (3) Bài toán xác định toàn bộ tập giá trị hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc; (4) Bài toán tối ưu trên tập hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc.
  • Phạm vi nghiên cứu: Nghiên cứu xây dựng mô hình toán học, phân tích cấu trúc giải tích và hình học của bài toán; đề xuất thuật toán tối ưu địa phương và toàn cục; lập trình tính toán thử nghiệm trên máy tính, so sánh hiệu năng của thuật toán mới với các thuật toán hiện có trên các bộ dữ liệu ngẫu nhiên và bộ dữ liệu chuẩn.

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

Các hướng nghiên cứu trước được điểm luận

Tác giả đã hệ thống hóa các tài liệu khoa học liên quan trực tiếp đến các lớp bài toán nghiên cứu:

  • Tối ưu không lồi và quy hoạch DC: Xuất phát từ nghiên cứu của Hoàng Tụy (1964) [1, 2]. Cơ sở lý thuyết quy hoạch DC và thuật toán DCA được khởi xướng bởi Phạm Đình Tảo (1986) và phát triển toàn diện bởi Lê Thị Hoài An và Phạm Đình Tảo (1994, 2005) [3, 44], cho thấy hầu hết các bài toán không lồi có thể chuyển về dạng DC và giải hiệu quả bằng DCA.
  • Tối ưu đơn điệu và tối ưu đơn điệu rời rạc: Lý thuyết tối ưu đơn điệu được Hoàng Tụy phát triển tổng quát trong tài liệu [2], cùng các công trình nghiên cứu về thuật toán xấp xỉ ngoài đa khối và thuật toán nhánh-giảm-cận (BRB) cho bài toán tối ưu đơn điệu rời rạc [41, 42].
  • Bài toán phân bổ tài nguyên OFDMA/TDD: Các công trình trước đây của các tác giả trong lĩnh vực viễn thông [47, 48, 49, 50, 51, 52, 53] chủ yếu giải quyết bài toán cấp phát tài nguyên theo kinh nghiệm kỹ thuật vô tuyến hoặc sử dụng các thuật toán heuristic, chưa thiết lập mô hình toán học chuẩn xác và chưa có thuật toán toàn cục để đánh giá nghiệm.
  • Bài toán năng lượng phủ cảm biến (SCEP): Được đề xuất bởi Astorino và Miglionico (2013) [38]. Công trình [38] sử dụng kỹ thuật hàm phạt để đưa bài toán về dạng DC liên tục và giải bằng DCA địa phương, chưa có công cụ kiểm tra tính tối ưu toàn cục.
  • Tối ưu đa mục tiêu và tối ưu trên tập hữu hiệu: Tiếp cận trên không gian ảnh đối với quy hoạch đa mục tiêu được nghiên cứu bởi Benson [5], cùng các công trình giải bài toán đa mục tiêu rời rạc bằng các phương pháp $\varepsilon$-ràng buộc, vô hướng hóa Tchebycheff, vô hướng hóa tổng có trọng của Przybylski (2010) [25], Klamroth và cộng sự (2015) [24], Dächert và Klamroth (2015) [13], Dächert và cộng sự (2017) [23]. Về bài toán tối ưu trên tập hữu hiệu (tập Pareto), công trình khởi đầu của Philip (1971) [26] xét trường hợp tuyến tính, tiếp sau đó là các nghiên cứu mở rộng [27-37].

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

Luận án tập trung giải quyết:

  1. Thiếu vắng mô hình quy hoạch toán học chặt chẽ và thuật toán toàn cục có bảo đảm hội tụ cho bài toán phân bổ tài nguyên dạng hình chữ nhật theo tiêu chuẩn IEEE 802.16e trên khung OFDMA/TDD.
  2. Thiếu thuật toán toàn cục cho bài toán SCEP do ràng buộc không lồi phức tạp; chưa có sự kết hợp giữa cấu trúc đơn điệu rời rạc và thuật toán tối ưu địa phương để tăng tốc độ phân nhánh.
  3. Miền tìm kiếm trong quy hoạch đa mục tiêu rời rạc chưa được mô tả hình học trực quan bằng đa khối nửa mở; chưa có công trình nào đánh giá sự ảnh hưởng của cách thức quản lý và lưu trữ các bài toán con vô hướng hóa đến hiệu năng của lược đồ GM.
  4. Chưa có thuật toán toàn cục cho bài toán tối ưu hàm tựa lõm đơn điệu tăng trên tập hữu hiệu của bài toán đa mục tiêu rời rạc có miền chấp nhận được là tập hữu hạn điểm.

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 hai nhánh lý thuyết giải tích lồi và tối ưu hóa không lồi:

  1. Lý thuyết tối ưu DC và đối ngẫu DC:

    • Xét không gian $\mathbb{R}^n$ và tập $\Gamma_0(\mathbb{R}^n)$ các hàm nửa liên tục dưới, lồi chính thường.
    • Hàm liên hợp Fenchel-Moreau: $f^*(y) = \sup{\langle x, y\rangle - f(x) \mid x \in \mathbb{R}^n}$.
    • Dưới vi phân: $\partial f(x_0) = {p \in \mathbb{R}^n \mid \langle p, x - x_0\rangle \le f(x) - f(x_0), \forall x \in \mathbb{R}^n}$.
    • Cặp bài toán đối ngẫu DC: $$\text{Bài toán gốc } (P): \alpha = \inf{g(x) - h(x) \mid x \in \mathbb{R}^n}$$ $$\text{Bài toán đối ngẫu } (D): \alpha = \inf{h^(y) - g^(y) \mid y \in \mathbb{R}^n}$$
    • Điều kiện tối ưu: Điểm tới hạn thỏa mãn $\partial g(x^) \cap \partial h(x^) \neq \emptyset$.

  2. Lý thuyết tối ưu đơn điệu (Monotonic Optimization - MO) và Tối ưu đơn điệu rời rạc (DMO):

    • Tập chuẩn $G \subset [a, b]$ (nếu $x \in G, a \le x' \le x \Rightarrow x' \in G$) và tập đối chuẩn $H \subset [a, b]$ (nếu $x \in H, x \le x' \le b \Rightarrow x' \in H$).
    • Khái niệm đa khối (polyblock) $P = \bigcup_{z \in T} [a, z]$ xác định bởi tập đỉnh $T$, đa khối nửa mở $P' = \bigcup_{z \in T} [a, z)$, đỉnh chính, phép chiếu $\pi_G(z)$ lên biên trên $\partial^+ G$ và phép chiếu $\rho_H(z)$ lên biên dưới $\partial^- H$.
    • Dạng bài toán tối ưu đơn điệu rời rạc tổng quát (DDM): $\max{f(x) \mid g(x) - h(x) \le 0, x \in [a, b] \cap S^*}$.

Phương pháp nghiên cứu và kỹ thuật tính toán

  • Phương pháp chuyển đổi bài toán và kỹ thuật hàm phạt: Chuyển đổi các biến nhị phân $x_i \in {0, 1}$ qua hàm phạt lõm $p(x) = \sum_{i=1}^n \min{x_i, 1 - x_i}$ để đưa bài toán quy hoạch nhị phân về bài toán quy hoạch DC đa diện tương đương $\min {c^T x + \tau p(x) \mid x \in S}$.
  • Thuật toán DCA (DC Algorithm): Xây dựng hai dãy ${x^k}$ và ${y^k}$ qua công thức $y^k \in \partial h(x^k)$ và $x^{k+1} \in \partial g^*(y^k) = \arg\min {g(x) - \langle x, y^k\rangle \mid x \in \mathbb{R}^n}$.
  • Thuật toán nhánh cận kết hợp DCA: Nhúng thuật toán DCA vào quy trình tính toán cận trên của từng nút trong cây nhánh cận để sớm thu được nghiệm chấp nhận được chất lượng cao, phục vụ việc cắt tỉa nhánh.
  • Thuật toán nhánh-giảm-cận (BRB): Kết hợp phép chia đôi hộp, thủ tục cắt giảm gồm hai giai đoạn ($\gamma$-cắt giảm và $S$-hiệu chỉnh) và phép tính cận trên $\omega(M)$ trên từng hộp.
  • Phương pháp tiếp cận trên không gian ảnh: Thay vì tìm tập nghiệm hữu hiệu $X_E \subset \mathbb{R}^n$, thuật toán tìm tập giá trị hữu hiệu $Y_N = f(X_E) \subset \mathbb{R}^m$ với số mục tiêu $m \ll n$.

Nguồn tư liệu và môi trường thử nghiệm

  • Thuật toán được lập trình bằng ngôn ngữ C++.
  • Sử dụng solver mã nguồn mở CLP trong bộ thư viện COIN-OR để giải các bài toán quy hoạch tuyến tính con.
  • Môi trường thực nghiệm: Máy tính cá nhân phần cứng Intel Core i3, CPU 2.53GHz.
  • Dữ liệu thực nghiệm bao gồm 10 bộ dữ liệu ngẫu nhiên với kích thước biến tăng dần cho bài toán phân bổ tài nguyên OFDMA/TDD; các bộ dữ liệu mô phỏng vị trí cảm biến và điểm đích trong không gian 2D/3D cho bài toán SCEP; các bộ dữ liệu thử nghiệm tối ưu đa mục tiêu với số mục tiêu $m$ và số điểm khác nhau.

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

Chương 1. Kiến thức chuẩn bị

Chương 1 hệ thống hóa các cơ sở giải tích và hình học làm nền tảng cho các thuật toán ở Chương 2 và Chương 3:

  1. Lý thuyết tối ưu DC: Trình bày định nghĩa hàm lồi chính thường, hàm liên hợp, dưới vi phân, $\varepsilon$-dưới vi phân. Luận án nêu chi tiết Định lý hàm phạt (Định lý 2.1) cho phép đưa bài toán tối ưu với ràng buộc hàm lõm về dạng bài toán tối ưu DC không ràng buộc thông qua tham số phạt $\tau > \tau_0$. Cấu trúc thuật toán DCA tổng quát được trình bày cùng điều kiện hội tụ đến điểm tới hạn sau hữu hạn bước lặp đối với trường hợp DC đa diện.
  2. Lý thuyết tối ưu đơn điệu: Định nghĩa tập chuẩn, tập đối chuẩn, đa khối, đối đa khối, đa khối nửa mở và các tính chất cực trị của hàm đơn điệu trên đỉnh chính. Luận án trình bày thuật toán xấp xỉ ngoài đa khối cho bài toán đơn điệu chính tắc (MO'), phân tích nguyên nhân hội tụ chậm do sự bùng nổ số đỉnh ($n$ nút con ở mỗi bước).
  3. Thuật toán nhánh-giảm-cận (BRB) cho bài toán tối ưu đơn điệu rời rạc tổng quát (DDM): Trình bày chi tiết 3 kỹ thuật cơ bản:
    • Phép chia nhánh: Chia đôi hộp $M = [p, q]$ theo cạnh dài nhất tại tọa độ $i_M$.
    • Phép cắt giảm: Thực hiện $\gamma$-cắt giảm để thu gọn hộp theo mức giá trị kỷ lục hiện tại $\gamma$, tiếp theo là phép $S$-hiệu chỉnh dưới $\lceil p'\rceil_{S^}$ và $S$-hiệu chỉnh trên $\lfloor q'\rfloor_{S^}$ dựa trên cấu trúc rời rạc của tập $S$.
    • Phép tính cận: Xây dựng cận trên $\omega(M)$ thỏa mãn điều kiện hội tụ thắt dần khi đường kính hộp tiến về 0.

Chương 2. Thuật toán giải một số bài toán tối ưu không lồi trong viễn thông

Chương này giải quyết hai bài toán tối ưu thực tiễn trong ngành viễn thông:

1. Bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD (RAP)

Mạng có $K$ người dùng, $M$ kênh con và $N$ khe thời gian; $b_{ijk}$ là lượng dữ liệu người dùng $k$ cần gửi tại kênh $i$, khe thời gian $j$. Bài toán tối ưu hóa tổng thông lượng: $$\max f(x) = \sum_{k=1}^K \sum_{i=1}^M \sum_{j=1}^N b_{ijk} x_{ijk}$$ với các ràng buộc:

  • Ràng buộc không xung đột: $\sum_{k=1}^K x_{ijk} \le 1, \forall i \in {1, \dots, M}, j \in {1, \dots, N}$.
  • Ràng buộc cấu trúc hình chữ nhật (theo chuẩn IEEE 802.16e của WiMAX): $$\sum_{i \in I_{i_1 i_2}} \sum_{j \in J_{j_1 j_2}} (|i_1 - i_2| + 1)(|j_1 - j_2| + 1)(x_{i_1 j_1 k} + x_{i_2 j_2 k} - 1) - x_{ijk} \le 0$$ với $I_{i_1 i_2} = {i \mid \min{i_1, i_2} \le i \le \max{i_1, i_2}}$, $J_{j_1 j_2} = {j \mid \min{j_1, j_2} \le j \le \max{j_1, j_2}}$.

Tổng số biến nhị phân là $n = M \cdot N \cdot K$, số ràng buộc là $M \cdot N + K \frac{MN(MN-1)}{2}$. Bằng cách áp dụng hàm phạt $p(x) = \sum_{i=1}^n \min{x_i, 1 - x_i}$, bài toán nhị phân (RAP) được chuyển đổi thành bài toán tối ưu DC đa diện $\min {c^T x + \tau p(x) \mid x \in S}$. Thuật toán DCA (Thuật toán 2.1) được thiết lập, quy việc tìm dãy ${x^k}$ về việc giải các bài toán quy hoạch tuyến tính con.

Để tìm nghiệm tối ưu toàn cục, luận án đề xuất Thuật toán 2.3 (nhánh cận kết hợp DCA). So sánh thực nghiệm trên 10 bộ dữ liệu ngẫu nhiên với sai số $\varepsilon = 10^{-2}$ và giới hạn $10^5$ bước lặp được tổng hợp trong bảng sau:

Bộ dữ liệu $M$ $N$ $K$ Số biến (#Var) Số ràng buộc (#Constr) Thuật toán 2.2 (Nhánh cận cổ điển) - Số bước lặp (#Iter) Thuật toán 2.2 - Thời gian (s) Thuật toán 2.3 (Nhánh cận + DCA) - Số bước lặp (#Iter) Thuật toán 2.3 - Cận trên (UB) Thuật toán 2.3 - Cận dưới (LB) Thuật toán 2.3 - Thời gian (s) Lần chạy DCA cho nghiệm tốt (No F)
1 3 3 4 36 153 5 1.4 5 4981 4981 1.4 1
9 5 4 6 120 1160 Thất bại - 399 12367 12356 1500 2
10 5 5 5 125 1525 Thất bại - 278 98794 98765 1809 2

Kết quả cho thấy DCA tìm được nghiệm chấp nhận được ngay từ lần chạy thứ 1 hoặc thứ 2. Thuật toán 2.3 giải quyết thành công các bài toán kích thước lên đến 125 biến trong khi thuật toán nhánh cận cổ điển (Thuật toán 2.2) thất bại sau $10^5$ bước lặp.

2. Bài toán năng lượng phủ cảm biến cho mạng cảm biến vô tuyến (SCEP)

Xét mạng gồm $n$ cảm biến tại vị trí $s_i \in \mathbb{R}^p$ và $m$ điểm đích tại $t_j \in \mathbb{R}^p$ ($p = 2$ hoặc $3$). Năng lượng tiêu thụ của cảm biến $i$ là $E_i(r_i) = \alpha_i r_i^{\beta_i} + \gamma$ với bán kính $r_i \in [l_i, u_i]$. Bài toán tối ưu năng lượng toàn mạng: $$\min \sum_{i=1}^n E_i(r_i) \quad \text{với điều kiện mỗi điểm đích được phủ bởi ít nhất một cảm biến}$$ Bằng cách đổi biến $x_i = \alpha_i r_i^{\beta_i}$, $a_{ji} = \alpha_i |s_i - t_j|^{\beta_i}$, bài toán trở thành bài toán tối ưu hàm tuyến tính với các ràng buộc lồi đảo $g_j(x) = \max_{1 \le i \le n} (x_i - a_{ji}) \ge 0, \forall j = 1, \dots, m$.

Luận án nhận diện tính chất đơn điệu của hàm $g_j(x)$ và chuyển đổi tương đương bài toán về dạng tối ưu đơn điệu rời rạc. Tác giả đề xuất 3 thuật toán:

  • Thuật toán tìm nghiệm địa phương.
  • Thuật toán toàn cục nhánh-giảm-cận (BRB) truyền thống.
  • Thuật toán nhánh-giảm-cận cải tiến (Thuật toán 2.6): sử dụng nghiệm chấp nhận được từ thuật toán địa phương để liên tục cập nhật kỷ lục $\gamma$, tăng tốc loại bỏ các hộp không chứa nghiệm.

Thực nghiệm cho thấy thuật toán địa phương giải được các bài toán có số biến lên đến $n = 1000$, trong khi thuật toán BRB cải tiến giải toàn cục hiệu quả các bài toán có kích thước đến $n = 75$ biến.

Chương 3. Thuật toán trên không gian ảnh giải bài toán tối ưu đa mục tiêu rời rạc

Chương này tập trung vào bài toán tối ưu đa mục tiêu rời rạc (MODO) và bài toán tối ưu trên tập hữu hiệu:

  1. Biểu diễn miền tìm kiếm bằng đa khối nửa mở:
    • Đối với bài toán MODO có $m$ hàm mục tiêu và không gian quyết định $\mathbb{R}^n$ ($m \ll n$), việc tìm kiếm trên không gian ảnh $Y_N = f(X_E)$ giúp giảm độ phức tạp tính toán.
    • Luận án sử dụng đa khối nửa mở để mô tả miền tìm kiếm $S(N)$ sau mỗi bước lặp của lược đồ GM.
    • Đề xuất thủ tục cập nhật miền tìm kiếm mới, xác định chính xác tập đỉnh của đa khối nửa mở nhằm loại bỏ triệt để các phần không gian không chứa điểm giá trị hữu hiệu.
  2. Nghiên cứu ảnh hưởng của việc quản lý bài toán con:
    • Luận án phân tích cấu trúc lưu trữ và thứ tự giải các bài toán con tạo ra từ phép vô hướng hóa trong suốt quá trình thực thi lược đồ GM.
    • Các thử nghiệm số khẳng định chiến lược quản lý bài toán con tác động trực tiếp đến số lượng bài toán vô hướng hóa phải giải và thời gian tính toán tổng thể.
  3. Thuật toán giải bài toán tối ưu trên tập hữu hiệu:
    • Xét bài toán cực đại hàm mục tiêu đơn điệu tăng, tựa lõm trên tập nghiệm hữu hiệu $X_E$ của bài toán tối ưu đa mục tiêu rời rạc có miền chấp nhận được $X$ là tập hữu hạn điểm.
    • Xây dựng thuật toán toàn cục dựa trên việc duyệt tập đỉnh của bao đa khối trong không gian ảnh kết hợp với giải bài toán vô hướng hóa tương ứng. Thử nghiệm số chứng minh tính đúng đắn và hiệu năng của thuật toán.

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

Đóng góp về lý luận và thuật toán

  1. Về bài toán phân bổ tài nguyên OFDMA/TDD: Thiết lập mô hình quy hoạch nguyên nhị phân hoàn chỉnh kết hợp ràng buộc hình chữ nhật IEEE 802.16e; chứng minh sự tương đương giữa bài toán gốc và bài toán tối ưu DC đa diện; xây dựng thuật toán toàn cục nhánh cận kết hợp DCA, chứng minh tính dừng hữu hạn và hội tụ về $\varepsilon$-nghiệm tối ưu toàn cục.
  2. Về bài toán năng lượng phủ cảm biến (SCEP): Phát hiện cấu trúc tối ưu đơn điệu ẩn trong mô hình ràng buộc lồi đảo; đưa bài toán SCEP về bài toán tối ưu đơn điệu rời rạc tương đương; đề xuất thuật toán nhánh-giảm-cận cải tiến kết hợp nghiệm địa phương, khắc phục hạn chế không kiểm tra được tính toàn cục của các nghiên cứu trước.
  3. Về bài toán tối ưu đa mục tiêu rời rạc: Ứng dụng thành công đa khối nửa mở để mô tả hình học miền tìm kiếm trên không gian ảnh; đề xuất thủ tục cập nhật miền tìm kiếm mới cho lược đồ GM; lần đầu tiên khảo sát và đánh giá thực nghiệm ảnh hưởng của chiến lược quản lý bài toán con đối với hiệu quả của lược đồ GM.
  4. Về bài toán tối ưu trên tập hữu hiệu: Đề xuất thuật toán toàn cục giải bài toán tối ưu hàm tựa lõm đơn điệu tăng trên tập hữu hiệu của bài toán đa mục tiêu rời rạc có miền chấp nhận được là tập hữu hạn điểm.

Ý nghĩa thực tiễn và giải pháp kỹ thuật

  • Cung cấp công cụ toán học hỗ trợ các nhà cung cấp mạng không dây OFDMA/TDD phân bổ kênh truyền và khe thời gian tối ưu, tối đa hóa thông lượng dữ liệu và nâng cao chất lượng dịch vụ (QoS).
  • Đưa ra giải pháp cấu hình bán kính hoạt động của các nút cảm biến trong mạng cảm biến vô tuyến, giúp tiết kiệm năng lượng pin và kéo dài thời gian vận hành của toàn mạng.

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

Theo nội dung văn bản luận án và phạm vi nghiên cứu thực nghiệm:

  • Hạn chế về quy mô giải toán toàn cục: Thuật toán nhánh cận kết hợp DCA giải toàn cục bài toán OFDMA/TDD đạt hiệu quả tốt với quy mô biến nhị phân đến $n = 125$. Đối với bài toán SCEP, thuật toán toàn cục BRB cải tiến giải được bài toán có quy mô lên đến $n = 75$ cảm biến. Khi quy mô bài toán tăng lên mức lớn hơn, chi phí thời gian cho việc phân nhánh và tính cận tăng nhanh.
  • Hướng nghiên cứu tiếp được mở ra:
    1. Nghiên cứu cải tiến các kỹ thuật chia nhánh và phép cắt giảm hộp để nâng cao khả năng giải toàn cục cho bài toán OFDMA/TDD và bài toán SCEP với số lượng biến lớn hơn.
    2. Mở rộng ứng dụng của cấu trúc đa khối nửa mở cho các lớp bài toán quy hoạch đa mục tiêu phi tuyến phức tạp hơn.
    3. Phát triển các thuật toán song song hóa cho lược đồ BRB và lược đồ quản lý bài toán con trong quy hoạch đa mục tiêu rời rạc.

Giá trị tham khảo

Luận án là tài liệu tham khảo hữu ích cho 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, Tối ưu hóa: Tham khảo cách vận dụng giải tích lồi, phép biến đổi DC, lý thuyết tối ưu đơn điệu, đa khối nửa mở và các kỹ thuật chứng minh hội tụ thuật toán trong Chương 1, Chương 2 và Chương 3.
  • Kỹ sư, nhà nghiên cứu trong lĩnh vực Viễn thông và Mạng cảm biến không dây: Tham khảo mô hình toán học và mã giả thuật toán phân bổ tài nguyên OFDMA/TDD (Mục 2.1) cùng thuật toán tối ưu năng lượng cảm biến SCEP (Mục 2.2) để ứng dụng trong bài toán điều khiển mạng thực tế.
  • Nhà nghiên cứu Khoa học dữ liệu và Hỗ trợ ra quyết định: Tham khảo kỹ thuật tiếp cận trên không gian ảnh và thuật toán tối ưu trên tập hữu hiệu rời rạc trong Chương 3.

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

1. Hàm phạt nào được sử dụng để chuyển đổi bài toán phân bổ tài nguyên nhị phân về bài toán tối ưu DC?

Luận án sử dụng hàm phạt lõm $p(x) = \sum_{i=1}^n \min{x_i, 1 - x_i}$ trên miền đa diện $S = {x \in [0, 1]^n \mid x \text{ thỏa mãn các ràng buộc tuyến tính}}$. Vì $p(x) \ge 0, \forall x \in S$ và $p(x) = 0 \Leftrightarrow x \in {0, 1}^n$, nên với tham số phạt $\tau > \tau_0$ đủ lớn, bài toán nhị phân tương đương với bài toán tối ưu DC đa diện $\min {c^T x + \tau p(x) \mid x \in S}$.

2. Thuật toán 2.3 (Nhánh cận kết hợp DCA) có ưu điểm gì so với thuật toán nhánh cận cổ điển (Thuật toán 2.2)?

Thuật toán 2.3 khởi động DCA tại nghiệm của bài toán nới lỏng tuyến tính ở từng nút phân nhánh. DCA nhanh chóng tìm ra nghiệm nguyên chấp nhận được chất lượng cao ngay ở lần chạy thứ 1 hoặc thứ 2, giúp cập nhật cận trên sớm và cắt tỉa hiệu quả các nhánh không chứa nghiệm tối ưu. Thực nghiệm cho thấy Thuật toán 2.3 giải được các bài toán quy mô 120-125 biến mà nhánh cận cổ điển thất bại sau $10^5$ bước lặp.

3. Làm thế nào bài toán năng lượng phủ cảm biến (SCEP) được chuyển đổi về bài toán tối ưu đơn điệu rời rạc?

Bằng phép đổi biến $x_i = \alpha_i r_i^{\beta_i}$, bài toán SCEP chuyển về dạng cực tiểu hàm tuyến tính với các ràng buộc lồi đảo $g_j(x) = \max_{1 \le i \le n} (x_i - a_{ji}) \ge 0$. Do các hàm $g_j(x)$ đều là hàm đơn điệu tăng theo từng biến $x_i$, bài toán mang cấu trúc tối ưu đơn điệu và được chuyển đổi tương đương về bài toán tối ưu đơn điệu rời rạc trên hộp.

4. Tại sao tiếp cận trên không gian ảnh lại hiệu quả hơn không gian quyết định trong bài toán tối ưu đa mục tiêu rời rạc?

Trong nhiều bài toán thực tế, số hàm mục tiêu $m$ nhỏ hơn rất nhiều so với số chiều biến quyết định $n$ ($m \ll n$). Cấu trúc của tập giá trị hữu hiệu $Y_N = f(X_E) \subset \mathbb{R}^m$ đơn giản hơn nhiều so với tập nghiệm hữu hiệu $X_E \subset \mathbb{R}^n$, do đó việc tìm kiếm và cập nhật miền tìm kiếm trên không gian ảnh giúp giảm đáng kể thời gian và khối lượng tính toán.

Kết luận

Luận án "Một số lớp bài toán tối ưu không lồi: Thuật toán và ứng dụng" của tác giả Phạm Thị Hoài đã giải quyết trọn vẹn 4 bài toán tối ưu không lồi từ lý thuyết giải tích đến thực nghiệm ứng dụng trong viễn thông và quy hoạch đa mục tiêu rời rạc. Bằng việc kết hợp lý thuyết tối ưu DC, thuật toán DCA, lý thuyết tối ưu đơn điệu và công cụ đa khối nửa mở, tác giả đã đề xuất các thuật toán tối ưu địa phương và toàn cục mới có tính dừng và tính hội tụ chặt chẽ. Kết quả thực nghiệm trên các bộ dữ liệu ngẫu nhiên và mô phỏng đã chứng minh tính hiệu quả của các thuật toán đề xuất so với các phương pháp truyền thống. Các công trình công bố trên các tạp chí quốc tế chuyên ngành khẳng định giá trị học thuật và đóng góp chuyên môn của luận án.