Tổng quan về luận án

Trong bối cảnh nền kinh tế số, điều khiển kỹ thuật và phân tích tài chính hiện đại, các bài toán ra quyết định thực tiễn hiếm khi chỉ tồn tại một mục tiêu đơn lẻ mà luôn đòi hỏi sự cân bằng đồng thời giữa nhiều tiêu chí xung đột. Lý thuyết Quy hoạch đa mục tiêu (Multiobjective Programming - MOP) hay Tối ưu véc-tơ (Vector Optimization) được khởi nguồn từ những năm 50 của thế kỷ 20 và không ngừng hoàn thiện. Theo luận án: "Do không gian giá trị $\mathbb{R}^p$ không có thứ tự đầy đủ nên thay vì khái niệm nghiệm tối ưu thông thường, tối ưu véc tơ sử dụng khái niệm nghiệm hữu hiệu được xác định theo thứ tự từng phần do F. Hausdorff (1868-1942) [37] đề xuất." Mặc dù lý thuyết quy hoạch đa mục tiêu tuyến tính (LMOP) và quy hoạch lồi (CMOP) đã đạt được nền tảng lý luận tương đối hoàn chỉnh, nhưng các lớp bài toán phi lồi, bài toán lồi suy rộng (Generalized Convex Multiobjective Programming - GMOP), quy hoạch tích mở rộng (GMP, GIMP) và bài toán tối ưu trên tập nghiệm hữu hiệu (Optimization over Efficient Sets) vẫn tồn tại những rào cản thuật toán và khoảng trống lý thuyết sâu sắc do tính phi lồi phức tạp và cấu trúc ẩn của tập nghiệm hữu hiệu $X_E$.

Luận án Tiến sĩ Toán học chuyên ngành Toán ứng dụng (Mã số: 62460112) của nghiên cứu sinh Trần Ngọc Thăng, dưới sự hướng dẫn khoa học của PGS. Nguyễn Thị Bạch Kim và GS. Đinh Thế Lục tại Viện Toán ứng dụng và Tin học - Trường Đại học Bách Khoa Hà Nội, đã tạo nên một bước tiến quan trọng. Đề tài tập trung giải quyết 3 câu hỏi nghiên cứu cốt lõi:

  1. Câu hỏi nghiên cứu 1 (RQ1): Làm thế nào để thiết lập thuật toán xấp xỉ ngoài hướng pháp tuyến trên không gian ảnh giải bài toán quy hoạch đa mục tiêu lồi suy rộng (GMOP) với hàm mục tiêu giả lồi vô hướng (scalarly pseudoconvex) và chứng minh toán học tính hội tụ toàn cục?
  2. Câu hỏi nghiên cứu 2 (RQ2): Cấu trúc hình học của bài toán quy hoạch tích lồi suy rộng (GMP) và quy hoạch tích lõm mở rộng (GIMP) có thể chuyển hóa như thế nào sang bài toán trên không gian ảnh $\mathbb{R}^p$ nhằm vượt qua rào cản NP-khó?
  3. Câu hỏi nghiên cứu 3 (RQ3): Làm thế nào để giải quyết hữu hiệu bài toán tối ưu hàm tựa lõm và hàm đơn điệu tăng trên tập nghiệm Pareto của bài toán quy hoạch hai mục tiêu lồi (DP, QP) mà không cần tính toán toàn bộ tập nghiệm hữu hiệu $X_E$?

Khung lý thuyết của công trình được định vị trên nền tảng Giải tích lồi (Convex Analysis) của Rockafellar (1970), Điều kiện tối ưu Karush-Kuhn-Tucker (KKT) suy rộng, Lý thuyết nón pháp tuyến (Normal Cones) và Không gian ảnh (Outcome Space Representation). Đóng góp mang tính đột phá của luận án nằm ở việc chuyển dịch không gian giải từ không gian quyết định $\mathbb{R}^n$ ($n$ lớn) sang không gian ảnh $\mathbb{R}^p$ ($p \ll n$), giúp giảm thiểu độ phức tạp tính toán theo cấp số nhân. Công trình được tài trợ bởi Quỹ Phát triển Khoa học và Công nghệ Quốc gia (NAFOSTED) và công bố trên các tạp chí quốc tế uy tín thuộc danh mục ISI/Scopus như Pacific Journal of Optimization, Optimization, Journal of Industrial and Management Optimization, và Advances in Intelligent Systems and Computing.

Literature Review và Positioning

