Tối ưu hóa

Trang web này tập trung các slide bài giảng và bài tập của môn tối ưu hóa giảng dạy tại trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội.

Link đăng kí nhóm bài tập: xem trên classroom của từng lớp.

Mã google classroom jajnpyg (cần dùng gmail để đăng ký, không dùng được email hus)

Nội dung bài giảng

Bài giảng được chia thành hai phần chính là quy hoạch tuyến tính và quy hoạch phi tuyến. Song hành với bài giảng là các bài tập lập trình sử dụng ngôn ngữ Python.

A. Quy hoạch tuyến tính:

Nội dung chính của phần này là định lý đối ngẫu, thuật toán đơn hình, thuật toán đơn hình hai pha và thuật toán đơn hình đối ngẫu.

Tài liệu tham khảo bắt buộc:

1. D. Bertsimas and J. N. Tsitsiklis, Introduction to Linear Optimization (Athena Scientific).

Tài liệu tham khảo thêm (thuật toán điểm trong không được dạy trên lớp, có thể tham khảo qua tài liệu 4 & 5):

1. D. Luenberger and Y. Ye, Linear and Nonlinear Programming (Springer)
2. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization. Algorithms and Complexity (Dover).
3. R. J. Vanderbei, Linear Programming: Foundations and Extensions (Springer).
4. C. Roos, T. Terlaky, J.-Ph. Vial, Interior Point Methods for Linear Optimization (Springer).
5. S. J. Wright, Primal-dual Interior-Point Methods (SIAM).

Một số bài giảng online:

1. Linear Programming, Prof. L. Vandenberghe (UCLA): http://www.seas.ucla.edu/~vandenbe/ee236a/ee236a.html
2. Linear Optimization, Prof. J. Burke (UW): https://sites.math.washington.edu/~burke/crs/407/

B. Quy hoạch phi tuyến

Trong phần quy hoạch phi tuyến chúng ta sẽ lần lượt xét bài toán tối ưu hóa không điều kiện và bài toán tối ưu hóa có điều kiện (đẳng thức). Chúng ta sẽ nghiên cứu khái niệm đối ngẫu, điều kiện tối ưu, điều kiện Karush-Kuhn-Tucker, các thuật toán tối ưu bậc nhất và bậc hai.

Tài liệu tham khảo bắt buộc:

1. J. Nocedal and S. Wright, Numerical Optimization (Springer).
2. S. Boyd and L. Vandenberghe, Convex Optimization (Cambridge University Press)

Tài liệu tham khảo thêm

1. D. Luenberger and Y. Ye, Linear and Nonlinear Programming (Springer)

Một số bài giảng online:

1. Convex Optimization, Prof. L. Vandenberghe, (UCLA): http://www.seas.ucla.edu/~vandenbe/ee236b/ee236b.html
2. Optimization Methods for Large-Scale Systems, Prof. L. Vandenberghe, (UCLA): http://www.seas.ucla.edu/~vandenbe/ee236c.html
3. Convex Optimization, Prof. R. Tibshirani (CMU): http://www.stat.cmu.edu/~ryantibs/convexopt/
4. Machine learning refined, https://jermwatt.github.io/mlrefined/

C. Lập trình

Song hành với môn học là các bài tập lập trình trên ngôn ngữ Python 3.

Hướng dẫn cài đặt phần mềm và các gói trên Python: link.

Slide bài giảng và bài tập

Phần 1: Giới thiệu chung

Tuần 1

• Giới thiệu về môn học và giới thiệu chung: 1 mặt, 4 mặt (2 tiết)
• Giới thiệu về ngôn ngữ lập trình Python: 1 mặt, 4 mặt, code, bảng tóm tắt (2 tiết)

Phần 2: Quy hoạch tuyến tính

Tuần 2

• Giới thiệu về tối ưu hóa: 1 mặt, 4 mặt (1 tiết)
• Quy hoạch tuyến tính: 1 mặt, 4 mặt (1 tiết)
• Fourier Motzkin elimination: 1 mặt, 4 mặt (tham khảo, tự đọc tài liệu tham khảo)
• Giới thiệu về ngôn ngữ lập trình Python (tiếp tục tuần 1): 1 mặt, 4 mặt, code, bảng tóm tắt (2 tiết)

Bài tập về nhà: Bài 1

Tuần 3

• Lý thuyết đa diện: 1 mặt, 4 mặt (2 tiết)
• Chữa BT 1 (1 tiết)
• Python cho tính toán khoa học: 1 mặt, 4 mặt, code, cách lưu/load file trên google colab (1 tiết)

Bài tập về nhà: Bài 2

Tuần 4

• Lý thuyết đa diện (tiếp tục tuần 3): 1 mặt, 4 mặt (1 tiết)
• Thuật toán đơn hình - giới thiệu: 1 mặt, 4 mặt (2 tiết)
• Thuật toán đơn hình - tính đúng đắn và thuật toán đơn hình 2 pha: 1 mặt, 4 mặt (1 tiết)

Bàu tập về nhà: Bài 3

Tuần 5

• Thuật toán đơn hình - tính đúng đắn và thuật toán đơn hình 2 pha (tiếp tục tuần 5): 1 mặt, 4 mặt (2 tiết)
• Chữa BT 2 & BT 3 (2 tiết)

Bài tập về nhà: Bài 4

Tuần 6

