Bỏ qua tới nội dung chính

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

Tối ưu hóa lồi cho kỹ thuật

Nâng caokhoảng 75 giờ6 bước

Tập lồi và hàm lồi, bình phương tối thiểu, đối ngẫu, LP/QP/SDP và ứng dụng trong điều khiển, xử lý tín hiệu, truyền thông và học máy (Berkeley EECS 127, Stanford EE364A).

Bắt đầu học

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

  • Giải và diễn giải bài toán bình phương tối thiểu, kể cả có điều chỉnh, nhiều mục tiêu và có ràng buộc
  • Nhận biết tập lồi và hàm lồi, dùng các phép toán bảo toàn tính lồi để chứng minh một bài toán là lồi
  • Đưa bài toán kỹ thuật về các dạng chuẩn LP, QP, SOCP, SDP và giải bằng CVXPY
  • Lập bài toán đối ngẫu Lagrange, kiểm tra điều kiện Slater, viết và dùng điều kiện KKT
  • Diễn giải ý nghĩa của biến đối ngẫu, ví dụ giá biên trong điều độ hệ thống điện, nghiệm đổ nước trong phân bổ công suất
  • Áp dụng tối ưu lồi cho xấp xỉ, ước lượng, thiết kế bộ lọc FIR và điều khiển dự báo theo mô hình
  • Giải thích nguyên lý phương pháp Newton và phương pháp điểm trong, đọc được kết quả và cảnh báo của bộ giải

Nên học trước

Giới thiệu

Tối ưu hóa lồi cho kỹ thuật dạy một kỹ năng mà kỹ sư điện hiện đại dùng hằng ngày: phát biểu bài toán thiết kế thành một bài toán tối ưu, nhận ra nó là lồi, rồi giải bằng phần mềm có sẵn. Thiết kế bộ lọc số theo đặc tả, phân bổ công suất phát giữa các người dùng vô tuyến, điều độ kinh tế tổ máy phát điện, điều khiển dự báo theo mô hình (MPC), khôi phục tín hiệu từ ít mẫu (compressed sensing), huấn luyện mô hình học máy — đều là bài toán tối ưu lồi hoặc gần lồi. Chủ đề tương ứng Stanford EE364A, UC Berkeley EECS 127 (Optimization Models in Engineering) và MIT 6.079.

Vì sao "lồi" là ranh giới quan trọng

Với bài toán tối ưu lồi — hàm mục tiêu lồi, các ràng buộc bất đẳng thức cho bởi hàm lồi và ràng buộc đẳng thức affine — mọi cực tiểu địa phương đều là cực tiểu toàn cục, và có thuật toán giải hiệu quả, đáng tin cậy cho bài toán hàng nghìn tới hàng triệu biến. Vì vậy kỹ năng then chốt không phải là viết thuật toán, mà là mô hình hóa: nhận ra các tập lồi (nửa không gian, đa diện, ellipsoid, nón bậc hai, nón ma trận nửa xác định dương), các hàm lồi và các phép toán bảo toàn tính lồi, để đưa bài toán kỹ thuật về các dạng chuẩn LP, QP, SOCP, SDP.

Từ bình phương tối thiểu tới đối ngẫu

Lộ trình bắt đầu bằng bài toán lồi quen thuộc nhất: bình phương tối thiểu — khớp mô hình với dữ liệu, ước lượng tham số từ phép đo có nhiễu, bình phương tối thiểu có điều chỉnh (regularization) và có ràng buộc. Sách Introduction to Applied Linear Algebra (VMLS) của Boyd và Vandenberghe trình bày phần này bằng các ví dụ kỹ thuật cụ thể. Sau đó là lý thuyết: đối ngẫu Lagrange cho một cận dưới của giá trị tối ưu; với bài toán lồi thỏa điều kiện Slater (tồn tại một điểm khả thi chặt), đối ngẫu mạnh xảy ra và điều kiện KKT là điều kiện cần và đủ cho nghiệm tối ưu. Biến đối ngẫu có ý nghĩa vật lý: trong điều độ hệ thống điện, nó là giá điện biên tại từng nút; trong phân bổ công suất vô tuyến, nó dẫn tới nghiệm đổ nước (water-filling).

Ứng dụng và thuật toán