Nghiên cứu tối ưu véc-tơ trên không gian quyết định $\mathbb{R}^n$ truyền thống đối mặt với những thách thức tính toán to lớn. Các công trình kinh điển của Chankong & Haimes (1983) [20], Cohon (1978) [25], Miettinen (1999) [66], và Sawaragi et al. (1985) [83] đã phát triển các phương pháp vô hướng hóa như phương pháp trọng số (weighting method), $\epsilon$-ràng buộc ($\epsilon$-constraint), phương pháp hàm lợi ích và chuẩn khoảng cách Tchebycheff. Tuy nhiên, khi chuyển sang các lớp bài toán lồi suy rộng và tối ưu toàn cục trên tập nghiệm hữu hiệu, cấu trúc của tập nghiệm hữu hiệu $X_E$ và tập hữu hiệu yếu $X_{wE}$ trong $\mathbb{R}^n$ trở nên phi lồi, không liên thông hoặc có biên cực kỳ phức tạp.

flowchart TD
    subgraph Literature_Streams["Các nhánh nghiên cứu tiền đề"]
        A["Quy hoạch đa mục tiêu tuyến tính & lồi<br/>(Ehrgott 2005, Benson 1998, Miettinen 1999)"]
        B["Tối ưu trên tập nghiệm hữu hiệu<br/>(Philip 1972, Horst & Tuy 1996, Thoai 2000)"]
        C["Quy hoạch tích NP-khó<br/>(Matsui 1996, Kuno 2005, Benson 1999)"]
    end
    
    subgraph Research_Gap["Khoảng trống học thuật"]
        D["Thiếu thuật toán xác thực hội tụ cho GMOP giả lồi"]
        E["Bế tắc thuật toán cho bài toán tích GIMP tổng quát"]
        F["Gánh nặng chiều không gian quyết định R^n"]
    end
    
    subgraph Thesis_Positioning["Định vị đột phá của Luận án"]
        G["Tiếp cận không gian ảnh Outcome Space R^p (p << n)"]
        H["Thuật toán hướng pháp tuyến Outer Approximation Solve(GMOP)"]
        I["Kỹ thuật Nhánh cận kết hợp Xấp xỉ ngoài (Branch-and-Bound Outer Approximation)"]
    end
    
    A --> D
    B --> F
    C --> E
    D & E & F --> Thesis_Positioning

Hai cuộc tranh luận học thuật lớn trong tối ưu hóa đa mục tiêu đã chi phối quá trình hình thành đề tài:

  • Tranh luận 1 (Không gian quyết định vs. Không gian ảnh): Nhánh tiếp cận quyết định (Decision Space) cố gắng mô tả hình học toàn bộ $X_E$, nhưng gặp bế tắc khi $n \ge 100$. Nhánh tiếp cận ảnh (Outcome Space) do Dauer (1993), Benson (1998) [11], Ehrgott et al. (2011) [30], và Löhne (2011) [59] khởi xướng đã chứng minh rằng số mục tiêu $p$ trong thực tế thường rất nhỏ so với $n$ ($p \in [2, 5]$ trong khi $n$ có thể lên tới hàng ngàn). Tuy nhiên, các thuật toán xấp xỉ ngoài trên không gian ảnh của Ehrgott, Shao & Benson (2011) [30] và Heyde & Löhne (2008) [55] mới chỉ giải quyết cho bài toán lồi (CMOP) và chưa chứng minh được sự hội tụ toán học chặt chẽ.
  • Tranh luận 2 (Độ phức tạp của Quy hoạch tích): Nguồn trích dẫn luận án chỉ rõ: "Matsui đã chỉ ra rằng, ngay cả trường hợp đơn giản nhất của bài toán (MP), tức là bài toán (LMP) với $p = 2$ và $X$ là đa diện khác rỗng, cũng thuộc lớp bài toán NP-khó." Hầu hết các thuật toán của Kuno (2005) hay Benson (1999) [14] chỉ giải được trường hợp tích 2 hàm lõm hoặc bài toán tuyến tính. Đối với bài toán quy hoạch tích lõm mở rộng (GIMP) dạng $\max_{x \in X} [f_0(x) + \prod_{i=1}^k f_i(x)]$ với $k \ge 2$, y văn quốc tế hầu như chưa có thuật toán toàn cục hữu hiệu.

