Tối ưu hóa Lồi

📚 Tóm tắt nội dung

Một khóa học và sách giáo khoa cấp cao toàn diện về lý thuyết, ứng dụng và thuật toán số của tối ưu hóa lồi. Trọng tâm là nhận diện và xây dựng các bài toán tối ưu hóa lồi trong kỹ thuật và khoa học.

Nắm vững nền tảng toán học và các thuật toán thực tiễn của tối ưu hóa lồi cho kỹ thuật và khoa học dữ liệu.

Tác giả: Stephen Boyd, Lieven Vandenberghe

Lời cảm ơn: Được hỗ trợ một phần bởi NSF, và thông qua đóng góp từ sinh viên và đồng nghiệp tại Stanford và UCLA, bao gồm những lời ghi nhận đặc biệt đối với Arkadi Nemirovski và Kishan Baheti.

🎯 Mục tiêu học tập

1. Xác định các thành phần của một bài toán tối ưu hóa toán học, bao gồm hàm mục tiêu, các ràng buộc và biến số.
2. Phân biệt giữa các bài toán bình phương nhỏ nhất, quy hoạch tuyến tính và tối ưu hóa lồi dựa trên các tính chất toán học của chúng.
3. So sánh các chiến lược tối ưu hóa cục bộ và toàn cục, và đánh giá độ phức tạp tính toán liên quan đến từng phương pháp.
4. Định nghĩa và phân biệt các tập affine, tập lồi và các nón bằng ký hiệu tổ hợp chính xác.
5. Nhận diện và biểu diễn các tập lồi chuẩn như hình cầu Euclid, ellipsoid, đa diện và nón nửa xác định dương.
6. Áp dụng các phép toán bảo toàn tính lồi như giao, biến đổi affine và hàm perspective để kiểm chứng các tính chất tập hợp.
7. Nhận diện và áp dụng các phép toán bảo toàn tính lồi, bao gồm supremum điểm theo điểm của các hàm affine và các quy tắc kết hợp vector.
8. Chứng minh hàm liên hợp Lagrange của nhiều loại hàm khác nhau và áp dụng bất đẳng thức Young.
9. Đặc trưng hóa tính chất quasilồi bằng các tập mức và điều kiện khả vi bậc nhất/hai.
10. Biến đổi và chuyển đổi: Chuyển đổi các bài toán tối ưu thô thành dạng chuẩn lồi bằng cách sử dụng biến dư và loại bỏ ràng buộc.

🔹 Bài học 1: Giới thiệu về Tối ưu hóa Toán học

Tổng quan: Bài học này giới thiệu các khái niệm nền tảng của tối ưu hóa toán học, từ việc lập luận tổng quát đến các lớp cụ thể có thể giải được như bình phương nhỏ nhất và quy hoạch tuyến tính. Nó nhấn mạnh sự khác biệt then chốt giữa tối ưu hóa lồi và phi lồi, mô tả cách các phương pháp lồi hoạt động như "điểm nút" đáng tin cậy về hiệu quả, đồng thời cung cấp công cụ thiết yếu để xử lý các bài toán phi tuyến khó hơn.

Kết quả học tập:

• Định nghĩa các thành phần của một bài toán tối ưu hóa toán học, bao gồm hàm mục tiêu, các ràng buộc và biến số.
• Phân biệt giữa các bài toán bình phương nhỏ nhất, quy hoạch tuyến tính và tối ưu hóa lồi dựa trên các tính chất toán học của chúng.
• So sánh các chiến lược tối ưu hóa cục bộ và toàn cục, và đánh giá độ phức tạp tính toán liên quan đến mỗi phương pháp.

🔹 Bài học 2: Lý thuyết về Tập hợp Lồi

Tổng quan: Bài học này khám phá hình học nền tảng của tối ưu hóa, chuyển từ các cấu trúc tuyến tính cơ bản sang các tính chất phức tạp của tập hợp lồi và nón. Nó bao gồm các định nghĩa toán học về tập affine và tập lồi, xem xét các hình học cụ thể như đa diện và nón nửa xác định dương, đồng thời trình bày các phép toán và định lý giúp nhà nghiên cứu đặc trưng và thao tác với các tập hợp lồi trong không gian nhiều chiều.

Kết quả học tập:

• Định nghĩa và phân biệt các tập affine, tập lồi và nón bằng ký hiệu tổ hợp chính xác.
• Nhận diện và biểu diễn các tập lồi chuẩn như hình cầu Euclid, ellipsoid, đa diện và nón nửa xác định dương.
• Áp dụng các phép toán bảo toàn tính lồi như giao, biến đổi affine và hàm perspective để kiểm chứng các tính chất tập hợp.

🔹 Bài học 3: Hàm Lồi và Các Tính Chất

