Bỏ qua tới nội dung chính
Toán học

Hướng dẫn học chủ đề

Tối ưu hóa

Trung bìnhkhoảng 45 giờ6 bước

Quy hoạch tuyến tính và phương pháp đơn hình, đối ngẫu, tối ưu lồi, điều kiện KKT, phương pháp gradient và phương pháp Newton.

Bắt đầu học

Bạn sẽ học được gì

  • Mô hình hóa bài toán thực tế (sản xuất, vận tải, phân bổ, khớp dữ liệu) thành bài toán tối ưu với biến, hàm mục tiêu và ràng buộc rõ ràng
  • Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình và giải thích nghiệm theo hình học đa diện
  • Lập bài toán đối ngẫu, áp dụng định lý đối ngẫu và diễn giải biến đối ngẫu như giá bóng
  • Nhận biết tập lồi, hàm lồi và đưa bài toán về các dạng lồi chuẩn (LP, QP, SOCP, SDP)
  • Viết điều kiện KKT và dùng chúng để kiểm tra hoặc tìm nghiệm tối ưu của bài toán có ràng buộc
  • Cài đặt phương pháp gradient và Newton, phân tích tốc độ hội tụ và vai trò của số điều kiện
  • Dùng bộ giải (CVXPY, scipy.optimize) để giải bài toán cỡ vừa và kiểm tra kết quả

Nên học trước

Giới thiệu

Tối ưu hóa nghiên cứu cách chọn phương án tốt nhất theo một tiêu chí, dưới các ràng buộc: phân bổ ngân sách để lợi nhuận lớn nhất, xếp lịch sản xuất để chi phí nhỏ nhất, chọn tham số của mô hình học máy để sai số thấp nhất. Mọi bài toán như vậy đều có chung một khuôn: cực tiểu hóa f(x) với x thỏa các ràng buộc gᵢ(x) ≤ 0, hⱼ(x) = 0. Chủ đề này tương ứng với Berkeley Math 170, MIT 6.251J/15.093J và các học phần Quy hoạch tuyến tính, Tối ưu hóa, Các phương pháp tối ưu ở ĐHBK Hà Nội và ĐHKHTN.

Đường ranh giới quan trọng nhất: lồi và không lồi

Một thông điệp xuyên suốt của lý thuyết tối ưu hiện đại (được Boyd và Vandenberghe phổ biến): ranh giới giữa bài toán “dễ” và “khó” không phải là tuyến tính – phi tuyến, mà là lồi – không lồi. Với bài toán tối ưu lồi (hàm mục tiêu lồi, miền ràng buộc lồi), mọi cực tiểu địa phương đều là cực tiểu toàn cục, có lý thuyết đối ngẫu đẹp và có thuật toán giải hiệu quả cho bài toán hàng triệu biến. Vì vậy kỹ năng quan trọng nhất của môn học là nhận ra và đưa bài toán về dạng lồi.

Quy hoạch tuyến tính: điểm khởi đầu

Quy hoạch tuyến tính (hàm mục tiêu và ràng buộc đều tuyến tính) là lớp bài toán lồi đơn giản và được ứng dụng nhiều nhất: vận tải, pha trộn, lập kế hoạch sản xuất. Miền chấp nhận được là một đa diện; nếu bài toán có nghiệm tối ưu và đa diện có đỉnh thì tồn tại một nghiệm tối ưu tại một đỉnh — ý tưởng dẫn tới phương pháp đơn hình của Dantzig, đi từ đỉnh này sang đỉnh kề tốt hơn. Lý thuyết đối ngẫu gắn mỗi bài toán với một bài toán đối ngẫu: giá trị tối ưu của hai bài toán bằng nhau, và biến đối ngẫu có ý nghĩa kinh tế là giá bóng của tài nguyên. Phân tích độ nhạy cho biết nghiệm thay đổi thế nào khi dữ liệu thay đổi.

Tối ưu lồi và điều kiện KKT

Tiếp theo là ngôn ngữ của giải tích lồi: tập lồi, hàm lồi, các phép toán bảo toàn tính lồi, và các lớp bài toán chuẩn — quy hoạch toàn phương, quy hoạch nón bậc hai, quy hoạch nửa xác định, quy hoạch hình học. Đối ngẫu Lagrange tổng quát hóa đối ngẫu tuyến tính; khi có đối ngẫu mạnh (điều kiện Slater), nghiệm tối ưu được đặc trưng bởi điều kiện Karush–Kuhn–Tucker (KKT) — phiên bản có ràng buộc bất đẳng thức của phương pháp nhân tử Lagrange trong giải tích nhiều biến.

