- Đây là một giáo trình trình bày có hệ thống các nguyên lý và thuật toán của tối ưu hóa toán học, bao quát cả bài toán liên tục lẫn rời rạc
- Giải thích theo từng bước nhiều cách tiếp cận, từ các kỹ thuật dựa trên đạo hàm đến các phương pháp ngẫu nhiên và tiến hóa
- Bao gồm các cấu trúc toán học cần cho ứng dụng thực tế như ràng buộc, đối ngẫu, lập trình tuyến tính và bậc hai
- Mỗi chương đều có tóm tắt và bài tập, giúp kết hợp học lý thuyết với thực hành
- Được phát hành theo giấy phép mở của MIT Press (CC BY-NC-ND)
Lời nói đầu và tổng quan
- Đây là một giáo trình về lý thuyết và triển khai các thuật toán giải bài toán tối ưu hóa, được xuất bản dưới dạng ấn bản thứ 2
- Tác giả là Mykel J. Kochenderfer và Tim A. Wheeler
- Do MIT Press xuất bản, công bố theo giấy phép Creative Commons phi thương mại, không cho phép phái sinh
- Sau phần lời nói đầu và lời cảm ơn, sách gồm 13 chương
- Mỗi chương được tổ chức theo cấu trúc học tập với khái niệm cốt lõi, tóm tắt và bài tập
Chương 1. Giới thiệu
- Giới thiệu lịch sử, quy trình, mô hình hóa toán học và các lĩnh vực ứng dụng của tối ưu hóa
- Giải thích cực tiểu (minima) và điều kiện tối ưu (optimality conditions)
- Bao gồm tổng quan, tóm tắt và bài tập của toàn chương
Chương 2. Đạo hàm và gradient
- Giải thích định nghĩa và cách tính đạo hàm một biến và nhiều biến
- Bao gồm các kỹ thuật vi phân số (numerical differentiation) và vi phân tự động (automatic differentiation)
- Đề cập đến gradient hồi quy và kỹ thuật xấp xỉ ngẫu nhiên (SPSA)
Chương 3. Bracketing
- Giải thích khái niệm đơn đỉnh (unimodality) và quy trình tìm khoảng ban đầu
- Bao gồm các thuật toán dựa trên khoảng như tìm kiếm Fibonacci, tìm kiếm chia vàng, tìm kiếm xấp xỉ bậc hai
- Có cả các phương pháp Shubert-Piyavskii và chia đôi (bisection)
Chương 4. Hạ dốc cục bộ (Local Descent)
- Giải thích các khái niệm lặp theo hướng giảm (descent direction iteration) và kích thước bước (step factor)
- Bao gồm các kỹ thuật line search và xấp xỉ line search
- Đề cập đến cách tiếp cận vùng tin cậy (trust region) và điều kiện dừng
Chương 5. Phương pháp bậc một (First-Order Methods)
- Bao gồm các kỹ thuật chính như gradient descent, conjugate gradient, momentum, Nesterov momentum
- Trình bày các thuật toán tối ưu hiện đại như AdaGrad, RMSProp, Adadelta, Adam, Hypergradient Descent
- Cung cấp đặc điểm và phần tóm tắt so sánh của từng phương pháp
Chương 6. Phương pháp bậc hai (Second-Order Methods)
- Giải thích phương pháp Newton (Newton’s Method) và phương pháp dây cung (Secant Method)
- Bao gồm thuật toán Levenberg-Marquardt và các phương pháp quasi-Newton
- Kết thúc bằng tóm tắt và bài tập
Chương 7. Phương pháp trực tiếp (Direct Methods)
- Giới thiệu coordinate search, Powell, Hooke-Jeeves, pattern search, phương pháp simplex Nelder-Mead
- Bao gồm kỹ thuật Divided Rectangles
- Tập trung vào các cách tiếp cận tối ưu hóa không dựa trên đạo hàm
Chương 8. Phương pháp ngẫu nhiên (Stochastic Methods)
- Trình bày các cách tiếp cận ngẫu nhiên như noise descent, mesh adaptive search, tối ưu hóa không đạo hàm
- Bao gồm simulated annealing, cross-entropy, natural evolution strategies, thích nghi ma trận hiệp phương sai (CMA)
- Nhấn mạnh hiệu quả của tìm kiếm dựa trên xác suất
Chương 9. Phương pháp dựa trên quần thể (Population Methods)
- Giải thích các kỹ thuật tìm kiếm theo quần thể như thuật toán di truyền, tiến hóa vi phân, tối ưu bầy đàn hạt (PSO)
- Bao gồm Firefly, Cuckoo Search, các phương pháp lai
- Giải quyết bài toán theo cấu trúc lặp quần thể (population iteration)
Chương 10. Ràng buộc (Constraints)
- Giải thích các khái niệm cơ bản của tối ưu hóa có ràng buộc (constrained optimization) và các loại ràng buộc
- Bao gồm phương pháp nhân tử Lagrange, biến slack, penalty và phương pháp điểm trong (interior point)
- Đề cập đến các phép biến đổi loại bỏ ràng buộc (transformations) và phương pháp nhân tử (method of multipliers)
Chương 11. Đối ngẫu (Duality)
- Giải thích bài toán đối ngẫu (dual problem) và các phương pháp primal-dual
- Bao gồm dual ascent và ADMM (Alternating Direction Method of Multipliers)
- Đề cập đến ứng dụng trong tối ưu hóa phân tán (distributed methods)
Chương 12. Lập trình tuyến tính (Linear Programming)
- Giải thích mô hình hóa bài toán, thuật toán Simplex, và chứng nhận đối ngẫu (dual certificates)
- Trình bày có hệ thống cấu trúc tối ưu hóa dưới các ràng buộc tuyến tính
Chương 13. Lập trình bậc hai (Quadratic Programming)
- Mô hình hóa các bài toán có hàm mục tiêu bậc hai và ràng buộc tuyến tính
- Đề cập đến bài toán bình phương tối thiểu (least squares) và ràng buộc bất đẳng thức tuyến tính
- Bao gồm least distance programming
Phụ lục và thông tin khác
- Cuối mỗi chương đều có tóm tắt và bài tập
- MIT Press phát hành bản năm 2025, cho phép chia sẻ phi thương mại (CC BY-NC-ND)
- Dàn trang bằng LaTeX, địa chỉ liên hệ: bugs@algorithmsbook.com
3 bình luận
https://algorithmsbook.com/optimization/#download
Có vẻ bây giờ liên kết đã thay đổi một chút, và bạn có thể xem hoặc tải xuống file PDF từ đây.
Cảm ơn!!
Ý kiến trên Hacker News
Thật vui khi thấy chủ đề tối ưu hóa (optimization) xuất hiện trên trang chủ HN
Tôi muốn giới thiệu trang trực quan hóa LP mà tôi tạo ra. Ở đó có thể quan sát trực quan cách các thuật toán Quy hoạch tuyến tính (Linear Programming) phản ứng khi ràng buộc hoặc hàm mục tiêu thay đổi
Nếu vào trang demo, đa giác sẽ được vẽ tự động, và bạn có thể kéo các đỉnh hoặc các đường ràng buộc để quan sát các vòng lặp (iteration) của thuật toán
Mức độ hoàn thiện vẫn chưa cao, nhưng nếu bạn thích học theo cách trực quan thì có lẽ sẽ thấy khá thú vị. Rất mong nhận được phản hồi
Tôi muốn chia sẻ một số tài liệu về metaheuristics
Ở Timefold, nơi tôi đang làm việc, chúng tôi dùng các thuật toán như Tabu Search và Simulated Annealing được giới thiệu trong những cuốn sách này để nhanh chóng tìm ra nghiệm tối ưu gần đúng
Sơ đồ thuật toán tìm kiếm cục bộ trong tài liệu Timefold cũng rất đáng tham khảo
Đây là một giáo trình tối ưu hóa 521 trang phát hành theo giấy phép CC và trông thực sự xuất sắc
Phần đầu nói về các thuật toán dựa trên gradient hiện đại dùng automatic differentiation, chẳng hạn như Adam; phần sau (chương 12) nói về tối ưu hóa tuyến tính như simplex
Có rất nhiều bài tập, và đây đúng là kiểu sách mà tôi đã chờ đợi từ lâu
Tôi nghĩ các thuật toán tối ưu hóa không chỉ đơn thuần là để giải bài toán, mà là một nỗ lực hướng tới một “bộ giải quyết vấn đề tổng quát”. Thay vì chương trình tự tìm ra đáp án trực tiếp, ta định nghĩa ‘đáp án sẽ có hình thức như thế nào’ rồi áp dụng tối ưu hóa lên đó
AI hiện nay cũng dựa trên cách tiếp cận này
Cuốn sách này của Kochenderfer và tác phẩm trước đó Decision Making Under Uncertainty(PDF) là một trong những sách kỹ thuật tôi yêu thích nhất
Cách giải thích rất rõ ràng, phần trực quan hóa rất xuất sắc, và sách đề cập đến nhiều cách tư duy tối ưu hóa ngoài gradient descent
Mã nguồn dùng Julia, nhưng không khó để chuyển sang ngôn ngữ khác. Không nên bị trói buộc vào ngôn ngữ, hãy tập trung vào khái niệm
Tối ưu hóa không chỉ là một kỹ thuật, mà chính là một cách tư duy để giải các bài toán khó
Đây là một trong số ít tài liệu hiếm hoi gói gọn CMA-ES, surrogate model, Gaussian process trong cùng một cuốn sách
Nếu hồi còn làm nghiên cứu bậc cử nhân đã có cuốn sách này thì hẳn sẽ rất hữu ích. Trước đây những nội dung liên quan thường bị phân tán giữa nhiều bài báo và sách khác nhau
Tôi đã đọc kỹ cuốn sách này nhiều lần khi học tiến sĩ. Tôi nghiên cứu mạng nơ-ron và giải tích số, và thấy sách có sự cân bằng rất tốt giữa chiều sâu và độ bao quát
Đến giờ tôi vẫn thường xuyên dùng nó như tài liệu tham khảo
Tôi ngạc nhiên khi thấy sách có cả các metaheuristic như Firefly, Cuckoo Search
Những thuật toán này không được giới học thuật tin tưởng, và cũng từng bị chỉ trích trong bài báo ITOR
Có một cộng đồng nhỏ chỉ nghiên cứu kiểu phương pháp này, họ trích dẫn lẫn nhau và tạo thành một bong bóng. Ở các hội nghị cũng thường gây tranh cãi
Chương về tối ưu hóa đa mục tiêu (multiobjective optimization) rất xuất sắc
Tôi muốn hỏi liệu có cuốn sách hay tài liệu nào khác tập trung vào chủ đề này không
Tôi tò mò liệu ai đó có thể so sánh cuốn này với Numerical Optimization của Nocedal & Wright không