Đề tài Thuật toán Frank - Wolfe

Tất cả các ngành, các lĩnh vực dù hoạt động ở phương diện nào thì mục đích cuối cùng cũng là giải các bài toán tối ưu của đơn vị mình. Việt Nam là một minh chứng. Trong xu thế hội nhập hiện nay, đặc biệt sau kí kết hiệp định thương mại thế giới WTO, Việt Nam đang đứng trước nhiều thử thách mới. Và cạnh tranh trên thương trường quốc tế là bài toán hàng đầu đối với các doanh nghiệp trong nước. Do tính cấp thiết của thực tế nên em đã quyết định chọn đề tài: “Thuật toán Frank-Wolfe”- đây là thuật toán giải các bài toán quy hoạch lồi với các ràng buộc tuyến tính. Em hi vọng nó có thể góp một phần làm phong phú hơn kho tàng thuật toán giải các bài toán tối ưu. Bài viết của em gồm 3 phần lớn (ngoài phần mục lục và phần tài liệu tham khảo): ỉ Thứ nhất : Lời mở đầu ỉ Thứ hai : Nội dung ỉ Thứ ba : Kết luận Trong phần nội dung,em sẽ trỡnh bày 4 vấn đề chính: 1. Tổng quan về quy hoạch phi tuyến 2. Thuật toỏn Frank-Wolfe 3. Thớ dụ 4. Chương trỡnh Gamside Cuối cùng, em xin chân thành cảm ơn các thầy giáo,cô giáo khoa Toán kinh tế đó tạo mụi trường cho em được học tập và rèn luyện. Em hết sức biết ơn thầy giáo Ngô Văn Mỹ đó giỳp em hoàn thành đề án môn học này. Nội dung: 1. Tổng quan về quy hoạch phi tuyến 1.1. Giới thiệu chung về QHFT Bài toán QHFT sẽ nói ở dưới đây không phải là bài toán QHFT thực tổng quát, mà ta chỉ xét lớp bài toán QHFT có hàm mục tiêu là hàm khả vi liên tục( tới bậc tuỳ ý) trờn tập mở bao tập phương án D; bản thân tập phương án cũng được xác định bởi các hàm số trong các ràng buộc là các hàm khả vi liên tục n biến. Cụ thể ta có bài toán tổng quát sau: (1) Trong đó: và là cỏc hàm n biến độc lập. Ngoài ra: trong các hàm và phải cú ớt nhất một hàm phi tuyến; luụn giả thiết cỏc hàm là cỏc hàm liờn tục; hàm mục tiờu khả vi liờn tục trờn tập mở bao tập phương án D. Tuy bài toán QHFT đó được giới hạn như trên, nhưng tính phi tuyến của bài toán luôn tạo ra những phức tạp đáng kể khi tiệm cận với nó. Với bài toán QHFT người ta cũng sử dụng phương pháp tiệm cận giống như bài toán cực trị có ràng buộc cổ điển trong giải tích-tức là tỡm cỏch đưa bài toán cực trị có ràng buộc về bài toán cực trị tự do rồi tỡm cỏch đưa ra điều kiện Kunh- Tucker. Với một nhóm điều kiện bổ sung đủ mạnh thì điều kiện Kunh-Tucker có thể trở thành điều kiện cần và đủ đối với lời giải của (1). 1.2. Bài toỏn QHFT Bài toán tổng quát QHFT có dạng như (1); tuy nhiên đôi khi để thuận tiện trong việc giải thích ý nghĩa kinh tế ta cú thể biểu diễn cỏc dạng cụ thể sau: ã