• Thuật toán đơn hình - tính đúng đắn và thuật toán đơn hình 2 pha (tiếp tục tuần 6): 1 mặt, 4 mặt (1 tiết)
• Bài toán đối ngẫu và các định lý đối ngẫu: 1 mặt, 4 mặt (1 tiết)
• Giải LP dùng python 1 mặt, code, colab code, pulp (2 tiết)

Tuần 7

• Bài toán đối ngẫu và các định lý đối ngẫu (tiếp tục tuần 6): 1 mặt, 4 mặt (2 tiết)
• Chữa BT 4

Bài tập về nhà: Bài 5

Phần mềm lindo:

• Download: https://www.lindo.com/index.php/ls-downloads/try-lingo (chọn bản 64 bit)
• Hướng dẫn sử dụng (ngắn): http://home.ubalt.edu/ntsbarsh/LindoCitrix.pdf
• Hướng dẫn sử dụng (đầy đủ): https://www.lindo.com/downloads/PDF/LindoUsersManual.pdf
• Thư viện các mô hình ứng dụng của Lindo https://www.lindo.com/index.php/application-models-library

Tuần 8

• Bài toán đối ngẫu và các định lý đối ngẫu (tiếp tục tuần 7): 1 mặt, 4 mặt (1 tiết)
• Phân tích độ nhạy (Sensitivity analysis) (cần có email hus để xem). Tham khảo sách Mathematical Modeling của Mark M. Meerschaert, trang 74 đến 82 (1 tiết).
• Thuật toán đơn hình đối ngẫu: 1 mặt, 4 mặt (1 tiết)
• Giải thích thêm cho thuật toán đơn hình đối ngẫu
• Cách tính nghiệm tối ưu của bài toán đối ngẫu
• Ôn tập thi giữa kì (1 tiết)

Đăng ký đề tài thuyết trình

1. Bước 1: Xem danh sách các đề tài đã đăng ký. Các nhóm không được chọn trùng với các đề tài đã đăng ký.
2. Bước 2: Điền nội thông tin đề tài nhóm muốn đăng ký.

Các link tương ứng được post trong classroom của mỗi lớp.

Nội dung thuyết trình là một ứng dụng thực tế bất kì của tối ưu hóa. Nếu là các ứng dụng của mô hình quy hoạch tuyến tính thì phải được tính toán sử dụng phần mềm trên dữ liệu thực. Các mô hình LP có thể giải sử dụng các gói trên python, excel, hay lindo. Lưu ý rằng lập trình trên python sẽ được đánh giá cao hơn chỉ dùng excel hay lindo.

Bài thuyết trình được chấm điểm dựa trên độ khó của nội dung, chất lượng thuyết trình, trả lời câu hỏi và sự chuẩn bị.

Tuần 9 (buổi 1)

• Chữa BT5 (2 tiết)

Bài tập về nhà: Bài 6

Phần 3: Quy hoạch phi tuyến

Tuần 9 (buổi 2)

Tự đọc lại một số kiến thức cơ sở về đạo hàm

• Đạo hàm riêng
• Gradient
• Hessian matrix
• Cách tính gradient của hàm tuyến tính và bậc 2 ở dạng ma trận

Slide bài giảng

• Các kiến thức cơ sở: 1 mặt, 4 mặt
• Ma trận xác định dương

Tuần 10

• Thi giữa kì
• Chữa bài thi giữa kì và BT6

Tuần 11

• Bài toán tối ưu phi tuyến không ràng buộc: 1 mặt, 4 mặt (2 tiết)
• Line search: 1 mặt, 4 mặt (2 tiết)

Bài tập về nhà: Bài 7

Tuần 12

• Thuật toán gradient descent: 1 mặt, 4 mặt, accelerated gradient descent (2 tiết)
• Chữa BT 7 (2 tiết)

Tuần 13

• Thuật toán Newton: 1 mặt, 4 mặt (2 tiết)
• Stochastic gradient descent: 1 mặt, 4 mặt (tham khảo, tự đọc)
• Lập trình và sử dụng phần mềm cho tối ưu phi tuyến

Bài tập về nhà: Bài 8

Tuần 14 (buổi 1)

• Chữa BT 8 và hỏi đáp ôn tập cuối kì

Tuần 14 (buổi 2) & tuần 15

Thuyết trình về dự án (ứng dụng thực tế, mô hình hóa dưới dạng LP/IP và giải tìm nghiệm dùng code hoặc phần mềm)

Lưu ý: Mọi thành viên của nhóm đều phải tham gia thuyết trình và trả lời câu hỏi, giảng viên có thể tùy ý đảo lại thứ tự thuyết trình của các thành viên trong nhóm (mỗi thành viên đều phải nắm rõ nội dung toàn bộ bài thuyết trình).

Tiêu chí chấm điểm:

• Nội dung: Độ khó của vấn đề, sự sáng tạo và hoàn thiện của giải pháp (giải thuật và code)
• Thuyết trình: Slide và trình bày
• Trả lời câu hỏi.

• Mỗi nhóm có 12 phút trình bày, 8 phút trả lời câu hỏi
• Buổi 1 (7.12): Các nhóm từ 1 đến 6
• Buổi 2 (9.12): Các nhóm từ 7 đến 12
• Buổi 3 (14.12): Các nhóm từ 13 đến 19.

Lưu ý: Để tiết kiệm thời gian trong mỗi buổi thuyết trình các nhóm phải copy nội dung thuyết trình (slide & code) lên cùng 1 máy tính có kết nối HDMI.

Tuần 16

• Sẽ sử dụng nếu thiếu thời gian