Luận văn Thạc sĩ Toán học: Một số phương pháp tối ưu không dùng đạo hàm

Luận văn Thạc sĩ Toán học: Một số phương pháp tối ưu không dùng đạo hàm nêu lên phương pháp Nelder – Mead cực tiểu hàm nhiều biến; phương pháp tìm kiếm trực tiếp Hooke – Jeeves. Mời các bạn tham khảo luận văn để nắm bắt nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Một số phương pháp tối ưu không dùng đạo hàmBỘ GIÁO DỤC VÀ ĐÀO TẠOVIỆN HÀN LÂM KHOA HỌCVÀ CÔNG NGHỆ VIỆT NAMVIỆN TOÁN HỌCLê Xuân ĐoànMỘT SỐ PHƯƠNG PHÁP TỐI ƯUKHÔNG DÙNG ĐẠO HÀMLUẬN VĂN THẠC SĨ TOÁN HỌCHÀ NỘI – 2015BỘ GIÁO DỤC VÀ ĐÀO TẠOVIỆN HÀN LÂM KHOA HỌCVÀ CÔNG NGHỆ VIỆT NAMVIỆN TOÁN HỌCLê Xuân ĐoànMỘT SỐ PHƯƠNG PHÁP TỐI ƯUKHÔNG DÙNG ĐẠO HÀMChuyên ngành: Toán ứng dụngMã số: 60460112LUẬN VĂN THẠC SĨ TOÁN HỌCNGƯỜI HƯỚNG DẪN KHOA HỌCPGS.TS. Bùi Thế TâmHÀ NỘI – 2015Một số phương pháp Tối ưu không dùng Đạo hàmMỤC LỤCTrangLỜI NÓI ĐẦU4Chương 1. PHƯƠNG PHÁP NELDER – MEAD CỰC TIỂUHÀM NHIỀU BIẾN ............................................................................. 61. Mô tả thuật toán Nelder – Mead trong không gian.................................. 62. Mô tả thuật toán Nelder – Mead trong không gian............................... 122.1. Phát biểu chung của thuật toán ................................................................... 132.2. Mô tả một bước lặp của thuật toán Nelder – Mead ............................. 132.3. Kiểm tra hội tụ ..................................................................................................... 172.4. Xây dựng đơn hình xuất phát ........................................................................ 172.5. Sơ đồ khối của thuật toán Nelder – Mead ................................................ 183. Bài toán tối ưu với ràng buộc tổng quát ............................................................ 184. Thuật toán Nelder – Mead với các biến bị chặn ............................................. 225. Các tính chất của thuật toán Nelder – Mead..................................................... 236. Chương trình máy tính cho thuật toán Nelder – Mead ............................... 336.1. Bài toán .................................................................................................................. 336.2. Các biến và mảng dùng trong chương trình ............................................ 346.3. Văn bản chương trình ...................................................................................... 346.4. Giải ví dụ bằng số ............................................................................................... 426.5. Các ví dụ đã chạy chương trình .................................................................... 452Một số phương pháp Tối ưu không dùng Đạo hàmChương 2. PHƯƠNG PHÁP TÌM KIẾM TRỰC TIẾPHOOKE – JEEVES .................................................................................. 491. Mô tả thuật toán Hooke - Jeeves trong không gian.............................. 491.1. Phát biểu bài toán .............................................................................................. 491.2. Tư tưởng cơ bản của thuật toán .................................................................. 491.3. Mô tả một bước lặp của thuật toán Hooke – Jeeves ........................... 512. Ví dụ minh họa cho thuật toán Hooke – Jeeves trong không gian... 533. Chương trình máy tính cho thuật toán Hooke – Jeeves .............................. 553.1. Bài toán .................................................................................................................. 553.2. Các biến và mảng dùng trong chương trình ........................................... 553.3. Văn bản chương trình ...................................................................................... 563.4. Giải ví dụ bằng số ............................................................................................... 613.5. Các ví dụ đã chạy chương trình .................................................................... 65KẾT LUẬN70TÀI LIỆU THAM KHẢO713Một số phương pháp Tối ưu không dùng Đạo hàmLỜI NÓI ĐẦUTrong các vấn đề thực tế chúng ta thường gặp bài toán phải cực tiểu haycực đại một hàm nhiều biến mà nó không có đạo hàm bậc nhất, không có đạohàm bậc hai, không lồi, không lõm, không DC, không đơn điệu, không thỏamãn điều kiện Lipchitz. Do đó các phương pháp tụt gradien, phương phápNiu-tơn, phương pháp gradien liên hợp… đều không áp dụng được. Khi đó tacần sử dụng các phương pháp tối ưu không dùng đạo hàm, ví dụ như phươngpháp dò tìm theo các tọa độ Hooke – Jeeves 1960 [6] và phương pháp tụt theocác đơn hình Nelder – Mead 1965 [1], phương pháp Monte – Carlo…Mục đích của luận văn này nhằm trình bày lại hai thuật toán không dùngđạo hàm Nelder – Mead và Hooke – Jeeves để cực tiểu một hàm nhiều biếnvà thử nghiệm các thuật toán này trên máy tính. Từ khi ra đời hai thuật toántrên đã được sử dụng rộng rãi trong các ngành kĩ thuật. Chính vì sự hiệu quảcủa hai thuật toán mà trong những năm gần đây nhiều tác giả đã cố gắng cảitiến các thuật toán này và xây dựng cơ sở lý thuyết chặt chẽ của các thuậttoán, chứng minh sự hội tụ của chúng (xem [2], [3], [5]).Các chương trình máy tính lập t ...