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 vào học kì 2 năm học 2018-2019.


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

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


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


Tuần 2

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


Tuần 3

Lý thuyết đa diện


Tuần 4

  • Thuật toán đơn hình – giới thiệu: 1 mặt, 4 mặ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

Bài 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) (25.2)
  • Bài toán đối ngẫu và các định lý đối ngẫu: 1 mặt, 4 mặt (27.2)

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


Tuần 6 

  • Bài toán đối ngẫu và các định lý đối ngẫu (tiếp tục) (4.3)
  • Chữa bài tập 1, 2, 3 (6.3)

Tuần 7 


Tuần 8 

  • Chữa bài tập 4 (18.3)
  • Thuyết trình về code thuật toán đơn hình (20.3)

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


Tuần 9 

  • Các kiến thức cơ sở: 1 mặt, 4 mặt (25.3)
  • Bài toán tối ưu phi tuyến không ràng buộc: 1 mặt, 4 mặt (25.3)
  • Thi giữa kì (27.3)

Tuần 10


Tuần 11

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


Tuần 12

  • Stochastic gradient descent: 1 mặt, 4 mặt
  • Thực hành phòng máy

Tuần 13

  • Thuật toán Newton
  • Thuật toán tựa Newton
  • Chữa bài tập 5

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


Tuần 14

  • Bài toán tối ưu có ràng buộc, đối ngẫu và điều kiện KKT
  • Thực hành phòng máy

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


Tuần 15

  • Chữa bài tập 6 & 7
  • Tổng kết