Luận văn Về bài toán cân bằng giả đơn điệu mạnh và áp dụng vào một mô hình kinh tế thị trường điện

Đ IN H THẾ TH O BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG --------------------------------------- Đinh Thế Tho C H U Y ÊN N G À N H TO Á N Ứ N G DỤ N G VỀ BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU MẠNH VÀ ÁP DỤNG VÀO MỘT MÔ HÌNH KINH TẾ THN TRƯỜNG ĐIỆN LUẬN VĂN THẠC SĨ TOÁN HỌC K H O Á 1 Hà Nội – Năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG --------------------------------------- Đinh Thế Tho VỀ BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU MẠNH VÀ ÁP DỤNG VÀO MỘT MÔ HÌNH KINH TẾ THN TRƯỜNG ĐIỆN LUẬN VĂN THẠC SĨ TOÁN HỌC CHUYÊN NGÀNH : TOÁN ỨNG DỤNG MÃ SỐ: 60. 46. 01. 12 NGƯỜI HƯỚNG DẪN KHOA HỌC : GS.TSKH Lê Dũng Mưu Hà Nội - Năm 2015 Thang Long University Libraty Lời cam đoan Bản luận văn này là của tôi dưới sự hướng dẫn của GS. TSKH Lê Dũng Mưu. Bản luận văn tổng hợp lại từ các tài liệu trích dẫn dựa trên các mục tiêu của đề tài. Bản luận văn này không phải là một sự sao chép lại hoàn toàn từ các tài liệu đã có. Lời cảm ơn Tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới GS. TSKH Lê Dũng Mưu, người thầy đã tận tình hướng dẫn và đóng góp cho tôi nhiều ý kiến về nội dung của luận văn. Tôi xin gửi lời cảm ơn đến các thầy cô đã giảng dạy và giúp đỡ tôi trong suốt quá trình tôi học tập tại trường Đại học Thăng Long. Tôi xin gửi lời cảm ơn chân thành tới những người thân yêu trong gia đình, bạn bè, đã luôn cổ vũ, động viên, giúp đỡ tôi để tôi có thể hoàn thành được luận văn này. Bước đầu nghiên cứu khoa học nên bản luận văn thạc sĩ của tôi chắc chắn còn rất nhiều thiếu sót. Tôi rất mong nhận được sự đóng góp ý kiến của các thầy giáo, cô giáo và bạn đọc để bản luận văn được hoàn thiện hơn. Hà Nội, tháng 5 năm 2015 Học viên Đinh Thế Tho Thang Long University Libraty Danh mục các kí hiệu viết tắt H : Không gian Hilbert thực; 〈. | .〉 : Tích vô hướng; ‖.‖ : Chuẩn trên không gian Hilbert; NC : Nón chuẩn tắc của C; PC : Phép chiếu lên tập C; dC : Hàm khoảng cách của tập C; ∇f (x) : Đạo hàm của hàm f tại x; argmin f : Tập các cực tiểu của hàm f . Danh mục hình và bảng Hình 2.1: Lợi nhuận tốt nhất của nhà máy thủy điện đối với nhà máy nhiệt điện ( Trang 25) Hình 2.2: Lợi nhuận tốt nhất của nhà máy nhiệt điện đối với nhà máy thủy điện ( Trang 25) Hình 2.3: Lợi nhuận tốt nhất của hai nhà máy ( Trang 26) Bảng 2.1: Kết quả tính toán Ví dụ 2 theo Thuật toán 2 ( Trang 29) Thang Long University Libraty Mục lục Lời mở đầu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1.BÀI TOÁN CÂN BẰNG. . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.Một số khái niệm và các kết quả cơ bản. . . . . . . . . . . . . . 2 1.1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.3. Toán tử chiếu lên một tập lồi đóng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.Bài toán cân bằng và các trường hợp riêng . . . . . . . . . . . 7 1.2.1. Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2. Bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.3. Bài toán điểm bất động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.4. Bài toán cân bằng Nash trong trò chơi không hợp tác . . . . . . . . 10 1.3.Sự tồn tại nghiệm của bài toán cân bằng. . . . . . . . . . . . 11 Chương 2.HAI THUẬT TOÁN GIẢI BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU MẠNH VÀ ÁP DỤNG . . . . . . . . 16 2.1.Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1. Thuật toán 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.1.2. Thuật toán 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.1.3. Sự hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.Áp dụng vào mô hình cân bằng thị trường điện . . . . . 23 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 i Lời mở đầu Bài toán cân bằng có nhiều ứng dụng trong khoa học, kĩ thuật và đời sống. Có rất nhiều bài toán liên quan đến bài toán cân bằng như: bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash trong các trò chơi không hợp tác,.... Do đó việc trình bày và đưa ra các thuật toán giải bài toán cân bằng là rất cần thiết. Luận văn này nhằm giới thiệu về bài toán cân bằng giả đơn điệu mạnh và hai thuật toán giải bài toán cân bằng giả đơn điệu mạnh qua đó áp dụng vào mô hình kinh tế thị trường điện. Luận văn được chia làm hai chương • Chương 1. của luận văn trình bày tóm tắt một số kết quả đã biết trong giải tích lồi liên quan đến luận văn. Giới thiệu bài toán cân bằng và các trường hợp riêng. • Chương 2. của luận văn trình bày hai thuật toán để giải bài toán cân bằng giả đơn điệu mạnh, xét sự hội tụ của hai thuật toán và cuối chương là áp dụng vào mô hình kinh tế thị trường điện. Cuối cùng trình bày các ví dụ cụ thể để minh họa thuật toán. 1 Thang Long University Libraty Chương 1 BÀI TOÁN CÂN BẰNG Trong chương này ta nhắc lại những khái niệm cơ bản, tính chất đặc trưng của tập lồi và hàm lồi trong không gian Hilbert−H thực qua đó giới thiệu về bài toán cân bằng và các trường hợp riêng của nó cùng một số điều kiện về sự tồn tại nghiệm của bài toán cân bằng. Nội dung của chương này được lấy từ [1], [2], [3], [4] . 1.1. Một số khái niệm và các kết quả cơ bản 1.1.1. Tập lồi Định nghĩa 1.1.1. Một tập C ⊆ H được gọi là lồi nếu ∀x, y ∈ C, 0 ≤ λ ≤ 1⇒ λx+ (1− λ) y ∈ C. Định lý 1.1.1. Tập lồi là đóng với phép giao, phép cộng, phép nhân với một số thực. Tức là nếu C và D là hai tập lồi trong H thì các tập sau cũng là tập lồi. (i) C ∩D = {x : x ∈ C, x ∈ D}. (ii) αC + βD = {x = α.c+ β.d : c ∈ C, d ∈ D} . Định nghĩa 1.1.2. Tập C ⊆ H được gọi là nón nếu. ∀x ∈ C, ∀λ > 0⇒ λx ∈ C. Định nghĩa 1.1.3. Tập C ⊆ H được gọi là nón lồi nếu C vừa là nón vừa là tập lồi, tức là. λ1x+ λ2y ∈ C, ∀x, y ∈ C, ∀λ1 > 0, ∀λ2 > 0. Định nghĩa 1.1.4. Cho C ⊆ H là một tập lồi và x ∈ C, tập NC (x) = {w ∈ H, 〈w, y − x〉 ≤ 0, ∀y ∈ C} 2 được gọi là nón pháp tuyến ngoài của C và tập −NC (x) được gọi là nón pháp tuyến trong của C tại x. 1.1.2. Hàm lồi Định nghĩa 1.1.5. Hàm f : C → R ∪ {+∞} được gọi là (i) Lồi trên C nếu f [λx+ (1− λ) y] ≤ λf (x) + (1− λ) f (y) , ∀x, y ∈ C, 0 < λ < 1; (ii) Lồi chặt trên C nếu f [λx+ (1− λ) y] < λf (x)+(1− λ) f (y) , ∀x, y ∈ C, x 6= y, 0 < λ < 1; (iii) Lồi mạnh trên C với hệ số γ > 0 nếu f [λx+ (1− λ) y] < λf (x) + (1− λ) f (y)− γλ (1− λ) ‖x− y‖2, ∀x, y ∈ C, ∀λ ∈ (0, 1) ; (iv) Tựa lồi trên C nếu ∀α ∈ R tập mức dưới Lα (f) = {x ∈ C, f (x) ≤ α} . Định lý 1.1.2. Cho f là hàm lồi trên tập lồi C và g là hàm lồi trên tập lồi D. Khi đó các hàm số sau là hàm lồi trên tập lồi C ∩D. (i) αf + βg, ∀α, β ≥ 0; (ii) max {f, g} (x) = max {f (x) , g (x)} . Định lý 1.1.3. Cho f : C → R ∪ {+∞} là một hàm lồi, khả vi trên tập lồi C . Khi đó với mọi x, y thuộc C ta có: f (x)− f (y) ≤ 〈∇f (x) , y − x〉; Nếu f lồi chặt, khả vi trên tập lồi C, thì với mọi x, y thuộc C ta có: f (x)− f (y) < 〈∇f (x) , y − x〉; Nếu f lồi mạnh với hệ số α > 0 , khả vi trên tập lồi C, thì với mọi x, y thuộc C ta có: f (x)− f (y) ≤ 〈∇f (x) , y − x〉 − α‖x− y‖2. 3 Thang Long University Libraty Định nghĩa 1.1.6. Một hàm f : H → R được gọi là nửa liên tục dưới đối với C tại một điểm x, nếu như với mọi dãy { xk } ⊂ C, xk → x ta có lim inf f ( xk ) ≥ f (x). Hàm f được gọi là nửa liên tục trên đối với C tại x nếu −f nửa liên tục dưới đối với C tại x hay với mọi dãy { xk } ⊂ C, xk → x thì lim sup f ( xk ) ≤ f (x). Định nghĩa 1.1.7. Cho C là một tập lồi và f : C → R ∪ {+∞} là một hàm lồi, khi đó w ∈ C được gọi là dưới đạo hàm của f tại x nếu: f (y) ≥ f (x) + 〈w, y − x〉, ∀y ∈ C. Tập tất cả các điểm w thỏa mãn bất đẳng thức trên được kí hiệu là ∂f (x) . Nếu ∂f (x) 6= φ thì ta nói f khả dưới vi phân tại x 1.1.3. Toán tử chiếu lên một tập lồi đóng Định nghĩa 1.1.8. Giả sử C 6= ∅ (không nhất thiết lồi) là một tập con của không gian Hilbert −H và y ∈ H là một véc tơ bất kì, gọi dC (y) = inf x∈C ‖x− y‖ . Ta nói dC (y) là khoảng cách từ y đến C. Nếu tồn tại PC (y) ∈ C sao cho dC (y) = ‖y − PC (y)‖, thì ta nói PC (y) là hình chiếu của y trên C. Từ định nghĩa này hình chiếu PC (y) của y trên C là nghiệm của bài toán tối ưu min x∈C { 1 2 ‖x− y‖2 } . Nói cách khác, việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu của hàm ‖x− y‖2 trên C. Mệnh đề 1.1.1. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert −H, khi đó: với mọi y ∈ H và w ∈ C thì w = PC (y) khi và chỉ khi y − w ∈ NC (w) Chứng minh: Giả sử w = PC (y), lấy x ∈ C và λ ∈ (0, 1). Đặt xλ = λx+ (1− λ)w. Do x, w ∈ C và C lồi, nên xλ ∈ C. Hơn nữa do w là hình chiếu của y, nên ‖w − y‖ ≤ ‖y − xλ‖ . 4 hay ‖w − y‖2 ≤ ‖λ (x− w) + (w − y)‖2; ‖w − y‖2 ≤ λ2‖x− w‖2 + 2λ〈x− w,w − y〉 + ‖w − y‖2; λ‖x− w‖2 + 2〈x− w,w − y〉 ≥ 0. Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ tiến đến 0, ta được 〈w − y, x− w〉 ≥ 0∀x ∈ C. Vậy y − w ∈ NC (w). Ngược lại: Giả sử y − w ∈ NC (w), với mọi x ∈ C, ta có 0 ≥ (y − w)T (x− w) = (y − w)T (x− y + y − w) = ‖y − w‖2 + (y − w)T (x− y) Áp dụng bất đẳng thức Cauchy-Schwarz ta có: ‖y − w‖2 ≤ (y − w)T (y − x) ≤ ‖y − w‖ ‖y − x‖ . Suy ra ‖y − w‖ ≤ ‖y − x‖ ∀x ∈ C, do đó w = PC (y) . Mệnh đề 1.1.2. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert −H, khi đó với mọi x ∈ H, hình chiếu PC (x) của x trên C luôn tồn tại và duy nhất. Chứng minh: Giả sử x ∈ H, y ∈ C, y = PC (x) ta có dC (x) = ‖y − x‖, suy ra tồn tại dãy (xn)n∈N trong C sao cho ‖xn − x‖ → dC (x) < +∞. Vậy dãy (xn)n∈N là bị chặn do đó có một dãy con (xnk) hội tụ yếu đến y. Do C đóng nên y ∈ C vậy ‖y − x‖ = lim k ‖xnk − x‖ = limn ‖xn − x‖ = dC (x) . Chứng tỏ y là hình chiếu của x trên C. Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy nếu tồn tại hai điểm y và z đều là hình chiếu của x trên C thì x− y ∈ NC (y) , x− z ∈ NC (z) . Tức là 〈y − x, z − y〉 ≤ 0 5 Thang Long University Libraty và 〈z − x, y − z〉 ≤ 0. Cộng hai bất đẳng thức này ta suy ra ‖y − z‖ ≤ 0, và do đó y = z. Mệnh đề 1.1.3. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert −H, ánh xạ y →֒ PC (y) khi đó: (i) ‖PC (x)− PC (y)‖ ≤ ‖x− y‖ ∀x, y ∈ H (tính không giãn); (ii) ‖PC (x)− PC (y)‖ 2 ≤ 〈PC (x) − PC (y) , x − y〉∀x, y ∈ H (tính đồng bức). Chứng minh: Theo (ii) ánh xạ x →֒ PC (x) xác định khắp nơi. Do z − p (z) ∈ NC (p (z)) với mọi z. Nên áp dụng với z = x và z = y, ta có: 〈x− p (x) , p (y)− p (x)〉 ≤ 0; và 〈y − p (y) , p (x)− p (y)〉 ≤ 0. Cộng hai bất đẳng thức lại ta được 〈p (y)− p (x) , p (y)− p (x) + x− y〉 ≤ 0. Áp dụng bất đẳng thức Cauchy-Schwarz suy ra ‖p (x)− p (y)‖ ≤ ‖x− y‖ . Để chứng minh tính đồng bức áp dụng mệnh đề 1.3.1. lần lượt với p (x) và p (y) ta có: 〈p (x)− x, p (x)− p (y)〉 ≤ 0. 〈y − p (y) , p (x)− p (y)〉 ≤ 0. Cộng hai bất đẳng thức ta được 〈p (x)−p (y)+y−x, p (x)−p (y)〉 = 〈p (x)−p (y) , y−x〉+‖p (x)− p (y)‖2 ≤ 0. Chuyển vế ta có 〈p (x)− p (y) , x− y〉 ≥ ‖p (x)− p (y)‖2. 6 1.2. Bài toán cân bằng và các trường hợp riêng Cho f : C × C → R ∪ {+∞} thỏa mãn f (x, x) = 0, với mọi x ∈ C. C là tập lồi đóng khác rỗng trong không gian Hilbert −H. Khi đó bài toán cân bằng hay bất đẳng thức Ky Fan được phát biểu như sau: Tìm x∗ ∈ C : f (x∗, y) ≥ 0, ∀y ∈ C. (1.2.1) Bài toán cân bằng có ý nghĩa quan trọng trong kinh tế và nhiều lĩnh vực khác, nó bao hàm được rất nhiều bài toán khác như: bài toán tối ưu,bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán cân bằng Nash . . . Phần trình bày dưới đây là một số ví dụ về những bài toán có thể được mô tả dưới dạng bài toán cân bằng. 1.2.1. Bài toán tối ưu Cho C ⊂ H là tập lồi đóng khác rỗng và ϕ : C → R xác định trên C. Khi đó bài toán tối ưu được phát biểu như sau: Tìm x∗ ∈ C : ϕ (y) ≥ ϕ (x∗) , ∀y ∈ C. (1.2.2) Bằng cách đặt f (x, y) = ϕ (y)− ϕ (x) , ∀x, y ∈ C thì bài toán (1.2.2) tương đương với bài toán (1.2.1). Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.2). Nên ta có ϕ (y) ≥ ϕ (x∗) , ∀y ∈ C mặt khác theo cách đặt f (x, y) = ϕ (y)− ϕ (x) , ∀x, y ∈ C. Do đó f (x∗, y) = ϕ (y)− ϕ (x∗) ≥ 0, ∀x, y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.2.1). Ngược lại, cho x∗ ∈ C là nghiệm của bài toán (1.2.1), ta có f (x∗, y) ≥ 0, ∀y ∈ C. Mặt khác theo cách đặt ta có f (x∗, y) = ϕ (y)− ϕ (x∗) ≥ 0, ∀y ∈ C Suy ra ϕ (y) ≥ ϕ (x∗) , ∀y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.2.2). 7 Thang Long University Libraty 1.2.2. Bài toán bất đẳng thức biến phân Cho C ⊂ H là tập lồi đóng khác rỗng và F : C → R là một ánh xạ đa trị. Khi đó bài toán bất đẳng thức biến phân được phát biểu như sau. Tìm: { x∗ ∈ C,w∗ ∈ F (x∗) sao cho 〈w∗, y − x∗〉 ≥ 0, ∀y ∈ C. (1.2.3) Bằng cách đặt f (x, y) = max︸︷︷︸ w∈F (x) 〈w, y − x〉, ∀x, y ∈ C. thì bài toán (1.2.3) tương đương với bài toán (1.2.1). Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.3). Ta có 〈w∗, y − x∗〉 ≥ 0, ∀y ∈ C, w ∈ F (x∗) . Mặt khác theo cách đặt ta có f (x∗, y) = max︸︷︷︸ w∗∈F (x∗) 〈w∗, y − x∗〉 ≥ 0, y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.2.1). Ngược lại, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.1) nên ta có f (x∗, y) ≥ 0, ∀y ∈ C. Theo cách đặt ta có f (x∗, y) = max︸︷︷︸ w∗∈F (x∗) 〈w∗, y − x∗〉 ≥ 0, y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.2.3). Nếu F là ánh xạ đơn trị thì bài toán bất đẳng thức biến phân có dạng. Tìm { x∗ ∈ C sao cho 〈f (x∗) , y − x∗〉 ≥ 0, ∀y ∈ C. (1.2.4) Bằng cách đặt f (x, y) = 〈F (x) , y − x〉, ∀x, y ∈ C. Thì bài toán (1.2.4) tương đương với bài toán (1.2.1). 8 1.2.3. Bài toán điểm bất động Cho C ⊂ H là tập lồi đóng khác rỗng và F : C → 2C là ánh xạ đa trị. Khi đó bài toán điểm bất động được phát biểu như sau, tìm x∗ ∈ C, sao cho x∗ ∈ F (x∗) . (1.2.5) Bằng cách đặt f (x, y) = max︸︷︷︸ w∈F (x) 〈x− w, y − x〉, ∀x, y ∈ C. Thì bài toán (1.2.5) tương đương với bài toán (1.2.1). Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.5) nên ta có F (x∗) = x∗. Mặt khác theo cách đặt ta có f (x∗, y) = 〈x∗ − F (x∗) , y − x∗〉 ≥ 0, ∀y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.2.1). Ngược lại, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.1) nên ta có f (x∗, y) ≥ 0, ∀y ∈ C. Mặt khác theo cách đặt ta được f (x∗, y) = 〈x∗ − F (x∗) , y − x∗〉, ∀y ∈ C. Chọn y = F (x∗) ∈ C ta có f (x∗, y) = 〈x∗ − F (x∗) , F (x∗)− x∗〉 ≥ 0, ∀y ∈ C. Suy ra −‖x∗ − F (x∗)‖ ≥ 0, ∀y ∈ C. Hay ‖x∗ − F (x∗)‖ ≤ 0, ∀y ∈ C. Suy ra x∗ = F (x∗) , ∀y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.2.5). Nếu F là ánh xạ đơn trị thì bài toán điểm bất động có dạng. Tìm: x∗ ∈ C, saocho x∗ = F (x∗) . (1.2.6) Bằng cách đặt f (x, y) = 〈x− F (x) , y − x〉, ∀x, y ∈ C. Thì bài toán (1.2.6) tương đương với bài toán (1.2.1). 9 Thang Long University Libraty 1.2.4. Bài toán cân bằng Nash trong trò chơi không hợp tác Xét một trò chơi không hợp tác gồm p đối thủ, C ⊆ H là tập lồi khác rỗng, Ci là tập chiến lược của người chơi thứ i. Hàm chi phí( tổn thất của người chơi thứ i) là fi : C1 × C2 × ...× Cp → R. Với C = C1 × C2 × ...× Cp; x1 ∈ C1, x2 ∈ C2, ..., xp ∈ Cp. Thì chi phí của mỗi đối thủ tương ứng là f1 (x1, x2, ..., xp) , f2 (x1, x2, ..., xp) , ..., fp (x1, x2, ..., xp) ; x = (x1, x2, ..., xp) . Khi đó bài toán cân bằng Nash được phát biểu như sau. Tìm:  x∗ ∈ C sao cho fi (x ∗) ≤ fi (x ∗ [yi]) ⇔ fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., xp ) ≤ fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., xp ) ∀yi ∈ Ci, ∀i = 1, 2, ..., p (1.2.7) Điểm x∗ ∈ C được gọi là điểm cân bằng Nash nếu bất kì đối thủ nào chọn phương án ra khỏi điểm cân bằng trong khi các đối thủ còn lại vẫn giữ phương án điểm cân bằng thì đối thủ ra khỏi điểm cân bằng sẽ bị thua thiệt. Bằng cách đặt f (x, y) = p∑ i=1 [fi (x1, ..., yi, ..., xp)− fi (x1, ..., xi, ..., xp)] , ∀x, y ∈ C. Thì bài toán (1.2.7) tương đương với bài toán (1.2.1). Thật vậy, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.7) nên ta có fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., x ∗ p ) ≤ fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., x ∗ p ) , ∀xi, yi ∈ Ci, ∀i = 1, 2, ..., p. Suy ra fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., x ∗ p ) − fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., x ∗ p ) ≥ 0, ∀xi, yi ∈ Ci, ∀i = 1, 2, ..., p. 10 Suy ra p∑ i=1 [ fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., x ∗ p ) − fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., x ∗ p )] ≥ 0. Theo cách đặt ta được f (x∗, y) ≥ 0, ∀y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.2.1). Ngược lại, giả sử x∗ ∈ C là nghiệm của bài toán (1.2.1) nên ta có f (x∗, y) ≥ 0, ∀y ∈ C. Theo cách đặt ta được  p∑ i=1 [ fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., xp ) − fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., xp )] ≥ 0, ∀xi, yi ∈ Ci, ∀i = 1, 2, ..., p. (1.2.8) Giả sử x∗ ∈ C không là nghiệm của bài toán (1.2.7) nên tồn tại i và một yi ∈ Ci sao cho fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., x ∗ p ) > fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., x ∗ p ) . Suy ra fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., x ∗ p ) − fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., x ∗ p ) < 0. Suy ra p∑ i=1 fi ( x∗1, ..., x ∗ i−1, yi, x ∗ i−1, ..., x ∗ p ) − fi ( x∗1, ..., x ∗ i−1, x ∗ i , x ∗ i−1, ..., x ∗ p ) < 0. Điều này trái với (1.2.8). Vậy x∗ ∈ C là nghiệm của bài toán (1.2.7). 1.3. Sự tồn tại nghiệm của bài toán cân bằng C ⊆ H là một tập lồi đóng, khác rỗng và f : C × C → R ∪ {+∞} là song hàm cân bằng xác định trên C, với các giả thiết sau: (P1) f (., y) là hàm số nửa liên tục trên với mọi y thuộc C; (P2) f (x, .) là hàm lồi, nửa liên tục dưới và khả dưới vi phân trên C với mọi x thuộc C; 11 Thang Long University Libraty (P3) f thỏa mãn điều kiện bức trên C tức là tồn tại tập compact D sao cho C ∩D 6= ∅, ∀x ∈ C\D, ∃y ∈ C; f (x, y) < 0. Định lý 1.3.1. (Ky Fan) Giả sử C là một tập lồi đóng khác rỗng trong không gian Hilbert −H và f : C × C → R ∪ {+∞} là song hàm cân bằng xác định trên C. Nếu f thỏa mãn (P1) và f (x, .) tựa lồi trên C với mọi x thuộc C. Khi đó nếu C là tập compact hoặc điều kiện bức (P3) được thỏa mãn thì bài toán (1.2.1) có nghiệm. Từ định lí này ta suy ra hệ quả sau. Hệ quả 1.3.1. Cho f : C × C → R ∪ {+∞} là song hàm cân bằng , f (., y) là nửa liên tục trên với mọi y ∈ C và f (x, .) là lồi, nửa liên tục dưới với mọi x ∈ C. Giả sử điều kiện bức sau đây thỏa mãn. Tồn tại tập compact B sao cho C ∩B 6= ∅, ∀x ∈ C\B, ∃y ∈ C : f (x, y) < 0. Khi đó bài toán (1.2.1) có nghiệm. Để xét tính duy nhất nghiệm và các phương pháp tìm nghiệm của bài toán (1.2.1) ta cần có các định nghĩa về tính đơn điệu của song hàm cân bằng sau. Định nghĩa 1.3.1. Giả sử f : C × C → R ∪ {+∞} là song hàm cân bằng. Khi đó hàm f được gọi là : (i) đơn điệu mạnh trên C với hệ số λ > 0, nếu: f (x, y) + f (y, x) ≤ −λ‖x− y‖2, ∀x, y ∈ C; (ii) đơn điệu chặt trên C, nếu: f (x, y) + f (y, x) < 0, ∀x, y ∈ C; (iii) đơn điệu trên C, nếu: f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; (iv) giả đơn điệu trên C, nếu: f (x, y) ≥ 0⇒ f (y, x) ≤ 0, ∀x, y ∈ C; 12 (v) giả đơn điệu mạnh trên C với hệ số λ > 0, nếu: f (x, y) ≥ 0⇒ f (y, x) ≤ −λ‖x− y‖2, ∀x, y ∈ C; (vi) tựa đơn điệu trên C, nếu: f (x, y) > 0⇒ f (y, x) ≤ 0, ∀x, y ∈ C. Từ định nghĩa trên ta có đơn điệu mạnh thì đơn điệu và giả đơn điệu, đơn điệu thì giả đơn điệu. Tính chất đơn điệu của song hàm có liên quan chặt chẽ với tính chất đơn điệu của toán tử sau. Định nghĩa 1.3.2. Cho C ∈ H và toán tử A : C → R được gọi là: (i) đơn điệu mạnh trên C với hệ số λ > 0, nếu: 〈A (x)− A (y) , x− y〉 ≥ λ‖x− y‖2, ∀x, y ∈ C; (ii) đơn điệu chặt trên C, nếu: 〈A (x)− A (y) , x− y〉 > 0, ∀x, y ∈ C, x 6= y; (iii) đơn điệu trên C, nếu: 〈A (x)− A (y) , x− y〉 ≥ 0, ∀x, y ∈ C; (iv) giả đơn điệu trên C,nếu: 〈A (x) , x− y〉 ≥ 0⇒ 〈A (y) , x− y〉 ≥ 0, ∀x, y ∈ C; (v) giả đơn điệu mạnh trên C, nếu: 〈A (x) , x− y〉 ≥ 0⇒ 〈A (y) , x− y〉 ≥ λ‖x− y‖2, ∀x, y ∈ C; (vi) tựa đơn điệu trên C, nếu: 〈A (x) , x− y〉 > 0⇒ 〈A (y) , x− y〉 ≥ 0, ∀x, y ∈ C. Định lý 1.3.2. Cho C ⊂ H là một tập lồi đóng khác rỗng và f : C×C → R ∪ {+∞} là song hàm cân bằng giả đơn điệu mạnh thỏa mãn các tính chất (P1), (P2). Khi đó bài toán (1.2.1) có duy nhất nghiệm. 13 Thang Long University Libraty Chứng minh: Giả sử C không bị chặn. Khi đó nó thỏa mãn điều kiện bức sau: Tồn tại hình cầu đóng B sao cho ∀x ∈ C\B, ∃y ∈ C ∩B : f (x, y) < 0. Thật vậy, với bất kì hình cầu đóng Br với tâm 0 và bán kính r, xr ∈ C\Br sao cho f (x, y) ≥ 0, ∀y ∈ C ∩Br. (1.3.9) r0 > 0 cố định, khi đó với mỗi r > r0, tồn tại xr ∈ C\Br sao cho f ( xr, y0 ) ≥ 0, ∀y0 ∈ C ∩Br0. Do f giả đơn điệu mạnh với tham số λ, nên ta có f ( y0, xr ) + λ ∥∥xr − y0∥∥2 ≤ 0, ∀r. (1.3.10) Mặt khác, Tập C lồi và f ( y0, . ) là lồi trên C. Theo tính lồi tồn tại x0 ∈ C sao cho ∂2f ( y0, x0 ) 6= ∅, ở đây ∂2f ( y0, x0 ) là dưới vi phân của hàm lồi f ( y0, . ) tại điểm x0. Đặt w∗ ∈ ∂2f ( y0, x0 ) là dưới gradient được định nghĩa bởi 〈w∗, x− x0〉 + f ( y0, x0 ) ≤ f ( y0, x ) , ∀x. Với x = xr ta có f ( y0, x ) + λ ∥∥xr − y0∥∥2 ≥ f (y0, x0)+ 〈w∗, xr − x0〉+ λ∥∥xr − y0∥∥2 ≥ f ( y0, x0 ) + ‖w∗‖ ∥∥xr − x0∥∥+ λ∥∥xr − y0∥∥2. Cho r tiến ra ∞, thì ‖xr‖ → ∞ ta được f ( y0, x0 ) + λ ∥∥xr − y0∥∥2 →∞. Điều này mâu thuẫn với (1.3.10). Vậy điều kiện bức (1.3.9) được thỏa mãn, khi đó theo hệ quả 1.3.1 thì bài toán (1.2.1) có nghiệm duy nhất. Trường hợp C là Compact, thì chứng minh được suy ra bằng định lý Ky Fan. Để chứng minh tính duy nhất ta giả sử ngược lại là bài toán có hai nghiệm là x∗ và y∗. Khi đó f (x∗, y∗) ≥ 0 Và f (y∗, x∗) ≥ 0 14 Theo tính giả đơn điệu mạnh, từ f (x∗, y∗) ≥ 0, suy ra f (y∗, x∗) ≤ −λ‖x∗ − y∗‖2 Tương tự, ta có f (y∗, x∗) ≥ 0, suy ra f (x∗, y∗) ≤ −λ‖x∗ − y∗‖2. Vì λ > 0 và ‖x∗ − y∗‖2 ≥ 0, nên suy ra f (x∗, y∗) = f (y∗, x∗) = 0, suy ra x∗ = y∗. 15 Thang Long University Libraty Chương 2 HAI THUẬT TOÁN GIẢI BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU MẠNH VÀ ÁP DỤNG Trong chương này, tôi trình bày hai thuật toán giải bài toán cân bằng giả đơn điệu mạnh trên tập nghiệm của nó. Qua đó chứng minh tính đúng đắn và sự hội tụ của thuật toán và đưa vào áp dụng mô hình kinh tế thị trường điện. Nội dung của chương này được lấy từ [5], [6], [7]. 2.1. Thuật toán và sự hội tụ Để tìm được tập nghiệm của bài toán cân bằng trong chương này ta sử dụng các giả thiết sau với song hàm cân bằng f : C × C → R có các tính chất sau: (P1) f (., y) là hàm số nửa liên tục trên với mọi y thuộc C; (P2) f (x, .) là hàm lồi, nửa liên tục dưới và khả dưới vi phân trên C với mọi x thuộc C. Mệnh đề 2.1.1. Giả sử f : C × C → R là song hàm cân bằng. Khi đó với các giả thiết (P1) , (P2), thì các điều kiện sau đây là tương đương. (i) x∗ là nghiệm của bài toán (1.2.1) (ii) min {g (x) : x ∈ C} = 0, trong đó hàm g được cho bởi g (x) = sup {f (x, y) : y ∈ C} ; (iii) x∗ = argmin {f (x∗, y) : y ∈ C} . 16 Chứng minh: Từ (i)⇒ (ii). Giả sử x∗ là nghiệm của bài toán (1.2.1), do f (x, x) = 0, ∀x ∈ C Nên inf f (x, y) ≤ 0, ∀x ∈ C. Do đó sup︸︷︷︸ x∈C   inf︸︷︷︸ y∈C f (x, y)   ≤ 0. Mặt khác x∗ ∈ C nên sup︸︷︷︸ x∈C   inf︸︷︷︸ y∈C f (x, y)   ≥ inf︸︷︷︸ y∈C f (x∗, y) . Nhưng do x∗ là nghiệm của bài toán (1.2.1) nên f (x∗, y) ≥ 0, ∀y ∈ C. Vậy inf︸︷︷︸ y∈C f (x∗, y) ≥ 0. Suy ra 0 ≤ inf︸︷︷︸ y∈C f (x∗, y) ≤ sup︸︷︷︸ x∈C   inf︸︷︷︸ y∈C f (x, y)   ≤ 0. Vậy sup︸︷︷︸ x∈C   inf︸︷︷︸ y∈C f (x, y)   = max   inf︸︷︷︸ y∈C f (x, y)   = inf︸︷︷︸ y∈C f (x∗, y) = 0. Ngược lại, giả sử có (ii). Khi đó theo lập luận ở trên ta có sup︸︷︷︸ y∈C {−f (x∗, y)} = min︸︷︷︸ x∈C sup︸︷︷︸ y∈C {−f (x∗, y)} = 0. Chứng tỏ −f (x∗, y) ≤ 0, ∀y ∈ C. Hay f (x∗, y) ≥ 0, ∀y ∈ C. 17 Thang Long University Libraty Vậy x∗ là nghiệm của bài toán (1.2.1). Bây giờ ta chứng tỏ (i) tương đương với (iii). Thật vậy x∗ là cực tiểu của f (x∗, .) trên C khi và chỉ khi f (x∗, y) ≥ f (x∗, x∗) = 0, ∀y ∈ C. Mệnh đề 2.1.2. Giả sử f giả đơn điệu mạnh trên C với hệ số λ và thỏa mãn điều kiện kiểu Lipschitz, theo nghĩa sau:{ ∃L1 > 0, L2 > 0 : ∀x, y, z ∈ C, ta có f (x, y) + f (y, z) ≥ f (x, z)− L1‖x− y‖ 2 − L2‖y − z‖ 2 . Khi đó với bất kì x0 ∈ C, dãy { xk } được xác định theo công thức xk+1 = s ( xk ) = arg min︸︷︷︸ y∈C { ρf ( xk, y ) + 1 2 ∥∥y − xk∥∥2 } . (2.1.1) Có tính chất ∥∥xk+1 − x∗∥∥2 ≤ α∥∥xk − x∗∥∥2, ∀k ≥ 0. Nếu như 0 < ρ ≤ 1 2L2 , trong đó x∗ là nghiệm duy nhất của bài toán (1.2.1) và α = 1− 2ρ (λ− L1) . Chứng minh: Đặt fk (x) = ρf ( xk, x ) + 1 2 ∥∥x− xk∥∥2, ∀k ≥ 0. Do f ( xk, . ) lồi, nên hàm fk lồi mạnh trên C với hệ số 1. Vậy fk ( xk+1 ) + + 1 2 ∥∥x− xk+1∥∥2 ≤ fk (x) , ∀x ∈ C. (2.1.2) Trong đó wk ∈ ∂fk ( xk+1 ) . Do xk+1 là nghiệm của bài toán (2.1.1) , nên 〈wk, x− xk+1〉 ≥ 0, ∀x ∈ C. Từ (2.1.2) ta có fk ( xk+1 ) + 1 2 ∥∥x− xk+1∥∥2 ≤ fk (x) , ∀x ∈ C. (2.1.3) Thay x = x∗ trong (2.1.3) theo định nghĩa fk ta được∥∥xk+1 − x∥∥2 ≤ 2ρ [f (xk, x∗)− f (xk, xk+1)]+∥∥xk − x∗∥∥2−∥∥xk+1 − xk∥∥2. (2.1.4) 18 Do f giả đơn điệu mạnh với hệ số λ nên f ( xk, x∗ ) ≤ −f ( x∗, xk ) − λ ∥∥xk − x∗∥∥2. Thay vào (2.1.4) ta có∥∥xk+1 − x∗∥∥2 ≤ (1− 2ρλ) ∥∥xk − x∗∥∥2+ +2ρ [ −f ( x∗, xk ) − f ( xk, xk+1 )] − ∥∥xk+1 − xk∥∥2. Áp dụng tính Lipschitz với x = x∗, y = xk, z = xk+1 ta được −f ( xk, xk+1 ) − f ( x∗, xk ) ≤ −f ( x∗, xk+1 ) + L1 ∥∥x∗ − xk∥∥2 + L2∥∥xk − xk+1∥∥2 ≤ L1 ∥∥x∗ − xk∥∥2 + L2∥∥xk − xk+1∥∥2. Thay vào ta được∥∥xk+1 − x∗∥∥2 ≤ [1− 2ρ (λ− L1)] ∥∥xk − x∗∥∥2 − (1− 2ρL2) ∥∥xk+1 − xk∥∥2. Theo giả thiết 0 < ρ ≤ 1 2L2 nên ta có ∥∥xk+1 − x∗∥∥2 ≤ [1− 2ρ (λ− L1)] ∥∥xk − x∗∥∥2. Vậy mệnh đề được chứng minh. Hệ quả 2.1.1. Nếu L1 < λ và 0 < ρ ≤ 1 2L2 khi đó ∥∥xk+1 − x∗∥∥ ≤ r ∥∥xk − x∗∥∥ , ∀k ≥ 0. Trong đó 0 < r = √ 1− 2ρ (λ− L1) < 1. Nhận xét: Do λ ≤ L1+L2 và 0 < ρ ≤ 1 2L2 , nên ta có 2ρ (λ− L1) < 1. Vậy r đạt giá trị nhỏ nhất tại ρ = 1 2L2 . Nếu xk = xk+1, thì xk là nghiệm, do đó ta gọi một điểm x ∈ C là nghiệm τ − xấp xỉ của bài toán (1.2.1) nếu ‖x− x∗‖ ≤ τ , trong đó xk là nghiệm chính xác của bài toán (1.2.1). Dựa vào mệnh đề và hệ quả trên ta có thuật toán sau để giải bài toán cân bằng giả đơn điệu mạnh. 2.1.1. Thuật toán 1 Bước khởi tạo: Chọn sai số τ ≥ 0 và 0 < ρ ≤ 1 2L2 , lấy x0 ∈ C Bước lặp thứ k: k = (0, 1, 2, ...) 19 Thang Long University Libraty Tính xk+1 bằng cách giải bài toán quy hoạch lồi mạnh xk+1 = arg min︸︷︷︸ y∈C { ρf ( xk, y ) + 1 2 ∥∥y − xk∥∥2 } . (a) Nếu ∥∥xk+1 − xk∥∥ ≤ τ (1− r) r , với r = √ 1− 2ρ (λ− L1), thì dừng: xk+1 là một nghiệm τ − xấp xỉ của bài toán (1.2.1). (b) Trái lại chuyển sang bước lặp thứ k với k được thay bằng k + 1. Chú ý: Do ∥∥xk+1 − x∗∥∥ ≤ r ∥∥xk − x∗∥∥ với r < 1, ta có ∥∥xk+1 − x∗∥∥ ≤ ( r 1− r )∥∥xk+1 − xk∥∥ , ∀k ≥ 0. Do đó ∥∥xk+1 − x∗∥∥ ≤ ( rk+1 1− r )∥∥x0 − x1∥∥ , ∀k ≥ 0. Có xk+1 → x∗ khi k →∞ Vậy, nếu ∥∥xk+1 − x∗∥∥ ≤ τ (1− r) r hoặc rk+1 1− r ∥∥x0 − x1∥∥ ≤ τ thì∥∥xk+1 − x∗∥∥ ≤ τ . Trong trường hợp này ta được một nghiệm τ − xấp xỉ của bài toán. Dưới đây ta sẽ trình bày một phương pháp dựa vào toán tử chiếu để giải bài toán cân bằng giả đơn điệu mạnh không cần điều kiện Lipschitz. 2.1.2. Thuật toán 2 Bước khởi tạo: Chọn các dãy số {ak} ⊂ (0, 1) sao cho ∞∑ k=0 ak = ∞; ∞∑ k=0 a2k <∞, ak = 1 k + 1 , lấy x0 ∈ C. Bước 1: Chọn wk sao cho ρf ( xk, y ) + 〈wk, y − xk〉 ≥ 0,∀y ∈ C, trong đó ρ > 0 là tham số hiệu chỉnh. (a) Nếu wk = 0, và ρk ≤ τ thì dừng thuật toán: xk là τ − nghiệm của bài toán. 20 (b) nếu wk 6= 0, chuyển qua bước 2. Bước 2: Đặt zk+1 = xk + akwk và xk+1 = PC ( zk+1 ) , trong đó PC là toán tử chiếu lên C. Nếu xk+1 = xk thì dừng thuật toán: xk là nghiệm của bài toán (1.2.1). Trái lại, quay lại bước 1 với k = k + 1. Chú ý: Bài toán toán chính phải giải trong thuật toán trên là bài toán tìm wk ở bước 1. Để tìm wk ta có thể giải như sau: (i) Giả sử bài toán quy hoạch lồi:min︸︷︷︸ y∈C f ( xk, y ) có nghiệm. bằng cách đặt mk = − min︸︷︷︸ y∈C f ( xk, y ) < +∞. Chọn wk sao cho 〈wk, y − xk〉 ≥ ρmk,∀y ∈ C. Khi đó wk là điểm cần tìm ở bước 1 của thuật toán trên. (ii) Do f (x, .) lồi, khả dưới vi phân trên C, nên với mọi y thuộc C, gk ∈ ∂2f ( xk, xk ) , ta có f ( xk, y ) − f ( xk, xk ) ≥ 〈gk, y − xk〉. Vì f ( xk, xk ) = 0 nên ta thấy wk = −ρ−1gk thỏa mãn bất đẳng thức ρf ( xk, y ) + 〈wk, y − xk〉 ≥ 0, ∀y ∈ C. Do đó wk là điểm cần tìm. 2.1.3. Sự hội tụ của thuật toán Để chứng minh sự hội tụ của thuật toán, ta cần đến bổ đề sau: Bổ đề 2.1.1. Giả sử {ak}∞0 là một dãy vô hạn không âm thỏa mãn ak+1 ≤ ak + σk, ∀k với ∞∑ k=0 σk <∞. Khi đó dãy {ak} hội tụ. Định lý 2.1.1. Giả sử f giả đơn điệu mạnh trên C với hệ số λ và { xk } là dãy được tạo ra bởi Thuật toán 2. Khi đó ta có∥∥xk+1 − x∗∥∥2 ≤ (1− 2ρλak) ∥∥xk − x∗∥∥2 + a2k∥∥wk∥∥2, ∀k ≥ 0, 21 Thang Long University Libraty trong đó x∗ là nghiệm duy nhất của bài toán (1.2.1). Hơn nữa, nếu 0 < ρ ≤ 1 2λ và dãy wk bị chặn thì x∗ hội tụ đến nghiệm x∗ của bài toán (1.2.1). Chứng minh: Giả sử x∗ là nghiệm duy nhất của bài toán (1.2.1). Thay zk+1 = xk + akw k Ta được∥∥xk+1 − x∗∥∥2 = ∥∥xk + akwk − x∗∥∥2 = ∥∥xk − x∗∥∥2+2ak〈wk, xk−x∗〉+a2k∥∥wk∥∥2. (2.1.5) Với y = x∗ ta có ρf ( xk, x∗ ) ≥ 〈wk, xk − x∗〉. (2.1.6) Vì f giả đơn điệu mạnh trên C với hệ số λ và x∗ là nghiệm của bài toán (1.2.1), nên ρf ( xk, x∗ ) ≤ −ρλ ∥∥xk − x∗∥∥2 − ρf (x∗, xk) ≤ −ρλ∥∥xk − x∗∥∥2. (2.1.7) Từ (2.1.5), (2.1.6), (2.1.7) suy ra∥∥zk+1 − x∗∥∥2 ≤ (1− 2ρλak) ∥∥xk − x∗∥∥2 + a2k∥∥wk∥∥2. (2.1.8) Mặt khác do xk+1 = PC ( zk+1 ) , nên theo tính chất của toán tử chiếu ta có ∥∥xk+1 − x∗∥∥2 ≤ ∥∥zk+1 − x∗∥∥2. (2.1.9) Từ (2.1.8), (2.1.9) ta có∥∥xk+1 − x∗∥∥2 ≤ (1− 2ρλak) ∥∥xk − x∗∥∥2 + a2k∥∥wk∥∥2. Để chứng tỏ lim k→∞ xk = x∗ ta giả sử dãy { wk } bị chặn. Theo Định lí 2.1.1 ta được ∥∥xk+1 − x∗∥∥2 ≤ (1− 2ρλak) ∥∥xk − x∗∥∥2 + a2kM ≤ ∥∥xk − x∗∥∥2 + a2kM, ∀k ≥ 0. (2.1.10) Với M > 0 là một hằng số. Do ∞∑ k=0 ak = +∞; ∞∑ k=0 a2k < +∞. 22 Nên từ (2.1.10) theo Bổ đề 2.1.1 ta có ∥∥xk+1 − x∗∥∥ hội tụ khi k → +∞. Vậy { xk+1 } bị chặn, do đó tồn tại một dãy con { xkj } hội tụ đến x với x là nghiệm của bài toán cân bằng. Tương tự như trên ta chứng minh được ∥∥xkj − x∥∥ hội tụ, nhưng do xkj → x nên ∥∥xkj − x∥∥→ 0 do đó ∥∥xk+1 − x∗∥∥→ 0 khi k → +∞. Vậy định lí được chứng minh. 2.2. Áp dụng vào mô hình cân bằng thị trường điện Giả sử có nc công ty sản xuất điện, công ty thứ i (i = 1, 2, ..., nc) sở hữu Ii nhà máy phát điện. Gọi x là véc tơ có các thành phần là xi (i = 1, 2, ..., n g) với ng là tổng số tất cả các nhà máy phát điện và xi là lượng điện năng được sản xuất bởi nhà máy phát điện thứ i. Giả sử giá điện p là một hàm affine của σ với σ = ng∑ i=1 xi là tổng điện năng sản xuất được của tất cả các nhà máy phát điện, cụ thể là: p (x) = a0 − 2 ng∑ i=1 xi = p (σ) . Ở đây a0 > 0 là một hằng số(rất lớn). Khi đó lợi nhuận của công ty thứ i được cho bởi fi (x) = p (σ) ∑ j∈Ii xj − ∑ j∈Ii cj (xj). Với cj (xj) là chi phí của nhà máy thứ j khi sản xuất lượng điện năng ở mức xj. Ta giả sử hàm chi phí cj (xj) được cho bởi cj (xj) = max { c0j (xj) , c 1 j (xj) } . Với c0j (xj) = α0j 2 x2j + β 0 jxj + γ 0 j , c 1 j (xj) = α 1 jxj + β0j β1j + 1 γ −1/β1j j (xj) (β1j+1)/β1j , trong đó: αkj , βkj , γkj là các tham số cho trước. Gọi xminj và xmaxj tương ứng là lượng điện năng nhỏ nhất và lớn nhất có thể sản xuất được bởi nhà máy phát điện thứ j. Khi đó tập chiến lược của mô hình được xác định như sau C = { x = (x1, ..., xng) T : xminj ≤ xj ≤ x max j , ∀j = 1, 2, ..., n g } . 23 Thang Long University Libraty Ta định nghĩa ma trận A,B như sau: A = 2 nc∑ i=1 ( 1− qi )( qi )T , B = 2 nc∑ i=1 qi ( qi )T , trong đó qi = ( qi1, ..., q i ng )T với qij = { 1 nếu j ∈ Ii 0 trong các trường hợp khác và a = −a0 nc∑ i=1 qi, c (x) = ng∑ j=1 cj (xj). Khi đó mô hình bài toán trên có thể đưa về bài toán cân bằng như sau:  x ∈ C sao cho f (x, y) = (( A+ 3 2 B ) x+ 1 2 By + a )T (y − x) + c (y)− c (x) ≥ 0, ∀y ∈ C. Lưu ý f (x, y) + f (y, x) = −(y − x)T (A +B) (y − x)T . Vậy, do A + B không xác định dương, f có thể không đơn điệu trên C. Tuy nhiên nếu chúng ta thay f bởi f được định nghĩa như sau. f (x, y) = f (x, y)− 1 2 (y − x)TB (y − x) , thì f là giả đơn điệu mạnh trên C. Thực ra ta có f (x, y) + f (y, x) = −(y − x)T (A + 2B) (y − x) . Vậy, nếu f (x, y) ≥ 0 thì f (y, x) ≤ −(y − x)T (A+ 2B) (y − x) ≤ −λ‖y − x‖2, với mọiλ > 0. Bổ đề sau đây là hệ quả trực tiếp của nguyên tắc trên. Bổ đề 2.2.1. Bài toán cân bằng Tìm x∗ ∈ C : f (x∗, y) ≥ 0, ∀y ∈ C. tương đương với bài toán cân bằng Tìm x∗ ∈ C : f (x∗, y) + 1 2 (y − x∗)TB (y − x∗) ≥ 0, ∀y ∈ C. (2.2.11) Nghĩa là chúng có họ nghiệm trùng nhau. 24 Từ bổ đề trên ta có thể áp dụng thuật toán trên để giải bài toán cân bằng (2.2.11). Ta minh họa thuật toán cho vấn đề này ở ví dụ sau đây. Ví dụ 1: Nhà máy thủy điện và nhiệt điện có hàm chi phí lần lượt là c (y1) = 10y1, c (y2) = 30y2. Giá bán điện là p = 120 − Q, trong đó Q là tổng sản lượng điện của hai nhà máy. Hãy tìm điểm cân bằng Nash trong mô hình trên. Giải: Ta có lợi nhuận của các nhà máy lần lượt là: Nhà máy thủy điện π1 = y1 (120− y1 − y2)− 10y1 Nhà máy nhiệt điện π2 = y2 (120− y1 − y2)− 30y2 Nhận thấy hàm lợi nhuận là một hàm hai biến y1, y2. Do đó ta lấy đạo hàm của hàm lợi nhuận theo từng biến và cho bằng không ta được. π1 ′ = 120− 2y1 − y2 − 10 = 0. Hay 2y1 = 110− y2. Suy ra y1 = 110− y2 2 . Tương tự π2 ′ = 120− 2y2 − y1 − 30 = 0. Hay 2y2 = 90− y1. Suy ra y2 = 90− y1 2 . Ta đặt y1 = f1 (y2) = 110− y2 2 ; y2 = f2 (y1) = 90− y1 2 . Lần lượt là hàm sản lượng của mỗi nhà máy. Khi đó ta có biểu đồ sau. 25 Thang Long University Libraty by2 b O by1 b110 b 55 y1 = f1 (y2) Hình 2.1: Sản lượng tốt nhất của nhà máy thủy điện đối với nhà máy nhiệt điện by2 b O b y1 b45 b 90 y2 = f2 (y1) Hình 2.2: Sản lượng tốt nhất của nhà máy nhiệt điện đối với nhà máy thủy điện 26 by2 b O b y1 b45 b 90 y2 = f2 (y1) b110 b 55 y1 = f1 (y2) b Hình 2.3: Sản lượng tốt nhất của hai nhà máy Bây giờ ta cần phải tìm điểm (y1, y2) thuộc cả hai hàm số trên. Ta có y1 = 110− y2 2 và y2 = 90− y1 2 Suy ra y1 = 110− 90− y1 2 2 ⇔ 2y1 = 220− 90 + y1 2 Vậy y1 = 130 3 ⇒ y2 = 90− 130 3 2 = 70 3 Khi đó ta tìm được một điểm cân bằng Nash duy nhất trong đó sản lượng của nhà máy thủy điện là y1 = 130 3 và nhà máy nhiệt điện là y2 = 70 3 . Và Lợi nhuận của mỗi nhà máy là π1 = 130 3 ( 120− 130 3 − 70 3 ) − 10. 130 3 = 16900 9 ; π2 = 70 3 ( 120− 130 3 − 70 3 ) − 30. 70 3 = 4900 9 . Ví dụ 2: Nhà máy điện A và B có hàm chi phí là c (x1) = lnx1, c (x2) = lnx2. Giá bán điện là p = 10 − 1 2 Q , trong đó Q là tổng sản lượng điện của hai nhà máy. Dùng thuật toán 2 để tìm điểm cân bằng Nash trong mô hình trên. 27 Thang Long University Libraty Giải: Ta có lợi nhuận của các nhà máy lần lượt là: Nhà máy điện A f1 (x1, x2) = x1 [ 10− 1 2 (x1 + x2) ] − lnx1 (2.2.12) Nhà máy điện B f2 (x1, x2) = x2 [ 10− 1 2 (x1 + x2) ] − lnx2 (2.2.13) Tập C1 = [5, 100] tức là 5 ≤ x1 ≤ 100 Tập C2 = [10, 100] tức là 10 ≤ x2 ≤ 100 Lấy hàm: f (x, y) = f (x1, x2, y1, y2) f (x1, x2; y1, y2) = f1 (y1, x2)− f1 (x1, x2) + f2 (x1, y2)− f2 (x1, x2) Ở đây f1 được cho bởi (2.2.12) và f2 được cho bởi (2.2.13), C = C1×C2. Áp dụng thuật toán 2: Ta có: f (x, y) = y1 [ 10− 1 2 (y1 + x2) ] − lny1 − x1 [ 10− 1 2 (x1 + x2) ] + lnx1+ +y2 [ 10− 1 2 (x1 + y2) ] − lny2 − x2 [ 10− 1 2 (x1 + x2) ] + lnx2 f (x, y) = − 1 2 y21 + ( 10− 1 2 x2 ) y1 − lny1 − 1 2 y22 + ( 10− 1 2 x1 ) y2 − lny2+ + 1 2 x21 − 10x1 + x1x2 + lnx1 + 1 2 x22 − 10x2 + lnx2 Ta có q1 = ( q11 q12 ) = ( 1 0 ) và q2 = ( q21 q22 ) = ( 0 1 ) 1− q1 = ( 1 1 ) − ( 1 0 ) = ( 0 1 ) và 1− q2 = ( 1 1 ) − ( 0 1 ) = ( 1 0 ) A = 2 [( 0 1 )( 1 0 ) + ( 1 0 )( 0 1 )] = ( 0 2 2 0 ) B = 2 [( 1 0 )( 1 0 ) + ( 0 1 )( 0 1 )] = ( 2 0 0 2 ) Lại có y = ( y1 y2 ) , x = ( x1 x2 ) 28 Suy ra y − x = ( y1 y2 ) − ( x1 x2 ) = ( y1 − x1 y2 − x2 ) Nên (y − x)TB (y − x) = ( y1 − x1 y2 − x2 )( 2 0 0 2 )( y1 − x1 y2 − x2 ) = 2(y1 − x1) 2 + 2(y2 − x2) 2 Đặt f (x, y) = f (x, y)− 1 2 (y − x)TB (y − x) Từ đó ta có: f (x, y) = − 1 2 y21 + ( 10− 1 2 x2 ) y1 − lny1 − 1 2 y22 + ( 10− 1 2 x1 ) y2 − lny2+ + 1 2 x21 − 10x1 + x1x2 + lnx1 + 1 2 x22 − 10x2 + lnx2 − (y1 − x1) 2 − (y2 − x2) 2 Bước khởi tạo: Chọn ak = 1 k + 1 (k = 0, 1, ...), x0 = ( x01, x 0 2 ) = (10, 20) và ρ = 1 Ta có: f ( x0, y ) + 〈w0, y − x0〉 ≥ 0 ⇔ w0 ∈ ∂f ( x0, x0 ) = ∇2f ( x0, x0 ) Cụ thể: f ( x0, y1, y2 ) = f (10, 20, y1, y2) = = − 1 2 y21 + ( 10− 1 2 .20 ) y1 − lny1 − 1 2 y22 + ( 10− 1 2 .10 ) y2 − lny2+ + 1 2 .102 − 10.10 + 10.20 + ln10 + 1 2 .202 − 10.20 + ln20− (y1 − 10) 2 − (y2 − 20) 2 = − 3 2 y21 + 20y1 − lny1 − 3 2 y22 + 45y2 − lny2 − 350 + ln200 Ta có: ∇2f ( x0, y1, y2 ) =   −3y1 + 20− 1 y1 −3y2 + 45− 1 y2   Do đó: w0 =   ∂f ∂y1 ( x0, x0 ) = −3.10 + 20− 1 10 = −10, 1 ∂f ∂y2 ( x0, x0 ) = −3.20 + 45− 1 20 = −15, 05 29 Thang Long University Libraty Nhận thấy w0 6= 0 ta chuyển qua bước 2 Các bước lặp, được thực hiện theo công thức sau: ak = 1 k + 1 , wk = ∇2f ( x0, xk ) , zk+1 = xk + ak.wk, xk+1 = PC ( zk+1 ) Trong đó: xk+1 =   zk+1,nếu zk+1 ∈ C (5, .) ; (., 10) ; (5, 10) ,nếu zk+1 /∈ C k ak x k wk zk+1 xk+1 0 1 (10, 20) T (−10, 1;−15, 05)T (−0, 1; 4, 95)T (5, 10)T 1 1 2 (5, 10) T (4, 8; 14, 9) T (7, 4; 17, 45) T (7, 4; 17, 45) T 2 1 3 (7, 4; 17, 45)T (−2, 33;−7, 40)T (6, 62; 14, 98)T (6, 62; 14, 98)T 3 1 4 (6, 62; 14, 98) T (−0, 02;−0, 01)T (6, 61; 14, 97)T (6, 61; 14, 97)T Bảng 2.1: Kết quả tính toán Ví dụ 2 theo Thuật toán 2 Bảng trên minh họa đến bước lặp 3. Thực hiện các bước lặp cho đến khi xk+1 = xk thì kết luận xk là nghiệm. 30 Kết luận Bản luận văn đã trình bày các vấn đề sau. 1. Các kiến thức cơ bản về tập lồi, hàm lồi, toán tử chiếu. 2. Các kiến thức và kết quả cơ bản về bài toán cân bằng như sự tồn tại nghiệm, các trường hợp riêng quan trọng của bài toán cân bằng. Đặc biệt là sự tồn tại và duy nhất nghiệm của bài toán cân bằng giả đơn điệu mạnh. 3. Trình bày hai thuật toán giải bài toán cân bằng giả đơn điệu mạnh, trong trường hợp đòi hỏi có tính chất kiểu Lipschitz (Thuật toán 1) và trường hợp không đòi hỏi tính Lipschitz (Thuật toán 2). 4. Áp dụng vào một mô hình cân bằng kinh tế điện bằng cách chuyển mô hình về bài toán cân bằng giả đơn điệu mạnh. Cuối cùng là ví dụ minh họa. 31 Thang Long University Libraty Tài liệu tham khảo [Tài liệu tiếng Việt] [1] Đỗ Văn Lưu - Phan Huy Khải (2000), Giải tích lồi, NXB Khoa học và kĩ thuật, Hà Nội. [2] Lê Dũng Mưu (1998),Nhập môn các phương pháp tối ưu, NXB Khoa học và kĩ thuật, Hà Nội. [3] Lê Dũng Mưu, Nguyễn Văn Hiền, Nguyễn Hữu Điển (Sẽ ra), Nhập môn Giải tích lồi ứng dụng, NXB Đại Học Quốc Gia Hà Nội, Hà Nội. [4] Trần Vũ Thiệu - Nguyễn Thị Thu Thủy (2011), Giáo trình tối ưu phi tuyến, NXB Đại Học Quốc Gia Hà Nội, Hà Nội. [5] Lê Dũng Mưu (Sẽ ra), Equilibrium Problems: Methods and Applica- tions, NXB Viện HLKHCN Việt Nam. [Tài liệu tiếng Anh] [6] I Konnov (2001), Combined Relaxation Methods for Variational In- equalities, Springer. [7] Le D. Muu and N. V. Quy (Sẽ ra), Existence Solution and Algorithms for Strongly Pseudomonotone Equilibrium Problems, Vietnam Jour- nal of Mathematics. 32