Phần ứng dụng đi qua xấp xỉ và khớp dữ liệu (chuẩn L1 cho nghiệm thưa và bền vững với điểm ngoại lai), ước lượng thống kê (hợp lý cực đại), các bài toán hình học (phân loại tuyến tính, đặt vị trí). Phần thuật toán giải thích cái gì chạy bên trong bộ giải: phương pháp gradient, phương pháp Newton, bài toán có ràng buộc đẳng thức và phương pháp điểm trong — đủ để bạn đọc được thông báo của bộ giải và biết khi nào cần đổi cách phát biểu.

Khác gì chủ đề Tối ưu hóa của lộ trình Toán học?

Lộ trình Toán học có chủ đề Tối ưu hóa thiên về lý thuyết và thuật toán (quy hoạch tuyến tính, điều kiện tối ưu, phương pháp số). Chủ đề này dùng cùng sách của Boyd nhưng tập trung vào mô hình hóa và ứng dụng trong ngành điện, với phần mềm CVXPY là công cụ chính.

Nên học thế nào

  • Nền tảng cần có: đại số tuyến tính vững (không gian con, trị riêng, ma trận nửa xác định dương, phân tích SVD), giải tích nhiều biến (gradient, ma trận Hesse) và lập trình Python.
  • Sách: Convex Optimization của Boyd và Vandenberghe (đọc miễn phí trên trang Stanford với sự cho phép của Cambridge University Press) là sách chính; VMLS (cũng miễn phí) cho phần bình phương tối thiểu. Bài giảng video của Stanford EE364A là tài liệu đồng hành tốt.
  • Học bằng mô hình: với mỗi khái niệm, viết một bài toán nhỏ bằng CVXPY, giải, rồi kiểm tra điều kiện KKT bằng tay. Ưu tiên bài toán lấy từ chính ngành điện: bộ lọc FIR, phân bổ công suất, điều độ kinh tế, MPC.

Học xong, bạn có thể mô hình hóa và giải phần lớn bài toán thiết kế tối ưu trong điều khiển, xử lý tín hiệu, truyền thông và hệ thống điện.

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 của Boyd và Vandenberghe (Cambridge University Press), đọc miễn phí trên trang Stanford của tác giả với sự cho phép của nhà xuất bản (bản quyền vẫn thuộc nhà xuất bản); sách của Stanford EE364A và nhiều khóa tối ưu ngành điện. Chọn làm sách chính vì cân bằng lý thuyết, mô hình hóa và thuật toán, với rất nhiều ví dụ kỹ thuật.

Nên đọc: Chương 2–5 (tập lồi, hàm lồi, bài toán lồi, đối ngẫu); Chương 6–8 (ứng dụng); Chương 9–11 (thuật toán)

Miễn phíCơ bảnTiếng Anh474 trang

Giáo trình đại số tuyến tính ứng dụng của Boyd và Vandenberghe (VMLS, Cambridge University Press), đọc miễn phí trên trang Stanford; có tài liệu đồng hành Python và Julia. Dùng cho bước đầu tiên về bình phương tối thiểu và để ôn đại số tuyến tính theo lối ứng dụng.

Nên đọc: Chương 12–13, 15–16 (bình phương tối thiểu, khớp dữ liệu, nhiều mục tiêu, có ràng buộc)