Thuật toán

Phần cuối học cách máy tính thực sự giải bài toán: phương pháp gradient (hạ gradient) với tìm kiếm theo tia, phương pháp Newton và phân tích hội tụ, phương pháp tựa Newton (BFGS), và phương pháp điểm trong dùng hàm chắn logarit — thuật toán đứng sau các bộ giải hiện đại. Đây cũng là nơi tối ưu gặp học máy: huấn luyện hồi quy tuyến tính, hồi quy logistic hay mạng nơ-ron đều là cực tiểu hóa một hàm mất mát bằng gradient.

Nên học thế nào

  • Nền tảng: giải tích nhiều biến (gradient, ma trận Hesse, khai triển Taylor, nhân tử Lagrange) và đại số tuyến tính (ma trận xác định dương, không gian con, hạng).
  • Sách: Convex Optimization của Boyd và Vandenberghe (đọc miễn phí trên trang tác giả với sự cho phép của Cambridge University Press) là sách chính; Introduction to Linear Optimization của Bertsimas và Tsitsiklis cho phần quy hoạch tuyến tính; Numerical Optimization của Nocedal và Wright là tài liệu chuẩn về thuật toán.
  • Thực hành với bộ giải: dùng CVXPY (Python) để mô hình hóa và giải bài toán lồi, scipy.optimize.linprog cho quy hoạch tuyến tính. Tự cài đặt gradient và Newton cho vài hàm nhỏ trước khi tin vào bộ giải.
  • Tài liệu MIT: MIT 6.251J Introduction to Mathematical Programming và 15.093J Optimization Methods (do Bertsimas giảng dạy), 6.079 Introduction to Convex Optimization trên MIT OpenCourseWare.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Convex Optimization

Stephen Boyd, Lieven Vandenberghe · 2004

Miễn phíTrung bìnhTiếng Anh730 trang

Vì sao chọn: Giáo trình tối ưu lồi chuẩn mực, đọc miễn phí trên trang tác giả với sự cho phép của Cambridge University Press (bản quyền thuộc nhà xuất bản), kèm slide và bài tập bổ sung. Chọn làm sách chính vì cung cấp khung lý thuyết – mô hình hóa – thuật toán thống nhất cho toàn bộ lộ trình; Chương 6–8 (xấp xỉ, ước lượng thống kê, bài toán hình học) là kho ứng dụng để đọc thêm.

Nên đọc: Chương 2–5 (tập lồi, hàm lồi, bài toán tối ưu lồi, đối ngẫu); Chương 9–11 (cực tiểu hóa không ràng buộc, có ràng buộc đẳng thức, phương pháp điểm trong)

Introduction to Linear Optimization

Dimitris Bertsimas, John N. Tsitsiklis · 1997

Có phíTrung bìnhTiếng Anh587 trang

Giáo trình quy hoạch tuyến tính của Bertsimas và Tsitsiklis (Bertsimas là người dạy MIT 6.251J và 15.093J trên MIT OpenCourseWare), trình bày hình học và đối ngẫu rất rõ ràng. Dùng cho ba bước đầu của lộ trình; sách trả phí.

Nên đọc: Chương 1–5 (nhập môn, hình học của quy hoạch tuyến tính, phương pháp đơn hình, đối ngẫu, phân tích độ nhạy)

Numerical Optimization

Jorge Nocedal, Stephen J. Wright · 2006 · Bản thứ 2

Có phíNâng caoTiếng Anh664 trang

Tài liệu tham khảo chuẩn về thuật toán tối ưu liên tục (Springer), đi sâu vào cài đặt thực tế: tìm kiếm theo tia, miền tin cậy, tựa Newton, quy hoạch toàn phương tuần tự. Đọc khi cần hiểu bộ giải hoạt động ra sao; sách trả phí.