Tổng quan: Bài học này khám phá các phép toán nâng cao bảo toàn tính lồi, như supremum điểm theo điểm và các quy tắc kết hợp cụ thể, đồng thời giới thiệu hàm liên hợp Lagrange. Nó mở rộng khái niệm lồi sang các hàm quasilồi và log-lồi, đồng thời xem xét tính lồi theo các bất đẳng thức tổng quát và các tính chất ma trận cụ thể như phần bù Schur. Những khái niệm này tạo nên nền tảng toán học để nhận diện và xây dựng các bài toán tối ưu hóa phức tạp.

Kết quả học tập:

• Nhận diện và áp dụng các phép toán bảo toàn tính lồi, bao gồm supremum điểm theo điểm của các hàm affine và các quy tắc kết hợp vector.
• Chứng minh hàm liên hợp Lagrange của nhiều loại hàm khác nhau và áp dụng bất đẳng thức Young.
• Đặc trưng hóa tính quasilồi bằng các tập mức và điều kiện khả vi bậc nhất/hai.

🔹 Bài học 4: Thiết lập Bài toán Tối ưu Hóa Lồi

Tổng quan: Bài học này đề cập đến cấu trúc chính thức và quá trình biến đổi bài toán tối ưu hóa lồi, từ các dạng chuẩn và điều kiện tối ưu đến các lớp bài toán cụ thể như Quy hoạch tuyến tính (LP), Quy hoạch bậc hai (QP) và Quy hoạch nửa xác định (SDP). Sinh viên sẽ học cách nhận biết tối ưu toàn cục, sử dụng phương pháp chia đôi để giải quyết bài toán quasilồi, và áp dụng phương pháp chiếu để tối ưu hóa vectơ nhiều tiêu chí.

Kết quả học tập:

• Biến đổi và chuyển đổi: Chuyển đổi các bài toán tối ưu thô thành dạng chuẩn lồi bằng cách sử dụng biến dư và loại bỏ ràng buộc.
• Phân tích tối ưu: Áp dụng tiêu chuẩn tối ưu dựa trên gradient để xác định một điểm có phải là tối ưu toàn cục hay không.
• Phân loại và giải: Phân biệt giữa LP, QP, SOCP, GP và SDP, và áp dụng các phương pháp chuyên biệt như Phương pháp Chia đôi cho các hàm quasilồi.

🔹 Bài học 5: Đối ngẫu Lagrange và Điều kiện KKT

Tổng quan: Bài học này khám phá lý thuyết nền tảng của đối ngẫu Lagrange, từ định nghĩa hàm đối ngẫu Lagrange đến việc thiết lập bài toán đối ngẫu. Nó đề cập đến khoảng trống quan trọng giữa các giá trị tối ưu nguyên và đối ngẫu, các cách diễn giải hình học và trò chơi lý thuyết cho mối quan hệ này, cùng với các điều kiện Karush-Kuhn-Tucker (KKT) đặc trưng cho nghiệm tối ưu. Cuối cùng, bài học mở rộng các khái niệm này sang phân tích độ nhạy và giá bóng.

Kết quả học tập:

• Chứng minh hàm đối ngẫu Lagrange và thiết lập bài toán đối ngẫu cho nhiều bài toán tối ưu khác nhau.
• Đánh giá mối quan hệ giữa bài toán nguyên và bài toán đối ngẫu bằng cách sử dụng đối ngẫu yếu/mạnh và điều kiện ràng buộc Slater.
• Áp dụng điều kiện tối ưu KKT để giải và xác minh các nghiệm tối ưu cho cả bài toán lồi và phi lồi.

🔹 Bài học 6: Xấp xỉ, Phù hợp và Régular hóa

Tổng quan: Bài học này khám phá nền tảng toán học và ứng dụng thực tiễn của việc xấp xỉ nghiệm cho hệ phương trình tuyến tính và phù hợp hàm số với dữ liệu. Nó bao gồm xấp xỉ dựa trên chuẩn, bao gồm các hàm phạt và kỹ thuật régular hóa để quản lý điểm ngoại lệ và độ thưa, cũng như các kỹ thuật tối ưu bền vững nhằm xử lý sự không chắc chắn trong dữ liệu. Ngoài ra, nó chi tiết hóa việc phù hợp hàm số dưới các ràng buộc cụ thể như tính lồi và tính đơn điệu.

Kết quả học tập:

• Thiết lập và giải các bài toán xấp xỉ chuẩn, và giải thích sự khác biệt hình học và thống kê giữa các phương pháp bình phương nhỏ nhất, Chebyshev và L1.
• Thiết kế và triển khai các mô hình xấp xỉ đã được régular hóa để đạt được sự cân bằng giữa sai số dư, độ lớn nghiệm và độ thưa.
• Xây dựng các khung xấp xỉ bền vững để tính đến sự không chắc chắn trong ma trận dữ liệu.

🔹 Bài học 7: Ước lượng và Suy luận Thống kê