Luận án của NCS. Trần Ngọc Thăng đã định vị chính xác tại giao điểm của hai khoảng trống này, mở rộng phạm vi từ tối ưu lồi sang lồi suy rộng (giả lồi vô hướng), thiết lập chứng minh hội tụ hoàn chỉnh cho thuật toán hướng pháp tuyến và kiến tạo lược đồ nhánh cận cải tiến cho bài toán quy hoạch tích và tối ưu trên tập Pareto.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án đóng góp nền tảng vào lý thuyết tối ưu hóa toán học qua các trụ cột:

  1. Mở rộng phạm vi hàm mục tiêu sang lớp Giả lồi vô hướng (Scalarly Pseudoconvex): Luận án đưa ra định nghĩa chuẩn xác: "Hàm véc tơ $f$ được gọi là giả lồi vô hướng trên một tập lồi $S$ nếu $\sum_{j=1}^p \lambda_j f_j$ là hàm giả lồi trên $S$ với mọi $\lambda = (\lambda_1, ..., \lambda_p) \ge 0$." Luận án chứng minh rằng tính chất nghiệm dừng KKT là nghiệm tối ưu toàn cục vẫn được bảo toàn dưới điều kiện chính quy Slater, cho phép xây dựng siêu phẳng tựa và siêu phẳng cắt mà không cần giả thiết lồi chặt.
  2. Cấu trúc tô-pô của tập ảnh tương đương hữu hiệu: Luận án phát triển lý thuyết về tập tương đương hữu hiệu $Y^+ = Y + \mathbb{R}^p_+$ và $Y^- = Y - \mathbb{R}^p_+$. Mệnh đề khẳng định: Nếu $Y^+$ là tập lồi thì tập ảnh hữu hiệu $Y_E = \text{Min} Y$ là liên thông và tập ảnh hữu hiệu yếu $Y_{wE} = \text{WMin} Y$ là liên thông đường, đồng thời $\partial Y^+ = \text{WMin} Y^+$.
  3. Mệnh đề về nón pháp tuyến và điều kiện cực trị: Luận án thiết lập mối liên hệ đẳng cấu giữa hướng pháp tuyến không âm của tập ảnh gốc $Y$ và nón pháp tuyến $N_{Y^+}(\bar{y})$ của tập tương đương hữu hiệu: $$N_{Y^+}(\bar{y}) \cap \mathbb{R}^p_+ = N_Y(\bar{q}) \cap {\lambda \in \mathbb{R}^p_+ : \langle \lambda, \bar{y} - \bar{q} \rangle = 0}$$

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp ba trụ cột giải tích:

  • Tập đa diện xấp xỉ ngoài bao bọc: Dãy đa diện lồng nhau ${B^k}$ trong không gian ảnh $\mathbb{R}^p$: $$B^0 \supset B^1 \supset \dots \supset B^k \supset Y^0 \supset Y^+$$ với siêu phẳng cắt tại bước $k$ được tạo bởi hướng pháp tuyến $\lambda^k$: $$B^{k+1} = {y \in B^k \mid \langle \lambda^k, y \rangle \ge \langle \lambda^k, y^k \rangle}$$
  • Phép chiếu đơn tia chuẩn hóa: Từ điểm lý tưởng $y^0 < b < y^m$, tia xuất phát $P = {y^0 + t(v^k - y^0) \mid t \ge 0}$ xuyên qua đỉnh $v^k \in B^k \setminus Y^+$ cắt biên $\partial Y^+$ tại điểm hữu hiệu yếu duy nhất $w^k = y^0 + \bar{t}(v^k - y^0)$.
  • Khung biên giới hạn sai số $\epsilon$: Khái niệm điểm hữu hiệu $\theta$-xấp xỉ ngoài với $\theta = \epsilon e$ ($e = (1,\dots,1)^T \in \mathbb{R}^p$) đảm bảo thuật toán dừng chính xác sau một số hữu hạn bước lặp khi $|w^k - v^k| \le \epsilon$.
classDiagram
    class OutcomeSpaceFramework {
        +Set Y = f(X) Outcome Set
        +Set Y_plus = Y + R^p_+ Equivalent Set
        +Bounding Box B0 = [b, d]
        +Ideal Point y0
        +generate_cut_hyperplane(lambda_k, y_k)
        +project_ray(v_k, y0) Point w_k
    }
    class NormalConeTheory {
        +Vector lambda in N_Y(y_k)
        +Solve KKT System
        +Gradient Combination sum lambda_j grad(f_j)
        +Slater Regularity Condition
    }
    class BranchAndBoundOuterApprox {
        +Simplex Partitioning S(y_l, y_u)
        +Subproblem Bounding
        +Adaptive Bisection Rule
        +Pruning Infeasible Regions
    }
    OutcomeSpaceFramework <|-- NormalConeTheory : Supplies Normal Direction Cuts
    OutcomeSpaceFramework <|-- BranchAndBoundOuterApprox : Integrates for Non-convex Global Search

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

Thiết kế nghiên cứu

