Bài giảng Tối ưu hóa - Chương 1: Giới thiệu về tối ưu hóa - Hoàng Nam Dũng

Giới thiệu về tối ưu hóa Hoàng Nam Dũng Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Toán học để làm gì? 1 Bill Gates nói về toán học America’s young people must come to see science and math degrees as key to opportunity. If we fail at this, we won’t be able to compete in the global economy. — Bill Gates, 2007 Speaking to LinkedIn Executive Editor Daniel Roth, Mr Gates said: “I do think of basic knowledge of the sciences, math skills, economics — a lot of careers in the future will be very demanding on those things.” — Bill Gates, 2016 2 Toán học - kính hiển vi của vạn vật Mathematics Is Biology’s Next Microscope, Only Better; Biology Is Mathematics’ Next Physics, Only Bettera ahttps://doi.org/10.1371/journal.pbio.0020439 — Joel E. Cohen, 2004 3 Mô hình hóa Mô hình hóa toán học là gì? Modeling is a process that uses math to represent, analyze, make predictions, or otherwise provide insight into real-world phenomena.1 1SIAM: What is math modeling? 4 Thales of Miletus (624 BC - 546 BC) 5 Đường đi ngắn nhất Đồ thị có hướng D gồm có I Tập hợp V các đỉnh. I Tập hợp các cạnh có hướng A, là tập chứa các cặp có thứ tự của các đỉnh thuộc V . I Mỗi cạnh có một trọng số không âm. Hàm trọng số c : A→ R+. 6 Đường đi ngắn nhất Đồ thị có hướng D gồm có I Tập hợp V các đỉnh. I Tập hợp các cạnh có hướng A, là tập chứa các cặp có thứ tự của các đỉnh thuộc V . I Mỗi cạnh có một trọng số không âm. Hàm trọng số c : A→ R+. 6 Dự báo thời tiết2 2 NWP_LecturesFall2013.pdf 7 Dự báo thời tiết Sử dụng các phương trình toán học để mô tả trạng thái vật lí của khí quyển và dự đoán về sự biến đổi của nó. Siêu máy tính sẽ được sử dụng để giải các phương trình này. 8 Tối ưu hóa trong tự nhiên Bài toán tối ưu minimize x f (x) subject to x ∈ X . I Biến x = (x1, x2, . . . , xn) là gì? I Hàm mục tiêu f là gì? I Điều kiện x ∈ X (tập hợp nghiệm chấp nhận được X ) là gì? x , f , X của các bài toán thực tế đến từ quá trình mô hình hóa (modeling). 9 Bài toán tối ưu minimize x f (x) subject to x ∈ X . I Biến x = (x1, x2, . . . , xn) là gì? I Hàm mục tiêu f là gì? I Điều kiện x ∈ X (tập hợp nghiệm chấp nhận được X ) là gì? x , f , X của các bài toán thực tế đến từ quá trình mô hình hóa (modeling). 9 Bài toán tối ưu minimize x f (x) subject to x ∈ X . I Biến x = (x1, x2, . . . , xn) là gì? I Hàm mục tiêu f là gì? I Điều kiện x ∈ X (tập hợp nghiệm chấp nhận được X ) là gì? x , f , X của các bài toán thực tế đến từ quá trình mô hình hóa (modeling). 9 Tự nhiên "luôn" tối ưu Whether by design or accident, nature optimizes. The motions of stars, planets, and rays of light through the universe are governed by an optimization principle: the principle of least action. The shapes and functions of proteins –the building blocks of living organisms – are determined by a minimum-energy configuration of the molecule. Balls come to rest in valleys rather than on hillsides, because they seek a state of optimal potential energy. a awid.wisc.edu/the-natural-order-and-divine-law-of-optimization/ — M. Ferris and S. Wright, 2015 10 Ánh sáng - kẻ tiết kiệm thời gian Hiện tượng phản xạ: Theo nguyên lý thời gian tối thiểu của Fermat ta có θ1 = θ2. 11 Ong - kiến trúc sư đại tài Cấu trúc tổ ong cho phép sử dụng ít nguyên liệu nhất, nhẹ nhất, đồng thời có tỉ lệ sức bền vật liệu/trọng lượng cao.3 3https://en.wikipedia.org/wiki/Honeycomb_structure 12 Ong - kiến trúc sư đại tài Cấu trúc tổ ong cho phép sử dụng ít nguyên liệu nhất, nhẹ nhất, đồng thời có tỉ lệ sức bền vật liệu/trọng lượng cao.3 3https://en.wikipedia.org/wiki/Honeycomb_structure 12 Tại sao bong bóng xà phòng có hình cầu? Lực căng sẽ khiến bong bóng chuyển dần sang hình dạng có chu vi nhỏ nhất (để cùng chứa một lượng không khí bị giữ bên trong) và đó chính là hình cầu. 13 Tại sao bong bóng xà phòng có hình cầu? Lực căng sẽ khiến bong bóng chuyển dần sang hình dạng có chu vi nhỏ nhất (để cùng chứa một lượng không khí bị giữ bên trong) và đó chính là hình cầu. 13 Quả bóng cũng biết tối ưu 14 Một vài ứng dụng của toán học Ứng dụng của toán học4 4https://mathigon.org/applications 15 Ứng dụng của toán học4 4https://mathigon.org/applications 15 Automatic guided vehicle (AGV)5 5https://www.youtube.com/watch?v=zm_rlLyelQo 16 Amazon robot6 6https://www.youtube.com/watch?v=3eQAFVetNGI 17 Môn học tối ưu hóa nâng cao Môn học tối hóa nâng cao Trang chủ: I Thông tin môn học I Slides bài giảng I Bài tập Điểm thành phần I Bài tập về nhà, bài tập lập trình: 20%. I Giữa kì 20% I Cuối kì 60% 18 Tài liệu tham khảo Download sách: Sách tham khảo I J. Nocedal and S. Wright, Numerical Optimization, Springer. I S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, I R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press Slide bài giảng I Optimization Methods for Large-Scale Systems, UCLA: I Convex Optimization, CMU: 19