Tổng quan: Bài học này khám phá sự giao thoa giữa suy luận thống kê và tối ưu hóa lồi. Nó tập trung vào việc thiết lập các bài toán ước lượng — bao gồm cực đại hóa khả năng, ước lượng phân phối phi tham số và thiết kế bộ phát hiện tối ưu — dưới dạng các chương trình lồi. Sinh viên sẽ học cách dùng tối ưu hóa để tìm tham số và thiết kế các thí nghiệm mang tính thông tin.

Kết quả học tập:

• Thiết lập và giải các bài toán Ước lượng cực đại khả năng (MLE) và Hồi quy Logistic như các bài toán tối ưu hóa lồi.
• Thiết kế bộ phát hiện tối ưu bằng Quy hoạch tuyến tính (LP) và giải thích các đặc tính nhận diện người dùng (ROC).
• Áp dụng các kỹ thuật ước lượng phi tham số, bao gồm Cực đại entropy và tối thiểu hóa khoảng cách Kullback-Leibler.

🔹 Bài học 8: Các Vấn đề Hình học và Phân loại

Tổng quan: Bài học này khám phá ứng dụng của tối ưu hóa lồi vào các vấn đề hình học, bao gồm phép chiếu điểm lên tập hợp, tính khoảng cách giữa các tập hợp, và đặc trưng các tâm của tập hợp. Nó còn mở rộng các nguyên lý hình học này sang các nhiệm vụ thực tế như phân loại tuyến tính và phi tuyến, đặt vị trí cơ sở tối ưu, và bố trí mặt sàn bằng quy hoạch hình học.

Kết quả học tập:

• Thiết lập và giải các bài toán chiếu và khoảng cách giữa các tập hợp lồi bằng điều kiện KKT và biểu diễn đối ngẫu.
• Xấp xỉ các tập hợp lồi phức tạp bằng các ellipsoid thể tích cực đại và xác định các yếu tố hiệu suất của chúng.
• Tính toán các tâm tập hợp khác nhau và áp dụng chúng vào phân loại và phân biệt bền vững.

🔹 Bài học 9: Các Thuật toán Tối thiểu hóa Không Có Ràng Buộc

Tổng quan: Bài học này đề cập đến các nền tảng lý thuyết và triển khai thuật toán cho tối thiểu hóa không có ràng buộc đối với hàm lồi. Nó chi tiết hóa các phương pháp giảm dần từ Gradient Descent bậc nhất đến Newton bậc hai. Một phần lớn được dành cho phân tích hội tụ, tập trung vào tính lồi mạnh và lý thuyết bất biến affine về tự đồng nhất.

Kết quả học tập:

• Định nghĩa tính lồi mạnh và tận dụng các hệ quả của nó để đưa ra giới hạn trên cho sai số và khoảng cách đến điểm tối ưu.
• So sánh và đối chiếu Gradient Descent với Steepest Descent dưới các chuẩn Euclid, bậc hai và L1.
• Tính bước Newton và giảm Newton, giải thích vì sao phương pháp Newton là bất biến affine.

🔹 Bài học 10: Tối thiểu hóa Có Ràng Buộc Đẳng Thức

Tổng quan: Bài học này khám phá các phương pháp giải bài toán tối ưu hóa lồi với ràng buộc đẳng thức tuyến tính. Nó tập trung vào việc suy diễn và triển khai bước Newton, so sánh các phương pháp bắt đầu khả thi và không khả thi, và diễn giải các bước này trong khuôn khổ song song nguyên – đối ngẫu. Đặc biệt nhấn mạnh vào triển khai số hiệu quả thông qua loại bỏ khối hệ phương trình KKT.

Kết quả học tập:

• Tính toán và diễn giải bước Newton và giảm Newton cho các bài toán có ràng buộc đẳng thức.
• Chứng minh tính tương đương giữa phương pháp Newton với ràng buộc đẳng thức và việc loại bỏ các ràng buộc đó.
• Triển khai phương pháp Newton bắt đầu không khả thi và giải thích thuộc tính giảm dư nguyên – đối ngẫu của nó.

🔹 Bài học 11: Phương Pháp Điểm Nội

Tổng quan: Bài học này đề cập đến các phương pháp điểm nội, giải các bài toán tối ưu hóa lồi với ràng buộc bất đẳng thức bằng cách áp dụng phương pháp Newton cho một dãy bài toán có ràng buộc đẳng thức. Nòng cốt là các hàm tường minh logarithmic barrier, theo dõi một đường trung tâm hướng tới nghiệm tối ưu, và tận dụng khung nguyên – đối ngẫu để tăng hiệu quả và độ bền.

Kết quả học tập:

• Định nghĩa và xây dựng các hàm barrier logarithmic, đặc trưng hóa đường trung tâm và các điểm đối ngẫu liên quan.
• Triển khai phương pháp barrier, bao gồm sự đánh đổi giữa các bước trung tâm và các vòng lặp ngoài.
• Thiết lập và giải các bài toán khả thi Phases I để tìm các điểm khởi đầu nghiêm ngặt khả thi.