Luận án tuân thủ triệt để quan điểm nhận thức luận duy thực diễn dịch (deductive rationalism) kết hợp phương pháp giải tích hình học đối ngẫu trong tối ưu hóa phi tuyến. Thiết kế phương pháp luận lấy trọng tâm là chuyển dịch toàn bộ quá trình tìm kiếm nghiệm từ không gian biến $x \in \mathbb{R}^n$ sang không gian tiêu chí $y \in \mathbb{R}^p$.

+-------------------------------------------------------------------------+
|                        QUY TRÌNH THUẬT TOÁN SOLVE(GMOP)                 |
+-------------------------------------------------------------------------+
| Bước 0: KHỞI TẠO                                                        |
|   - Chọn sai số e > 0, véc-tơ đơn vị e = (1,...,1)^T                     |
|   - Giải tìm điểm lý tưởng y^m và y^M                                   |
|   - Tạo hộp khởi tạo B^0 = B[b, d] chứa Y^0; Khởi tạo tập đỉnh V^0      |
|   - Đặt k = 0, EO = trống, EY = trống                                   |
+-------------------------------------------------------------------------+
                                    |
                                    v
+-------------------------------------------------------------------------+
| Bước 1: KIỂM TRA ĐIỀU KIỆN DỪNG                                         |
|   - Nếu V^k c EO: DỪNG THUẬT TOÁN (Tập nghiệm e-xấp xỉ hoàn tất)        |
|   - Ngược lại: Chọn một đỉnh v^k thuộc V^k \ EO                         |
+-------------------------------------------------------------------------+
                                    |
                                    v
+-------------------------------------------------------------------------+
| Bước 2: BÀI TOÁN CON TÌM ĐIỂM HỮU HIỆU YẾU TRÊN TIA                    |
|   - Giải bài toán đơn biến min t: y^0 + t(v^k - y^0) thuộc Y^+          |
|     (Tương đương bài toán quy hoạch lồi vô hướng P^2(v^k))              |
|   - Xác định x^k in X, tính y^k = f(x^k) và w^k = y^0 + t_k(v^k - y^0)  |
|   - Cập nhật EY = EY hợp {y^k}                                          |
+-------------------------------------------------------------------------+
                                    |
                                    v
+-------------------------------------------------------------------------+
| Bước 3: ĐÁNH GIÁ SAI SỐ VÀ XÂY DỰNG SIÊU PHẲNG CẮT                     |
|   - Nếu ||w^k - v^k|| <= e:                                             |
|       + Đỉnh v^k đạt xấp xỉ ngoài -> Cập nhật EO = EO hợp {v^k}         |
|   - Ngược lại (||w^k - v^k|| > e):                                      |
|       + Giải hệ KKT: sum lambda_j grad(f_j) + sum mu_i grad(g_i) = 0   |
|         với điều kiện trực giao <lambda^k, w^k - f(x^k)> = 0            |
|       + Xác định hướng pháp tuyến lambda^k thuộc N_{Y^+}(w^k)           |
|       + Cắt đa diện: B^{k+1} = B^k giao {y | <lambda^k, y> >= <lambda^k, y^k>} |
|       + Cập nhật tập đỉnh V^{k+1}                                       |
|   - Tăng k = k + 1 -> Quay lại Bước 1                                   |
+-------------------------------------------------------------------------+

Quy trình nghiên cứu rigorous

Tính chặt chẽ của phương pháp thể hiện qua quy trình kiểm soát 4 bước nghiêm ngặt:

  1. Thiết lập bài toán quy hoạch phụ vô hướng $P^2(v^k)$: Thay vì giải bài toán đa mục tiêu phức tạp, tại mỗi bước lặp, thuật toán giải bài toán cực tiểu hóa hàm lồi suy rộng một mục tiêu: $$\min_{x \in X} \max_{j=1,\dots,p} \left{ \frac{f_j(x) - y^0_j}{v^k_j - y^0_j} \right}$$ Nhờ tính chất phân thức lồi/dương và tính đóng của phép lấy cực đại giữa các hàm giả lồi, bài toán con này được giải quyết hiệu quả bằng các thuật toán quy hoạch lồi tiêu chuẩn.
  2. Xác định hướng pháp tuyến qua hệ phương trình KKT: Giải tường minh hệ: $$\begin{cases} \sum_{j=1}^p \lambda_j \nabla f_j(x^k) + \sum_{i \in I(x^k)} \mu_i \nabla g_i(x^k) = 0 \ \sum_{j=1}^p \lambda_j (w^k_j - f_j(x^k)) = 0 \ \sum_{j=1}^p \lambda_j = 1, \quad \lambda_j \ge 0, \quad \mu_i \ge 0 \end{cases}$$
  3. Thuật toán Nhánh cận kết hợp Xấp xỉ ngoài giải bài toán (DP) và (QP):
    • Không gian ảnh hai chiều $\mathbb{R}^2$ được phân hoạch thành các đơn hình dạng nón $S(y^l, y^u)$.
    • Đánh giá cận trên và cận dưới thông qua việc tối ưu hàm đơn điệu $\phi(y)$ trên các đoạn thẳng biên xấp xỉ ngoài.
    • Chiến lược rẽ nhánh chia đôi (bisection) thích nghi dựa trên điểm chiếu hữu hiệu mới $y^{new}$, bảo đảm kích thước đơn hình co về 0 khi số bước lặp tăng.

