Một số sách về optimization
Những ai phải đối đầu với những vấn đề cụ thể trong nghiên cứu về kỹ thuật (engineering) đều gặp phải những bài toán tối ưu hóa (optimization) phức tạp, hoặc là rất nhiều chiều (high dimension), hoặc liên quan đến tính không lồi (nonconvexity), hoặc liên quan đến tính phi tuyến tính (nonlinearity), hoặc có tính tổ hợp và rời rạc (combinatorial/discrete), hoặc một vài các yếu tố khó khăn trên gộp lại.
Những kiến thức ban đầu về numerical analysis học từ đại học và phổ thông thì rất hạn chế, không đủ để giải quyết những vấn đề thực tế. Mặt khác, lại có rất nhiều sách về optimization. Một học trò bắt đầu tìm hiểu về optimization thường bị hoa mắt về các loại thuật ngữ programming (như linear programming, nonlinear programming, quadratic programming, convex programming, semi-infinite programming, semidefinite programming, d.c. programming, integer programming v.v)
Phải bắt đầu từ đâu? Cái gì thì cần đọc và cái gì không? Đây là những câu hỏi thường gặp phải với những ai bắt đầu tìm hiểu sâu một chút về optimization. Trừ khi ngành của bạn nghiên cứu chuyên về optimization (như giáo sư Hoàng Tụy), thường thì chúng ta không thể đọc hết mọi thứ một lúc, mà phải có chiến thuật học tập (chủ yếu là tự học). Chỉ nên học những khái niệm căn bản trước, và sau đó tra khảo thêm các phương pháp optimization mới khi cần.
Như anh Hưng đã nói, quyển đầu tiên nên sử dụng là quyển miễn phí của Stephen Boyd and Lieven Vandenberghe.
Convex optimization, S. Boyd and L. Vandenberghe, Cambridge Press, 2002.
Quyển này viết rất rõ ràng dễ hiểu, nhiều minh họa hình học, và chú trọng đặc biệt những khái niệm căn bản về giải tích lồi, trong đó có khái niệm đối ngẫu trong bài toán convex optimization. Thế mạnh của quyển sách là sự tập trung vào những bài toán có thể quy ra thành convex problems. Rất nhiều ví dụ thú vị bắt nguồn từ thực tế hoặc các nghiên cứu các ngành như thống kê hay information theory, nằm trong diện này, và do đó có thể giải quyết hiệu quả bằng interior point method. Phương pháp interior point (của hai nhà toán học người Nga, Nemirovski và Nesterov), có thể nói một trong những nguyên nhân chính góp phần dẫn đến sự ứng dụng rộng rãi của convex optimization methods vào các vấn đề trong engineering.
Xin nói thêm Nemirovski là người có nhiều đóng góp to lớn đối với lớp thuật toán hiện đại về optimization. Ông này cũng có ảnh hưởng đến sự phát triển của thuật toán polynomial time đầu tiên (của Khachyan) cho linear programs vào những năm 70 bằng ellipsoid methods. Thuật toán của Khachyan không được hiệu quả so với thuật toán simplex (dù về mặt lý thuyết có thể là exponential-time) của Dantzig, nhưng gây chấn động trong giới computational complexity. Đến thập niên 80 thì Karmakar mới giới thiệu một thuật toán hiệu quả hơn cho linear programs. Ý tưởng của Karmakar được Nemirovski phát triển lên cho semidefinite programs (cái sau kỳ thực có thể coi như linear programs cho không gian là những ma trận dương tính), và các bài toán convex bậc cao hơn.
Quyển sách của Boyd và Vandenberghe chủ yếu chỉ tập trung vào những ý tưởng thuật toán mới kể trên. Tuy vậy hai tác giả bỏ qua nhiều phương pháp tối ưu cổ điển rất hữu dụng cho cả các bài toán convex và nonconvex. Do đó, theo tôi nên đọc quyển sách của Boyd song song với quyển sách của Bertsekas:
Nonlinear programming. Dimitri P. Bertsekas, 2nd Edition, 2004.
Bertsekas nói rất tỉ mỉ về các vấn đề cụ thể ta thường phải đối phải khi phải sử dụng một thuật toán tối ưu. Ví dụ, nếu dung gradient descent thì cần phải tính đến chuyện điều khiển update stepsize như thế nào, v.v. Có mô tả khá đầy đủ các phương pháp cổ điển khác như conjugate gradient, golden section, v.v.
Đi sâu vào các dạng bài toán convex đặc thù, như linear programming (chuyên sâu về linear constraints và linear cost functions), có một quyển sách rất tốt của hai người đồng hương và đồng nghiệp của Bertsekas:
Linear optimization. Dimitris Bertsimas and John N. Tsitsiklis., 1997.
Rất nhiều bài toán ta thường gặp hàng ngày và trong nghiên cứu có thể quy về dạng linear programs khá đơn giản (ví dụ như max flow, min cut).
Một dạng bài toán convex khác khá thú vị, liên quan đến max functions (hàm số có thể biểu diễn dưới dạng maximum của một số hàm khác). Bài toán đi tìm giá trị cực tiểu của max functions gọi là bài toán min-max, và hay gặp nhiều trong nhiều tình huống như game theory, decision theory và thống kê. Nếu là max của một số lượng vô hạn các hàm khác, thì bài toán minimax này được gọi là semi-infinite programs. Một quyển sách rất hay đi sâu về lĩnh vực này là:
Optimization: Algorithms and Consistent Approximations, by Elijah Polak, 1997.
Polak và Bertsikas có thể được xếp vào nhóm những người muôn năm cũ, so với lớp hậu sinh như Boyd. Những lớp già thường vẫn có những túi mẹo rất quý. Đọc những quyển sách của họ ta có thể học được nhiều cách nhìn vấn đề thú vị mà không thấy ở quyển sách của Boyd.
Rất nhiều vấn đề ta gặp không thể nào quy được về các dạng lồi cơ bản như kể trên. Tuy vậy những phương pháp optimization cho bài toán convex, và những hiểu biết về giải tích lồi rất cần thiết và hữu ích. Một mảng quan trọng là các vấn đề về combinatorial optimization, hay còn gọi là integer programming. Làm thế nào để sử dụng các phương pháp convex optimization (như linear programming, hay semidefinite programming) để thiết kế các thuật toán xấp xỉ cho các bài toán có tính chất combinatorial này? Đây đang là một hướng nghiên cứu nóng hổi trong thập niên 90 cho tới nay. Như anh Hưng đã nhắc đến, có nhiều đóng góp đáng kể của các tác giả như Lovasz, Schrijver, Jean Lasserre, Michel Goemans, v.v. Đây là một lĩnh vực cực kỳ rộng lớn, bao trùm nhiều ngành từ bên toán, theoretical CS, operations research, AI,… và tôi cũng không biết là bao. Theo tôi biết thì chưa có một quyển sách hệ thống nào về mảng này, đặc biệt nói về sự kết hợp giữa lý thuyết convex optimization cổ điển với combinatorial optimization, ngoài hệ thống lecture notes mà anh Hưng đã nhắc đến.
Một lĩnh vực rất rộng và tổng quát để tấn công các bài toán không convex gọi là global optimization. Chú ý là phần lớn các phương pháp optimization cho các bài toán convex đều dựa vào khái niệm gradient/subgradient, và do đó các update đều mang tính địa phương (local). Các phương pháp update không mang tính local có thể kể ra như các phép cắt, các phép decomposition, các phép branch and bound v.v. Giáo sư Hoàng Tụy chính là một trong những cha đẻ của lĩnh vực này. Một quyển sách rất hay của ông là:
Giá của quyển này trên amazon thật là kinh khủng. Có lẽ giáo sư Hoàng Tụy phải in thêm nhiều nữa. Quyển sách của Hoàng Tụy có phần đầu giới thiệu những khái niệm cơ bản về giải tích lồi (convex analysis) một cách rất súc tích, rõ ràng và bổ ích. Sau đó tác giả đi vào các khái niệm về d.c. programming (difference-of-convex programming), và các phương pháp global optimization kinh điển, bắt đầu từ nhát cắt Tụy nổi tiếng mà tác giả đã giới thiệu vào năm 1964. Xuyên suốt quyển sách là một tính chất căn bản của các hàm số liên tục (có lẽ tổng quát hơn thế): Tất cả các hàm này, kể cả khi không convex, đều có thể biểu diễn dưới dạng hiệu của hai hàm convex. Với các tập hợp không convex cũng có phát biểu tương tự. Vấn đề là làm sao ta có thể lợi dụng những tính chất về convexity để tìm điểm global optimum của các hàm d.c. Có thể nói có cả một trường phái về D.C. programming rất hung hậu bao gồm nhiều nhà toán học người Việt nam (ở viện Toán ở trong nước và nước ngoài). Đây là lĩnh vực khó, chưa có nhiều thuật toán hiệu quả, và hình như sự hiện diện còn hạn chế trong mainstream của ngành optimization.
Nếu nghề của bạn phải sử dụng nhiều đến optimization algorithms, thì không chóng thì chày cũng phải bỏ thời gian để tìm hiểu quy củ hơn các khái niệm cơ bản về giải tích lồi, như khái niệm đối ngẫu, convex calculus, v.v. Giải tích lồi tuy không khó, và có tính hình học trực quan cao, nhưng tôi vẫn luôn kinh ngạc khi thấy những khái niệm này xuất hiện “bất thình lình” ở mọi ngóc ngách một cách khá sâu sắc trong information theory, trong statistics, trong decision theory,… Hiểu biết sâu về giải tích lồi có thể giúp ta thiết kế và phân tích các thuật toán hiệu quả cho nhiều vấn đề tưởng như rất hóc búa.
Một quyển sách kinh điển về giải tích lồi là của Rockafellar:
Convex Analysis (Princeton Landmarks in mathematics and physics), R. Rockafellar, 1996.
Quyển sách này nên dung để tra khảo khi bạn cần tìm hiểu hoặc sử dụng một cách thấu đáo một khái niệm nào đó về giải tích lồi. Không nên dung để tự học vì sẽ bị ngập ngày vào những chi tiết chưa cần ngay. Để tự học thêm về convex analysis, một quyển sách rất tốt của hai tác giả người Pháp là:
Convex analysis and minimization algorithms, Jean-Baptiste Hiriart-Urruty and Claude Lemarechal.
Quyển này viết rất sư phạm. Được chia làm hai volumes, phần một dành cho người mới học, phần hai cho cả chuyên gia. Ngoài ra, các tác giả còn có một quyển sách tóm lược cho cả hai cuốn vào một volume. Tất cả đều rất bổ ích.
Chắc chắn còn nhiều quyển sách rất hay về optimization nữa mà tôi chưa biết. Những chuyên gia nghiên cứu về optimization (các nhà toán học ứng dụng) phải mất cả đời để suy nghĩ và sáng tạo các thuật toán mới. Còn với những người sử dụng optimization trong công việc của mình như phần lớn dân học KHMT, có lẽ cũng phải mất cả đời tìm hiểu và mày mò sử dụng, biến tấu chúng vào bài toán cụ thể thì mới thành thạo được.
Vài quyển sách về optimization tôi không muốn giới thiệu cho bất kỳ ai vì các lý do (chủ quan) khác nhau:
- Convex analysis and nonlinear optimization: Theory and Examples (by Jonathan Borwein, Adrian Lewis) : Quá ngắn gọn và cô đọng, có lẽ chỉ dành cho chuyên gia.
- Combinatorial optimization: algorithms and comnplexity (Christo Papadimitriou and Ken Steiglitz): Không tệ, nhưng hơi hời hợt.
