Bối cảnh và vấn đề nghiên cứu
Bài toán tối ưu hóa hàm mục tiêu lồi giữ vai trò trung tâm trong toán ứng dụng với nhiều ứng dụng thực tiễn như tối ưu hóa danh mục đầu tư trong kinh tế và tài chính, xử lý tín hiệu và thông tin liên lạc, cũng như xác định kích thước thiết bị trong thiết kế điện tử. Đối với các bài toán có hàm mục tiêu khả vi liên tục, phương pháp gradient cổ điển là công cụ tiêu chuẩn và hiệu quả. Tuy nhiên, khi hàm mục tiêu không trơn (không khả vi), phương pháp gradient cổ điển không thể áp dụng trực tiếp. Để giải quyết lớp bài toán tối ưu lồi không trơn, N. Shor đã đề xuất thuật toán subgradient từ năm 1962, mở đầu cho hướng nghiên cứu mở rộng sang các bài toán quy mô lớn và không khả vi.
Khóa luận tốt nghiệp "Thuật toán subgradient và ứng dụng" của sinh viên Trần Hoàng Phi (ngành Toán ứng dụng, Khoa Toán - Tin học, Trường Đại học Sư phạm Thành phố Hồ Chí Minh, thực hiện dưới sự hướng dẫn của TS. Phạm Duy Khánh và ThS. Trần Bá Đạt, tháng 04/2023) tập trung nghiên cứu cơ sở giải tích và tính chất hội tụ của thuật toán subgradient, đồng thời hiện thực hóa thuật toán trên hai bài toán ứng dụng điển hình.
Mục tiêu và nhiệm vụ nghiên cứu của đề tài gồm 4 nhiệm vụ cụ thể:
- Hệ thống hóa các kiến thức giải tích lồi nền tảng phục vụ cho việc phân tích cực trị không trơn và lý thuyết tối ưu.
- Khảo sát và chứng minh chi tiết sự hội tụ của thuật toán subgradient trong trường hợp tổng quát và trường hợp bài toán có tập nghiệm bị chặn.
- Nghiên cứu cơ sở toán học và thiết lập công thức dưới vi phân cho hai bài toán ứng dụng: bài toán Lasso (Least Absolute Selection and Shrinkage Operator) và mô hình phân cụm lồi (Convex Clustering).
- Xây dựng các ví dụ số học, mô phỏng thuật toán trên ngôn ngữ lập trình Python và đánh giá kết quả tính toán trên dữ liệu thực nghiệm.
Đối tượng nghiên cứu của khóa luận là thuật toán subgradient, các điều kiện hội tụ và cấu trúc dưới vi phân của hàm mục tiêu lồi không trơn. Phạm vi nghiên cứu về mặt không gian lý thuyết là không gian Euclide hữu hạn chiều $\mathbb{R}^n$ và $\mathbb{R}^{d \times n}$. Phạm vi thực nghiệm tập trung vào bài toán tối ưu hàm lồi đa chiều giải tích và bài toán hồi quy tuyến tính dự đoán tỷ lệ mỡ cơ thể trên bộ dữ liệu thực tế.
Cơ sở lý thuyết và phương pháp
Khóa luận xây dựng trên khung lý thuyết giải tích lồi hiện đại và giải tích biến phân. Các khái niệm và mô hình toán học cốt lõi bao gồm:
- Hình học tập lồi và giải tích lồi: Hàm khoảng cách $d_\Omega(x) = \inf{|x - w| : w \in \Omega}$, phép chiếu Euclide $P_\Omega(x)$, nón lùi xa $\text{rec}(C)$, hàm lồi, hàm $\sigma$-lồi mạnh, tập mức $\text{Lev}(f, \alpha) = {x \in \mathbb{R}^n : f(x) \le \alpha}$ và đường mức $U(f, \alpha) = {x \in \mathbb{R}^n : f(x) = \alpha}$.
- Lý thuyết dưới vi phân: Khái niệm subgradient $v \in \partial f(\bar{x})$ thỏa mãn $\langle v, x - \bar{x} \rangle \le f(x) - f(\bar{x})$, dưới vi phân của hàm khả vi, quy tắc cộng và biến đổi affine của dưới vi phân, điều kiện tối ưu Fermat suy rộng $0 \in \partial f(\bar{x})$.
- Mô hình thuật toán subgradient: Sơ đồ lặp dạng $x^{k+1} = x^k - \alpha_k \frac{v^k}{|v^k|}$ (hoặc $x^{k+1} = x^k - \alpha_k v^k$) với dãy bước nhảy $\alpha_k > 0$ thỏa mãn điều kiện suy giảm $\lim_{k \to \infty} \alpha_k = 0$ và chuỗi phân kỳ $\sum_{k=1}^\infty \alpha_k = +\infty$.
Phương pháp nghiên cứu được tác giả sử dụng bao gồm:
- Phương pháp phân tích giải tích toán học: Sử dụng các bất đẳng thức giải tích, tiêu chuẩn Cauchy, định lý Weierstrass, định lý giá trị trung gian và các kỹ thuật đánh giá khoảng cách trong không gian Hilbert/Euclide để chứng minh sự hội tụ của dãy lặp và dãy hàm mục tiêu.
- Phương pháp mô phỏng số và thực nghiệm tính toán: Cài đặt thuật toán bằng ngôn ngữ Python, áp dụng các tiêu chuẩn dừng dựa trên chuẩn của subgradient ($|v^k| < 10^{-10}$) và độ biến thiên giá trị hàm mục tiêu ($|f(x^{k+1}) - f(x^k)| < 10^{-6}$).
- Nguồn dữ liệu: Dữ liệu giải tích tự tạo để minh họa tính chất nghiệm (không gian 2 chiều, 4 chiều) và bộ dữ liệu thực tế dự đoán tỷ lệ mỡ cơ thể (gồm 252 quan sát, 14 chỉ số đo lường nhân trắc học) được trích xuất từ thư viện dữ liệu LIBSVM của Chih-Jen Lin.
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 định nghĩa, bổ đề và định lý nền tảng của giải tích lồi:
- Hàm khoảng cách và phép chiếu Euclide: Chứng minh tính liên tục Lipschitz toàn cục với hệ số $L=1$ của hàm khoảng cách $d_\Omega(x)$. Nếu $\Omega$ là tập lồi đóng khác rỗng trong $\mathbb{R}^n$, hình chiếu Euclide $P_\Omega(x)$ tồn tại duy nhất và được đặc trưng bởi bất đẳng thức $\langle x - \bar{w}, w - \bar{w} \rangle \le 0, \forall w \in \Omega$. Thiết lập công thức tường minh tính khoảng cách và hình chiếu lên siêu phẳng $L = {x \in \mathbb{R}^n : \langle u, x \rangle = a}$.
- Nón lùi xa: Trình bày định nghĩa $\text{rec}(C) = {x \in \mathbb{R}^n : x + C \subseteq C}$ cho tập lồi $C$. Tác giả chứng minh định lý quan trọng: một tập lồi, đóng, khác rỗng $C \subset \mathbb{R}^n$ bị chặn khi và chỉ khi $\text{rec}(C) = {0}$.
- Hàm lồi và tính chất cực trị: Trình bày tính liên tục Lipschitz địa phương của hàm lồi, định nghĩa hàm $\sigma$-lồi mạnh, tính chất bảo toàn tính lồi qua phép tổ hợp tuyến tính và phép lấy giá trị lớn nhất. Xác lập điều kiện cần và đủ cho điểm cực tiểu toàn cục $0 \in \partial f(\bar{x})$, quy tắc tính dưới vi phân của tổng và ánh xạ hợp thành với phép biến đổi affine. Phân tích cấu trúc tập mức $\text{Lev}(f, \alpha)$, chứng minh tính compact của tập mức và đường mức khi tập nghiệm $\text{argmin}(f)$ khác rỗng và bị chặn.
Chương 2: Sự hội tụ của thuật toán subgradient
Chương này đi sâu vào phân tích toán học cơ chế hoạt động và tính chất hội tụ của thuật toán subgradient:
- Phân tích bước lặp không đơn điệu: Thông qua phản ví dụ hàm $f(x) = |x_1| + 2|x_2|$ trên $\mathbb{R}^2$, tác giả chỉ ra rằng việc di chuyển ngược hướng subgradient có thể làm giá trị hàm mục tiêu tăng lên tại một số bước lặp ($f(y') > f(y)$). Do đó, thuật toán subgradient không phải là phương pháp giảm đơn điệu.
- Hội tụ trong trường hợp tổng quát: Để theo dõi tiến trình tối ưu, tác giả đưa ra khái niệm dãy giá trị ghi (record values) $\phi_k = \min_{1 \le i \le k} f(x^i)$. Định lý 2.1 chứng minh rằng với điểm khởi tạo $x^1$ tùy ý và dãy bước nhảy thỏa mãn $\lim_{k\to\infty} \alpha_k = 0$, $\sum_{k=1}^\infty \alpha_k = +\infty$, dãy giá trị ghi luôn hội tụ về giá trị tối ưu: $\lim_{k\to\infty} \phi_k = \inf_{x\in\mathbb{R}^n} f(x)$.
- Hội tụ khi tập nghiệm bị chặn: Khi tập nghiệm $S = \text{argmin}(f)$ khác rỗng và bị chặn, Định lý 2.2 chứng minh kết quả hội tụ mạnh hơn: khoảng cách từ dãy lặp đến tập nghiệm tiến về 0 ($\lim_{k\to\infty} d_S(x^k) = 0$) và dãy giá trị hàm mục tiêu hội tụ về giá trị tối ưu ($\lim_{k\to\infty} f(x^k) = \min f(x)$). Định lý 2.3 và 2.4 mở rộng kết quả cho dạng bước cập nhật không chuẩn hóa $x^{k+1} = x^k - \alpha_k v^k$ với điều kiện dãy subgradient ${v^k}$ bị chặn.
+----------------------------------------------------------------------------------------------------+
| BẢNG TỔNG HỢP CÁC KẾT QUẢ HỘI TỤ |
+------------------------------+-------------------------------+-------------------------------------+
| Trường hợp khảo sát | Điều kiện giả thiết | Kết luận hội tụ |
+------------------------------+-------------------------------+-------------------------------------+
| Trường hợp tổng quát | alpha_k -> 0, tổng alpha_k = oo| lim phi_k = inf f(x) (dãy giá trị |
| | f lồi trên R^n | ghi hội tụ về giá trị tối ưu) |
+------------------------------+-------------------------------+-------------------------------------+
| Tập nghiệm S bị chặn | S khác rỗng, bị chặn; | lim d_S(x^k) = 0 và |
| (bước chuẩn hóa v^k/||v^k||) | alpha_k -> 0, tổng alpha_k = oo| lim f(x^k) = min f(x) |
+------------------------------+-------------------------------+-------------------------------------+
| Tập nghiệm S bị chặn | S khác rỗng, bị chặn; | lim d_S(x^k) = 0 và |
| (bước không chuẩn hóa) | {v^k} bị chặn; alpha_k -> 0 | lim f(x^k) = min f(x) |
+------------------------------+-------------------------------+-------------------------------------+
Chương 3: Ứng dụng của thuật toán subgradient
Chương 3 áp dụng lý thuyết đã xây dựng vào hai bài toán tối ưu cụ thể:
- Bài toán Lasso: Mô hình có dạng $\min_{x\in\mathbb{R}^n} \frac{1}{2}|Ax - b|^2 + \mu |x|_1$ ($\mu > 0$). Tác giả chứng minh tập nghiệm $S$ của bài toán Lasso luôn bị chặn với mọi ma trận $A \in \mathbb{R}^{m \times n}$ và vector $b \in \mathbb{R}^m$. Trong trường hợp 1 chiều, bài toán Lasso luôn có nghiệm duy nhất; trong không gian nhiều chiều ($n \ge 2$), bài toán có thể có vô số nghiệm không đếm được (được minh họa qua hàm 2 chiều cụ thể). Công thức dưới vi phân của hàm mục tiêu Lasso được xác định: $$\partial f(x) = {A^T(Ax - b)} + \mu \partial(|x|_1)$$ trong đó $(\partial |x|_1)_i = {\text{sign}(x_i)}$ nếu $x_i \ne 0$ và $[-1, 1]$ nếu $x_i = 0$.
- Mô hình phân cụm lồi: Bài toán phân cụm $n$ điểm dữ liệu $a^i \in \mathbb{R}^d$ được phát biểu dưới dạng tối ưu lồi: $$\min_{X \in \mathbb{R}^{d \times n}} \frac{1}{2} \sum_{i=1}^n |x^i - a^i|^2 + \gamma \sum_{i < j} |x^i - x^j|_p \quad (\gamma > 0, p \ge 1)$$ Tác giả chứng minh hàm mục tiêu của mô hình là hàm 1-lồi mạnh trên $\mathbb{R}^{d \times n}$, do đó bài toán luôn có nghiệm tối ưu duy nhất. Khóa luận thiết lập biểu thức giải tích của dưới vi phân cho cả hai trường hợp chuẩn $p=1$ và chuẩn $p=2$, kèm theo ma trận biến đổi đại số $(A^1 - A^2)$ trên các ví dụ cụ thể.
Chương 4: Thử nghiệm tính toán
Chương 4 trình bày kết quả thực nghiệm tính toán trên môi trường Python với dãy bước nhảy $\alpha_k = \frac{\alpha}{\sqrt{k}}$:
- Thử nghiệm bài toán Lasso 2 chiều: Giải bài toán $f(x_1, x_2) = (x_1 + x_2 - 1)^2 + |x_1| + |x_2|$ với $A = [\sqrt{2}, \sqrt{2}]$, $b = \sqrt{2}$, $\mu = 1$. Chọn điểm khởi tạo ngẫu nhiên $x^1 = (-0.44064899, \dots)$, tham số $\alpha = 0.5$. Thuật toán dừng sau 2.431 bước lặp do thỏa mãn điều kiện $|v^k| < 10^{-10}$, nghiệm tìm được là $x^* = (0.47935107, \dots)$ khớp với nghiệm giải tích chính xác.
- Thử nghiệm bài toán hồi quy Lasso trên dữ liệu thực tế: Áp dụng mô hình hồi quy tuyến tính dự đoán tỷ lệ mỡ cơ thể từ 14 thông số nhân trắc học trên bộ dữ liệu gồm 252 người. Dữ liệu được chia theo tỷ lệ 80% huấn luyện ($A_{\text{train}} \in \mathbb{R}^{201 \times 14}, y_{\text{train}} \in \mathbb{R}^{201}$) và 20% kiểm tra ($A_{\text{test}} \in \mathbb{R}^{51 \times 14}, y_{\text{test}} \in \mathbb{R}^{51}$). Bài toán được chuyển đổi về dạng Lasso với ma trận mở rộng $A = [A_{\text{train}} \mid \mathbf{1}] \in \mathbb{R}^{201 \times 15}$. Kết quả chạy thuật toán với $\mu = 0.1, \alpha = 0.7$ cho thấy thuật toán hội tụ nhanh chóng, nghiệm thu được dùng để tính $y_{\text{pred}} = [A_{\text{test}} \mid \mathbf{1}]x^*$ cho độ khớp cao khi so sánh trực quan giữa giá trị thực tế và giá trị dự báo.
+----------------------------------------------------------------------------------------------------+
| BẢNG THÔNG SỐ THỬ NGHIỆM BÀI TOÁN LASSO |
+-------------------+----------------+-----------+---------------+------------+----------------------+
| Bài toán | Kích thước | Tham số mu| Tham số alpha | Số bước lặp| Điều kiện dừng |
+-------------------+----------------+-----------+---------------+------------+----------------------+
| Lasso giải tích | 2 chiều (R^2) | 1.0 | 0.5 | 2.431 | ||v^k|| < 10^(-10) |
+-------------------+----------------+-----------+---------------+------------+----------------------+
| Dự đoán tỷ lệ mỡ | 15 chiều (R^15)| 0.1 | 0.7 | Hội tụ | |f(x^(k+1))-f(x^k)| |
| (Bodyfat dataset) | (201 mẫu train)| | | ngắn | < 10^(-6) |
+-------------------+----------------+-----------+---------------+------------+----------------------+
Chương 5: Lập trình Python
Chương 5 cung cấp toàn bộ mã nguồn lập trình chi tiết thực hiện trên Python:
- Cài đặt hàm tính giá trị mục tiêu và hàm xác định dưới vi phân cho bài toán Lasso.
- Cài đặt cấu trúc lặp subgradient tổng quát với các tham số điều khiển bước nhảy và kiểm tra điều kiện hội tụ.
- Cài đặt mã nguồn giải bài toán phân cụm lồi và xử lý ma trận dữ liệu.
Kết quả và đóng góp
Khóa luận đã đạt được các kết quả cụ thể sau:
- Về mặt lý thuyết: Hệ thống hóa đầy đủ và chặt chẽ các chứng minh toán học về sự hội tụ của thuật toán subgradient. Làm rõ sự khác biệt giữa hai trường hợp: trường hợp tổng quát (hội tụ thông qua dãy giá trị ghi $\lim \phi_k = \inf f(x)$) và trường hợp tập nghiệm bị chặn (khoảng cách dãy lặp tiến về tập nghiệm $\lim d_S(x^k) = 0$).
- Về mặt ứng dụng và tính toán: Chứng minh được tính bị chặn nghiệm của bài toán Lasso và tính lồi mạnh (nghiệm duy nhất) của mô hình phân cụm lồi. Thiết lập công thức dưới vi phân tường minh cho cả hai mô hình và lập trình thực thi thành công trên Python.
- Đóng góp so với nghiên cứu trước: Khóa luận kết nối mạch lạc giữa lý thuyết giải tích lồi trừu tượng với việc giải quyết các bài toán tối ưu thực tế trong học máy và xử lý dữ liệu (Lasso và Convex Clustering), cung cấp quy trình hoàn chỉnh từ mô hình hóa, thiết lập giải tích đến cài đặt thuật toán số.
Hạn chế và hướng nghiên cứu tiếp
Dựa trên phạm vi và các nhận định được trình bày trong văn bản:
- Hạn chế: Tốc độ hội tụ của thuật toán subgradient tương đối chậm so với các phương pháp bậc hai (như phương pháp Newton) hoặc phương pháp điểm trong (interior point methods), xuất phát từ bản chất của dãy bước nhảy suy giảm tiến về 0. Khóa luận chủ yếu khảo sát dạng bước nhảy $\alpha_k = \frac{\alpha}{\sqrt{k}}$ trên quy mô dữ liệu thử nghiệm vừa phải.
- Hướng nghiên cứu tiếp: Nghiên cứu và thử nghiệm các quy tắc chọn bước nhảy cải tiến (như bước nhảy Polyak khi biết trước giá trị tối ưu, hoặc bước nhảy chiếu subgradient của Ruszczyński); mở rộng áp dụng thuật toán subgradient cho các bài toán tối ưu lồi quy mô lớn hơn hoặc các bài toán đối ngẫu phức tạp trong học máy.
Giá trị tham khảo
Khóa luận là tài liệu tham khảo hữu ích cho:
- Sinh viên và học viên ngành Toán học, Toán ứng dụng, Khoa học dữ liệu và Trí tuệ nhân tạo: Cung cấp tài liệu học tập toàn diện về giải tích lồi không trơn và phương pháp tối ưu hóa hiện đại.
- Người nghiên cứu thuật toán tối ưu: Có thể tham khảo trực tiếp các chứng minh giải tích chi tiết ở Chương 2, công thức thiết lập dưới vi phân ở Chương 3 và cấu trúc chương trình mẫu viết bằng Python ở Chương 5 để áp dụng cho các bài toán tối ưu lồi không khả vi khác.
Câu hỏi thường gặp
1. Tại sao không thể sử dụng phương pháp gradient cổ điển cho bài toán Lasso và bài toán phân cụm lồi?
Hàm mục tiêu của bài toán Lasso chứa số hạng chuẩn $|x|_1$ và mô hình phân cụm lồi chứa số hạng $|x^i - x^j|_p$. Các hàm chuẩn này không khả vi tại các điểm bằng 0 (hoặc khi $x^i = x^j$), dẫn đến hàm mục tiêu không trơn trên toàn miền xác định. Do đó, gradient cổ điển không tồn tại tại các điểm này và phải thay thế bằng khái niệm dưới vi phân (subdifferential).
2. Dãy giá trị ghi $\phi_k$ là gì và tại sao cần sử dụng trong chứng minh hội tụ trường hợp tổng quát?
Dãy giá trị ghi được định nghĩa bởi $\phi_k = \min_{1 \le i \le k} f(x^i)$, lưu lại giá trị nhỏ nhất của hàm mục tiêu đạt được sau $k$ bước lặp đầu tiên. Khái niệm này bắt buộc phải sử dụng vì thuật toán subgradient không phải là thuật toán giảm đơn điệu (giá trị hàm mục tiêu $f(x^k)$ có thể tăng ở một số bước lặp). Sử dụng $\phi_k$ tạo ra một dãy giảm đơn điệu để thiết lập kết quả hội tụ $\lim_{k\to\infty} \phi_k = \inf_{x\in\mathbb{R}^n} f(x)$.
3. Điều kiện cần thiết đối với dãy bước nhảy $\alpha_k$ trong thuật toán subgradient là gì?
Dãy bước nhảy ${\alpha_k}$ phải là dãy số thực dương thỏa mãn đồng thời hai điều kiện: $\lim_{k \to \infty} \alpha_k = 0$ (bước nhảy triệt tiêu dần để đảm bảo độ chính xác quanh điểm tối ưu) và $\sum_{k=1}^\infty \alpha_k = +\infty$ (chuỗi bước nhảy phân kỳ để đảm bảo thuật toán không bị dừng sớm trước khi tiếp cận điểm tối ưu từ một điểm khởi tạo tùy ý).
4. Mô hình phân cụm lồi có bao nhiêu nghiệm tối ưu và căn cứ vào đâu để khẳng định?
Mô hình phân cụm lồi luôn có duy nhất một nghiệm tối ưu. Khóa luận đã chứng minh hàm mục tiêu của mô hình phân cụm lồi là hàm 1-lồi mạnh trên không gian $\mathbb{R}^{d \times n}$ (do được phân tích thành tổng của hàm toàn phương 1-lồi mạnh và các hàm lồi dạng chuẩn). Theo tính chất giải tích lồi, hàm lồi mạnh trên toàn không gian luôn đạt cực tiểu toàn cục tại một điểm duy nhất.
Kết luận
Khóa luận tốt nghiệp "Thuật toán subgradient và ứng dụng" của tác giả Trần Hoàng Phi là một công trình nghiên cứu hoàn chỉnh, chặt chẽ trong chuyên ngành Toán ứng dụng. Tác giả đã hệ thống hóa tường minh nền tảng giải tích lồi, chứng minh chi tiết các định lý hội tụ cốt lõi của thuật toán subgradient và giải quyết thành công bài toán Lasso cùng mô hình phân cụm lồi. Kết quả thử nghiệm trên ngôn ngữ Python đã kiểm chứng tính chính xác của lý thuyết giải tích và khẳng định khả năng ứng dụng thực tiễn của phương pháp subgradient trong xử lý dữ liệu và học máy.