Data và phân tích thử nghiệm

Các thuật toán được lập trình, kiểm thử và phân tích độ phức tạp tính toán thông qua hệ thống thực nghiệm số đa chiều:

  • Môi trường thực nghiệm: Ngôn ngữ lập trình tính toán khoa học chuyên dụng, tích hợp bộ giải quy hoạch phi tuyến để giải các bài toán con KKT và quy hoạch lồi.
  • Dữ liệu thử nghiệm: Bao gồm cả các bài toán mẫu kinh điển trong y văn (benchmark test problems) và các bài toán sinh ngẫu nhiên có kích thước biến lớn: số biến quyết định $n$ chạy từ $n = 10$ đến $n = 500$, số ràng buộc $m$ từ $10$ đến $100$, số mục tiêu $p \in {2, 3, 4, 5}$.
  • Chỉ số đánh giá: Thời gian tính toán CPU (giây), số bước lặp hội tụ $k$, số lượng bài toán quy hoạch lồi con cần giải, sai số xấp xỉ $\epsilon \in [10^{-3}, 10^{-6}]$.
  • Đối chuẩn so sánh (Benchmarking): So sánh trực tiếp với thuật toán xấp xỉ ngoài kinh điển của Benson (1998) [11], Ehrgott et al. (2011) [30], và phương pháp nhánh cận của Kuno (2005).

Phát hiện đột phá và implications

Những phát hiện then chốt

  1. Chứng minh toán học hoàn chỉnh về tính hội tụ của Thuật toán hướng pháp tuyến Solve(GMOP): Đây là đóng góp đột phá then chốt của Chương 2. Trong khi các nghiên cứu quốc tế tương đồng (như Ehrgott et al. 2011 [30], Heyde & Löhne 2008 [55]) để ngỏ chứng minh hội tụ cho lớp bài toán mở rộng, luận án đã thiết lập định lý khẳng định: Với sai số $\epsilon > 0$ cho trước, thuật toán Solve(GMOP) luôn dừng sau một số hữu hạn bước lặp, sinh ra tập nghiệm $\epsilon$-hữu hiệu yếu $X_{wE,\theta}$ chứa toàn bộ tập nghiệm hữu hiệu thực sự $X_{wE}$. Khi $\epsilon \to 0$, dãy đa diện ${B^k}$ hội tụ theo khoảng cách Hausdorff về tập $Y^0$.
  2. Khả năng giải phóng chiều không gian (Dimensionality Reduction Breakthrough): Thực nghiệm số chỉ ra rằng tốc độ hội tụ của thuật toán Solve(GMOP) phụ thuộc chủ yếu vào số lượng hàm mục tiêu $p$ chứ không bị suy thoái nghiêm trọng khi số biến $n$ tăng từ $10$ lên $500$. Số bước lặp trung bình chỉ tăng dưới 15% khi $n$ tăng gấp 50 lần, chứng minh ưu thế áp đảo của tiếp cận không gian ảnh so với các phương pháp trên không gian quyết định.
  3. Phá vỡ bế tắc của Bài toán quy hoạch tích lõm mở rộng (GIMP): Luận án chứng minh định lý biến đổi cấu trúc: Hàm trung bình nhân $\left(\prod_{i=1}^m f_i(x)\right)^{1/m}$ của các hàm lõm dương là một hàm lõm thực sự trên tập lồi $S$. Nhờ đó, bài toán GIMP phức tạp với $k$ hàm mục tiêu được chuyển đổi tương đương về bài toán cực đại một hàm đơn điệu tăng trên tập các điểm hữu hiệu trong không gian ảnh 2 chiều $\mathbb{R}^2$, giải quyết triệt để rào cản NP-khó trong trường hợp tổng quát.
  4. Hiệu năng vượt trội của lược đồ Nhánh cận - Xấp xỉ ngoài trong bài toán (DP) và (QP): Thuật toán giải bài toán tối ưu hàm tựa lõm và hàm đơn điệu tăng $\phi(f(x))$ trên tập nghiệm hữu hiệu của bài toán hai mục tiêu lồi cho thấy số phép lặp cắt giảm hơn 40% so với phương pháp nhánh cận truyền thống của Horst & Tuy (1996), nhờ tận dụng đường cong hữu hiệu đồng phôi với đoạn thẳng trong $\mathbb{R}^2$.
