Luận án tiến sĩ: Một số lớp bài toán tối ưu không lồi: thuật toán và ứng dụng - NCS Phạm Thị Hoài


Ngày đăng: 02/12/2019
Tê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
Ngành: Toán học               Mã số: 9460101
Nghiên cứu sinh: Phạm Thị Hoài
Người hướng dẫn khoa học:
                                              1. TS. Nguyễn Cảnh Nam
     2. GS. TSKH. Lê Thị Hoài An
 
Cơ sở đào tạo: Trường Đại học Bách khoa Hà Nội
 
TÓM TẮT KẾT LUẬN MỚI CỦA LUẬN ÁN
Luận án nghiên cứu các thuật toán giải một số bài toán tối ưu không lồi có nhiều ứng dụng trong thực tế, cụ thể là:
 
  1. Đối với bài toán phân bổ tài nguyên cho mạng không dây OFDMA/TDD, chúng tôi đã xây dựng mô hình toán học cho bài toán này dưới dạng một bài toán quy hoạch tuyến tính nhị phân. Sau đó, sử dụng tiếp cận liên tục (kĩ thuật hàm phạt) bài toán được đưa về dạng một bài toán tối ưu DC. Cuối cùng chúng tôi đề xuất thuật toán toàn cục nhánh cận kết hợp DCA để giải bài toán này.
  2. Đối với  bài toán phủ năng lượng cảm biến cho mạng cảm biến vô tuyến, chúng tôi xuất phát từ mô hình bài toán tối ưu không lồi liên tục khó (với ràng buộc không lồi), được đề xuất bởi Astorino và Miglionico [A. Astorino, G. Miglionico (2016), "Optimizing sensor cover energy via DC programming", Optim. Lett., Vol. 10 (2), pp. 355-368]. Bằng cách khai thác các tính chất từ cấu trúc đơn điệu của bài toán, chúng tôi đã đề xuất ba thuật toán mới giải bài toán trên, bao gồm: một thuật toán tìm nghiệm địa phương,  một thuật toán toàn cục dựa trên lược đồ nhánh-giảm-cận truyền thống và một thuật toán cải tiến thuật toán nhánh-giảm-cận truyền thống. Trong đó, các thuật toán toàn cục thu được sau khi bài toán gốc được đưa về một bài toán tối ưu đơn điệu rời rạc tương đương.
  3. Đối với  bài toán tìm toàn bộ tập giá trị hữu hiệu cho bài toán tối ưu đa mục tiêu rời rạc, sử dụng khái niệm đa khối nửa mở cho biểu diễn miền kiếm của bài toán tối ưu đa mục tiêu rời rạc, chúng tôi đề xuất một thủ tục cập nhật miền tìm kiếm mới dùng cho lược đồ GM để 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. Ngoài ra, chúng tôi còn nghiên cứu sự ảnh hưởng của việc quản lí những bài toán con được lưu trong suốt quá trình tìm kiếm thông qua việc khảo sát lược đồ GM với một số cách quản lí khác nhau.
  4. Đối với bài toán tối ưu trên tập hữu hiệu, chúng tôi xét một lớp các bài toán dạng này với hàm mục tiêu không giảm tựa lõm, miền ràng buộc là 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 với ràng buộc cho bởi tập hữu hạn các điểm. Chúng tôi đề xuất thuật toán tính toàn bộ tập đỉnh của bao Edgeworth-Pareto trong không gian ảnh và sử dụng kết quả này cho việc đề xuất thuật toán toàn cục giải bài toán trên.
 
Tất cả các thuật toán được đề xuất trong luận án đều được lập trình thử nghiệm và so sánh với các phương pháp khác trên rất nhiều các bộ dữ liệu sinh ngẫu nhiên và có sẵn. Kết quả số được tổng hợp, phân tích kĩ lưỡng cho thấy được tính hiệu quả và ý nghĩa của việc đề xuất các thuật toán này.
 
 Phạm Thị Hoài.rar Chia sẻ bài viết lên facebook