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.


Đăng kí địa chỉ email: https://forms.gle/VmTRRx7a5mGpxh9n6

Đăng kí nhóm bài tập: https://forms.gle/goEUZCAToeM6g3QE7

Đăng kí vào classroom: link


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 


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


Tuần 2

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


Tuần 3


Tuần 4

  • Lý thuyết đa diện (tiếp)
  • Thuật toán đơn hình – giới thiệu: 1 mặt, 4 mặt

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


Tuần 5

  • 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
  • Chữa bài tập 1

Tuần 6 

  • Bài toán đối ngẫu và các định lý đối ngẫu: 1 mặt, 4 mặt

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


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

  1. Bước 1: Xem danh sách các đề tài đã đăng ký tại đây. 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ý tại link.

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 hay sử dụng nhiều phương pháp 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ị.

Một số ví dụ ứng dụng: link. Lưu ý: không được chọn các bài 1, 6, 14, 16, 21, 28.

 


Tuần 7 


Tuần 8

  • buffer
  • Hỏi đáp chuẩn bị thi giữa kì

Tuần 9 


Tuần 10 (buổi 1)

  • Chữa bài thi giữa kì

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


Tuần 10 (buổi 2)


Tuần 11

  • Bài toán tối ưu phi tuyến không ràng buộc (tiếp)
  • Chữa bài tập 3

Tuần 12 

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


Tuần 13 

  • Thuật toán Newton: 1 mặt, 4 mặt
  • Stochastic gradient descent: 1 mặt, 4 mặt
  • Chữa bài tập 4

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


Tuần 14 & 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ó 15 phút trình bày, 8 phút trả lời câu hỏi
  • Buổi 1 (9.6): Các nhóm từ 1 đến 5
  • Buổi 2 (10.6): Các nhóm từ 6 đến 10
  • Buổi 3 (16.6): Các nhóm từ 11 đến 15.

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 15 (buổi 2)  (+ 1 buổi tuần 16 nếu cần)

  • Chữa bài tập 5
  • Tổng kết