graph LR
    subgraph Theoretical_Findings["4 Phát hiện cốt lõi"]
        F1["Chứng minh hội tụ toàn cục Solve(GMOP)"]
        F2["Bất biến thứ nguyên: Hiệu năng độc lập với n lớn"]
        F3["Quy hoạch tích GIMP quy về R^2"]
        F4["Nhánh cận lai Xấp xỉ ngoài giảm 40% số bước lặp"]
    end
    
    subgraph Practical_Implications["Hệ quả & Ứng dụng thực tiễn"]
        I1["Thiết kế kỹ thuật VLSI & Viễn thông đa kênh"]
        I2["Tối ưu hóa danh mục đầu tư đa tiêu chí Markowitz mở rộng"]
        I3["Hệ thống hỗ trợ ra quyết định DSS thời gian thực"]
    end
    
    F1 & F2 --> I3
    F3 --> I1
    F4 --> I2

Implications đa chiều

  • Về mặt lý thuyết: Cung cấp cầu nối hoàn chỉnh giữa Giải tích lồi suy rộng và Lý thuyết tối ưu véc-tơ hiện đại, làm sáng tỏ cấu trúc tô-pô của biên hữu hiệu trên không gian ảnh.
  • Về mặt thuật toán: Đóng góp một gói thuật toán tối ưu toàn cục có độ tin cậy cao, có khả năng tích hợp trực tiếp vào các phần mềm tối ưu hóa thương mại và mã nguồn mở (như solver phi tuyến trong MATLAB, Python scipy.optimize, COIN-OR).
  • Về mặt ứng dụng kinh tế và kỹ thuật: Cho phép giải quyết các bài toán thiết kế hệ thống viễn thông (tối ưu đồng thời băng thông, độ trễ và năng lượng tiêu thụ), bài toán phân bổ nguồn lực chuỗi cung ứng, và bài toán tối ưu danh mục đầu tư tài chính với hàm lợi ích phi tuyến tính.

Limitations và Future Research

Nhằm duy trì tính khách quan khoa học, luận án đã thẳng thắn chỉ ra các giới hạn nội tại:

  1. Ràng buộc về tính lồi suy rộng của tập chấp nhận được: Thuật toán hiện tại yêu cầu tập chấp nhận được $X$ phải là tập lồi compact khác rỗng. Khi $X$ là tập rời rạc (tối ưu nguyên/hỗn hợp) hoặc tập phi liên thông, tính chất của siêu phẳng tựa nón pháp tuyến không còn được bảo toàn.
  2. Sự bùng nổ số đỉnh của đa diện khi số mục tiêu $p \ge 6$: Mặc dù không phụ thuộc vào $n$, nhưng khi số mục tiêu $p$ tăng cao (Many-Objective Optimization, $p \ge 6$), số lượng đỉnh của đa diện $B^k$ trong không gian $\mathbb{R}^p$ tăng theo cấp số nhân, dẫn đến chi phí tính toán quản lý tập đỉnh $V^k$ tăng đáng kể.
  3. Yêu cầu khả vi liên tục của các hàm thành phần: Việc xác định hướng pháp tuyến $\lambda^k$ thông qua hệ KKT đòi hỏi các hàm mục tiêu $f_j$ và hàm ràng buộc $g_i$ phải khả vi liên tục ($C^1$).

Chương trình nghiên cứu mở rộng trong tương lai:

  • Phát triển thuật toán xấp xỉ ngoài không gian ảnh cho bài toán tối ưu đa mục tiêu không khả vi (Nonsmooth Multiobjective Optimization) sử dụng dưới vi phân Clarke hoặc Mordukhovich.
  • Mở rộng lược đồ giải cho bài toán quy hoạch đa mục tiêu ngẫu nhiên (Stochastic Multiobjective Programming) và tối ưu bền vững (Robust Multiobjective Optimization) có tham số bất định.
  • Nghiên cứu kỹ thuật quản lý đỉnh đa diện nâng cao (Dual Benson Algorithm) để xử lý hiệu quả các bài toán có số mục tiêu lớn $p \in [6, 10]$.
  • Xây dựng toolbox chuyên dụng tích hợp trên nền tảng Python/C++ phục vụ cộng đồng nghiên cứu toàn cầu.

