Luận văn Thạc sĩ Toán học: Bài toán quy hoạch lồi

Luận văn Thạc sĩ Toán học - Bài toán quy hoạch lồi nhằm trình bày một số phương pháp cơ bản nhất cho bài toán quy hoạch lồi. Cụ thể luận văn trình bày các phương án sau: các phương pháp sử dụng đạo hàm bậc nhất, phương pháp Newton và các phương pháp hàm phạt. Mời bạn đọc cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Toán học: Bài toán quy hoạch lồi i M cl c M c l c............................................ i L i c m ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii M đ u............................................ 1Chương 1. Các ki n th c cơ b n v t p l i và hàm l i . . . . . . . . . 2 1.1. T p l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Hàm l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Chương 2. Đi u ki n c c ti u hàm l i . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1. Bài toán quy ho ch l i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.1. Các khái ni m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1.2. S t n t i nghi m t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.1.3. Đi u ki n t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2. T i ưu có ràng bu c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1. Đ i ng u Lagrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.2. Đi u ki n t i ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19Chương 3. M t s phương pháp gi i bài toán quy ho ch l i . . 27 3.1. Các thu t toán s d ng đ o hàm b c nh t . . . . . . . . . . 27 3.1.1. Thu t toán gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.2. Phương pháp chi u Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.1.3. Thu t toán chi u dư i gradient x p x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.4. Thu t toán Frank-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2. Phương pháp Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3. Phương pháp hàm ph t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.1. Phương pháp hàm ph t đi m ngoài. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.3.2. Phương pháp hàm ph t đi m trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 K t lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Tài li u tham kh o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 ii L I C M ƠN Trư c khi trình bày n i dung chính c a khóa lu n, em xin bày t lòngbi t ơn sâu s c t i GS.TSKH. Lê Dũng Mưu ngư i đã t n tình hư ng d nvà giúp đ em trong su t quá trình h c t p và nghiên c u đ em có thhoàn thành khóa lu n này. Em cũng xin bày t lòng bi t ơn chân thành t i quý th y, cô giáo Vi nToán h c - Vi n Khoa h c và Công ngh Vi t Nam đã gi ng d y và giúpđ em hoàn thành khóa h c. Nhân d p này em cũng xin chân thành c m ơn Ban Giám hi u, các b nđ ng nghi p Trư ng Đ i h c Công ngh Thông tin và Truy n thông - Đ ih c Thái Nguyên, gia đình và b n bè đã luôn đ ng viên, giúp đ và t ođi u ki n cho em v m i m t trong su t quá trình h c t p và th c hi nkhóa lu n t t nghi p. M c dù đã có nhi u c g ng nhưng Lu n vă ...