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. NGUYỄN CẢNH NAM 2. 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.

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. 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.

Lê Dũng Mưu, PGS. Nguyễn Thị Bạch Kim, GS. 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. 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. Đỗ Đứ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 Một số khái niệm cơ bản .2 Thuật toán DCA .1 Một số khái niệm cơ bản .2 Thuật toán giải bài toán tối ưu đơn điệu.

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 .1 Mô tả bài toán .2 Bài toán tối ưu DC đa diện tương đương với bài toán (RAP) .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) .4 Kết quả tính toán thử nghiệm .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 .1 Mô tả bài toán .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.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.4 Kết quả tính toán thử nghiệm. 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 .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 .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) .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) .3 Kết quả tính toán thử nghiệm .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 .1 Mô tả bài toán .2 Thuật toán toàn cục giải bài toán (P ) .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 = (x1 ,. , n x, y ∈ Rn , x ≤ y xi ≤ yi , i = 1,.

, n} : xi > yi , x, y ∈ Rn , x < y xi < yi , i = 1,. , n Rn+ {x ∈ Rn | x ≥ 0} u = x ∨ y, x, y ∈ Rn ui = max{xi , yi }, i = 1,. , n v = x ∧ y, x, y ∈ Rn vi = min{xi , yi }, i = 1,. , n ei véc-tơ đơn vị thứ i trong Rn , tức là, eii = 1, eij = 0, ∀j 6= i [a, b], a, b ∈ Rn {x ∈ Rn | a ≤ x ≤ b} (a, b], a, b ∈ Rn {x ∈ Rn | a < x ≤ b} [a, b), a, b ∈ Rn {x ∈ Rn | 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.

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.2 Kết quả áp dụng các Thuật toán 2.6 cho bài toán (SCEP) .3 Kết quả áp dụng Thuật toán 2.5 cho bài toán (SCEP) .1 Dữ liệu của Ví dụ 3.2 Kết quả tính toán theo Thuật toán 3.3 Kết quả tính toán theo Thuật toán 3.4 Kết quả tính toán theo Thuật toán 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 .6 Kết quả tính toán thử nghiệm Thuật toán 3.7 Kết quả so sánh Thuật toán 3.3 và Thuật toán 3. 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) .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 .3 Đa khối với tập đỉnh {u1 , u2 , u3 , u4 }, trong đó {u1 , u2 , u4 } là tập đỉnh chính, u3 là đỉnh không chính .4 Đối đa khối với tập đỉnh chính {z 1 , z 2 , z 3 } .5 Minh họa Mệnh đề 1.1 Khung OFDMA/TDD mô tả xung đột giữa hai người dùng .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 (i1 , j1 ) và (i2 , j2 ) là đỉnh nếu anh ta được cấp hai nút này .3 n=25, m=5, Bộ dữ liệu 1 .4 n=25, m=5, Bộ dữ liệu 2 .5 n=25, m=5, Bộ dữ liệu 3 .6 n=25, m=5, Bộ dữ liệu 4 .7 n=25, m=5, Bộ dữ liệu 5 .8 n=25, m=50, Bộ dữ liệu 1 .9 n=25, m=50, Bộ dữ liệu 3 .10 n=25, m=50, Bộ dữ liệu 4 .11 n=25, m=50, Bộ dữ liệu 5 .12 n=75, m=15, Bộ dữ liệu 1 .13 n=75, m=15, Bộ dữ liệu 2 .14 n=75, m=15, Bộ dữ liệu 3 .15 n=75, m=15, Bộ dữ liệu 4 .16 n=75, m=15, Bộ dữ liệu 5 .1 Minh họa Ví dụ 3.2 Khởi tạo, N = ∅ và S(N ) = [y I , b) .7 Minh họa Ví dụ 3.8 Minh họa Ví dụ 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 ) .10 Minh họa Ví dụ 3. 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.