Các bước học

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

  1. Bước 1: Bình phương tối thiểu và mô hình tuyến tính

    khoảng 12 giờ

    Ôn vectơ, ma trận, chuẩn và phép nghịch đảo theo góc nhìn ứng dụng; học bình phương tối thiểu, khớp dữ liệu, bình phương tối thiểu nhiều mục tiêu (điều chỉnh) và có ràng buộc. Luyện tập bằng NumPy: ước lượng điện trở và điện áp hở mạch của một pin từ các cặp đo dòng – áp có nhiễu; khớp đa thức cho đường đặc tính cảm biến và so sánh nghiệm khi thêm điều chỉnh L2. Khóa Đại số tuyến tính và bài hồi quy trên trang giúp ôn lại nền tảng.

  2. Bước 2: Tập lồi và hàm lồi

    khoảng 14 giờ

    Học tập affine, tập lồi, nón, các ví dụ quan trọng (đa diện, ellipsoid, nón bậc hai, nón nửa xác định dương), phép toán bảo toàn tính lồi, siêu phẳng tách; hàm lồi, điều kiện bậc một và bậc hai, các phép toán bảo toàn tính lồi của hàm, hàm liên hợp. Luyện tập: chứng minh tính lồi của các hàm chuẩn, log-sum-exp, giá trị riêng lớn nhất của ma trận đối xứng; phân loại 15 hàm lồi, lõm hoặc không xác định và kiểm tra bằng quy tắc DCP của CVXPY.

  3. Bước 3: Bài toán tối ưu lồi và mô hình hóa bằng CVXPY

    khoảng 14 giờ

    Học dạng chuẩn của bài toán tối ưu, bài toán lồi, LP, QP, QCQP, SOCP, SDP, quy hoạch hình học, bài toán nhiều mục tiêu. Luyện tập bằng CVXPY: thiết kế bộ lọc FIR thông thấp 31 hệ số làm nhỏ nhất độ gợn dải chắn (dạng LP hoặc SOCP); bài toán điều độ kinh tế ba tổ máy có giới hạn công suất và chi phí bậc hai; so sánh kết quả với scipy.signal.remez cho bài toán bộ lọc.

  4. Bước 4: Đối ngẫu và điều kiện KKT

    khoảng 12 giờ

    Học hàm Lagrange, hàm đối ngẫu, bài toán đối ngẫu, đối ngẫu yếu và mạnh, điều kiện Slater, diễn giải hình học và diễn giải theo giá, điều kiện KKT, phân tích độ nhạy. Luyện tập: suy ra nghiệm đổ nước cho bài toán phân bổ công suất trên n kênh song song từ điều kiện KKT rồi kiểm tra bằng CVXPY; trong bài điều độ kinh tế ở bước trước, đọc biến đối ngẫu của ràng buộc cân bằng công suất và giải thích nó là giá điện biên.

  5. Bước 5: Ứng dụng: xấp xỉ, ước lượng và hình học

    khoảng 13 giờ

    Học xấp xỉ theo chuẩn và hàm phạt, điều chỉnh, xấp xỉ bền vững; ước lượng hợp lý cực đại, thiết kế thí nghiệm; các bài toán hình học như phân loại tuyến tính và đặt vị trí. Luyện tập: khôi phục một tín hiệu thưa từ ít phép đo tuyến tính bằng cực tiểu chuẩn L1; khử nhiễu một tín hiệu bậc thang bằng điều chỉnh biến phân toàn phần (total variation) và so với lọc thông thấp; phân loại tuyến tính hai lớp dữ liệu. Khóa Học máy trên trang cho góc nhìn học máy của cùng bài toán.

    • Đọc: Chương 6 Approximation and fitting; Chương 7 Statistical estimation; Chương 8 Geometric problems — Convex Optimization
  6. Bước 6: Thuật toán: Newton và điểm trong

    khoảng 10 giờ

    Học cực tiểu hóa không ràng buộc (gradient, Newton, tìm kiếm theo đường), cực tiểu hóa có ràng buộc đẳng thức, phương pháp hàm chắn và phương pháp điểm trong gốc – đối ngẫu. Luyện tập: tự cài phương pháp Newton có tìm kiếm quay lui cho bài toán phân tích tâm (analytic centering) và vẽ tốc độ hội tụ; so sánh số vòng lặp với phương pháp gradient. Kết thúc bằng một bài toán điều khiển dự báo theo mô hình (MPC) cho hệ tuyến tính bậc hai giải bằng CVXPY ở mỗi bước thời gian.

    • Đọc: Chương 9 Unconstrained minimization; Chương 10 Equality constrained minimization; Chương 11 Interior-point methods — Convex Optimization

Khái niệm chính

