Tài liệu Phương pháp số cho bài toán trường trung bình

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN PHƯỚC BẢO DUY PHƯƠNG PHÁP SỐ CHO BÀI TOÁN TRƯỜNG TRUNG BÌNH Chuyên ngành: Toán ứng dụng Mã số: 60460112 LUẬN VĂN THẠC SĨ Thành phố Hồ Chí Minh, tháng 1 năm 2018 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA - ĐHQG TP. HCM Cán bộ hướng dẫn khoa học: TS. Nguyễn Tiến Dũng Cán bộ chấm nhận xét 1: TS. Nguyễn Bá Thi Cán bộ chấm nhận xét 2: PGS.TS. Nguyễn Văn Kính Luận văn thạc sĩ được bảo vệ tại Trường Đại học Bách Khoa, ĐHQG Tp. HCM ngày 11 tháng 01 năm 2018. Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: 1. Chủ tịch: PGS.TS. Nguyễn Đình Huy 2. Thư ký: TS. Huỳnh Thị Hồng Diễm 3. Phản biện 1: TS. Nguyễn Bá Thi 4. Phản biện 2: PGS.TS. Nguyễn Văn Kính 5. Ủy viên: TS. Lê Xuân Đại Xác nhận của Chủ tịch Hội đồng đánh giá luận văn và Trưởng khoa quản lý chuyên ngành sau khi luận văn đã được chỉnh sửa (nếu có). CHỦ TỊCH HỘI ĐỒNG TRƯỞNG KHOA KHOA HỌC ỨNG DỤNG PGS.TS. NGUYỄN ĐÌNH HUY PGS.TS HUỲNH QUANG LINH ii ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: Nguyễn Phước Bảo Duy Ngày, tháng, năm sinh: 28/11/1987 Chuyên ngành: Toán Ứng Dụng MSHV: 7140269 Nơi sinh: Đồng Nai Mã số: 60460112 I. TÊN ĐỀ TÀI: PHƯƠNG PHÁP SỐ CHO BÀI TOÁN TRƯỜNG TRUNG BÌNH II. NHIỆM VỤ VÀ NỘI DUNG: i. Thiết lập các phương trình Hamilton-Jacobi-Bellman và Fokker-Planck của mô hình trường trung bình. ii. Trình bày phương pháp sai phân hữu hạn để giải số hệ phương trình đạo hàm riêng của mô hình trường trung bình. iii. Mô phỏng một trường hợp cụ thể của mô hình trường trung bình và nhận xét kết quả. III. NGÀY GIAO NHIỆM VỤ: 10/07/2017 IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 03/12/2017 V. CÁN BỘ HƯỚNG DẪN: TS. Nguyễn Tiến Dũng Tp. HCM, ngày .... tháng .... năm 2018 CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN ĐÀO TẠO TS. NGUYỄN TIẾN DŨNG PGS.TS. NGUYỄN ĐÌNH HUY TRƯỞNG KHOA KHOA HỌC ỨNG DỤNG PGS.TS. HUỲNH QUANG LINH iii Lời cảm ơn Tôi xin chân thành cảm ơn đến Tập thể thầy cô giáo ở Bộ môn Toán ứng dụng, thuộc Khoa Khoa học ứng dụng, trường Đại học Bách Khoa - ĐHQG Tp. HCM đã dạy dỗ và truyền đạt kiến thức cho tôi trong suốt quá trình học tập tại nơi đây. TS. Nguyễn Tiến Dũng, cán bộ hướng dẫn, người đã giới thiệu tôi về đề tài và có những định hướng, góp ý quý báu trong quá trình thực hiện luận văn. PGS. TS. Nguyễn Đình Huy, chủ nhiệm Bộ môn Toán ứng dụng - Khoa Khoa học ứng dụng, đã giảng dạy cũng như hướng dẫn để giúp tôi có thể hoàn thành kịp thời các thủ tục hành chính. Tập thể thầy cô giáo ở Bộ môn Cơ sở Kỹ thuật điện, Khoa Điện - Điện tử, trường Đại học Bách Khoa - ĐHQG Tp. HCM, các đồng nghiệp, đã tạo điều kiện thuận lợi để hoàn thành khóa học. Cuối cùng tôi xin cám ơn gia đình và bạn bè đã ủng hộ và động viên về mặt tinh thần để tôi có thể hoàn thành luận văn này. Tp.HCM, ngày 03/12/2017 Nguyễn Phước Bảo Duy iv Tóm tắt luận văn Trường trung bình là một lý thuyết mới của Lý thuyết trò chơi, nghiên cứu các tình huống khi số lượng người tham gia rất lớn N → ∞. Luận văn này trình bày các khái niệm cơ bản của mô hình trường trung bình cũng như một số ứng dụng của mô hình này trong các bài toán kinh tế - xã hội. Luận văn cũng trình bày phương pháp sai phân hữu hạn để giải hệ phương trình mô tả mô hình trường trung bình đồng thời minh họa phương pháp thông qua một bài toán cụ thể. vi Abstract Mean Field Games is a novel brand of Games Theory, investigating the situations where the number of agents involved tends to infinity N → ∞. This thesis presents basic concepts of Mean Field Games as well as some of its applications in economical and social problems. This thesis also illustrates the Finite Difference Scheme in order to solve the system of partial differential describing the Mean Field Games and demonstrates the method through a specific problem. vii Lời cam đoan Tôi tên là Nguyễn Phước Bảo Duy, MSHV: 7140269, học viên cao học chuyên ngành Toán ứng dụng tại trường Đại học Bách Khoa - ĐHQG Tp.HCM khóa 2014. Tôi xin cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện với sự hướng dẫn của TS. Nguyễn Tiến Dũng. Tp.HCM, ngày 03/12/2017 Nguyễn Phước Bảo Duy v Mục lục Chương 1 Giới thiệu về đề tài 1.1 Trường trung bình . . . . . . . . . . . . . . . . . . 1.1.1 Phương trình Hamilton-Jacobi-Bellman . 1.1.2 Phương trình Fokker-Planck . . . . . . . . 1.1.3 Trường trung bình . . . . . . . . . . . . . 1.2 Một số ứng dụng của trường trung bình . . . . . 1.2.1 Ứng dụng trong bài toán quản lý sản xuất 1.2.2 Ứng dụng trong mô hình phân bố dân cư 1.2.3 Ứng dụng trong tài chính . . . . . . . . . 1.3 Tổng kết chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 4 6 8 14 14 17 21 24 . . . . . . . . . . . . 25 26 26 29 30 30 33 36 37 37 40 42 43 Chương 3 Mô phỏng và kết quả 3.1 Mô tả bài toán cần mô phỏng . . . . . . . . . . . . . . . . . . . . . . . 3.2 Một số phương trình quan trọng dùng để mô phỏng . . . . . . . . . . 3.3 Kết quả mô phỏng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 44 45 47 Kết luận và đề xuất 53 Tài liệu tham khảo 54 Phụ lục 55 . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 2 Phương pháp số cho bài toán trường trung bình 2.1 Phương pháp sai phân hữu hạn . . . . . . . . . . . . . 2.1.1 Đề xuất phương án . . . . . . . . . . . . . . . . 2.1.2 Tổng hợp . . . . . . . . . . . . . . . . . . . . . . 2.2 Phân tích bài toán tĩnh . . . . . . . . . . . . . . . . . . 2.2.1 Một vài kết quả ban đầu . . . . . . . . . . . . . 2.2.2 Sự tồn tại của nghiệm . . . . . . . . . . . . . . . 2.2.3 Tính duy nhất của nghiệm . . . . . . . . . . . . 2.3 Xấp xỉ hệ phương trình quá độ . . . . . . . . . . . . . 2.3.1 Định lý về sự tồn tại của nghiệm . . . . . . . . 2.3.2 Tính duy nhất của nghiệm . . . . . . . . . . . . 2.4 Tính hội tụ của bài toán . . . . . . . . . . . . . . . . . . 2.5 Tổng kết chương 2 . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Danh sách hình vẽ 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 Căn phòng và đám đông bên trong . . . . . . . . . Minh họa với h = 0.1 . . . . . . . . . . . . . . . . . Phân bố mật độ ban đầu . . . . . . . . . . . . . . . Trường hợp 1: Phân bố mật độ sau 30 giây . . . . . Trường hợp 1: Phân bố mật độ sau 60 giây . . . . . Trường hợp 1: Phân bố mật độ sau 2 phút . . . . . Trường hợp 1: Phân bố mật độ sau 3 phút . . . . . Trường hợp 1: Phân bố mật độ sau 4 phút 30 giây . Trường hợp 2: Phân bố mật độ sau 30 giây . . . . . Trường hợp 2: Phân bố mật độ sau 60 giây . . . . . Trường hợp 2: Phân bố mật độ sau 2 phút . . . . . Trường hợp 2: Phân bố mật độ sau 3 phút . . . . . Trường hợp 2: Phân bố mật độ sau 4 phút 30 giây . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 46 47 48 48 48 49 49 50 50 51 51 52 Chương 1 Giới thiệu về đề tài Trường trung bình (Mean field games, tiếng Pháp là Jeux à champ moyen) là một nhánh mới của lý thuyết trò chơi, được nghiên cứu và phát triển độc lập bởi nhóm các nhà khoa học Pierre-Louis Lions, Jean-Michael Lasry, Oliver Guéant (Pháp) và Peter Caines (Canada) vào khoảng năm 2006-2007. Hiện nay lý thuyết trò chơi được nghiên cứu tại phòng thí nghiệm MFG (MFG Labs) ở Paris, Pháp, phòng thí nghiệm này được thành lập bởi Pierre-Louis Lions và Jean-Michael Lasry, cả hai đều là giáo sư tại trường Collège de France. Đối tượng nghiên cứu của lý thuyết trường trung bình là các bài toán ngẫu nhiên động với số lượng lớn các thành viên tham gia trong các lĩnh vực như tài chính, quản lý năng lượng, mạng xã hội ..., được lấy ý tưởng từ việc thống kê đặc tính động học của các hạt vật lý, ngoài ra phương pháp trường trung bình còn được ứng dụng vào bài toán điều khiển tự động. Phương pháp nghiên cứu là xét một trò chơi (một tình huống nào đó cần nghiên cứu) với N người chơi tham gia, sau đó xét giới hạn khi N → ∞, khi đó hành vi của mỗi cá nhân sẽ không ảnh hưởng tới kết quả chung của tình huống. Bài toán trường trung bình được biểu diễn bằng phương trình Hamilton - Jacobi - Bellman và phương trình Fokker - Planck. Lời giải của bài toán trường trung bình giúp việc ra quyết định cho các vấn đề mà không cần chú ý quá nhiều đến các chi tiết của cả một hệ thống. Luận văn này giới thiệu các lý thuyết cơ bản của bài toán trường trung bình cũng như đưa ra một số ứng dụng thực tế của mô hình này trong các lĩnh vực kinh tế, xã hội, điều khiển học,... đồng thời luận văn trình bày phương pháp giải số cho bài toán trường trung bình và minh họa thông qua ví dụ cụ thể. Nội dung luận văn gồm 3 chương: - Chương 1: Giới thiệu về lý thuyết trường trung bình - Chương 2: Trình bày về phương pháp giải số cho bài toán trường trung bình. - Chương 3: Minh họa bài toán trường trung bình bằng các ví dụ cụ thể. 3 1.1 1.1.1 Trường trung bình Phương trình Hamilton-Jacobi-Bellman Trước khi đi vào bài toán trường trung bình, ta xét một ví dụ đơn giản: giả sử có một người xuất phát từ vị trí x (0) trong không gian Euclide Rd tại thời điểm t = 0 và muốn đi đến vị trí tốt hơn x ( T ) tại thời điểm t = T > 0. Mỗi vị trí x định nghĩa một ’chi phí’ là u( T, x ) ∈ R, chi phí sẽ nhỏ nếu x là gần vị trí mong muốn và lớn nếu ở xa hơn, do đó ta cần cực tiểu giá trị u( T, x ( T )). Trong thực tế, khi có ùn tắc giao thông, mặc dù muốn đến vị trí B tại thời điểm T, nhưng đôi lúc họ chỉ đi đến được một vị trí gần với B, hoặc một vị trí khác nếu không thể đến được B (ví dụ muốn đi ăn tối tại một nhà hàng lớn, nhưng do kẹt xe họ đành phải ghé một quán ăn nhỏ), do đó hàm chi phí có cực tiểu toàn cục tại B nhưng cũng có vài điểm cực tiểu cục bộ khác. Bây giờ ta cộng thêm một ’chi phí về di chuyển’ vào tổng chi phí, để làm được điều này, ta định nghĩa hàm chi phí vân tốc: C : Rd → R trong đó C (v)dt = C ( x 0 (t))dt là chi phí khi di chuyển với tốc độ v trong khoảng thời gian dt, từ đó ta có tổng chi phí: u ( T, x ( T )) + Z T 0
C x 0 (t) dt (1.1) Mục tiêu là lựa chọn lộ trình sao cho chi phí trên là nhỏ nhất. Mô hình này đang giả sử ’chi phí di chuyển’ chỉ phụ thuộc vào vận tốc, trong thực tế, chi phí này có thể phụ thuộc vào cả vị trí x và thời gian t nữa, khi đó C ( x 0 (t)) sẽ được thay bằng C ( x 0 (t), x (t), t), tuy nhiên để đơn giản, ta tạm thời bỏ qua các yếu tố này.   v+w Hàm chi phí C thường được chọn sao cho nó là một hàm lồi, có nghĩa là C ≤ 2 C (v) + C (w) , bởi vì rõ ràng việc thay đổi vận tốc liên tục (giữa v và w) sẽ tốn chi phí 2 v+w hơn là di chuyển với một vận tốc trung bình (trong trường hợp này là ). Ngoài 2 ra ta có thể giả sử C là một hàm chẵn, vì việc di chuyển với cùng một vận tốc, cho dù theo hướng nào, thì cũng tốn một chi phí di chuyển như nhau. Thông thường ta có thể chọn C (v) = tốc càng lớn sẽ càng tốn chi phí hơn. 1 2 |v| , theo đó thì việc di chuyển với vận 2 Một trong những phương pháp giải để tìm ra quỹ đạo di chuyển tối ưu là sử dụng phương trình Euler-Lagrange để cực tiểu (1), đây là phương trình vi phân theo x (t) với điều kiện đầu là x (0) cho trước. Tuy nhiên ở đây chúng ta sẽ khảo sát trường hợp tổng quát hơn để thu được nhiều thông tin hơn từ kết quả của bài toán: xét trường hợp thời điểm người này bắt đầu di chuyển là t0 với 0 ≤ t0 ≤ T, định nghĩa chi phí tối ưu u(t0 , x0 ) tại thời điểm (t0 , x0 ) là cận dưới (infimum) của hàm chi 4 phí: ( RT u ( T, x ( T )) + t C ( x 0 (t)) dt 0 x ( t0 ) = x0 (1.2) Theo định nghĩa trên thì khi t0 = T chi phí tối ưu tại x0 trùng với chi phí cuối cùng tại x0 , do đó chi phí cuối u( T, .) được xem là điều kiện biên của bài toán. Xét trường hợp khi t0 < T, chi phí tối ưu sẽ tuân theo phương trình HamiltonJacobi-Bellman, là một phương trình đạo hàm riêng, sẽ được diễn giải ở phần tiếp theo. Giả sử một người đang ở tại vị trí x0 tại thời điểm t0 < T, và đang suy nghĩ để quyết định đi đâu tiếp theo. Người đó biết bản thân nên di chuyển với tốc độ v là tốt nhất trong hoàn cảnh hiện tại, sau một khoảng thời gian dt người đó sẽ ở vị trí x0 + vdt và phát sinh chi phí C (v)dt, khi đó chi phí vị trí mới sẽ là u(t0 + dt, x0 + vdt), theo định nghĩa của u ta có công thức: u(t0 , x0 ) = u(t0 + dt, x0 + vdt) + C (v)dt (1.3) Dùng khai triển Taylor đến bậc 1 (bỏ qua các bận cao hơn) ta được: u(t0 , x0 ) = u(t0 , x0 ) + dt [∂t u(t0 , x0 ) + v · ∇ x u(t0 , x0 ) + C (v)] (1.4) Do v được chọn sao cho chi phí cuối cùng là nhỏ nhất, nên từ (1.4) ta thấy cần phải chọn v để v · ∇ x u ( t0 , x0 ) + C ( v ) (1.5) là nhỏ nhất. Lưu ý rằng C là một hàm lồi, nên giá trị v để (1.5) đạt cực tiểu phải là duy nhất, và là một hàm theo ∇ x u(t0 , x0 ). Định nghĩa ánh xạ H : Rd → R bởi: H ( p) := sup [v · p − C (v)] (1.6) v∈ Rd Khi đó giá trị nhỏ nhất của v · ∇ x u(t0 , x0 ) + C (v) là − H (∇ x u(t0 , x0 )) (lưu ý rằng C là hàm chẵn), bởi vì nếu đổi biến: ve := −v, ta cần giá trị nhỏ nhất của: −ve · p + C (−ve) = − (ve · p − C (ve)) = − H ( p) (1.7) với p := ∇ x u(t0 , x0 ). Do đó (1.4) trở thành: u(t0 , x0 ) = u(t0 , x0 ) + dt [∂t u(t0 , x0 ) − H (∇ x u(t0 , x0 ))] (1.8) Và việc xác định giá trị nhỏ nhất của (1.8) dẫn đến phương trình Hamilton-JacobiBellman: −∂t u + H (∇ x u) = 0 5 (1.9) Giá trị của ve thỏa yêu cầu có thể xem như một hàm theo p do: ∂ (ve · p − C (ve)) = 0 ∂e v (1.10) Như vậy vận tốc cần tìm được cho bởi: v = −ve = − H 0 (∇ x u) (1.11) Để tổng quát hơn, xét trường hợp người đó muốn di chuyển từ x0 đến x0 + vdt trong khoảng thời gian dt, nhưng cuối cùng chỉ đến được x0 + vdt + σdBt , với dBt là một nhiễu theo chuyển động Brownian trong Rd , và σ > 0 là biên độ nhiễu. Bằng cách sử dụng mô hình ngẫu nhiên, thì tổng chi phí cũng là một đại lượng ngẫu nhiên (thay vì là một giá trị xác định như đã xét ở trên), do đó thay vì tìm cách tối thiểu chi phí, bài toán thay đổi thành tìm cách tối thiểu kỳ vọng của chi phí. Phương trình (1.3) được điều chỉnh thành: u(t0 , x0 ) = E [u(t0 + dt, x0 + vdt + σdBt )] + C (v)dt (1.12) Khai triển Taylor vế phải của (1.12), sử dụng công thức Ito dBt = O(dt1/2 ) ta được: u(t0 , x0 ) = E [u(t0 , x0 )] + ∂t u0 (t0 , x0 )dt + v · ∇ x u0 (t0 , x0 )dt σ2 2 +σdBt · ∇ x u0 (t0 , x0 ) + ∇ u( x0 , t0 )(dBt , dBt ) + C (v)dt 2 (1.13) Do chuyển động Brownian dBt trong khoảng thời gian dt có kỳ vọng bằng 0, nên (1.13) trở thành: u(t0 , x0 ) = u(t0 , x0 ) + ∂t u0 (t0 , x0 )dt + v · ∇ x u0 (t0 , x0 )dt + σ2 ∆u( x0 , t0 )dt + C (v)dt 2 (1.14) σ2 2 ∇ u( x0 , t0 )dt, 2 do thành phần này không phụ thuộc vào v nên sẽ không ảnh hưởng đến các bước phân tích ở trên, nên cuối cùng ta sẽ thu được phương trình Hamilton-Jacobi-Bellman như sau: So sánh (1.14) và (1.4) ta thấy việc xuất hiện nhiễu sẽ sinh ra thành phần −∂t u − ν∆u + H (∇ x u) = 0 Trong đó ν := 1.1.2 (1.15) 1 2 σ , và vận tốc tối ưu vẫn được tính theo (1.11). 2 Phương trình Fokker-Planck Bây giờ ta xét một số lượng rất lớn N người cùng di chuyển trên đường. Để đơn giản, ta giả sử họ có cách di chuyển giống nhau, tức là bất kỳ người nào nếu ở vị trí (t0 , x0 ) thì đều di chuyển với cùng một vận tốc tức thời v(t0 , x0 ). Khi N → ∞ ta xét 6 R hàm mật độ m(t, x ), là một hàm không âm và Rd m(t, x )dx = 1 tại mọi thời điểm t, khi đó trong khoảng [ x, x + dx ] sẽ có Nm(t, x )|dx | người. Giả sử mật độ ban đầu m(0, x ) đã biết, ta sẽ tìm mật độ m(t, x ) tại thời điểm t, sử dụng lý thuyết phân phối với hàm thử F ( x ), là một hàm trơn và không phụ thuộc thời gian. Gọi xi (t) là vận tốc di chuyển của người thứ i tại thời điểm t, ta có: Z Rd m(t, x ) F ( x )dx ≈ 1 N N ∑ F(xi (t)) (1.16) i =1 Lấy đạo hàm hai vế theo thời gian: Z Rd ∂t m(t, x ) F ( x )dx ≈ 1 N N ∑ v(t, xi (t)) · ∇ F(xi (t)) (1.17) i =1 Cho N → ∞, vế phải của (1.17) trở thành tích phân: Z Rd m(t, x ) (v(t, x ) · ∇ F ( x )) dx = − Z Rd ∇ · (mv)(t, x ) F ( x )dx (1.18) Kết hợp các phương trình trên lại ta được: Z Rd [∂t m(t, x ) + ∇ · (mv)(t, x )] F ( x )dx = 0 ⇒ ∂t m(t, x ) + ∇ · (mv)(t, x ) = 0 (1.19) Cũng giống như phần trước, nếu xét thêm nhiễu, tức là vị trí tại thời điểm t + dt là x + vdt + σdBt (thay vì chỉ là x + vdt), và nhiễu Brownian là khác nhau cho mỗi người, ta sẽ có phương trình: Z Rd m(t + dt, x ) F ( x )dx ≈ 1 N N ∑ F(xi (t) + v(t, xi (t))dt + σdBt ) (1.20) i =1 Khai triển Taylor vế phải, sau đó lấy giới hạn khi N → ∞ như ở phần trước ta được:   Z σ2 m(t, x ) F ( x ) + vdt · ∇ F ( x ) + ∆F ( x )dt dx (1.21) 2 Rd Tiếp tục lấy tích phân từng phần và rút gọn, ta được phương trình Fokker-Planck: ∂t m(t, x ) − ν∆m(t, x ) + ∇ · (mv)(t, x ) = 0 với ν := (1.22) σ2 . 2 Trong phương trình Hamilton-Jacobi-Bellman ở trên, ta đang giả sử chi phí của mỗi người không phụ thuộc vào vị trí của những người khác. Bài toán trường trung bình xét trường hợp tổng quát hơn, ví dụ như chi phí C (v) không chỉ phụ thuộc vào 7 vận tốc v(t, x ) mà còn phụ thuộc vào mật độ người tham gia giao thông m(t, x ) tại thời điểm đó. Để đơn giản, ta chỉ xét mô hình cộng, có nghĩa là hàm chi phí có dạng: u( T, x ( T )) + Z T 0 0 C ( x (t))dt + Z T 0 (1.23) F (m(t, x (t)))dt trong đó F : R+ → R đại diện cho chi phí về mật độ giao thông tại vị trí x, F tăng khi người đó cảm thấy khó chịu và muốn thoát khỏi vị trí có mật độ giao thông cao và ngược lại. Với hàm chi phí mới này, có thể suy ra hàm Hamilton-Jacobi-Bellman mới: −∂t u − ν∆u + H (∇ x u) = F ( x, m) (1.24) Vận tốc v vẫn theo (1.11) và phương trình Fokker-Planck trở thành (sau khi đã đổi dấu): −∂t m + ν∆m + ∇ x · (mH 0 (∇ x u)) = 0 (1.25) Hệ (1.24) và (1.25) với các giá trị u( T, x ) và m(0, x ) cho trước là một ví dụ của bài toán trường trung bình. Lời giải của (1.24) thể hiện quyết định của mỗi cá nhân dựa vào việc họ đang muốn đi đến đâu, trong khi lời giải của (1.25) thể hiện vị trí (hay chính xác hơn là mật độ phân bố) của họ tại thời điểm t. 1.1.3 Trường trung bình Phần này ta tìm hiểu phương pháp xây dựng mô hình trường trung bình một cách tổng quát hơn. Bài toán tĩnh: Điểm cân bằng Nash Xét tình huống có N người tham gia (N ≥ 1) với động thái của họ được cho bởi: dXti = σi dWti − αi dt, X0i = xi ∈ Rd , 1 ≤ i ≤ N (1.26) trong đó d ≥ 1, σi ≥ 0, ∀i, (Wt1 , ..., WtN ) là N chuyển động Brownian trong Rd và αi tương ứng với chiến thuật của người tham gia thứ i tại thời điểm t ≥ 0 phù hợp với Wti . Để đơn giản trong trình bày, ta giả sử Xti ∈ T d (miền khảo sát) và các mô tả sau đây đều tuần hoàn với chu kỳ 1 theo xij (1 ≤ i ≤ N, 1 ≤ j ≤ d). Hàm chi phí cho mỗi X = ( x1 , ..., x N ) ∈ Q N như sau: 1 J (α , ..., α ) = lim inf E T →∞ T i 1 N T Z L 0 i ( Xti , αit ) + F i ( Xt1 , ..., XtN )dt  (1.27) với Fi và Li là các hàm liên tục, và: inf Li ( xi , αi )/|αi | → +∞ i f |αi | → +∞ xi 8 (1.28) Định nghĩa điểm cân bằng Nash: (ᾱ1 , ..., ᾱ N ) là một điểm cân bằng Nash nếu: J i (ᾱ1 , ..., ᾱ N ) ≥ J i (αi , ..., α N ), ∀αi (1.29) Cuối cùng, ký hiệu H i ( x, p) = supα∈ Rd ( p.α − Li ( x, α)) với p ∈ Rd , x ∈ Q, và 1 νi = (σi )2 , ∀i : 1 ≤ i ≤ d. Giả sử rằng H i ∈ C1 theo p (với mọi i, x). 2 Sự tồn tại của điểm cân bằng Nash phụ thuộc vào một số điều kiện nào đó của dữ liệu. Ở đây ta chỉ xét một trường hợp điểm cân bằng Nash tồn tại khi hàm Hamliton H i thõa điều kiện sau:  i  ∂H θ i i 2 ∃θ ∈ (0, 1), inf .p + ν ( H ) (1.30) x ∂x d với mọi giá trị 1 ≤ i ≤ N ) và | p| có giá trị lớn. Các định lý sau đây đã được chứng minh, có thể xem thêm [1], nên phần chứng minh sẽ không trình bày lại ở đây. Định lý 1.1.1: i. Tồn tại λ1 , ..., λ N ∈ R, v1 , ..., v N ∈ C2 và các giá trị m1 , ..., m N sao cho (∀1 ≤ i ≤ N): i i −ν ∆vi + H ( x, ∇vi ) + λi = Z Q N −1 Fi ( x1 , ..., xi−1 , x, xi+1 , ..., x N ) ∏ m j ( x j )dx j , i6= j (1.31) Z Q vi dx = 0, Z Q mi dx = 1, mi > 0, (1.32) −νi ∆mi − div  ∂H i ( x, ∇vi ) ∂p  = 0. (1.33) ii. Với mọi nghiệm (λ1 , ..., λ N ), (v1 , ..., v N ), (m1 , ..., m N ) của hệ phương trình trên, thì: 1 λi = J (ᾱ , ..., ᾱ ) = lim E T →∞ T i 1 N T Z 0 L i ( X̄ti , ᾱi ( X̄ti )) + F i ( X̄t1 , ..., X̄tN )  (1.34) trong đó X̄ti là nghiệm của (1.26) Định lý 1.1.2: Nếu giả sử rằng νi = ν, H i = H với ∀1 ≤ i ≤ N và Fi ( x1 , ..., x N ) = F j ( x1 , ..., xi−1 , x j , xi+1 , ..., x j−1 , xi , x j+1 , ..., x N ) với ∀1 ≤ i < j ≤ N, khi đó nghiệm của hệ phương trình ở Định lý 1.1 sẽ có dạng λ1 = ... = λ N , v1 = ... = v N , m1 = ... = m N . Bài toán tĩnh: khi N → +∞ Khi số lượng người tham gia tình huống là rất lớn, N → +∞, và giả sử rằng hành vi của mỗi người là giống nhau (ví dụ các công ty trong cùng một lĩnh vực đều 9 muốn thu lợi nhuận, hoặc ai trong đám đông kẹt xe cũng muốn nhanh chóng thoát ra ngoài v.v...) do đó νi = ν, H i = H với ∀1 ≤ i ≤ N. Ngoài ra, giả sử hàm Fi chỉ phụ 1 thuộc vào xi cũng như mật độ phân bố ∑ j6=i δx j : N " # 1 Fi ( x1 , ..., x N ) = V δx j ( xi ) (1.35) N−1 ∑ j 6 =i Một ví dụ thường gặp là V [m]( x ) = F (K ? m( x ), x ), trong đó K là một hàm LipsR chitz trên Rd × Q, K ? m( x ) = Q K ( x, y)m(y)dy. Trong thực tế, ta có thể giả sử rằng V [mn ] hội tụ đều trên Q nếu mn hội tụ yếu đến m. Định lý 1.1.3: Với các điều kiện đã liệt kê ở trên, bất kỳ điểm cân bằng Nash N N N N (λ1N , ..., λ N N ), ( v1 , ..., v N ), ( m1 , ..., m N ) nào cũng thõa các tính chất sau: i. (λiN )i,N bị chặn trên R, (viN )i,N và (miN )i,N là các tập  compact. N N N N ii. supi,j |λiN − λ N j | + k vi − v j k∞ + k mi − m j k∞ → 0 khi N → ∞. iii. Các giá trị nghiệm (λiN , viN , miN ) đều hội tụ về (λ, v, m) khi N → ∞ và thõa mãn: −ν∆v + H ( x, ∇v) + λ = V [m] Z Z vdx = 0, mdx = 1, m > 0 Q   ∂H −ν∆m − div ( x, ∇v)m = 0 ∂p Q (1.36) (1.37) (1.38) Hệ phương trình (1.36) - (1.38) chính là mô hình trường trung bình của bài toán tĩnh (bài toán phân bố xác lập, không phục thuộc và thời gian). Bài toán tĩnh: tính duy nhất của nghiệm Ở phần trước ta đã xác định được hệ phương trình mô tả bài toán trường trung bình tĩnh, phần này sẽ chứng minh về tính duy nhất nghiệm của hệ (1.36) - (1.38) với một số điều kiện cho trước. Định lý 1.1.4: Giả sử V là hàm đơn điệu trong L2 , tức là: Z Q (V [m1 ] − V [m2 ]) (m1 − m2 )dx ≥ 0, ∀m1 , m2 (1.39) hoặc có thể viết: Z Q (V [m1 ] − V [m2 ]) (m1 − m2 )dx ≤ 0, ⇒ m1 ≡ m2 và H là hàm lồi với mọi ( x, p) ∈ Q × Rd : H ( x, p + q) − H ( x, p) − ∂H ( x, p).q = 0 ⇒ q = 0 ∂p 10 (1.40) hoặc có thể dùng một điều kiện yếu hơn cho hàm Hamilton: H ( x, p + q) − H ( x, p) − ∂H ∂H ∂H ( x, p).q = 0 ⇒ ( x, p + q) = ( x, p) ∂p ∂p ∂p Khi đó hệ (1.36) - (1.38) có nghiệm duy nhất. Chứng minh: Nếu hệ (1.36) - (1.38) có hai nghiệm (λ1 , v1 , m1 ) và (λ2 , v2 , m2 ), khi đó ta nhân (1.36) với (m1 − m2 ) và (1.38) với (v1 − v2 ), sau đó trừ hai phương trình sẽ thu được: Z (V [m1 ] − V [m2 ]) (m1 − m2)dx +  Z  ∂H m1 ( H ( x, ∇v2 )) − H ( x, ∇v1 ) − ( x, ∇v2 ).∇(v2 − v1 ) dx + ∂p Q  Z  ∂H m2 ( H ( x, ∇v2 )) − H ( x, ∇v1 ) − ( x, ∇v2 ).∇(v1 − v2 ) dx = 0 ∂p Q Q (1.41) Do V đơn điệu và H là hàm lồi nên cả ba số hạng của phương trình trên đều không âm, nên có thể suy ra ∇v1 ≡ ∇v2 nên v1 ≡ v2 , từ đó có thể thấy được m1 ≡ m2 . Như vậy hệ (1.36) - (1.38) có nghiệm duy nhất. Bài toán động: một số phân tích Bài toán động hay có thể nói cách khác là bài toán quá độ, khi đó các đại lượng trong bài toán không chỉ phụ thuộc vào biến không gian x mà còn phụ thuộc vào biến thời gian t. Giả sử ta khảo sát trong khoảng t ∈ (0, T ), khi đó ta có hệ phương trình: ∂v − ν∆v + H ( x, ∇v) = V [m] trên Q × (0, T ) ∂t   ∂m ∂H − ν∆m + div ( x, ∇v)m = 0 trên Q × (0, T ) ∂t ∂p (1.42) (1.43) với các điều kiện biên: v|t=0 = V0 [m(0)] trên Q, m|t=T = m0 trên Q (1.44) Các giả thiết cho ν và H giữ nguyên như trong bài toán tĩnh. Các hàm V [m] và V [m(0)] có thể chọn tùy ý, thông thường được chọn như sau: V [m] = F (m( x, t), x, t) , V0 [m] = F0 (m( x ), x ) (1.45) Trong đó F, F0 lần lượt là các hàm xác định trên R × Q × [0, T ] và R × Q. Cuối R dùng, m0 là hàm trơn và dương trên Q sao cho Q m0 dx = 1. 11 Nếu số lượng người tham gia N là hữu hạn, thì nghiệm của (1.42) - (1.44) sẽ thu được bằng cách giải hệ phương trình: " # N ∂viN 1 ∂H N N δx j ( xi ) − ν ∑ ∆ x j viN + ∑ ( x, ∇ x j v N ∑ j ).∇ x j vi + H ( x, ∇ xi vi ) = V ∂t ∂p N − 1 j 6 =i j =1 j 6 =i (1.46) trên Q N × (0, T ) với " viN |t=0 = V0 # 1 δx j ( xi ) N−1 ∑ j 6 =i và hệ phương trình Fokker-Planck:   N N ∂m N ∂H i N N N + ν ∑ ∆ xi m + ∑ div xi ( x , ∇ xi vi ) m = 0 ∂t ∂p i =1 i +1 (1.47) với m N |t= T = N ∏ m0 (xi ) trên Q N . i =1 Lưu ý rằng m N (t) là mật độ người tham gia tại thời điểm T − t. Định lý 1.1.5: (Tính duy nhất của nghiệm) giả sử V và V0 là các hàm đơn điệu, lần lượt trên L2 ( Q × (0, T )) và L2 ( Q), H làm hàm lồi, khi đó hệ (1.42) - (1.44) sẽ có nghiệm duy nhất. Phần chứng minh định lý 1.5 cũng tương tự như ở định lý 1.4, đó là nhân (1.42) với (m1 − m2 ) và nhân (1.43) với (v1 − v2 ), trong đó (v1 , m1 ), (v2 , m2 ) là hai nghiệm của (1.42) - (1.44), sau đó trừ hai vế của phương trình, ta suy ra v1 = v2 và m1 = m2 . Định lý 1.1.6: (Điều kiện để tồn tại nghiệm) Hệ (1.42) - (1.44) sẽ có nghiệm nếu có các điều kiện sau: i. Điều kiện cho V và V0 : - V (hoặc V0 ) ánh xạ tập con X ∈ C ([0, T ]; L1 ( Q)) (hoặc C ( L1 ( Q))) định nghĩa bởi R m ≥ 0, Q mdx ≡ 1 thành một tập bị chặn trong L∞ (0, T; W 1,∞ ( Q)) (hoặc W 1,∞ ( Q)). - V là hàm ánh xạ liên tục từ X sang ( Q × [0, T ]). - V, V0 là ánh xạ bị chặn từ C k,α sang C k+1,α (∀k ≥ 0, ∀α ∈ (0, 1)). ii. Điều kiện cho H: H phải là hàm trơn trên Q × Rd và với C ≥ 0 thì:    ∂H  d    ∂p  ≤ C (1 + | p|), ∀( x, p) ∈ Q × R    ∂H  d    ∂x  ≤ C (1 + | p|), ∀( x, p) ∈ Q × R . 12 (1.48) (1.49) Trong trường hợp thông thường (1.45) thì điều kiện tồn tại nghiệm có thể được viết lại đơn giản hơn như sau: Giả sử F, F0 , H là các hàm liên tục và với a > 1, b > 1, q > 1, δ > 1, C ≥ 0: F ( x, t, λ) ≥ δ| F ( x, t, λ)| a − C (1.50) F0 ( x, λ)λ ≥ δ| F0 ( x, λ)|b − C (1.51) δ| p|q − C ≤ H ( x, p) ≤ C | p|q + C ∂H ∂H ( x, p).p ≥ qH − C; ( x, p) ≤ C | p|q−1 + C  ∂p ∂p (1.52)   Định lý 1.1.7: Nếu có các điều kiện (1.50) - (1.52) thì hệ (1.42) - (1.44) có nghiệm. Luận văn này chỉ trình bày ngắn gọn một số nội dung và các định lý, phần chứng minh các định lý, có thể xem thêm ở [1], [4] và [5]. Như vậy, ở phần này ta đã xây dựng mô hình trường trung bình trong trường hợp tổng quá, phần tiếp theo sẽ mô tả một số ứng dụng của bài toán trường trung bình trong một số lĩnh vực cụ thể. 13