Tác động và ảnh hưởng

Kênh tác động Đối tượng thụ hưởng Cơ chế tác động & Chỉ số kỳ vọng
Hàn lâm & Học thuật Các nhóm nghiên cứu Tối ưu hóa, Giải tích phi tuyến Cung cấp tài liệu tham khảo nền tảng về tối ưu véc-tơ trên không gian ảnh; trích dẫn quốc tế vững chắc trên các tạp chí ISI Q1/Q2.
Kỹ thuật & Viễn thông Kỹ sư thiết kế chip VLSI, mạng 5G/6G Tối ưu hóa đa thông số mạng (công suất phát, băng thông, tỷ lệ lỗi bit) với độ phức tạp tính toán được kiểm soát chặt chẽ.
Tài chính & Kinh tế Quỹ đầu tư, Chuyên gia phân tích rủi ro Cung cấp công cụ giải bài toán tối ưu danh mục đa hàm mục tiêu phi lồi (lợi nhuận kỳ vọng, VaR, CVaR, chi phí giao dịch).
Quản trị công & Chính sách Cơ quan điều phối năng lượng, quy hoạch đô thị Hỗ trợ phân tích cân bằng Pareto giữa tăng trưởng kinh tế, phát thải carbon và chi phí xã hội.

Đối tượng hưởng lợi

  • Nghiên cứu sinh và Giảng viên Toán ứng dụng: Nắm bắt kỹ thuật chứng minh hội tụ chặt chẽ cho các thuật toán xấp xỉ ngoài, phương pháp xây dựng siêu phẳng cắt KKT và kỹ thuật phân tích trên không gian ảnh.
  • Chuyên gia Tối ưu hóa phần mềm (Software Engineers / Operations Researchers): Sử dụng khung thuật toán nhánh cận và xấp xỉ ngoài để cài đặt các module solver giải quyết bài toán quy hoạch tích và tối ưu hàm đa mục tiêu phức tạp.
  • Kỹ sư Hệ thống và Tự động hóa: Ứng dụng giải các bài toán điều khiển tối ưu đa tiêu chí thời gian thực nhờ tốc độ xử lý nhanh trên không gian ảnh $p \ll n$.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo và có chiều sâu nhất của luận án là gì?

Đóng góp độc đáo nhất là việc mở rộng thành công lý thuyết xấp xỉ ngoài trên không gian ảnh từ lớp hàm lồi thông thường (CMOP) sang lớp hàm giả lồi vô hướng (scalarly pseudoconvex), đi kèm chứng minh toán học hoàn chỉnh về tính hội tụ của dãy nghiệm xấp xỉ. Luận án đã giải quyết khoảng trống tồn tại nhiều năm trong các nghiên cứu của Ehrgott et al. (2011) và Heyde & Löhne (2008), thiết lập nền tảng lý luận vững chắc cho việc sử dụng hệ điều kiện tối ưu KKT để xác định hướng pháp tuyến của siêu phẳng tựa trên tập tương đương hữu hiệu $Y^+ = Y + \mathbb{R}^p_+$.

2. Sự đổi mới về mặt phương pháp luận so với các nghiên cứu quốc tế tiền nhiệm?

So với phương pháp nhánh cận trên không gian quyết định của Horst & Tuy (1996) hay phương pháp xấp xỉ ngoài cổ điển của Benson (1998), luận án đổi mới căn bản ở 3 điểm:

  • Chuyển toàn bộ phép phân hoạch và xây dựng mặt cắt sang không gian ảnh $\mathbb{R}^p$, giúp độ phức tạp của thuật toán không phụ thuộc trực tiếp vào số chiều biến quyết định $n$.
  • Sử dụng phép chiếu đơn tia từ điểm lý tưởng $y^0$ qua các đỉnh $v^k \in B^k \setminus Y^+$ để sinh trực tiếp điểm hữu hiệu yếu $w^k$, giải quyết bài toán chiếu chỉ qua một bài toán quy hoạch lồi vô hướng đơn biến.
  • Kết hợp linh hoạt lược đồ nhánh cận với xấp xỉ ngoài trong không gian 2 chiều $\mathbb{R}^2$ cho bài toán (DP) và (QP), giảm thiểu triệt để số lượng bài toán con cần duyệt.

3. Phát hiện thực nghiệm nào bất ngờ nhất từ quá trình tính toán số?

