Luận án Tiến sĩ Toán học: Một số lớp bài toán tối ưu không lồi - Thuật toán và ứng dụng

Chia sẻ: Sơ Dương | Ngày: | Loại File: PDF | Số trang:110

Thêm vào BST

Báo xấu

31
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề 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" nghiên cứu 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 một bài toán tối ưu rời rạc và đưa bài toán này về một bài toán tối ưu DC, đề xuất thuật toán toàn cục (nhánh cận kết hợp DCA) để giải.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Toán học: Một số lớp bài toán tối ưu không lồi - Thuật toán và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHẠM THỊ HOÀ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 LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2020
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI PHẠM THỊ HOÀ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 Ngành: Toán học Mã số: 9460101 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC 1. TS. NGUYỄN CẢNH NAM 2. GS. TSKH. LÊ THỊ HOÀI AN Hà Nội - 2020
LỜI CAM ĐOAN Bản luận án này được hoàn thành tại Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội, dưới sự hướng dẫn khoa học của TS. Nguyễn Cảnh Nam và GS. TSKH. Lê Thị Hoài An. Tôi xin cam đoan các kết quả được trình bày trong luận án là trung thực và chưa từng được tác giả khác công bố. Các đồng tác giả đã đồng ý với việc đưa các kết quả công bố chung vào luận án. Hà Nội, ngày tháng năm 2020 Thay mặt tập thể hướng dẫn Nghiên cứu sinh TS. Nguyễn Cảnh Nam Phạm Thị Hoài i
LỜI CẢM ƠN Luận án được hoàn thành dưới sự hướng dẫn tận tình và nghiêm khắc của TS. Nguyễn Cảnh Nam và GS. TSKH. Lê Thị Hoài An. Tác giả xin được bày tỏ lòng kính trọng và biết ơn sâu sắc tới Thầy, Cô. Thầy Cô đã luôn ân cần hướng dẫn, chỉ bảo cho tác giả kiến thức về chuyên môn, từng bước định hướng nghiên cứu và truyền cho tác giả niềm đam mê nghiên cứu khoa học, ý thức tự học, tự tìm tòi bằng tấm gương của mình trong công việc cũng như trong cuộc sống. Những lời động viên, khích lệ của Thầy Cô là nguồn động lực to lớn để tác giả có thể vượt qua những khó khăn và trở ngại trên con đường học tập và nghiên cứu, tự tin bước tiếp trên con đường mình đã chọn. Trong quá trình học tập nói chung và thực hiện luận án này nói riêng, tác giả cũng nhận được sự quan tâm, giúp đỡ, chỉ dẫn tận tình cùng những lời khuyên quý báu của GS. Hoàng Tụy, GS. TSKH. Lê Dũng Mưu, PGS. TS. Nguyễn Thị Bạch Kim, GS. TSKH. Nguyễn Đông Yên, TS. Tạ Anh Sơn, TS. Trần Ngọc Thăng, TS. Trần Đức Quỳnh, TS. Lê Quang Thủy, TS. Nguyễn Thị Bích Thủy, TS. Nguyễn Quang Thuận. Tác giả xin được bày tỏ lòng biết ơn sâu sắc tới các Thầy Cô. Tác giả xin trân trọng cảm ơn Ban Giám hiệu, Phòng Tổ chức Cán bộ, Phòng Đào tạo - Trường Đại học Bách khoa Hà Nội, đã tạo điều kiện thuận lợi cho tác giả trong suốt quá trình làm việc, học tập, nghiên cứu và hoàn thành luận án. Tác giả xin được gửi lời cảm ơn chân thành tới Ban lãnh đạo cùng toàn thể cán bộ Viện Toán ứng dụng và Tin học, Trường Đại học Bách khoa Hà Nội, đã giúp đỡ, tạo điều kiện để tác giả vừa có thể hoàn thành công tác và vừa có thời gian học tập, hoàn thành chương trình nghiên cứu sinh. Trong quá trình thực hiện luận án tác giả cũng nhận được sự hỗ trợ của Quỹ Phát triển Khoa học và Công nghệ Quốc gia (NAFOSTED) về kinh phí tham gia báo cáo tại hội thảo khoa học quốc tế và sự giúp đỡ tài trợ từ dự án của GS. TSKH. Lê Thị Hoài An trong thời gian học tập tại phòng nghiên cứu về khoa học máy tính và ứng dụng, Đại học Lorraine, Cộng Hòa Pháp. Ngoài ra tác giả cũng nhận được kinh phí tài trợ mua vật tư, dụng cụ, tài liệu từ chương trình học bổng 911 trong nước. Tác giả trân trọng cảm ơn. Tác giả xin chân thành cảm ơn PGS. TS. Đỗ Đức Thuận, TS. Nguyễn Phương Thùy, TS. Nguyễn Hải Sơn, TS. Trịnh Ngọc Hải cùng các Thầy Cô và anh chị em đồng nghiệp trong Xêmina Lý thuyết tối ưu và ứng dụng và Xêmina Bài toán cân bằng, bài toán điểm bất động và các vấn đề liên quan, Viện Toán ứng dụng và Tin học - Đại học Bách khoa Hà Nội, đã dành cho tác giả những cơ hội học tập trao đổi chuyên môn cùng những ý kiến đóng góp quý báu giúp cho tác giả hiểu sâu sắc hơn ii
vấn đề nghiên cứu của mình. Cuối cùng tác giả xin dành lời cảm ơn đặc biệt gửi tới những người thân yêu trong gia đình cùng bạn bè của tác giả - những người đã, đang và sẽ là hậu phương vững chắc, cho tác giả nguồn cổ vũ và động viên tinh thần lớn lao để tác giả có thể hoàn thành công việc, học tập, nghiên cứu nói chung và việc viết luận án này nói riêng. iii
MỤC LỤC LỜI CAM ĐOAN i LỜI CẢM ƠN ii DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT vi DANH MỤC BẢNG vi DANH MỤC HÌNH VẼ viii MỞ ĐẦU 1 Chương 1. KIẾN THỨC CHUẨN BỊ 6 1.1 Tối ưu DC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . 6 1.1.2 Thuật toán DCA . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Tối ưu đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.2.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . 13 1.2.2 Thuật toán giải bài toán tối ưu đơn điệu . . . . . . . . . . . . 18 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 25 2.1 Thuật toán giải bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.2 Bài toán tối ưu DC đa diện tương đương với bài toán (RAP) . 29 2.1.3 Thuật toán toàn cục giải bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD (RAP) . . . . . . . . . . . . 32 2.1.4 Kết quả tính toán thử nghiệm . . . . . . . . . . . . . . . . . . 35 2.2 Thuật toán giải bài toán năng lượng phủ cảm biến cho mạng cảm biến vô tuyến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.2.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2.2 Bài toán tối ưu đơn điệu rời rạc tương đương với bài toán (SCEP) 38 2.2.3 Thuật toán toàn cục nhánh-giảm-cận (BRB) giải bài toán (SCEP) 42 2.2.4 Kết quả tính toán thử nghiệm . . . . . . . . . . . . . . . . . . 49 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 57 3.1 Bài toán tối ưu đa mục tiêu rời rạc . . . . . . . . . . . . . . . . . . . 58 iv
3.2 Thuật toán tìm 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.1 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 (MODO) . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.2.2 Thuật toán tìm 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 (MODO) . . . . . . . . . . . . . . . . . . 68 3.2.3 Kết quả tính toán thử nghiệm . . . . . . . . . . . . . . . . . 69 3.3 Thuật toán giải 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.3.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.3.2 Thuật toán toàn cục giải bài toán (P ) . . . . . . . . . . . . . 79 3.3.3 Kết quả tính toán thử nghiệm . . . . . . . . . . . . . . . . . 85 KẾT LUẬN CHUNG 89 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN 91 TÀI LIỆU THAM KHẢO 92 v
DANH MỤC CÁC KÍ HIỆU VÀ CHỮ VIẾT TẮT 0 véc-tơ không với số chiều phù hợp x ∈ Rn x = (x 1 , . . . , x n ) T , x i ∈ R, i = 1, . . . , n x, y ∈ R n , x ≤ y x i ≤ y i , i = 1, . . . , n x, y ∈ R n , x 6≤ y ∃i ∈ {1, . . . , n} : x i > y i , x, y ∈ R n , x < y x i < y i , i = 1, . . . , n R n+ {x ∈ R n | x ≥ 0} n u = x ∨ y, x, y ∈ R u i = max{x i , yi }, i = 1, . . . , n v = x ∧ y, x, y ∈ R n vi = min{x i, y i }, i = 1, . . . , n ei véc-tơ đơn vị thứ i trong R n , tức là, eii = 1, e ij = 0, ∀j 6= i [a, b], a, b ∈ Rn {x ∈ R n | a ≤ x ≤ b} (a, b], a, b ∈ R n {x ∈ R n | a < x ≤ b} [a, b), a, b ∈ R n {x ∈ R n | a ≤ x < b} #S số phần tử của tập S clG bao đóng của tập G V (P ) tập đỉnh của tập P vi
BB Branch and Bound Thuật toán nhánh cận BRB Branch-Reduce-Bound Thuật toán nhánh-giảm-cận DC Difference of two Convex functions Hiệu hai hàm lồi DCA DC Algorithm Thuật toán hiệu hai hàm lồi DMO Discrete Monotonic Optimization Tối ưu đơn điệu rời rạc FDMA Frequency Division Multiple Access Đa truy nhập phân chia theo tần số MO Monotonic Optimization Tối ưu đơn điệu OFDMA Orthogonal Frequency Division Multiple Access Đa truy nhập phân chia theo tần số trực giao SCEP Sensor Cover Energy Problem Bài toán năng lượng phủ cảm biến TDD Time Division Duplexing Song công phân chia theo thời gian TDMA Time Division Multiple Access Đa truy nhập phân chia theo thời gian t.ư. tương ứng v.đ.k. với điều kiện vii
DANH MỤC BẢNG 2.1 Kết quả giải bài toán (RAP) bằng Thuật toán 2.2 và Thuật toán 2.3 . . 36 2.2 Kết quả áp dụng các Thuật toán 2.4, 2.5, 2.6 cho bài toán (SCEP) . . . 50 2.3 Kết quả áp dụng Thuật toán 2.5 cho bài toán (SCEP) . . . . . . . . . 51 3.1 Dữ liệu của Ví dụ 3.1 [69] . . . . . . . . . . . . . . . . . . . . . . . 59 3.2 Kết quả tính toán theo Thuật toán 3.1- RA . . . . . . . . . . . . . . . 73 3.3 Kết quả tính toán theo Thuật toán 3.1- RE . . . . . . . . . . . . . . . 74 3.4 Kết quả tính toán theo Thuật toán 3.1- NEWVERTEX . . . . . . . . . 75 3.5 Kết quả tính toán theo Thuật toán 3.1 với các thủ tục cập nhật miền tìm kiếm và các cách quản lí khác nhau . . . . . . . . . . . . . . . . 76 3.6 Kết quả tính toán thử nghiệm Thuật toán 3.2 . . . . . . . . . . . . . . 86 3.7 Kết quả so sánh Thuật toán 3.3 và Thuật toán 3.4 . . . . . . . . . . . 87 viii
DANH MỤC HÌNH VẼ 1.1 Minh họa trên đồ thị của hàm lồi y = f (x) . . . . . . . . . . . . . . . 7 1.2 Minh họa tập chuẩn, đối chuẩn và biên trên, biên dưới tương ứng của chúng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3 Đa khối với tập đỉnh {u 1 , u 2 , u 3, u 4 }, trong đó {u 1 , u 2 , u 4 } là tập đỉnh chính, u 3 là đỉnh không chính . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Đối đa khối với tập đỉnh chính {z 1 , z 2 , z 3 } . . . . . . . . . . . . . . . 16 1.5 Minh họa Mệnh đề 1.9 . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1 Khung OFDMA/TDD mô tả xung đột giữa hai người dùng . . . . . . 27 2.2 Tài nguyên cấp phát cho một người dùng là khung hình chữ nhật nhận (i 1 , j 1 ) và (i 2 , j 2 ) là đỉnh nếu anh ta được cấp hai nút này . . . . . . . 28 2.3 n=25, m=5, Bộ dữ liệu 1 . . . . . . . . . . . . . . . . . . . . . . . . 52 2.4 n=25, m=5, Bộ dữ liệu 2 . . . . . . . . . . . . . . . . . . . . . . . . 52 2.5 n=25, m=5, Bộ dữ liệu 3 . . . . . . . . . . . . . . . . . . . . . . . . 52 2.6 n=25, m=5, Bộ dữ liệu 4 . . . . . . . . . . . . . . . . . . . . . . . . 52 2.7 n=25, m=5, Bộ dữ liệu 5 . . . . . . . . . . . . . . . . . . . . . . . . 52 2.8 n=25, m=50, Bộ dữ liệu 1 . . . . . . . . . . . . . . . . . . . . . . . . 52 2.9 n=25, m=50, Bộ dữ liệu 3 . . . . . . . . . . . . . . . . . . . . . . . . 53 2.10 n=25, m=50, Bộ dữ liệu 4 . . . . . . . . . . . . . . . . . . . . . . . . 53 2.11 n=25, m=50, Bộ dữ liệu 5 . . . . . . . . . . . . . . . . . . . . . . . . 53 2.12 n=75, m=15, Bộ dữ liệu 1 . . . . . . . . . . . . . . . . . . . . . . . . 53 2.13 n=75, m=15, Bộ dữ liệu 2 . . . . . . . . . . . . . . . . . . . . . . . . 53 2.14 n=75, m=15, Bộ dữ liệu 3 . . . . . . . . . . . . . . . . . . . . . . . . 53 2.15 n=75, m=15, Bộ dữ liệu 4 . . . . . . . . . . . . . . . . . . . . . . . . 54 2.16 n=75, m=15, Bộ dữ liệu 5 . . . . . . . . . . . . . . . . . . . . . . . . 54 2.17 n=75, m=150 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.18 n=125, m=25 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.19 n=125, m=250 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.20 n=175, m=35 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.21 n=175, m=350 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.22 n=225, m=45 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.23 n=225, m=450 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 ix
2.24 n=500, m=100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.25 n=500, m=1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.26 n=750, m=150 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.27 n=750, m=1000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.28 n=1000, m=500 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.1 Minh họa Ví dụ 3.1 [69] . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2 Khởi tạo, N = ∅ và S (N ) = [y I , b) . . . . . . . . . . . . . . 61 3.3 Bước 1, N = {y 1 } và S (N ) = [y I , u 1 ) ∪ [yI , u 2 ) . . . . . . . 61 3.4 Bước 2, N = {y 1 , y 2 } và S (N ) = [y I , u 2 ) ∪ [yI , u 12 ) . . . . 62 3.5 Bước 3, N = {y 1 , y 2 , y 3 } và S (N ) = [y I , u 12 ) ∪ [yI , u 21 ) . . . . . . 62 3.6 Bước 4, N = {y 1 , y 2 , y 3 } và S (N ) = [y I , u 21 ) . . . . . . . . . . . . 62 3.7 Minh họa Ví dụ 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.8 Minh họa Ví dụ 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.9 Số phần tử của tập V (Y) nhỏ hơn rất nhiều so với số phần tử của tập Y, YN hay V (convY ) . . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.10 Minh họa Ví dụ 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 x
MỞ ĐẦU 1. Lý do chọn đề tài Tối ưu không lồi và tối ưu toàn cục là những vấn đề quan trọng của lí thuyết tối ưu với rất nhiều ứng dụng trong thực tế. Công trình của GS. Hoàng Tụy năm 1964 [1] về việc tìm nghiệm tối ưu toàn cục của bài toán cực tiểu một hàm lõm với ràng buộc tuyến tính là xuất phát điểm cho hàng loạt những nghiên cứu về tối ưu không lồi và tối ưu toàn cục của rất nhiều nhà toán học trong và ngoài nước sau này. Trải qua hơn nửa thế kỷ, những công trình nghiên cứu về vấn đề này vô cùng đa dạng, phong phú cả về lí thuyết, phương pháp, thuật toán và ứng dụng. Tuy nhiên, do nhu cầu ứng dụng, sự hấp dẫn về mặt toán học cũng như tính phức tạp của bài toán tối ưu không lồi nên cho đến nay, việc nghiên cứu giải quyết hiệu quả các bài toán này vẫn mang tính thời sự và thu hút được sự quan tâm của nhiều nhà khoa học trong và ngoài nước (xem Tụy [2] và danh mục các tài liệu tham khảo kèm theo). Khó khăn lớn nhất của bài toán tối ưu không lồi tổng quát chính là sự có mặt của tính không lồi. Điểm khác biệt cơ bản so với bài toán tối ưu lồi là không có một đặc trưng cụ thể nào cho nghiệm tối ưu toàn cục của bài toán tối ưu không lồi. Đối với bài toán tối ưu không lồi liên tục thì nghiệm tối ưu địa phương chưa chắc đã là nghiệm tối ưu toàn cục của bài toán. Do đó việc tìm nghiệm tối ưu toàn cục cho một bài toán tối ưu không lồi, đặc biệt trong trường hợp số chiều lớn là vô cùng khó khăn. Một số phương pháp chung nổi tiếng giải toàn cục bài toán tối ưu không lồi phải kể đến là: phương pháp nhánh cận, phương pháp nhánh cắt, phương pháp siêu phẳng cắt. Theo một tiếp cận khác, ta có thể giải bài toán tối ưu không lồi bằng cách sử dụng những phương pháp tìm nghiệm tối ưu địa phương. Một trong những thuật toán địa phương hiệu quả được áp dụng cho rất nhiều lớp bài toán tối ưu không lồi, kể cả những bài toán cỡ lớn, là thuật toán DCA (Difference of two Convex functions Algorithm) (xem An và Tảo [3] và danh mục các tài liệu tham khảo kèm theo). Theo GS. Hoàng Tụy [2], nhiều bài toán tối ưu không lồi có thể được xem xét dưới hai cấu trúc: cấu trúc DC (difference of two convex functions) hoặc cấu trúc DM (difference of two monotonic functions). Tùy vào đặc điểm của từng bài toán mà ta chọn cách nhìn nhận phù hợp để có được lời giải hiệu quả. Đặc biệt đối với những mô hình bài toán cụ thể trong thực tế, việc vận dụng và kết hợp các phương pháp và thuật toán một cách linh hoạt rất quan trọng vì nó sẽ giúp việc giải quyết vấn đề trở nên dễ dàng hơn. Chẳng hạn, thông thường, việc giải toàn cục các bài toán tối ưu rời rạc 1
(thuộc lớp bài toán tối ưu không lồi) gặp khó khăn khi sử dụng các thuật toán truyền thống như: nhánh cận, nhánh cắt, siêu phẳng cắt. . . nhưng sau khi chuyển về một bài toán tối ưu liên tục, kết hợp với một số kĩ thuật trong tối ưu thì việc giải quyết trở nên dễ dàng hơn (xem [3, 4]...). Vậy, ngược lại, liệu có thể đưa một bài toán tối ưu không lồi liên tục về một bài toán tối ưu rời rạc với một lời giải dễ dàng và hiệu quả hơn không? Trong luận án này, chúng tôi sẽ nghiên cứu thuật toán giải hai bài toán tối ưu không lồi trong viễn thông, trong đó có vận dụng cả hai cách tiếp cận này. Như đã biết, các phương pháp giải bài toán tối ưu không lồi được ứng dụng rộng rãi để giải quyết rất nhiều bài toán tối ưu một hàm mục tiêu duy nhất theo những điều kiện nhất định. Với những bài toán cần tối ưu đồng thời nhiều mục tiêu khác nhau thì ta cần các công cụ của Quy hoạch đa mục tiêu (hay Tối ưu đa mục tiêu hoặc Tối ưu véc tơ). Mục đích của bài toán tối ưu đa mục tiêu là tìm cực đại hoặc cực tiểu của đồng thời m ≥ 2 hàm mục tiêu f 1 , . . . , f m trên một tập khác rỗng X ⊂ R n . Do không gian giá trị R m không có thứ tự đầy đủ nên trong tối ưu đa mục tiêu, khái niệm nghiệm hữu hiệu (hay nghiệm Pareto) được sử dụng thay cho khái niệm nghiệm tối ưu thông thường. Việc xác định một phần hoặc toàn bộ tập nghiệm hữu hiệu X E của bài toán tối ưu đa mục tiêu là một nhiệm vụ khó khăn, đòi hỏi thời gian và khối lượng tính toán rất lớn vì ngay trong trường hợp bài toán quy hoạch đa mục tiêu tuyến tính, tức bài toán tối ưu đồng thời m hàm mục tiêu tuyến tính trên một tập lồi đa diện khác rỗng thì tập nghiệm hữu hiệu X E , nói chung, đã là tập không lồi với cấu trúc rất phức tạp. Do đó, khối lượng tính toán để xác định toàn bộ X E tăng rất nhanh khi số chiều của không gian quyết định R n , số hàm mục tiêu m và số ràng buộc biểu diễn tập X tăng (xem Benson [5]). Tuy nhiên, thông thường, rất nhiều bài toán tối ưu đa mục tiêu nảy sinh trong thực tế thường có số hàm mục tiêu m nhỏ hơn rất nhiều thứ nguyên n của không gian quyết định R n nên đã có khá nhiều thuật toán được đề xuất để giải bài toán tối ưu đa mục tiêu theo hướng tiếp cận trên không gian ảnh. Cụ thể, thay vì xác định một phần hoặc toàn bộ tập nghiệm hữu hiệu XE , các thuật toán này sẽ cho phép xác định một phần hoặc toàn bộ tập giá trị hữu hiệu YN = f (X E ), trong đó f (x) = (f 1 (x), . . . , f m (x)) T . Vì m  n nên cấu trúc của Y N đơn giản hơn nhiều so với cấu trúc của X E và tiếp cận trên không gian ảnh, cho phép giảm đáng kể thời gian tính toán. Bài toán tối ưu đa mục tiêu liên tục đã được nghiên cứu từ lâu theo cách tiếp cận trên không gian quyết định cũng như không gian ảnh với rất nhiều thuật toán được đề xuất (xem [6, 7, 8, 9, 10] và danh mục tham khảo kèm theo). Tuy nhiên, trong khoảng hơn một thập kỉ trở lại đây, bài toán tối ưu đa mục tiêu rời rạc được nghiên cứu bằng nhiều phương pháp khác nhau như: ε-ràng buộc, vô hướng hóa Tchebycheff, vô hướng hóa tổng có trọng và các phương pháp biến thể khác (xem [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]). Trong đó, đáng chú ý phải kể đến một số công trình như: Przybylski [25], Klamroth và cộng sự [24], D ¨achert và Klamroth [13], 2
D¨achert và cộng sự [23] với các thuật toán hiệu quả được đề xuất. Những công trình này ([13, 23, 24, 25]) sử dụng lược đồ chung (generic method, viết tắt là GM) để tìm toàn bộ tập điểm giá trị hữu hiệu như sau: các điểm giá trị hữu hiệu được tìm ra sau mỗi bước lặp bằng cách sử dụng phép vô hướng hóa; sau bước giải bài toán vô hướng hóa, một phần không gian của tập ảnh sẽ được loại bỏ để tiếp tục tìm kiếm những điểm giá trị hữu hiệu còn lại. Miền ở trong không gian ảnh được sử dụng trong việc tìm kiếm điểm giá trị hữu hiệu được cập nhật sau mỗi bước lặp và được gọi chung là miền tìm kiếm (the search region). Việc nghiên cứu cấu trúc và cách cập nhật miền tìm kiếm đóng vai trò quan trọng và ảnh hưởng đến tính hiệu quả của phương pháp này (xem [13, 23, 24, 25]). Một bài toán tối ưu không lồi liên quan chặt chẽ với bài toán tối ưu đa mục tiêu là Bài toán tối ưu trên tập hữu hiệu (hay Bài toán tối ưu trên tập Pareto). Đó là bài toán tối ưu một hàm số 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. Việc giải bài toán này giúp ta chọn được một nghiệm hữu hiệu tốt nhất theo một mục tiêu nào đó mà không nhất thiết phải xác định toàn bộ X E . Điều này có ý nghĩa đặc biệt trong việc lựa chọn các phương án để đưa ra quyết định thích hợp. Bài toán tối ưu trên tập Pareto được nghiên cứu lần đầu trong công trình của Philip [26] cho trường hợp tuyến tính. Hướng nghiên cứu này sau đó thu hút được sự quan tâm của nhiều tác giả trong và ngoài nước (xem [27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37] và danh mục các tài liệu tham khảo kèm theo). Tuy nhiên, theo hiểu biết của chúng tôi, cho đến nay chưa có nghiên cứu nào cho trường hợp bài toán tối ưu trên tập hữu hiệu với hàm mục tiêu tựa lõm, đơn điệu tăng và bài toán tối ưu đa mục tiêu tương ứng có tập chấp nhận được là tập hữu hạn điểm. Thông thường, bài toán tối ưu đa mục tiêu dạng này là mô hình toán học của các bài toán thực tế mà số liệu được cho bằng phương pháp thống kê. 2. Mục đích nghiên cứu Trong luận án này, chúng tôi tiến hành các nghiên cứu sau: • 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 một bài toán tối ưu rời rạc và đưa bài toán này về một bài toán tối ưu DC, đề xuất thuật toán toàn cục (nhánh cận kết hợp DCA) để giải. • 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) được đề xuất bởi Astorino và Miglionico [39]. Đây là một bài toán tối ưu (liên tục) không lồi khó với ràng buộc không lồi. Astorino và Miglionico [39] đã đề xuất một thuật toán dựa trên tiếp cận địa phương để giải. Chúng tôi đưa bài toán (SCEP) về dạng một bài toán tối ưu đơn điệu rời rạc và xây dựng thuật toán toàn cục dựa trên lược đồ nhánh-giảm-cận để giải. Ngoài ra, chúng tôi cũng đề xuất thêm một thuật toán địa phương hiệu quả cho bài toán (SCEP). 3
• Xuất phát từ ý nghĩa quan trọng của miền tìm kiếm đối với bài toán tối ưu đa mục tiêu rời rạc chúng tôi sử dụng khái niệm đa khối (polyblock) nửa mở cho việc biểu diễn miền tìm kiếm. Từ đó có được cái nhìn trực quan về miền tìm kiếm của bài toán tối ưu đa mục tiêu rời rạc. Bên cạnh việc đề xuất một thủ tục mới cập nhật miền tìm kiếm cho lược đồ chung GM để tìm toàn bộ tập điểm giá trị hữu hiệu của bài toán tối ưu đa mục tiêu rời rạc, chúng tôi cũng nghiên cứu sự ảnh hưởng việc quản lí những bài toán con (chính là những bài toán có được nhờ phép vô hướng hóa) được lưu trong suốt quá trình tìm kiếm đến tính hiệu quả của lược đồ GM. Theo hiểu biết của chúng tôi, cho đến nay vấn đề này vẫn chưa được nghiên cứu. • Chúng tôi xét một lớp các bài toán tối ưu trên tập hữu hiệu với hàm mục tiêu (của bài toán tối ưu trên tập hữu hiệu) là đơn điệu tăng tựa lõm, tập ràng buộc là tập 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 ràng buộc X bao gồm hữu hạn các điểm cho trước. Chúng tôi đề xuất thuật toán toàn cục giải bài toán tối ưu trên tập hữu hiệu này. 3. Đối tượng nghiên cứu • Bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD. • Bài toán năng lượng phủ cảm biến cho mạng cảm biến vô tuyến. • Bài toán tìm 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. • Bài toán tối ưu trên tập hữu hiệu của một bài toán tối ưu đa mục tiêu rời rạc. 4. Phạm vi nghiên cứu • Nghiên cứu xây dựng mô hình. • Nghiên cứu đề xuất thuật toán giải những bài toán quan tâm. • Tính toán thử nghiệm những thuật toán mới và so sánh với những thuật toán khác. 5. Ý nghĩa khoa học và thực tiễn của đề tài Kết quả thu được của đề tài góp một phần nhỏ làm phong phú thêm cho lí thuyết tối ưu nói chung và tối ưu không lồi nói riêng. Tính hiệu quả của các thuật toán đề xuất đều được chúng tôi minh họa thông qua việc lập trình chạy thử nghiệm so sánh với các thuật toán khác cho rất nhiều các ví dụ sinh ngẫu nhiên và các ví dụ có sẵn với nhiều cỡ bài toán khác nhau. Những thuật toán mới đề xuất này có thể được áp dụng vào việc giải quyết những vấn đề tương tự trong thực tiễn một cách hiệu quả. 4
6. Cấu trúc và kết quả của luận án Nội dung chính của luận án được chia thành ba chương như sau: Chương 1: “Kiến thức chuẩn bị” trình bày một số khái niệm, kết quả và thuật toán quan trọng của tối ưu DC, tối ưu đơn điệu. Các kết quả ở đây có thể xem là sự chuẩn bị về mặt lý thuyết để giải ba bài toán tối ưu không lồi trong Chương 2 và Chương 3. Chương 2: “Một số thuật toán giải hai bài toán tối ưu không lồi trong viễn thông”. Chương này dành để trình bày những kết quả liên quan đến việc nghiên cứu hai bài toán tối ưu không lồi trong viễn thông là: bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD và bài toán năng lượng phủ cảm biến cho mạng cảm biến vô tuyến. Chương 3: “Thuật toán giải một số bài toán trong tối ưu đa mục tiêu rời rạc”. Chương này trình bày các kết quả nghiên cứu liên quan tới bài toán tìm 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 và 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. Các kết quả của luận án đã được công bố trong ba bài báo được nhận đăng ở các tạp chí Computer & Operations Research, Optimization Letters, Pacific Journal of Optimization, một bài đăng trong kỉ yếu hội nghị quốc tế về kĩ thuật công nghiệp và quản lí hệ thống Lần thứ 7, 11-13/10/2017 tại Đại học khoa học ứng dụng Saarland, Saarbrucken, Đức, và một bài báo đang gửi đăng tại tạp chí 4OR A Quarterly Journal of Operations Research. Các kết quả này đã được tác giả báo cáo tại: • Xêmina Lý thuyết tối ưu và ứng dụng, Bộ môn Toán ứng dụng, Viện Toán ứng dụng và Tin học, Đại học Bách Khoa Hà Nội, ngày 19/11/2015, 17/12/2015, 24/03/2016, • Xêmina Bài toán cân bằng, bài toán điểm bất động và các vấn đề liên quan, Viện Toán ứng dụng và Tin học, Đại học Bách Khoa Hà Nội, ngày 17/05/2016, • Hội nghị Toàn quốc Lần thứ 4 về Ứng dụng toán học, tổ chức tại Đại học kinh tế quốc dân, Hà Nội, ngày 23-25/12/2015, • Hội thảo Tối ưu và Tính toán khoa học Lần thứ 14, Ba Vì, ngày 21-23/04/2016, • Hội nghị quốc tế về kĩ thuật công nghiệp và quản lí hệ thống Lần thứ 7, 11- 13/10/2017, tại Đại học khoa học ứng dụng Saarland, Saarbrucken, Đức, (7th International Conference on Industrial Engineering and Systems Management, Saarland University of Applied Sciences, Saarbrucken, Germany, date 11-13/10/2017), • Xêmina Khoa học dữ liệu và tối ưu các hệ thống phức tạp, phòng nghiên cứu Opt-Data, Khoa quốc tế, Đại học quốc gia Hà Nội, ngày 04/12/2018. • Xêmina Bộ môn Toán ứng dụng, Viện Toán ứng dụng và Tin học, Đại học Bách Khoa Hà Nội, ngày 18/02/2019. 5
Chương 1 KIẾN THỨC CHUẨN BỊ Chương này được dành để nhắc lại một số khái niệm và kết quả cơ bản liên quan đến tối ưu DC (Mục 1.1) và tối ưu đơn điệu (Mục 1.2). Nội dung chính của chương này được tham khảo trong [2, 3, 40, 41, 42, 43, 44]. 1.1 Tối ưu DC Mục này sẽ nhắc lại một số khái niệm và kết quả cơ bản liên quan đến bài toán tối ưu DC và thuật toán DCA. 1.1.1 Một số khái niệm cơ bản Nếu hàm số f xác định trên một tập C ⊂ R n thì ta luôn có thể mở rộng nó thành một hàm xác định trên toàn không gian R n bằng cách đặt f (x) = +∞ với mọi x ∈/ C. Vì vậy không giảm tính tổng quát trong những phần tiếp theo của Mục 1.1 chúng ta sẽ xét hàm f : R n → R ∪ {−∞, +∞} (tức là một hàm xác định trên toàn không gian) và quy ước rằng +∞ − (+∞) = +∞. Kí hiệu: domf = {x ∈ R n | f (x) < +∞} (miền hữu hiệu của hàmf ), epif = {(x, t) ∈ R n × R | f (x) ≤ t} (trên đồ thị của hàmf ). Hàm f được gọi là (i) chính thường nếu domf 6= ∅ và f (x) > −∞ với mọi x ∈ R n ; (ii) nửa liên tục dưới nếu nó nửa liên tục dưới tại mọi x 0 ∈ R n , tức là lim inf f (x) ≥ f (x 0 ) với mọi x 0 ∈ Rn ; x→x 0 (iii) lồi nếu với mọi x1 , x 2 ∈ R n , λ ∈ [0, 1] ta có f (λx 1 + (1 − λ)x 2 ) ≤ λf (x 1 ) + (1 − λ)f (x 2 ). 6
Ngoài ra f được gọi là lõm nếu −f là hàm lồi; aphin nếu f vừa lồi vừa lõm; f được gọi là lồi chính thường nếu f vừa lồi vừa chính thường. Rõ ràng, từ định nghĩa ta có f lồi nếu và chỉ nếu trên đồ thị của nó là một tập lồi. Xem minh họa ở Hình 1.1. y epif y=f(x) x Hình 1.1: Minh họa trên đồ thị của hàm lồi y = f (x) Kí hiệu Γ 0 (Rn ) là tập tất cả các hàm nửa liên tục dưới, lồi chính thường trên R n ; h., .i và k.k tương ứng là tích vô hướng và chuẩn Euclide trong R n . Ví dụ 1.1. (i) Hàm chỉ của một tập lồi C khác rỗng 0 nếu x ∈ C χ C (x) = ( +∞ nếu trái lại là một hàm lồi chính thường. (ii) Hàm chuẩn của một véc-tơ ||x|| p = ( i |x i | p ) 1/p (p ≥ 1) là hàm lồi chính thường. Nói riêng chuẩn Euclide ||x|| =Phx, xi 1/2 cũng là một hàm lồi chính thường. (iii) Hàm toàn phương f (x) = 1/2 hx, Qxi + hx, ai + α, trong đó Q là ma trận thực đối xứng cấp n × n; a ∈ R n và α ∈ R. Nếu Q là ma trận nửa xác định dương thì f (x) là hàm lồi. (iv) Hàm θ(x) = max{ a i , x − α i , i = 1, . . . , m} + χ C (x),   với a ∈ R , α i ∈ R, i = 1, . . . , m; C là tập lồi đa diện khác rỗng trong R i n n, là hàm lồi và được gọi là hàm lồi đa diện. Hàm f ∗ xác định bởi f ∗(y) = sup{hx, yi − f (x) | x ∈ R n }, với y ∈ R n 7
được gọi là hàm liên hợp của f. Hàm bao lồi đóng của hàm f , kí hiệu là cof, là một hàm có trên đồ thị là bao lồi đóng của trên đồ thị của f. Hàm được gọi là lồi đóng nếu hàm bao lồi đóng của nó là chính nó. Như vậy nếu f ∈ Γ 0 (R n ) thì f là hàm lồi đóng và từ [41, Hệ quả 10.1, trang 154] ta suy ra mệnh đề sau. Mệnh đề 1.1. Nếu f ∈ Γ 0(R n ) thì f ∗ ∈ Γ 0 (R n ) và f ∗∗ = f. Ví dụ 1.2. (i) Hàm lồi toàn phương f (x) = 12 x T Qx + q T x, với Q là ma trận đối xứng xác định dương cấp n × n và q ∈ R n , có f ∗ (y) = sup{hx, yi − f (x) | x ∈ R n } 1 T = sup{hx, y i − x Qx − q T x | x ∈ R n } 2 1 T = sup{− x Qx + (y − q) T x | x ∈ R n } 2 1 = (y − q) T Q −1 (y − q). 2 Như vậy, hàm liên hợp của một dạng toàn phương đối xứng xác định dương cũng là một dạng toàn phương, đối xứng xác định dương. Trong trường hợp đặc biệt 1 ta có hàm liên hợp của hàm ||x|| 2 là chính nó (xem [41, trang 152]). 2 (ii) Hàm liên hợp của hàm chỉ χ ∗C (y) = sup{hx, yi − χ C (x) | x ∈ R n} = sup{hx, y i | x ∈ C }. Cho ε > 0, véc-tơ p ∈ R n được gọi là một ε-dưới gradient của hàm chính thường f tại x 0 (x0 ∈ domf ) nếu p, x − x 0 ≤ f (x) − f (x 0) + ε với mọi x ∈ R n .   Tập tất cả các ε-dưới gradient được gọi là ε-dưới vi phân của f tại x 0 . Kí hiệu là ∂ε f (x 0). Véc-tơ p ∈ R n được gọi là dưới gradient của hàm chính thường f tại x 0 (x 0 ∈ domf ) nếu p, x − x 0 ≤ f (x) − f (x 0 ) với mọi x ∈ R n .   Tập tất cả các dưới gradient được gọi là dưới vi phân của f tại x 0 . Kí hiệu là ∂f (x 0). Như vậy ta có ∂f (x 0 ) = ∩ ε>0 ∂ε f (x 0 ). Định lí sau cho ta biết sự tồn tại của ε-dưới vi phân và dưới vi phân của một hàm chính thường. 8