Nên đọc: Chương 3 Line Search Methods; Chương 6 Quasi-Newton Methods; Chương 12 Theory of Constrained Optimization; Chương 13 Linear Programming: The Simplex Method

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Mô hình hóa và hình học của quy hoạch tuyến tính

    khoảng 7 giờ

    Học các dạng của bài toán quy hoạch tuyến tính, ví dụ mô hình hóa (sản xuất, pha trộn, vận tải), hàm lồi tuyến tính từng khúc, giải bằng đồ thị; đa diện, phương án cực biên và nghiệm cơ sở chấp nhận được. Mô hình hóa một bài toán lập kế hoạch sản xuất 3 sản phẩm – 2 tài nguyên, giải bằng scipy.optimize.linprog và vẽ miền chấp nhận được cho phiên bản 2 biến.

  2. Bước 2: Phương pháp đơn hình

    khoảng 7 giờ

    Học điều kiện tối ưu, phát triển và cài đặt phương pháp đơn hình (bảng đơn hình), chống xoay vòng bằng quy tắc Bland, tìm phương án cực biên ban đầu (hai pha, M lớn) và độ phức tạp. Giải bằng tay bảng đơn hình cho bài toán ở bước 1, rồi kiểm tra đường đi qua các đỉnh trên hình vẽ.

  3. Bước 3: Đối ngẫu và phân tích độ nhạy

    khoảng 6 giờ

    Học bài toán đối ngẫu, định lý đối ngẫu yếu và mạnh, độ lệch bù (complementary slackness), biến đối ngẫu như giá bóng, bổ đề Farkas, phương pháp đơn hình đối ngẫu và phân tích độ nhạy. Viết bài toán đối ngẫu của bài toán sản xuất, giải thích ý nghĩa kinh tế của nghiệm đối ngẫu và kiểm tra bằng giá trị đối ngẫu mà bộ giải trả về.

  4. Bước 4: Tập lồi, hàm lồi và bài toán tối ưu lồi

    khoảng 9 giờ

    Học tập affine và tập lồi, các phép toán bảo toàn tính lồi, siêu phẳng tách và siêu phẳng tựa; hàm lồi, điều kiện bậc nhất và bậc hai, hàm liên hợp; bài toán tối ưu lồi và các lớp chuẩn LP, QP, SOCP, SDP, quy hoạch hình học. Mô hình hóa bài toán hồi quy có chính quy hóa L1 (LASSO) và bài toán danh mục đầu tư Markowitz bằng CVXPY.

    • Đọc: Chương 2 Convex sets; Chương 3 Convex functions; Chương 4 Convex optimization problems — Convex Optimization
  5. Bước 5: Đối ngẫu Lagrange và điều kiện KKT

    khoảng 7 giờ

    Học hàm Lagrange và hàm đối ngẫu, đối ngẫu yếu – mạnh, điều kiện Slater, diễn giải hình học và điểm yên ngựa, điều kiện tối ưu KKT, phân tích độ nhạy. Viết điều kiện KKT cho bài toán chiếu một điểm lên hình cầu đơn vị và cho bài toán phân bổ công suất “đổ nước” (water-filling), giải tường minh.

  6. Bước 6: Thuật toán: gradient, Newton và điểm trong

    khoảng 9 giờ

    Học phương pháp gradient với tìm kiếm theo tia (backtracking), ảnh hưởng của số điều kiện, phương pháp Newton và phân tích hội tụ, tựa Newton (BFGS), cực tiểu hóa có ràng buộc đẳng thức, phương pháp chắn logarit và điểm trong. Cài đặt gradient và Newton cho hồi quy logistic trên một bộ dữ liệu nhỏ, so sánh số vòng lặp; đọc thêm tài liệu OpenER về hồi quy tuyến tính và logistic để thấy bài toán học máy chính là bài toán tối ưu.

    • Đọc: Chương 9 Unconstrained minimization; Chương 10 Equality constrained minimization; Chương 11 Interior-point methods — Convex Optimization
    • Đọc: Chương 3 Line Search Methods; Chương 6 Quasi-Newton Methods — Numerical Optimization

Khái niệm chính

