ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN ANH TUẤN
MỘT SỐ PHƯƠNG PHÁP CƠ BẢN
GIẢI QUY HOẠCH LỒI
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2011
.
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN ANH TUẤN
MỘT SỐ PHƯƠNG PHÁP CƠ BẢN
GIẢI QUY HOẠCH LỒI
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số :60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH. LÊ DŨNG MƯU
Thái Nguyên - Năm 2011
.
i
Mục lục
Trang phụ bìa
Mụclục ............................... ii
Lời cảm ơn 1
Mở đầu 1
1 Kiến thức cơ bản về tập lồi và hàm lồi 3
1.1 Tậplồi............................. 3
1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Hàm lồi và hàm lõm . . . . . . . . . . . . . . . . . . 7
1.2.2 Hàm lồi liên tục . . . . . . . . . . . . . . . . . . . . 11
1.2.3 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . 13
1.2.4 Hàm lồi mạnh . . . . . . . . . . . . . . . . . . . . . 17
2 Các phương pháp giải quy hoạch lồi không ràng buộc 20
2.1 Bài toán quy hoạch lồi và các tính chất cơ bản . . . . . . . 20
2.2 Thuật toán hướng đạo hàm (dốc nhất) giải quy hoạch lồi. . 25
2.3 Phương pháp Newton. . . . . . . . . . . . . . . . . . . . . . 28
3 Phương pháp giải quy hoạch lồi có ràng buộc 31
3.1 Bài toán quy hoạch lồi có ràng buộc và điều kiện tối ưu . . 31
.
ii
3.1.1 Bài toán quy hoạch lồi có ràng buộc . . . . . . . . . 31
3.1.2 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . 33
3.1.3 Định lý (Karush-Kuhn-Tucker) . . . . . . . . . . . . 35
3.1.4 Định lý (Kuhn-Tucker) . . . . . . . . . . . . . . . . 39
3.2 Phương pháp hàm phạt giải quy hoạch lồi có ràng buộc. . . 41
3.2.1 Phương pháp hàm phạt điểm trong . . . . . . . . . 42
3.2.2 Phương pháp hàm phạt điểm ngoài. . . . . . . . . . 45
3.3 Phương pháp Frank – Wolfe . . . . . . . . . . . . . . . . . 47
Kết luận 49
Tài liệu tham khảo 51
.
1
Lời cảm ơn
Nghiên cứu khoa học là một chặng đường đầy khó khăn và thử thách.
Sau hơn một năm làm luận văn, tôi đã trải nghiệm được rất nhiều điều,
rút ra được những bài học bổ ích cho cuộc sống.
Công trình được hoàn thành bên cạnh sự cố gắng của cá nhân là sự
giúp đỡ tận tình của các thầy cô giáo, của đồng nghiệp, của bạn bè và
những người thân.
Trước tiên, tôi xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới
GS.TSKH Lê Dũng Mưu – người thầy đã trực tiếp hướng dẫn, động viên
và giúp đỡ tôi trong quá trình học tập và nghiên cứu để hoàn thành luận
văn này. Kính chúc thầy và gia đình luôn mạnh khỏe, hạnh phúc !
Tôi xin gửi lời cảm ơn tới các thầy cô giáo thuộc bộ môn Toán - Tin,
phòng Đào tạo và quan hệ Quốc tế, các cán bộ khoa Sau đại học trường
Đại học Khoa học – Đại học Thái Nguyên đã dạy dỗ, chỉ bảo tôi trong
suốt hai năm học vừa qua.
Tôi xin cảm ơn các bạn học viên Cao học Toán khóa 3 đã động viên,
giúp đỡ tôi trong quá trình học tập và rèn luyện tại trường, cũng như trong
quá trình nghiên cứu để hoàn thành luận văn.
Tôi xin được bày tỏ sự cảm ơn chân thành của mình tới bạn bè đồng
nghiệp, tới những người thân trong gia đình đã động viên, giúp đỡ tôi về
mọi mặt để tôi có thể hoàn thành khóa học và thực hiện luận văn này.
Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những
.
