Tối ưu hóa: chọn phương án tốt nhất trong vòng ràng buộc
Vì sao người học khoa học máy tính cần tối ưu hóa: mục tiêu, ràng buộc, quy hoạch tuyến tính, bài toán lồi, hạ gradient có đà, tối ưu nguyên, và bắt đầu từ đâu.
Ban biên tập OpenER
Cập nhật 09/11/2026 · 20 phút đọc · CC BY 4.0
Một xưởng mộc nhỏ ở làng Đồng Kỵ làm hai mặt hàng: bàn và ghế. Mỗi tuần xưởng có 30 tấm gỗ và 26 giờ công của người thợ chính. Một cái bàn tốn 4 tấm gỗ, 3 giờ công, lời 500 nghìn đồng; một cái ghế tốn 1 tấm gỗ, 2 giờ công, lời 200 nghìn. Tuần này nên làm mấy bàn, mấy ghế?
Làm toàn bàn thì hết gỗ trong khi thợ còn dư giờ; làm toàn ghế thì hết giờ trong khi gỗ còn chất đống. Với hai mặt hàng, người chủ có kinh nghiệm nhẩm được. Nhưng một nhà máy đồ gỗ xuất khẩu có hàng trăm mẫu hàng và hàng chục loại gỗ; một hãng giao hàng mỗi sáng phải chia hàng nghìn đơn cho vài trăm tài xế. Ở cỡ đó, nhẩm không còn đủ — và không ai biết phương án đang dùng có phải là tốt nhất không.
Những câu hỏi ấy có chung một khuôn: chọn vài con số sao cho một thước đo tốt nhất, mà vẫn tôn trọng các giới hạn. Môn học về cái khuôn đó là tối ưu hóa (optimization). Một mô hình học máy chỉnh hàng tỷ tham số cho sai số nhỏ nhất cũng đang giải đúng khuôn này.
Trước khi có tối ưu hóa
Tìm "cái tốt nhất" thì con người làm từ lâu. Tìm cực đại, cực tiểu bằng đạo hàm là ý tưởng có từ thế kỷ XVII; năm 1788, Lagrange thêm cách xử lý ràng buộc dạng đẳng thức, nay gọi là nhân tử Lagrange (Lagrange multiplier). Nhưng ràng buộc của đời thực thường là "không được vượt quá" — gỗ không quá 30 tấm, xe không chở quá hai tấn — và bài toán có hàng trăm biến. Giải tích cổ điển không có công cụ cho chuyện đó. Người ta lập kế hoạch theo kinh nghiệm, và không có cách nào biết còn cách tốt hơn hay không.
Tối ưu hóa thành một môn riêng qua từng bước:
- Hạ gradient (gradient descent) — năm 1847, Augustin-Louis Cauchy đề xuất cách giải hệ phương trình bằng cách lặp: từ điểm đang đứng, bước một bước theo hướng hàm số giảm nhanh nhất. Ý tưởng này phải chờ có máy tính mới thật sự có đất dụng võ.
- Kantorovich, 1939 — Leonid Kantorovich ở Leningrad được một tổ hợp gỗ dán nhờ tính cách chia việc cho các máy sao cho sản lượng cao nhất. Từ đó ông viết một cuốn sách mỏng về phương pháp toán học lập kế hoạch sản xuất — thực chất là quy hoạch tuyến tính. Năm 1975 ông nhận giải Nobel kinh tế cùng Tjalling Koopmans.
- Dantzig và phương pháp đơn hình, 1947 — độc lập với Kantorovich, George Dantzig, khi làm việc cho Không quân Mỹ, viết các bài toán lập kế hoạch thành quy hoạch tuyến tính (linear programming) và nghĩ ra phương pháp đơn hình (simplex method) để giải. Chữ "programming" khi đó nghĩa là lập kế hoạch, không phải viết chương trình. Mùa thu năm đó, bài toán của nhà kinh tế George Stigler — khẩu phần rẻ nhất mà đủ chất từ 77 loại thực phẩm — được giải bằng phương pháp mới: chín nhân viên với máy tính quay tay mất khoảng 120 ngày công. Stigler trước đó đã dò tay ra một khẩu phần 39,93 đô la một năm (giá năm 1939); lời giải tối ưu là 39,69 đô la. Dò tay đã rất sát — nhưng chỉ phương pháp mới chứng minh được không còn khẩu phần nào rẻ hơn.
- Máy tính và những nhánh mới — thập niên 1950–1980. Ralph Gomory (1958), rồi Ailsa Land và Alison Doig (1960) mở đường cho bài toán có biến nguyên. Năm 1979, Leonid Khachiyan chứng minh quy hoạch tuyến tính giải được trong thời gian đa thức; năm 1984, Narendra Karmarkar ở Bell Labs công bố một phương pháp điểm trong (interior-point method) vừa có bảo đảm lý thuyết vừa nhanh trong thực tế.
- Tối ưu cho dữ liệu lớn — thế kỷ XXI: tối ưu lồi thành công cụ thường ngày của kỹ sư, còn mạng nơ-ron sâu được huấn luyện bằng các biến thể của hạ gradient ngẫu nhiên (gốc từ Robbins và Monro, 1951) như Adam (2014).
Đặt cạnh nhau:
Không có tối ưu hóa | Có tối ưu hóa | |
|---|---|---|
Lập kế hoạch | Theo kinh nghiệm, thử vài phương án trên giấy | Viết thành mô hình, máy tìm phương án tốt nhất |
"Đã tốt nhất chưa?" | Không biết, chỉ biết "chưa thấy cách nào hơn" | Chứng minh được, hoặc biết còn cách tốt nhất bao xa |
Giá gỗ tăng, có thêm đơn hàng | Tính lại từ đầu | Sửa vài con số, chạy lại trong vài giây |
Thêm một giờ công đáng bao nhiêu | Đoán | Tính được |
Cách làm "không có" vẫn rất phổ biến hôm nay. Ở nhiều quán cà phê, phòng khám, lịch ca nhân viên vẫn được xếp bằng tay mỗi tuần trên một bảng tính: người quản lý mất cả buổi tối cân ai xin nghỉ, ai không làm được ca tối, giờ cao điểm phải đủ ba người. Lịch xếp xong thì chạy được, nhưng không ai biết có lịch nào công bằng hơn không — và một người báo ốm là xếp lại từ đầu. Trong khi đó, các hãng hàng không lớn xếp lịch tổ bay bằng bộ giải tối ưu đã nhiều thập niên.
Môn này trả lời câu hỏi gì
Mọi bài toán tối ưu có cùng một khuôn: chọn các biến quyết định (decision variables) để một hàm mục tiêu (objective function) lớn nhất hoặc nhỏ nhất, trong khi thỏa các ràng buộc (constraints). Môn Tối ưu hóa trả lời bốn câu hỏi quanh khuôn đó:
- Mô hình hóa: chọn biến gì, đo "tốt" bằng gì, giới hạn nào là thật?
- Khi nào bài toán dễ: khi nào tìm nhanh được phương án tốt nhất thật sự, và chứng minh được nó tốt nhất?
- Thuật toán: máy tìm phương án đó bằng cách nào — đơn hình, hạ gradient, Newton, điểm trong?
- Khi bài toán khó: làm sao có phương án đủ tốt, và biết nó cách tốt nhất bao xa?
Vì sao người học khoa học máy tính cần môn này? Vì huấn luyện mô hình học máy là giải một bài toán tối ưu, và môn này giải thích khi nào cách giải đó chạy tốt. Và vì nhận ra "bài này là quy hoạch tuyến tính" giúp bạn gọi một bộ giải có sẵn, thay vì mất hai tuần tự nghĩ thuật toán.
Năm ý tưởng cốt lõi
1. Mô hình hóa: biến, mục tiêu, ràng buộc
Xưởng mộc ở đầu bài, viết bằng toán:
Biến: x = số bàn, y = số ghế làm trong tuần
Mục tiêu: lời = 5x + 2y (trăm nghìn đồng) → lớn nhất
Ràng buộc: gỗ: 4x + y ≤ 30
công: 3x + 2y ≤ 26
x ≥ 0, y ≥ 0Phần lớn công sức — và phần lớn lỗi — nằm ở bước này, không phải ở bước giải. Bộ giải làm đúng điều bạn viết, không phải điều bạn muốn:
- Quên một ràng buộc thì bộ giải khai thác đúng chỗ hổng đó. Khẩu phần tối ưu của bài toán Stigler đủ chất và rẻ, nhưng chỉ gồm vài món không ai muốn ăn suốt một năm — vì mô hình không có ràng buộc nào về khẩu vị.
- Chọn sai mục tiêu thì kết quả đúng mà vô dụng. Ứng dụng giao hàng chỉ tối thiểu hóa thời gian chờ trung bình có thể để vài đơn ở xa chờ hai tiếng; muốn công bằng, phải thêm ràng buộc "không đơn nào chờ quá 60 phút".
- Giới hạn cứng hay mềm: hết gỗ là hết; còn "thợ không thích làm thứ Bảy" vi phạm được nếu chịu trả thêm tiền — nó là một khoản phạt trong hàm mục tiêu, không phải ràng buộc.
2. Quy hoạch tuyến tính: đáp án nằm ở một góc
Khi mục tiêu và mọi ràng buộc đều là tổng các biến nhân với hằng số, như ở xưởng mộc, ta có một quy hoạch tuyến tính. Trên mặt phẳng, mỗi ràng buộc cắt bỏ một nửa mặt phẳng; phần còn lại là một đa giác gọi là miền chấp nhận được (feasible region). Các đường "lời bằng nhau" 5x + 2y = hằng số song song với nhau; đẩy chúng ra xa dần tới lúc sắp rời đa giác, chỗ chạm cuối cùng luôn có một đỉnh (vertex). Vậy chỉ cần thử các đỉnh — cách mà học sinh lớp 10 ở Việt Nam gặp trong bài hệ bất phương trình bậc nhất hai ẩn.
Viết thành code: lấy giao điểm của từng cặp đường biên, giữ những điểm thỏa mọi ràng buộc, rồi tính lời ở từng điểm.
from fractions import Fraction # phân số chính xác, không sai số làm tròn
from itertools import combinations
def loi(x, y): # x bàn, y ghế; tiền lời tính bằng trăm nghìn đồng
return 5 * x + 2 * y
def cac_dinh(go, cong):
# mỗi ràng buộc viết dạng a*x + b*y <= c
rang_buoc = [(4, 1, go), # gỗ: bàn 4 tấm, ghế 1 tấm
(3, 2, cong), # công: bàn 3 giờ, ghế 2 giờ
(-1, 0, 0), # x >= 0
(0, -1, 0)] # y >= 0
dinh = []
for (a1, b1, c1), (a2, b2, c2) in combinations(rang_buoc, 2):
d = a1 * b2 - a2 * b1
if d == 0:
continue # hai đường biên song song
x = Fraction(c1 * b2 - c2 * b1, d) # giao điểm của hai đường biên
y = Fraction(a1 * c2 - a2 * c1, d)
if all(a * x + b * y <= c for a, b, c in rang_buoc):
dinh.append((x, y)) # thỏa mọi ràng buộc: một đỉnh
return dinh
for x, y in cac_dinh(30, 26):
print(f"đỉnh ({float(x)}, {float(y)}): lời {float(loi(x, y))}")
for go, cong in [(31, 26), (30, 27)]: # thêm 1 tấm gỗ, hoặc thêm 1 giờ công
x, y = max(cac_dinh(go, cong), key=lambda p: loi(*p))
print(f"{go} tấm gỗ, {cong} giờ công: tốt nhất ({float(x)}, {float(y)}), lời {float(loi(x, y))}")Kết quả:
đỉnh (6.8, 2.8): lời 39.6
đỉnh (7.5, 0.0): lời 37.5
đỉnh (0.0, 13.0): lời 26.0
đỉnh (0.0, 0.0): lời 0.0
31 tấm gỗ, 26 giờ công: tốt nhất (7.2, 2.2), lời 40.4
30 tấm gỗ, 27 giờ công: tốt nhất (6.6, 3.6), lời 40.2Phương án tốt nhất là 6,8 bàn và 2,8 ghế, lời 3,96 triệu, dùng hết cả gỗ lẫn giờ công. (Số lẻ thì sao? Để dành cho ý thứ năm.)
Hai dòng cuối trả lời một câu hỏi mà kinh nghiệm khó trả lời: thêm một tấm gỗ, lời tăng 80 nghìn; thêm một giờ công, lời tăng 60 nghìn — thuê thợ làm thêm giờ mà tốn dưới 60 nghìn một giờ là có lời. Đó là giá bóng (shadow price) của từng nguồn lực, nghiệm của một bài toán "song sinh" gọi là bài toán đối ngẫu (dual problem) — một trong những phần đẹp nhất của môn học.
Với hàng nghìn biến, số đỉnh lớn tới mức không máy nào thử hết. Phương pháp đơn hình xuất phát từ một đỉnh, đi dọc một cạnh sang đỉnh kề có lời cao hơn, và dừng khi không còn đỉnh kề nào tốt hơn; trong thực tế nó thường chỉ ghé rất ít đỉnh. Nhưng vì sao "không đỉnh kề nào tốt hơn" lại đủ để kết luận "tốt nhất trên toàn bộ"? Câu trả lời nằm ở ý tiếp theo.
3. Lồi: khi đáy gần nhất cũng là đáy thấp nhất
Thả một hòn bi vào cái chảo: thả ở đâu, nó cũng lăn về cùng một đáy. Thả nó trên vùng đồi nhiều thung lũng: nó lăn vào thung lũng gần nhất, không biết bên kia quả đồi có thung lũng sâu hơn.
Cái chảo là hình ảnh của hàm lồi (convex function): đoạn thẳng nối hai điểm bất kỳ trên đồ thị không bao giờ nằm dưới đồ thị. Tập lồi (convex set) là tập chứa trọn đoạn thẳng nối hai điểm bất kỳ của nó — đa giác của xưởng mộc là tập lồi, hình lưỡi liềm thì không. Định lý trung tâm của môn học: cực tiểu hóa một hàm lồi trên một tập lồi thì mọi cực tiểu địa phương (local minimum) đều là cực tiểu toàn cục (global minimum). Thấy mình đang ở đáy là biết chắc đó là đáy thấp nhất.
Thử chạy cùng một cách hạ dốc trên một hàm lồi và một hàm không lồi, từ bốn điểm xuất phát:
def ha_doc(dao_ham, x, buoc=0.01, so_buoc=2000):
for _ in range(so_buoc):
x -= buoc * dao_ham(x) # bước ngược chiều dốc
return x
def chao(x): # f(x) = (x - 2)² + 1: một cái chảo, chỉ có một đáy
return (x - 2) ** 2 + 1
def doc_chao(x):
return 2 * (x - 2)
def doi(x): # g(x) = x⁴ - 4x² + x: hai thung lũng, một sâu một nông
return x ** 4 - 4 * x ** 2 + x
def doc_doi(x):
return 4 * x ** 3 - 8 * x + 1
for x0 in (-2, 0, 0.5, 2):
a = ha_doc(doc_chao, x0)
b = ha_doc(doc_doi, x0)
print(f"xuất phát {x0:4}: chảo -> x = {a:.2f}, f = {chao(a):.2f} | đồi -> x = {b:.2f}, g = {doi(b):.2f}")xuất phát -2: chảo -> x = 2.00, f = 1.00 | đồi -> x = -1.47, g = -5.44
xuất phát 0: chảo -> x = 2.00, f = 1.00 | đồi -> x = -1.47, g = -5.44
xuất phát 0.5: chảo -> x = 2.00, f = 1.00 | đồi -> x = 1.35, g = -2.62
xuất phát 2: chảo -> x = 2.00, f = 1.00 | đồi -> x = 1.35, g = -2.62Trên cái chảo, mọi điểm xuất phát cho cùng một đáp án. Trên vùng đồi, xuất phát từ 0,5 thì dừng ở thung lũng nông (g = −2,62) mà không biết thung lũng sâu hơn (g = −5,44) nằm ngay bên kia. Ở cả hai đáy, độ dốc đều bằng 0 — thuật toán không phân biệt được.
Vì thế nhà toán học R. Tyrrell Rockafellar từng viết rằng đường phân thủy lớn của tối ưu hóa không nằm giữa tuyến tính và phi tuyến, mà giữa lồi và không lồi. Quy hoạch tuyến tính (nên đơn hình mới dừng đúng chỗ), bình phương tối thiểu, hồi quy logistic đều là bài toán lồi: giải được tin cậy, có khi với hàng triệu biến, và biết chắc khi nào đã xong. Hàm mất mát của mạng nơ-ron sâu thì không lồi — vậy mà hạ gradient vẫn thường tìm được nghiệm tốt, và vì sao lại thế vẫn là câu hỏi nghiên cứu. Kỹ năng quý nhất của môn học là nhận ra một bài toán là lồi, hoặc viết lại nó cho thành lồi.
4. Hạ gradient: bước dài bao nhiêu, và lấy đà
Bài Học máy đã giới thiệu hạ gradient và tốc độ học qua ví dụ đoán giá nhà. Ở đây ta nhìn một chuyện khác: hình dạng của thung lũng. Hàm f(x, y) = x² + 25y² là một khe núi dài và hẹp: theo hướng y vách dốc đứng, theo hướng x đáy gần như phẳng. Hình dạng này rất hay gặp, chẳng hạn khi một biến đo bằng mét còn biến kia bằng triệu đồng.
Bước phải đủ ngắn để không văng khỏi vách dốc theo hướng y; nhưng như thế thì theo hướng x, nơi cần đi xa nhất, lại chỉ nhích từng chút. Cách chữa cổ điển là đà (momentum), do Boris Polyak đề xuất năm 1964: mỗi bước giữ lại một phần bước trước, như hòn bi nặng lăn trong máng — lắc ngang thì triệt tiêu nhau, đi dọc máng thì cộng dồn.
def doc(x, y): # độ dốc của f(x, y) = x² + 25y²
return 2 * x, 50 * y
def so_buoc(buoc, da, toi_da=10_000):
x, y = 10.0, 1.0 # điểm xuất phát
vx, vy = 0.0, 0.0 # phần đà mang theo từ các bước trước
for n in range(1, toi_da + 1):
gx, gy = doc(x, y)
vx = da * vx - buoc * gx # đà = 0 thì đây là hạ gradient thường
vy = da * vy - buoc * gy
x, y = x + vx, y + vy
if x * x + 25 * y * y < 1e-6: # đã sát đáy (đáy ở (0, 0), f = 0)
return f"{n} bước"
return "không bao giờ tới"
for buoc, da in [(0.01, 0), (0.035, 0), (0.04, 0), (0.035, 0.6), (0.035, 0.9)]:
print(f"bước {buoc}, đà {da}: {so_buoc(buoc, da)}")bước 0.01, đà 0: 456 bước
bước 0.035, đà 0: 127 bước
bước 0.04, đà 0: không bao giờ tới
bước 0.035, đà 0.6: 35 bước
bước 0.035, đà 0.9: 148 bướcBước nhỏ thì an toàn mà chậm. Bước 0,04 thì theo hướng y mỗi lần nhảy từ vách này sang đúng điểm đối diện ở vách kia, mãi không xuống đáy. Thêm đà 0,6 với cùng độ dài bước, số bước giảm từ 127 xuống 35. Nhưng đà 0,9 lại chậm hơn cả không có đà: quá đà thì hòn bi lao qua đáy rồi phải quay lại. Đà cũng là một núm vặn phải chỉnh.
Tỷ số độ cong giữa hướng dốc nhất và hướng thoải nhất — ở đây là 25 — gọi là số điều kiện (condition number). Số bước của hạ gradient tăng theo số điều kiện; có đà thì chỉ tăng theo căn bậc hai của nó. Hai cách chữa khác: làm thung lũng tròn lại bằng chuẩn hóa dữ liệu về cùng thang đo, hoặc dùng cả độ cong như phương pháp Newton — với hàm này về đích sau một bước, nhưng mỗi bước rất đắt khi có hàng triệu biến. Các bộ tối ưu của thư viện học sâu như SGD có momentum hay Adam là những ý tưởng này, cộng thêm việc tính gradient trên một nhóm nhỏ dữ liệu thay vì cả tập — hạ gradient ngẫu nhiên (stochastic gradient descent). Phần đạo hàm đứng sau có trong bài Giải tích và Toán cho học máy.
5. Tối ưu nguyên: khi không thể làm 6,8 cái bàn
Xưởng mộc không bán được 0,8 cái bàn. Làm tròn thì sao?
def loi(x, y):
return 5 * x + 2 * y
def lam_duoc(x, y):
return x >= 0 and y >= 0 and 4 * x + y <= 30 and 3 * x + 2 * y <= 26
print(lam_duoc(7, 3), loi(6, 2)) # làm tròn lên: không làm được; bỏ phần lẻ: lời 34
phuong_an = [(x, y) for x in range(31) for y in range(31) if lam_duoc(x, y)]
tot = max(phuong_an, key=lambda p: loi(*p))
print(len(phuong_an), tot, loi(*tot)) # thử hết mọi phương án nguyênFalse 34
68 (7, 2) 39Làm tròn 6,8 và 2,8 thành 7 bàn, 3 ghế thì thiếu cả gỗ lẫn giờ công. Bỏ phần lẻ thành 6 bàn, 2 ghế thì chỉ lời 3,4 triệu. Thử hết 68 phương án nguyên làm được, tốt nhất là 7 bàn, 2 ghế, lời 3,9 triệu — không trùng cách làm tròn nào. Bài toán đòi biến là số nguyên như vậy gọi là quy hoạch nguyên (integer programming).
Có một mẹo đẹp. Bài toán cho phép số lẻ ở ý thứ hai — gọi là bài toán nới lỏng (relaxation) — cho lời 39,6. Không phương án nguyên nào vượt được con số đó, vì phương án nguyên nào cũng là một phương án của bài nới lỏng. Lời của phương án nguyên luôn tròn trăm nghìn, nên nhiều nhất là 39 — và (7, 2) đạt đúng 39. Ta chứng minh được nó tốt nhất mà không cần thử hết. Đó là hạt nhân của phương pháp nhánh và cận (branch and bound) của Land và Doig: giải bài nới lỏng để có mức trần; nghiệm còn lẻ thì chia hai nhánh (x ≤ 6 hoặc x ≥ 7) rồi làm tiếp; nhánh nào có trần thấp hơn phương án tốt nhất đã có thì bỏ.
Khó ở đâu? Nhiều quyết định thật chỉ là có hoặc không: mở kho ở đây không, xe này chạy tuyến kia không, ai trực ca đêm thứ Năm. Năm mươi quyết định có–không đã cho 2⁵⁰ — hơn một triệu tỷ — tổ hợp, và mỗi quyết định thêm vào làm số tổ hợp gấp đôi. Quy hoạch nguyên là bài toán NP-khó (NP-hard), họ hàng của những bài toán trong bài Lý thuyết tính toán và Thiết kế và phân tích thuật toán; xếp lịch thi, tức bài tô màu đồ thị trong bài Toán rời rạc, logic và chứng minh, cũng là một quy hoạch nguyên. Dù vậy, bộ giải hiện đại kết hợp nhánh và cận với mặt cắt (cutting planes) và heuristic vẫn giải được rất nhiều bài toán thực tế cỡ lớn; khi không giải xong, nó vẫn báo được khoảng cách tối ưu (optimality gap), kiểu "kém phương án tốt nhất không quá 2%". Biết mình có thể sai tới đâu — đó là khác biệt giữa tối ưu hóa và phỏng đoán.
Tối ưu hóa nằm ở đâu trong chồng tầng
Trong chồng tầng của bài Từ electron đến ứng dụng, tối ưu hóa không thuộc riêng tầng nào — nó là bộ đồ nghề mà tầng nào cũng mượn:
- Thiết kế chip: đặt hàng tỷ bóng bán dẫn và đi dây sao cho dây ngắn, chip nhỏ — xem bài Kiến trúc máy tính.
- Trình biên dịch: chọn biến nào được giữ trong số ít thanh ghi, xếp thứ tự lệnh cho bớt chờ.
- Đám mây: xếp máy ảo vào máy chủ sao cho tốn ít máy nhất.
- Mạng: chia lưu lượng cho không đường truyền nào nghẽn — nhiều bài toán luồng trên đồ thị là quy hoạch tuyến tính; xem bài Mạng máy tính.
- Cơ sở dữ liệu: bộ tối ưu truy vấn (query optimizer) chọn cách chạy rẻ nhất cho một câu SQL; xem bài Hệ cơ sở dữ liệu.
- Học máy: huấn luyện là cực tiểu hóa hàm mất mát.
Đưa lên
Một cách nói bài toán "chọn gì cho tốt nhất" bằng biến, mục tiêu và ràng buộc — và một bộ giải trả về phương án tốt nhất, hoặc phương án đủ tốt kèm khoảng cách tới tốt nhất, cùng giá trị của từng nguồn lực.
Giấu đi
Đơn hình, điểm trong, nhánh và cận, từng bước gradient. Người dùng chỉ viết mô hình; cái giá là khi mô hình viết sai, bộ giải vẫn trả lời rất tự tin.
Học trước và học sau
· 6 mônGiải tích
Calculus
Đạo hàm riêng, gradient, khai triển Taylor — ngôn ngữ của "dốc" và "độ cong". Nên học trước.
Đại số tuyến tính
Linear Algebra
Ràng buộc tuyến tính là ma trận, đỉnh của đa giác là nghiệm của hệ phương trình, độ cong là trị riêng. Nên học trước.
Toán cho học máy
Mathematics for Machine Learning
Gradient theo vector, nhân tử Lagrange và nhập môn tối ưu liên tục theo cách học máy dùng chúng — học trước hoặc song song.
Học máy
Machine Learning
Nơi tối ưu hóa được dùng nhiều nhất. Học trước để có ví dụ, hoặc sau để hiểu vì sao huấn luyện chạy được.
Học sâu
Deep Learning
Tối ưu không lồi ở quy mô hàng tỷ tham số: SGD, Adam, lịch tốc độ học, khởi tạo và chuẩn hóa.
Thiết kế và phân tích thuật toán
Design and Analysis of Algorithms
Luồng trên đồ thị, quy hoạch động, thuật toán xấp xỉ cho bài toán NP-khó — mặt rời rạc của tối ưu hóa.
Ứng dụng thật và nghề nghiệp
- Logistics và vận tải: chia đơn cho tài xế, xếp tuyến xe, chọn nơi đặt kho, lịch bay và lịch tổ bay.
- Sản xuất và năng lượng: kế hoạch sản xuất, pha trộn nguyên liệu (thức ăn chăn nuôi, xăng dầu), điều độ nhà máy điện theo nhu cầu từng giờ.
- Tài chính: chọn danh mục đầu tư cân bằng lợi nhuận và rủi ro, theo mô hình Markowitz (1952).
Các nghề liên quan: chuyên gia vận trù học (operations research) trong logistics, sản xuất, hàng không; nhà khoa học dữ liệu biến câu hỏi kinh doanh thành mô hình tối ưu; kỹ sư học máy; kỹ sư phát triển bộ giải và công cụ thiết kế chip; chuyên viên định lượng trong tài chính.
Học xong làm được gì, bắt đầu từ đâu
Sau môn này bạn có thể:
- viết một tình huống thật thành bài toán tối ưu — biến, mục tiêu, ràng buộc — và nhận ra nó thuộc loại nào: tuyến tính, lồi, nguyên hay không lồi;
- dùng bộ giải có sẵn (như
linprogcủa SciPy, CVXPY, OR-Tools) và đọc được kết quả, kể cả giá bóng; - tự cài hạ gradient có đà, phương pháp Newton, và chẩn đoán vì sao chúng chậm hay nhảy loạn;
- biết vì sao bài toán lồi giải được tin cậy, còn bài toán nguyên và không lồi thì khó.
Nên biết trước: giải tích nhiều biến (đạo hàm riêng, gradient), đại số tuyến tính, và lập trình Python. Chưa vững thì đi qua chủ đề Calculus và Linear Algebra trước.
Bắt đầu trên OpenER: trang chủ đề Optimization có hướng dẫn học từng bước, với sách chính Convex Optimization của Boyd và Vandenberghe. Các khóa đã chọn lọc cho môn này nằm ở chủ đề Tối ưu hóa của lộ trình Toán học — hai chủ đề dùng chung môn học. Khóa chính là Stanford EE364A Convex Optimization I của Stephen Boyd, có video từng buổi, đi theo cuốn sách trên. Muốn bản nhập môn bậc đại học thì có MIT 6.079 Introduction to Convex Optimization; muốn đi sâu quy hoạch tuyến tính và phương pháp đơn hình thì có MIT 6.251J Introduction to Mathematical Programming của Dimitris Bertsimas.
Lời khuyên cho môn này: viết mô hình ra giấy trước khi mở máy. Biến, mục tiêu, từng ràng buộc — không nói được bằng lời thì bộ giải cũng không cứu được. Rồi mỗi thuật toán chính, tự cài một bản nhỏ như các ví dụ ở trên và đối chiếu với bộ giải. Thấy tận mắt thuật toán vấp ở thung lũng nào, bạn sẽ tin bộ giải đúng mức — không hơn, không kém.
Tài liệu tham khảo
- Stephen Boyd, Lieven Vandenberghe — Convex Optimization, Cambridge University Press, 2004; đọc miễn phí trên trang của tác giả.
- Stanford EE364A Convex Optimization I (Stephen Boyd) — video bài giảng trên Stanford Engineering Everywhere.
- MIT 6.079 Introduction to Convex Optimization và MIT 6.251J Introduction to Mathematical Programming — tài liệu mở trên MIT OpenCourseWare.
- Dimitris Bertsimas, John N. Tsitsiklis — Introduction to Linear Optimization, Athena Scientific, 1997.
- Jorge Nocedal, Stephen J. Wright — Numerical Optimization, Springer, ấn bản thứ hai 2006.
- Ian Goodfellow, Yoshua Bengio, Aaron Courville — Deep Learning, MIT Press, 2016, chương 8 (tối ưu khi huấn luyện mạng sâu); đọc miễn phí tại deeplearningbook.org.
- George B. Dantzig — "The Diet Problem", Interfaces, 1990: Dantzig kể lại bài toán khẩu phần.