Bài toán tối ưu dạng chuẩn
Cực tiểu hóa f₀(x) với ràng buộc bất đẳng thức fᵢ(x) ≤ 0 và đẳng thức hⱼ(x) = 0; mọi bài toán cực đại đều đưa được về dạng này.
Quy hoạch tuyến tính (Linear programming)
Bài toán có hàm mục tiêu và ràng buộc tuyến tính; miền chấp nhận được là đa diện; nếu có nghiệm tối ưu và đa diện có đỉnh thì tồn tại nghiệm tối ưu tại một đỉnh.
Phương pháp đơn hình
Thuật toán của Dantzig di chuyển giữa các phương án cực biên (đỉnh) kề nhau, mỗi bước cải thiện hàm mục tiêu cho tới khi đạt tối ưu.
Đối ngẫu và giá bóng
Mỗi bài toán có một bài toán đối ngẫu cho cận dưới; trong quy hoạch tuyến tính hai giá trị tối ưu bằng nhau và biến đối ngẫu đo giá trị biên của tài nguyên.
Tập lồi và hàm lồi
Tập lồi chứa cả đoạn thẳng nối hai điểm bất kỳ của nó; hàm lồi có đồ thị nằm dưới dây cung — với hàm khả vi hai lần, ma trận Hesse nửa xác định dương.
Bài toán tối ưu lồi
Cực tiểu hóa hàm lồi trên tập lồi; mọi cực tiểu địa phương là toàn cục và giải được hiệu quả.
Đối ngẫu Lagrange
Hàm Lagrange kết hợp mục tiêu với ràng buộc qua nhân tử; hàm đối ngẫu cho cận dưới của giá trị tối ưu (đối ngẫu yếu), bằng nhau khi có đối ngẫu mạnh.
Điều kiện Slater
Tồn tại một điểm thỏa chặt các ràng buộc bất đẳng thức; với bài toán lồi, điều này bảo đảm đối ngẫu mạnh.
Điều kiện KKT
Điều kiện tối ưu gồm: chấp nhận được, nhân tử không âm, độ lệch bù (complementary slackness) và gradient hàm Lagrange bằng 0; đủ cho bài toán lồi.
Phương pháp gradient (hạ gradient)
Lặp x ← x − t∇f(x) với bước t chọn bằng tìm kiếm theo tia; đơn giản, nhưng hội tụ chậm khi bài toán có số điều kiện lớn.
Phương pháp Newton
Dùng ma trận Hesse để tính bước; hội tụ bậc hai gần nghiệm và bất biến với phép biến đổi affine của biến.
Phương pháp điểm trong
Thay ràng buộc bất đẳng thức bằng hàm chắn logarit và đi theo quỹ đạo trung tâm tới nghiệm; nền của các bộ giải LP và lồi hiện đại.

Học xong để làm gì

  • Vận trù học và chuỗi cung ứng: lập kế hoạch sản xuất, bài toán vận tải, xếp lịch, định tuyến xe giao hàng
  • Học máy: huấn luyện hồi quy, SVM, mạng nơ-ron đều là cực tiểu hóa hàm mất mát; chính quy hóa L1/L2 là tối ưu lồi
  • Tài chính: tối ưu danh mục đầu tư Markowitz (quy hoạch toàn phương), quản trị rủi ro
  • Kỹ thuật điều khiển và robot: điều khiển dự báo theo mô hình (MPC) giải một bài toán tối ưu ở mỗi bước thời gian
  • Xử lý tín hiệu và ảnh: khử nhiễu, cảm biến nén (compressed sensing), thiết kế bộ lọc
  • Năng lượng và mạng lưới: phân bổ công suất phát điện tối ưu, luồng cực đại – lát cắt cực tiểu trên mạng

Câu hỏi thường gặp

Học quy hoạch tuyến tính trước hay tối ưu lồi trước?

Quy hoạch tuyến tính trước: nó cho trực giác hình học (đa diện, đỉnh) và lý thuyết đối ngẫu ở dạng đơn giản nhất; tối ưu lồi sau đó tổng quát hóa tự nhiên các ý tưởng này.

Sách Boyd có miễn phí không?

Có: Convex Optimization đọc miễn phí trên trang của tác giả với sự cho phép của Cambridge University Press (bản quyền vẫn thuộc nhà xuất bản), kèm slide bài giảng và bài tập bổ sung.

Tối ưu hóa khác gì với môn học máy?

Học máy đặt ra bài toán (chọn mô hình, hàm mất mát); tối ưu hóa cung cấp lý thuyết và thuật toán để giải nó. Hiểu tối ưu giúp chọn thuật toán huấn luyện, tốc độ học và nhận ra khi bài toán không lồi.

Có cần lập trình không?

Nên có: mô hình hóa bằng CVXPY và tự cài gradient, Newton giúp hiểu sâu hơn nhiều so với chỉ giải tay các ví dụ nhỏ.

Bài toán không lồi thì sao?

Lộ trình tập trung vào bài toán lồi; bài toán không lồi (quy hoạch nguyên, mạng nơ-ron sâu) thường được giải gần đúng bằng thuật toán địa phương, nới lỏng lồi hoặc nhánh cận — những kỹ thuật đều dựa trên nền tảng lồi.

Chọn nguồn tự học

Kết hợp lý thuyết (đối ngẫu, điều kiện tối ưu) với thực hành bằng công cụ như CVXPY hoặc SciPy; chọn nguồn có bài toán mô hình hóa thật.