Bình phương tối thiểu
Tìm x làm nhỏ nhất bình phương chuẩn của Ax − b; khi A có các cột độc lập tuyến tính, nghiệm duy nhất thỏa phương trình chuẩn AᵀAx = Aᵀb.
Tập lồi
Tập chứa trọn đoạn thẳng nối hai điểm bất kỳ của nó; ví dụ nửa không gian, đa diện, hình cầu, ellipsoid, nón bậc hai, nón ma trận nửa xác định dương.
Hàm lồi
Hàm có miền xác định lồi và đồ thị nằm dưới dây cung nối hai điểm bất kỳ; với hàm khả vi hai lần, tương đương ma trận Hesse nửa xác định dương trên miền xác định (mở).
Bài toán tối ưu lồi
Cực tiểu hóa hàm lồi với ràng buộc bất đẳng thức cho bởi hàm lồi và ràng buộc đẳng thức affine; mọi cực tiểu địa phương là cực tiểu toàn cục.
LP, QP, SOCP, SDP
Các dạng chuẩn của bài toán lồi: quy hoạch tuyến tính, quy hoạch toàn phương lồi, quy hoạch nón bậc hai và quy hoạch nửa xác định; mỗi lớp sau bao lớp trước.
Hàm Lagrange và bài toán đối ngẫu
Hàm Lagrange cộng các ràng buộc có trọng số vào mục tiêu; hàm đối ngẫu là infimum của nó theo biến gốc và luôn cho cận dưới của giá trị tối ưu (đối ngẫu yếu).
Điều kiện Slater và đối ngẫu mạnh
Với bài toán lồi có một điểm khả thi làm mọi ràng buộc bất đẳng thức (không affine) thỏa chặt, giá trị tối ưu gốc và đối ngẫu bằng nhau.
Điều kiện KKT
Khả thi gốc, khả thi đối ngẫu, độ lệch bù và gradient hàm Lagrange bằng 0; với bài toán lồi khả vi có đối ngẫu mạnh, đây là điều kiện cần và đủ để tối ưu.
Độ lệch bù
Tại nghiệm tối ưu, tích của mỗi nhân tử Lagrange với ràng buộc tương ứng bằng 0: ràng buộc không chặt thì nhân tử bằng 0.
Điều chỉnh (regularization)
Thêm vào mục tiêu một số hạng phạt như chuẩn L2 (Tikhonov, ridge) để ổn định nghiệm hoặc chuẩn L1 để thu nghiệm thưa.
Phương pháp Newton
Thuật toán cực tiểu hóa dùng xấp xỉ bậc hai của hàm tại mỗi bước; hội tụ bậc hai khi đã ở gần nghiệm, với hàm lồi mạnh có ma trận Hesse liên tục Lipschitz.
Phương pháp điểm trong
Họ thuật toán giải bài toán có ràng buộc bằng cách thay ràng buộc bất đẳng thức bằng hàm chắn logarit và đi theo đường trung tâm; là lõi của hầu hết bộ giải lồi.
CVXPY và quy tắc DCP
Thư viện Python mô hình hóa bài toán lồi; quy tắc lập trình lồi có kỷ luật (DCP) kiểm tra tính lồi từ cách ghép các hàm cơ bản trước khi gọi bộ giải.

Học xong để làm gì

  • Thiết kế bộ lọc FIR và mảng anten theo đặc tả bằng quy hoạch tuyến tính, SOCP
  • Phân bổ công suất và tài nguyên trong thông tin vô tuyến (nghiệm đổ nước)
  • Điều độ kinh tế và dòng công suất tối ưu (dạng lồi hóa) trong hệ thống điện, tính giá điện biên
  • Điều khiển dự báo theo mô hình (MPC) cho động cơ, bộ biến đổi công suất, tòa nhà
  • Khôi phục tín hiệu thưa, compressed sensing và khử nhiễu ảnh
  • Huấn luyện các mô hình học máy lồi: hồi quy, máy vectơ hỗ trợ, hồi quy logistic

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

Chủ đề này khác gì Tối ưu hóa của lộ trình Toán học?

Cùng sách chính nhưng khác trọng tâm: lộ trình Toán học chú trọng lý thuyết và thuật toán; ở đây chú trọng mô hình hóa bài toán kỹ thuật điện và giải bằng phần mềm. Học một trong hai là đủ để bắt đầu, học cả hai thì bổ sung cho nhau.

Không lồi thì sao?

Nhiều bài toán thực tế không lồi, nhưng tối ưu lồi vẫn là công cụ chính: nới lỏng lồi cho cận dưới và nghiệm xấp xỉ, giải lặp một chuỗi bài toán lồi, hoặc dùng làm bước con trong thuật toán lớn hơn.

Có cần tự viết thuật toán giải không?

Không cho phần lớn ứng dụng: CVXPY cùng các bộ giải mã nguồn mở (ví dụ Clarabel, SCS, OSQP) giải tốt. Hiểu thuật toán giúp bạn chọn cách phát biểu, xử lý bài toán cỡ lớn và đọc được thông báo lỗi.

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

Có: cả Convex Optimization và VMLS đều đọc miễn phí trên trang Stanford 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 và bài tập bổ sung.

Vì sao đây là chủ đề nâng cao?

Vì cần đại số tuyến tính và giải tích nhiều biến vững, và tư duy mô hình hóa trừu tượng. Thời lượng 75 giờ là cho lượt học đầu; một học phần như EE364A thường cần nhiều hơn khi làm đủ bài tập.

Chọn nguồn tự học

Cần vững đại số tuyến tính; học song song lý thuyết với mô hình hóa bằng CVXPY, và giải các bài toán lấy từ chính ngành điện (thiết kế bộ lọc, phân bổ công suất).