Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Luận văn mô hình điều khiển markov rời rạc với thời gian vô hạn và ứng dụng giải...

Tài liệu Luận văn mô hình điều khiển markov rời rạc với thời gian vô hạn và ứng dụng giải bài toán điều chỉnh mực nước hồ thủy điện

.PDF
62
562
66

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI TRIỆU THU THỦY MÔ HÌNH ĐIỀU KHIỂN MARKOV RỜI RẠC VỚI THỜI GIAN VÔ HẠN Chuyên ngành : LÝ THUYẾT XÁC SUẤT VÀ THỐNG KÊ TOÁN HỌC Mã số : 60. 46 .01.06 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. NGUYỄN HỒNG HẢI HÀ NỘI - 2017 Mục lục Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . Phần mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Kiến thức chuẩn bị 1.1 Quá trình Markov và xích Markov . . . . . . . . . . . . 1.2 Mô hình điều khiển Markov . . . . . . . . . . . . . . . . 1.2.1 Định nghĩa mô hình điều khiển Markov . . . . . 1.2.2 Chiến lược điều khiển . . . . . . . . . . . . . . . 1.2.3 Quá trình điều khiển Markov với thời gian rời rạc 1.3 Chiến lược điều khiển Markov . . . . . . . . . . . . . . 1.3.1 Chiến lược điều khiển Markov . . . . . . . . . . 1.3.2 Quá trình điều khiển Markov rời rạc thuần nhất . . . . . . . . . . . . . . . . 2 Bài toán điều khiển ngẫu nhiên dạng hàm giá suy giảm với thời gian vô hạn 2.1 Một số khái niệm mở đầu . . . . . . . . . . . . . . . . . . . 2.2 Phương trình tối ưu dạng Bellman . . . . . . . . . . . . . . 2.2.1 Định nghĩa nghiệm của phương trình tối ưu Bellman 2.2.2 Chiến lược tối ưu . . . . . . . . . . . . . . . . . . . 2.3 Một số tính chất bổ sung cho phương trình tối ưu Bellman . 2.4 Chiến lược lặp và xấp xỉ giá tối ưu . . . . . . . . . . . . . . 2.4.1 Xấp xỉ hàm giá bị chặn . . . . . . . . . . . . . . . . 2.4.2 Xấp xỉ đệ quy giá bị chặn . . . . . . . . . . . . . . . 2.4.3 Chiến lược lặp . . . . . . . . . . . . . . . . . . . . 2.5 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 2.6 Tiệm cận tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Định nghĩa tiệm cận tối ưu . . . . . . . . . . . . . . 2 4 5 8 9 9 10 10 11 12 13 13 15 19 19 20 20 21 27 31 32 32 32 34 38 39 2.7 2.6.2 Điều kiện để tiệm cận điểm tối ưu là tiệm cận tối ưu 40 2.6.3 Chiến lược lặp . . . . . . . . . . . . . . . . . . . . . 41 Bài toán tối ưu với hàm giá dạng bậc 2 . . . . . . . . . . . 44 3 Bài toán điều khiển quá trình Markov với dạng hàm giá trung bình trên khoảng thời gian vô hạn 3.1 Định nghĩa mô hình điều khiển ngẫu nhiên . . . . . . . . . 3.1.1 Xây dựng mô hình . . . . . . . . . . . . . . . . . . . 3.1.2 Định nghĩa về giá tại bước nhảy thứ n . . . . . . . . 3.1.3 Định nghĩa về hàm giá . . . . . . . . . . . . . . . . 3.1.4 Định nghĩa chiến lược điều khiển tối ưu . . . . . . . 3.2 Công thức tính xác suất chuyển và một số tính toán bổ trợ 3.2.1 Định nghĩa xác suất chuyển . . . . . . . . . . . . . . 3.2.2 Xác định rn (x, µ) . . . . . . . . . . . . . . . . . . . 3.3 Sự tồn tại chiến lược tối ưu . . . . . . . . . . . . . . . . . . 3.4 Tìm chiến lược tối ưu và giá tối ưu . . . . . . . . . . . . . . 48 48 48 49 50 50 51 51 51 52 55 Kết luận 61 Tài liệu tham khảo 62 3 Lời cam đoan Tôi xin cam đoan bản luận văn này là kết quả nghiên cứu của cá nhân tôi. Các số liệu và tài liệu được trích dẫn trong luận văn là trung thực. Kết quả nghiên cứu này không trùng với bất cứ công trình nào đã được công bố trước đó. Tôi chịu trách nhiệm với lời cam đoan của mình. Hà Nội, ngày 05 tháng 6 năm 2017 Tác giả luận văn Triệu Thu Thủy 4 Phần mở đầu I. LÝ DO CHỌN ĐỀ TÀI Trong những năm gần đây, mô hình điều khiển quá trình Markov đã được chú ý nghiên cứu rất nhiều. Những mô hình với giả định khác nhau về không gian trạng thái, không gian điều khiển, các dạng hàm giá đã được xem xét bởi nhiều tác giả như: I.I. Gikhman, A.B. Skorokhod, Arapostathis, Kumar and Tangiralla; Bokar, Xi-Ren Cao, Chang, Fard, Marcus và Shayman; Liu. Một số ứng dụng của mô hình điều khiển Markov trên các lĩnh vực khác nhau như kinh tế, khoa học cũng được nghiên cứu bởi Sennott, Karel Sladky,... Trong luận văn này, tác giả giới thiệu một số kết quả về mô hình điều khiển Markov rời rạc với hai dạng hàm giá cơ bản: Thứ nhất, hàm giá dạng suy giảm với thời gian vô hạn: "∞ # X V (π, x) := Exπ αt .c(xt , at ) , π ∈ Π, x ∈ X. t=0 Thứ hai, hàm giá dạng trung bình với thời gian vô hạn ( n ) X 1 Ψx (U ) = lim ExU rk (xk , µk ) . n→∞ n k=1 Kết quả chính thu được của luận văn là đưa ra phương trình tối ưu dạng Bellman, nêu định nghĩa, điều kiện tồn tại và cách xác định chiến lược điều khiển tối ưu và giá tối ưu. Ngoài ra, chúng tôi xây dựng mô hình quá trình ngẫu nhiên rời rạc điều khiển được trên khoảng thời gian vô hạn. Với những lý do trên, dưới sự hướng dẫn tận tình của TS. Nguyễn Hồng Hải, tôi đã chọn luận văn thạc sĩ mang tên Mô hình điều khiển Markov rời rạc với thời gian vô hạn. II. MỤC ĐÍCH NGHIÊN CỨU Giới thiệu mô hình điều khiển quá trình Markov rời rạc với thời gian vô hạn. Cụ thể là phương trình tối ưu Bellman, nghiên cứu giá tối ưu và 5 chiến lược tối ưu với hai dạng hàm giá: dạng suy giảm và dạng trung bình trên khoảng thời gian vô hạn. III. ĐỐI TƯỢNG NGHIÊN CỨU • Mô hình điều khiển Markov. • Mô hình điều khiển Markov rời rạc với thời gian vô hạn. • Phương trình tối ưu Bellman, giá tối ưu và chiến lược điều khiển tối ưu với các dạng hàm giá khác nhau. IV. PHƯƠNG PHÁP NGHIÊN CỨU • Phương pháp nghiên cứu lí luận: đọc tài liệu, sách và các bài báo liên quan đến luận văn, tìm kiếm tài liệu trên mạng. • Sử dụng phương pháp phân tích để nắm vững vấn đề một cách chi tiết. • Sử dụng phương pháp tổng hợp, tổng hợp lại các kiến thức, trình bày vấn đề theo trình tự logic V. NHỮNG ĐÓNG GÓP CỦA LUẬN VĂN Tổng hợp và trình bày hai mô hình điều khiển quá trình Markov với dạng hàm giá suy giảm và hàm giá dạng trung bình trên khoảng thời gian vô hạn. VI.CẤU TRÚC LUẬN VĂN Luận văn bao gồm phần mở đầu, kết luận, tài liệu tham khảo và nội dung chính bao gồm 3 chương: Chương 1. Kiến thức chuẩn bị nêu lên những khái niệm, tính chất cần thiết cho những chương sau như định nghĩa quá trình điều khiển Markov, chiến lược điều khiển Markov. Chương 2: Bài toán điều khiển ngẫu nhiên dạng hàm giá suy 6 giảm với thời gian vô hạn. Trong chương nêu định nghĩa, điều kiện tồn tại giá tối ưu và chiến lược tối ưu, các phương pháp xấp xỉ hàm giá tối ưu. Phần cuối của chương giới thiệu bài toán cụ thể với hàm giá dạng bậc 2 và đưa ra phương pháp xác định hàm giá tối ưu trong trường hợp cụ thể. Chương 3: Bài toán điều khiển quá trình Markov với dạng hàm giá trung bình trên khoảng thời gian vô hạn. Trong chương này tác giả xây dựng mô hình điều khiển cho bài toán điều khiển quá trình Markov với bước nhảy Poisson liên quan đến quá trình semi Markov. 7 Lời cảm ơn Trong quá trình học tập, nghiên cứu và hoàn thành luận văn "Mô hình điều khiển Markov rời rạc với thời gian vô hạn", tôi đã nhận được sự hướng dẫn, giúp đỡ và động viên của nhiều cá nhân và tập thể, tôi xin được bày tỏ lòng biết ơn tới tất cả các cá nhân và tập thể đã tạo điều kiện giúp đỡ tôi. Đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành tới các thầy cô giáo trong khoa Toán, đặc biệt là các thầy trong Bộ môn Toán ứng dụng Trường Đại học Sư phạm Hà Nội đã mang đến cho tôi những kiến thức bổ ích trong những năm học vừa qua và trong công việc sắp tới. Tôi xin gửi lời cảm ơn sâu sắc đến TS. Nguyễn Hồng Hải - Người thầy đã trực tiếp hướng dẫn, tận tình chỉ bảo, giúp đỡ tôi trong quá trình nghiên cứu và hoàn thành luận văn. Cuối cùng tôi xin gửi lời cảm ơn đến gia đình, bạn bè đã luôn ở bên tôi, động viên và khuyến khích tôi trong quá trình thực hiện đề tài nghiên cứu của mình. Tôi rất mong nhận được những ý kiến đóng góp của các thầy cô, bạn bè và những người quan tâm để luận văn được hoàn thiện và phát triển hơn. Tôi xin chân thành cảm ơn! Hà Nội, ngày 05 tháng 6 năm 2017 Triệu Thu Thủy 8 Chương 1 Kiến thức chuẩn bị 1.1 Quá trình Markov và xích Markov Định nghĩa 1.1.1. Trên không gian xác suất (Ω, F, P ), xét quá trình ngẫu nhiên Xt với t ≥ 0 Ký hiệu các σ - đại số cảm sinh như sau: F≤t = σ(Xs |s ≤ t) Ft = σ(Xt ) Quá trình Xt được gọi là quá trình Markov nếu thỏa mãn điều kiện sau: E(Xh |F≤t ) = E(Xh |Ft ) với ∀h > t (1.1) Hệ thức (1.1) được gọi là tính Markov. Các trường hợp đặc biệt của quá trình Markov: Ký hiệu E là không gian trạng thái của quá trình Xt vớit ≥ 0, tức là: E := {Xt | ∀t} + Nếu lực lượng của tập E là không quá đếm được thì quá trình Xt được gọi là xích Markov. + Nếu t ∈ [0, +∞) thì Xt được gọi là quá trình Markov với thời gian liên tục. + Nếu t = 0, 1, 2, ... hay t ∈ N thì Xt được gọi là quá trình Markov với thời gian rời rạc. 9 + Nếu xích Markov có t ∈ [0, +∞) thì Xt được gọi là Xích Markov với thời gian liên tục. + Nếu xích Markov có t ∈ N thì Xt được gọi là Xích Markov với thời gian rời rạc. Định nghĩa 1.1.2. Xét {Xt } là xích Markov với thời gian rời rạc. Đặt: p(s, i, t, j) = P{X(t) = j|X(s) = i}, (s < t) là xác suất để thời điểm s xích ở trạng thái i, đến thời điểm t chuyển sang trạng thái j , được gọi tắt là xác suất chuyển. Nếu xác suất chuyển chỉ phụ thuộc vào (t − s) tức là, p(s, i, t, j) = p(s + h, i, t + h, j) với ∀h > 0 thì ta xích Markov rời rạc là thuần nhất theo thời gian. 1.2 1.2.1 Mô hình điều khiển Markov Định nghĩa mô hình điều khiển Markov Trước khi định nghĩa quá trình điều khiển Markov, ta có một số quy ước và ký hiệu sau: Không gian Borel: X là một không gian Borel nếu X là một không gian metric đầy, khả ly và σ− đại số sinh bởi các tập con mở của X là σ− đại số Borel, kí hiệu là B(X). Hàm đo được: Xét hai không gian đo (X, B(X)) và (E, B(E)). Một hàm số f : X → E gọi là đo được hay là "Borel đo được" nếu f −1 (A) ∈ B(X) với mọi A ∈ B(E) Hạt nhân ngẫu nhiên: Cho X và Y là hai không gian Borel. Một hạt nhân ngẫu nhiên trên X được cho bởi Y là một hàm số P (.|.) thỏa mãn 2 điều kiện sau: (i) P (.|y) là một độ đo xác suất trên X với mọi y ∈ Y cố định. (ii) P (B|.) là hàm số đo được trên Y với mọi B ∈ B(X) cố định. Lớp tất cả các hạt nhân ngẫu nhiên trên X được cho bởi Y được ký hiệu là P(X|Y ). 10 Định nghĩa 1.2.1. Một mô hình điều khiển Markov là bộ gồm 5 thành phần: (X, A, A(x)|x ∈ X, Q, c). (1.2) Trong đó, (a) X là không gian trạng thái, mỗi phần tử x ∈ X gọi là một trạng thái. (b) A là một không gian Borel được gọi là tập điều khiển hoặc tập hành động. (c) Lớp {A(x)|x ∈ X} khác rỗng, với A(x) đo được là tập hợp điều khiển được khi hệ ở trạng thái x ∈ X , khi đó ta đặt: K := {(x, a)|x ∈ X, a ∈ A(x)} (1.3) K là tập con đo được của không gian X × A. (d) Q là một hạt nhân ngẫu nhiên trên X cho bởi K, được gọi là luật chuyển đổi (transition law). (e) c : K → R là một hàm số đo được, gọi là hàm giá một bước (one- stage cost function). Trong một số trường hợp ta ký hiệu hàm giá là r : K → R thay vì c. Giải thích sự hoạt động của mô hình Tại thời điểm t, hệ thống có: + Trạng thái xt = x ∈ X + Điều khiển at = a ∈ A(x) + Khi đó hàm giá là c(x, a). + Đến thời điểm t + 1 quá trình chuyển sang trạng thái xt+1 là một biến ngẫu nhiên nhận giá trị trên X với phân phối Q(.|x, a) tức là: Q(B|x, a) := P (xt+1 ∈ B|xt = x, at = a) với B ⊂ X. 1.2.2 Chiến lược điều khiển Xét mô hình điều khiển Markov trong định nghĩa 1.2.1. Với ∀t = 0, 1, ... ta xác định không gian Ht - lịch sử (admissiable histories) đến thời điểm t như sau: Giả sử H0 := X , và Ht := Kt × X = K × Ht−1 , t = 1, 2, ... 11 (1.4) trong đó K được cho bởi (1.3). Mỗi phần tử ht ∈ Ht là một vectơ có dạng: ht = (x0 , a0 , ..., xt−1 , at−1 , xt ), (1.5) với (xi , ai ) ∈ K, i = 0, 1, ..., t − 1 và xt ∈ X . Trong một số trường hợp ta cần sử dụng tính đóng (hoặc tính đủ) của Ht nên ta xét không gian bao đóng của Ht như sau: H t := (X × A)t × X = (X × A) × H t−1 (1.6) với H 0 := H0 = X. Định nghĩa 1.2.2. Một chiến lược điều khiển ngẫu nhiên (hay chiến lược điều khiển, chiến lược) là dãy hạt nhân ngẫu nhiên π = (πt , t = 0, 1, 2, ...) nhận giá trị trên A với điều kiện Ht cho trước thỏa mãn đẳng thức sau: πt (A(xt )|ht ) = 1, ∀ht ∈ Ht , t = 0, 1, ... (1.7) Ta ký hiệu tập hợp tất cả các chiến lược là Π. Như vậy, chúng ta có thể hiểu một chiến lược π = {πt } là dãy biến điều khiển (at ) ∈ A(x) sao cho ∀ht ∈ Ht thì phân phối của at là πt (.|ht ) với t = 0, 1, 2, ..., được xác định bởi công thức (1.9) phía sau. 1.2.3 Quá trình điều khiển Markov với thời gian rời rạc Giả sử (Ω, F) là không gian đo được, với không gian mẫu Ω := H ∞ = (X × A)∞ và F là σ - đại số nhỏ nhất chứa các tập con của Ω, ta thấy H∞ = K∞ ⊂ Ω. Trên không gian Ω = (X × A)∞ = {(xn , an )|xn ∈ X, an ∈ A với n = 0, 1, 2, ...}. Giả sử π = (πt ) là một chiến lược điều khiển bất kì và ν là độ đo xác suất tùy ý trên X được gọi là "phân phối ban đầu". Kí hiệu Pνπ là độ đo xác suất trên Ω cảm sinh bởi chiến lược π = (π1 , π2 , ...) với điều kiện ν . Khi đó theo định lý Ionescu - Tulcea thì Pνπ tồn tại và duy nhất, ngoài ra nó thỏa mãn Pνπ (H∞ ) = 1 và với ∀B ∈ B(X), C ∈ B(A) và ht ∈ Ht , t = 12 0, 1, 2, ... thì Pνπ (x0 ∈ B) = ν(B) (1.8) Pνπ (at ∈ C|ht ) = πt (C|ht ) (1.9) Pνπ (xt+1 ∈ B|ht , at ) = Q(B|xt , at ) (1.10) Định nghĩa 1.2.3. Quá trình ngẫu nhiên (Ω, F, Pνπ , {xt }) được gọi là một quá trình điều khiển Markov thời gian rời rạc (hoặc quá trình quyết định Markov). Từ định nghĩa ta thấy quá trình {xt } ∈ X phụ thuộc vào chiến lược π và phân phối ban đầu ν Mặt khác,ta gọi họ {(Ω, F, Pνπ , {xt })|π ∈ Π} có thể thay thế cho ν như Quá trình điều khiển Markov (MCP). Vấn đề tìm chiến lược điều khiển tối ưu tốt nhất theo một nghĩa xác định nào đó của họ này được gọi là một Bài toán điều khiển Markov tối ưu. Kí hiệu Eνπ := E[Pνπ ], nếu ν = x ∈ X là trạng thái ban đầu thì ta viết Pxπ thay cho Pνπ và Exπ thay cho Eνπ . Chú ý 1.2.4. Mô hình điều khiển Markov được định nghĩa 1.2.1 được gọi là dừng nếu từng thành phần của nó: X, A, A(x) không phụ thuộc vào tham số t. Ngược lại, nếu mô hình có dạng: (Xt , At , {At (x)|x ∈ Xt }, Qt , ct ), t = 0, 1, ... thì ta gọi là không dừng. 1.3 1.3.1 Chiến lược điều khiển Markov Chiến lược điều khiển Markov Xét về mặt tổng quát, với chiến lược điều khiển π bất kì thì quá trình {xt } không có tính Markov vì nó phụ thuộc vào các trạng thái trước đó ht . Tuy nhiên, nếu những chiến lược π thỏa mãn một số điều kiện để {xt } trở thành quá trình Markov thì π được gọi là Chiến lược Markov. 13 Định nghĩa 1.3.1. X là không gian trạng thái. Φ là ký hiệu tập hợp tất cả các hạt nhân ngẫu nhiên ϕ trong P(A|X) thỏa mãn ϕ(A(x)|x) = 1 với ∀x ∈ X , tức là: Φ := {ϕ ∈ P(A|X)|ϕ(A(x)|x) = 1, ∀x ∈ X} Đặt F là tập hợp tất cả các hàm số đo được f : X → A sao cho f (x) ∈ A(x) với ∀x ∈ X . F = {f : X → A|f đo được và f (x) ∈ A(x) với ∀x ∈ X}. Ta có F 6= ∅ và Φ 6= ∅. Một hàm số f ∈ F có thể được xác định với một hạt nhân ngẫu nhiên ϕ ∈ Φ, vì thế ϕ(.|x) là đo được tại f (x) với ∀x ∈ X , ϕ(C|x) = IC [f (x)], ∀x ∈ X, C ∈ B(A) ở đó IC là hàm chỉ tiêu của C . Vì thế, chúng ta có thể thấy rằng F là một tập con của Φ, F ⊂ Φ. (1.11) Định nghĩa 1.3.2. Một chiến lược π = {πt } ∈ Π được gọi là: (a) Một chiến lược Markov ngẫu nhiên (randomized Markov policy) nếu tồn tại một dãy {ϕt } các hạt nhân ngẫu nhiên ϕt ∈ Φ sao cho: πt (.|ht ) = ϕt (.|xt ), ∀ht ∈ Ht , t = 0, 1, ...; (1.12) (b) Một chiến lược ngẫu nhiên dừng (randomized stationary policy) nếu tồn tại một hàm ϕ ∈ Φ sao cho πt (.|ht ) = ϕ(.|xt ), ∀ht ∈ Ht , t = 0, 1, ...; Tập hợp tất cả các chiến lược Markov ngẫu nhiên ký hiệu là ΠRM , tập các chiến lược ngẫu nhiên dừng ký hiệu là ΠRS . Ta thấy: ΠRS ⊂ ΠRM ⊂ Π (c) π = {πt } ∈ Π được gọi là một chiến lược tất định (deterministic policy) nếu tồn tại một dãy hàm gt : Ht → A đo được sao cho với ∀ht ∈ Ht , t = 0, 1, ... thì gt (ht ) ∈ A(xt ) và πt (.|ht ) = gt (ht ), tức là πt (C|ht ) = IC [gt (ht )] với ∀C ∈ B(A) 14 (d) π = {πt } ∈ Π được gọi là một chiến lược Markov tất định (deterministic Markov policy) nếu tồn tại một dãy {ft } ∈ F sao cho với mọi ht ∈ Ht và t = 0, 1, ... thì πt (.|ht ) = ft (xt ) ∈ A(xt ). (e) π = {πt } ∈ Π được gọi là một chiến lược không ngẫu nhiên (deterministic stationary policy) nếu tồn tại một hàm só f ∈ F sao cho với mọi ht ∈ Ht và t = 0, 1, ... thì πt (.|ht ) = f (xt ) ∈ A(xt ). Đặt ΠD , ΠDM , ΠDS lần lượt là tập hợp tất cả các chiến lược tất định, Markov tất định và không ngẫu nhiên, khi đó ta có: ΠDS ⊂ ΠDM ⊂ ΠD ⊂ Π Chú ý:Từ F ⊂ Φ kéo theo ΠDS ⊂ ΠRS . Giả sử F và Φ là những tập đã được định nghĩa trên và c là một hàm giá và Q là luật chuyển đổi. Với mọi x ∈ X , đặt Z c(x, ϕ) := c(x, a)ϕ(da|x) (1.13) A và Z Q(.|x, ϕ) := Q(.|x, a)ϕ(da|x) (1.14) A Đặc biệt nếu với f ∈ F(⊂ Φ) thì công thức (1.13) và (1.14) trở thành: c(x, f ) = c(x, f (x)) và Q(B|x, f ) = Q(B|x, f (x)) 1.3.2 Quá trình điều khiển Markov rời rạc thuần nhất Xét quá trình điều khiển Markov rời rạc {yt } trên không gian trạng thái X với dãy hạt nhân {Rt } tương ứng. Khi đó ta có tính Markov được viết thành: với mọi B ∈ B(X) và t = 0, 1, 2, ... thì P (yt+1 ∈ B|y0 , ..., yt ) = P (yt+1 ∈ B|yt ) = Rt (B|yt ) (1.15) Nếu Rt = R là tất định thì {yt } được gọi là một quá trình điều khiển Markov thuần nhất với hạt nhân chuyển R. Ngược lại nếu Rt phụ thuộc 15 vào thời gian t thì {yt } được gọi là quá trình điều khiển Markov không thuần nhất với hạt nhân {Rt } Mệnh đề 1.3.3. Giả sử ν là phân phối ban đầu tùy ý. Nếu π = {ϕt } là một chiến lược điều khiển Markov ngẫu nhiên (π ∈ ΠRM ) thì {xt } là một quá trình Markov không thuần nhất với hạt nhân {Q(.|., ϕt )}, tức là với B ∈ B(X) và t = 0, 1, ... thì Pνπ (xt+1 ∈ B|x0 , ..., xt ) = Pνπ (xt+1 ∈ B|xt ) = Q(B|xt , ϕt ) (1.16) Ta thu được kết quả tương tự nếu π = {ft } ∈ ΠDM và hạt nhân Q(.|., ft ). Ngược lại, với ϕ ∈ ΠRS và f ∈ ΠDS , thì {xt } là quá trình Markov thuần nhất theo thời gian với hạt nhân {Q(.|., ϕ)} và {Q(.|., f )}. Chứng minh. Trước hết ta chứng minh với chiến lược tùy ý π = {ϕt } ∈ Π, thì: Z Pνπ (xt+1 ∈ B|ht ) = Q(B|xt , at )πt (dat |ht ) (1.17) A với mọi B ∈ B(X) và t = 0, 1, .... Từ các tính chất của kỳ vọng điều kiện ta có: Pνπ (xt+1 ∈ B|ht ) = Eνπ [Pνπ (xt+1 ∈ B|ht , at )|ht ] = Eνπ [Q(B|xt , at )|ht ] Z = Q(B|xt , at )πt (dat |ht ) A Vậy ta chứng minh được (1.17). Đặc biệt, nếu π = {ϕt } là một chiến lược Markov ngẫu nhiên, π ∈ ΠRM thì (1.17) trở thành: Z π Pν (xt+1 ∈ B|ht ) = Q(B|xt , at )ϕt (dat |xt ) = Q(B|xt , ϕt ) (1.18) A vì Q(.|x, ϕ) được xác định trong (1.14). Đặt xt0 = (x0 , x1 , ..., xt ) ta có: Pνπ (xt+1 ∈ B|xt0 ) = Eνπ [Pνπ (xt+1 ∈ B|ht )|xt0 ] = Eνπ [Q(B|xt , ϕt )|xt0 ] = Q(B|xt , ϕt ) 16 ở đó, tiếp tục áp dụng tương tự, trong trường hợp này (1.16) thỏa mãn: Pνπ (xt+1 ∈ B|xt ) = Eνπ [Pνπ (xt+1 ∈ B|ht )|xt ] = Eνπ [Q(B|xt , ϕt )|xt ] = Q(B|xt , ϕt ) Vậy ta có điều phải chứng minh. Chú ý 1.3.4. (a)Xét quá trình điều khiển Markov rời rạc có phương trình xt+1 = F (xt , at , ξt ) (1.19) với t = 0, 1, ... và x0 là trạng thái ban đầu cho trước. Trong đó, ξt là một dãy biến ngẫu nhiên trên không gian S độc lập cùng phân phối gốc µ và không phụ thuộc vào x0 ,(dãy ξt được gọi là quá trình nhiễu (disturbance process). Trong trường hợp này, luật chuyển đổi Q xác định bởi: Q(B|x, a) = µ({s ∈ S|F (x, a, s) ∈ B}) Z = IB [F (x, a, s)]µ(ds) (1.20) (1.21) X = EIB [F (x, a, s)] (1.22) (b) Nếu ϕ ∈ Φ là hạt nhân Markov với luật chuyển đổi Q(.|., ϕ) thì tại bước nhảy thứ n ta kí hiệu Qn (.|., ϕ) với Qn (B|x, ϕ) := Pxϕ (xn ∈ B), n ≥ 0, B ∈ B(X), x ∈ X (1.23) quy ước Q1 (.|., ϕ) = Q(.|., ϕ) và Z n Q (B|x, ϕ) = Q(B|y, ϕ)Qn−1 (dy|x, ϕ) Z = Qn−1 (B|y, ϕ)Q(dy|x, ϕ), với n ≥ 1 (1.24) (1.25) (c) Với mô hình điều khiển Markov với chiến lược π = {at } và trạng thái ban đầu x0 = x. Thông thường có 2 dạng hàm giá phổ biến: Thứ nhất: hàm giá dạng suy giảm: "∞ # X V (π, x) := Exπ αt .c(xt , at ) , π ∈ Π, x ∈ X t=0 17 ở đó α ∈ (0, 1) là một hệ số cho trước, α được gọi là hệ số suy giảm hay tỷ lệ suy giảm (trong một số trường hợp cụ thể). Thứ hai: Hàm giá dạng trung bình theo thời gian. Cụ thể là giá trị trung bình của hàm giá sau N bước được tính theo công thức: N 1 X c(xt , at ) N + 1 t=0 Sau đó, ta tìm giới hạn của kỳ vọng biểu thức trên khi N → ∞, tức là: # " N X 1 lim Exπ c(xt , at ) N →∞ N + 1 t=0 Trong bài toán tối ưu mục đích chính là xác định điều kiện tồn tại, cách xác định chiến lược tối ưu và giá tối ưu. 18 Chương 2 Bài toán điều khiển ngẫu nhiên dạng hàm giá suy giảm với thời gian vô hạn 2.1 Một số khái niệm mở đầu Cho mô hình điều khiển Markov (X, A, {A(x)|x ∈ X}, Q, c). Nội dung chính của chương này là tìm giá trị nhỏ nhất của hàm giá dạng suy giảm với thời gian vô hạn: # "∞ X V (π, x) := Exπ αt .c(xt , at ) , π ∈ Π, x ∈ X (2.1) t=0 ở đó α ∈ (0, 1) là một hệ số cho trước gọi là tham số suy giảm hoặc tỷ lệ suy giảm. Một chiến lược π ∗ thỏa mãn: V (π ∗ , x) = inf V (π, x) =: V ∗ (x), ∀x ∈ X Π (2.2) thì π ∗ được gọi là chiến lược tối ưu và V ∗ được gọi là giá tối ưu. Ta luôn giả sử rằng hàm giá c là không âm (trong trường hợp tổng quát các kết quả đúng cho c bị chặn dưới). Ngoài ra, ta sử dụng ký hiệu Vn là giá tại bước nhảy n (n-stage cost) được định nghĩa bởi: " n−1 # X Vn (π, x) := Exπ αt .c(xt , at ) , π ∈ Π, x ∈ X (2.3) t=0 19 khi đó biểu thức V (π, x) tại (2.1) có thể viết dưới dạng: V (π, x) = lim Vn (π, x) n→∞ 2.2 2.2.1 (2.4) Phương trình tối ưu dạng Bellman Định nghĩa nghiệm của phương trình tối ưu Bellman Định nghĩa 2.2.1. Một hàm đo được v : X → R được gọi là một nghiệm của phương trình tối ưu dạng Bellman nếu nó thỏa mãn:   Z v(x) = min c(x, a) + α v(y)Q(dy|x, a) , ∀x ∈ X. (2.5) A(x) X Ta sẽ chứng minh rằng V ∗ là nghiệm của phương trình tối ưu Bellman, tức là   Z V ∗ (x) = min c(x, a) + α V ∗ (y)Q(dy|x, a) A(x) X Chứng minh. Xét trường hợp tổng quát c là hàm giá không bị chặn, ta xét hàm sau:   Z vn (x) = min c(x, a) + α vn−1 (y)Q(dy|x, a) , (2.6) A(x) X với ∀x ∈ X và n = 1, 2, ... và v0 (.) = 0. và # " n−1 X J(π, x) := Exπ αt .c(xt , at ) + αn .cn (xn ) t=0 đặt ct (x, a) := αt .c(x, a), Jn (x) = αn .cn (x) . Với t = n − 1, n − 2, ..., 0 ta đặt   Z Jt (x) := min αt .c(x, a) + Jt+1 (y)Q(dy|x, a)] A(x) X Đặt: Vt (.) := α−t .Jt (.) với t = 0, 1, 2, ..., n thì Vn (x) = cn (x) và với t = n − 1, n − 2, ..., 0 ta có:   Z Vt (x) := min c(x, a) + α Vt+1 (y)Q(dy|x, a)] A(x) X 20
- Xem thêm -

Tài liệu liên quan