Phát hiện bất ngờ nhất là tính bất biến tương đối của thời gian tính toán khi số chiều biến quyết định $n$ tăng vọt từ $n = 10$ lên $n = 500$ trong bài toán Solve(GMOP). Trong khi các phương pháp trên không gian quyết định bị bùng nổ tổ hợp và mất khả năng hội tụ khi $n > 50$, thuật toán của luận án duy trì số bước lặp gần như hằng số (chỉ dao động từ 12 đến 28 bước lặp đối với bài toán 3 mục tiêu), minh chứng rõ nét cho nhận định lý thuyết rằng cấu trúc hình học của tập ảnh hữu hiệu $Y_E$ trong $\mathbb{R}^p$ đơn giản hơn rất nhiều so với tập nghiệm $X_E$ trong $\mathbb{R}^n$.

4. Luận án có cung cấp giao thức tái lập nghiên cứu (Replication Protocol) hoàn chỉnh không?

Hoàn toàn có. Luận án mô tả tường minh từng bước của tất cả các thuật toán (các bước khởi tạo $B^0$, cách giải bài toán phụ $P^2(v^k)$, hệ điều kiện KKT tìm $\lambda^k$, điều kiện dừng $|w^k - v^k| \le \epsilon$, và lược đồ phân hoạch đơn hình $S(y^l, y^u)$). Toàn bộ tham số thực nghiệm, ma trận ràng buộc, hàm mục tiêu thử nghiệm và bảng kết quả đo lường thời gian CPU, số bước lặp đều được lập bảng chi tiết (từ Bảng 2.1 đến Bảng 4.4), cho phép cộng đồng khoa học độc lập tái lập và kiểm chứng kết quả.

5. Tầm nhìn chương trình nghiên cứu 10 năm tiếp theo từ kết quả luận án?

Tầm nhìn 10 năm mở ra ba hướng phát triển chủ đạo:

  • Giai đoạn 1-3 năm: Mở rộng thuật toán cho bài toán tối ưu đa mục tiêu không trơn và tối ưu trên đa tạp Riemann.
  • Giai đoạn 3-6 năm: Phát triển các thuật toán song song hóa phân tán trên nền tảng GPU/TPU xử lý bài toán Many-Objective Optimization ($p \ge 10$) trong học sâu đa nhiệm (Multi-task Deep Learning).
  • Giai đoạn 6-10 năm: Ứng dụng toàn diện vào các hệ thống tự hành thông minh, tối ưu hóa lưới điện thông minh quốc gia và lập kế hoạch tài chính vĩ mô thích ứng với biến đổi khí hậu.

Kết luận

Luận án Tiến sĩ Toán học của NCS. Trần Ngọc Thăng đã đúc kết và đạt được các thành tựu khoa học xuất sắc sau:

  1. Xây dựng thành công thuật toán Solve(GMOP) giải bài toán quy hoạch đa mục tiêu lồi suy rộng trên không gian ảnh, thiết lập chứng minh toán học hoàn chỉnh về tính hội tụ toàn cục với sai số $\epsilon$-xấp xỉ.
  2. Thiết lập mô hình giải tường minh cho Bài toán quy hoạch tích lồi suy rộng (GMP) dựa trên mối quan hệ đối ngẫu hữu hiệu với bài toán GMOP.
  3. Đề xuất bước đột phá lý thuyết cho Bài toán quy hoạch tích lõm mở rộng (GIMP) thông qua phép biến đổi trung bình nhân, đưa bài toán NP-khó tổng quát về bài toán tối ưu đơn điệu trên không gian ảnh $\mathbb{R}^2$.
  4. Phát triển hai thuật toán nhánh cận kết hợp xấp xỉ ngoài hiệu năng cao giải bài toán tối ưu hàm tựa lõm và hàm đơn điệu tăng trên tập nghiệm Pareto của quy hoạch hai mục tiêu lồi (QP, DP).
  5. Thực hiện hệ thống tính toán số quy mô lớn, chứng minh tính vượt trội về tốc độ và tính ổn định của các thuật toán đề xuất so với các phương pháp quốc tế tiền nhiệm.
  6. Mở ra 3 nhánh nghiên cứu mới đầy tiềm năng: Tối ưu hóa đa mục tiêu không trơn trên không gian ảnh, tối ưu hóa véc-tơ quy mô siêu lớn trong trí tuệ nhân tạo, và tối ưu hóa hệ thống kỹ thuật - tài chính phức hợp.

Công trình là một đóng góp học thuật quan trọng của trường phái Tối ưu hóa Việt Nam, kế thừa và phát triển xuất sắc truyền thống nghiên cứu của Viện Toán ứng dụng và Tin học - Đại học Bách Khoa Hà Nội và Viện Toán học - Viện Hàn lâm Khoa học và Công nghệ Việt Nam.