ĐINH THẾ THO BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG - Đinh Thế Tho CHUYÊN NGÀNH TOÁN ỨNG VỀ BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU MẠNH VÀ DỤNG Á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 KHOÁ 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 hướng dẫn GS TSKH Lê Dũng Mưu Bản luận văn tổng hợp lại từ tài liệu trích dẫn dựa mục tiêu đề tài Bản luận văn chép lại hoàn toàn từ 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 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 đóng góp cho nhiều ý kiến nội dung luận văn Tôi xin gửi lời cảm ơn đến thầy cô giảng dạy giúp đỡ suốt trình học tập trường Đại học Thăng Long Tôi xin gửi lời cảm ơn chân thành tới người thân yêu gia đình, bạn bè, cổ vũ, động viên, giúp đỡ để hoàn thành luận văn Bước đầu nghiên cứu khoa học nên luận văn thạc sĩ chắn nhiều thiếu sót Tôi mong nhận đóng góp ý kiến thầy giáo, cô giáo bạn đọc để luận văn hoàn thiện Hà Nội, tháng năm 2015 Học viên Đinh Thế Tho Thang Long University Libraty Danh mục kí hiệu viết tắt H : Không gian Hilbert thực; | : Tích vô hướng; : Chuẩn không gian Hilbert; NC : Nón chuẩn tắc C ; PC : Phép chiếu lên tập C ; dC : Hàm khoảng cách tập C ; ∇f (x) : Đạo hàm hàm f x; arg f : Tập cực tiểu hàm f Danh mục hình bảng Hình 2.1: Lợi nhuận tốt nhà máy thủy điện nhà máy nhiệt điện ( Trang 25) Hình 2.2: Lợi nhuận tốt nhà máy nhiệt điện nhà máy thủy điện ( Trang 25) Hình 2.3: Lợi nhuận tốt hai nhà máy ( Trang 26) Bảng 2.1: Kết tính toán Ví dụ theo Thuật toán ( Trang 29) Thang Long University Libraty Mục lục Lời mở đầu Chương 1.BÀI TOÁN CÂN BẰNG 1.1 ột số khái niệm kết 2M 1.1.1 Tập lồi 1.1.2 Hàm lồi 1.1.3 Toán tử chiếu lên tập lồi đóng 1.2 ài toán cân trường hợp riêng 7B 1.2.1 Bài toán tối ưu 1.2.2 Bài toán bất đẳng thức biến phân 1.2.3 Bài toán điểm bất động 1.2.4 Bài toán cân Nash trò chơi không hợp tác 10 1.3 ự tồn nghiệm toán cân 11S 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 huật toán hội tụ 16T 2.1.1 Thuật toán 19 2.1.2 Thuật toán 20 2.1.3 Sự hội tụ thuật toán 21 2.2 p dụng vào mô hình cân 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 có nhiều ứng dụng khoa học, kĩ thuật đời sống Có nhiều toán liên quan đến toán cân như: toán tối ưu, toán bất đẳng thức biến phân, toán cân Nash trò chơi không hợp tác, Do việc trình bày đưa thuật toán giải toán cân cần thiết Luận văn nhằm giới thiệu toán cân giả đơn điệu mạnh hai thuật toán giải toán cân 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 chia làm hai chương • Chương luận văn trình bày tóm tắt số kết biết giải tích lồi liên quan đến luận văn Giới thiệu toán cân trường hợp riêng • Chương luận văn trình bày hai thuật toán để giải toán cân giả đơn điệu mạnh, xét hội tụ hai thuật toán cuối chương áp dụng vào mô hình kinh tế thị trường điện Cuối trình bày ví dụ cụ thể để minh họa thuật toán Thang Long University Libraty Chương BÀI TOÁN CÂN BẰNG Trong chương ta nhắc lại khái niệm bản, tính chất đặc trưng tập lồi hàm lồi không gian Hilbert−H thực qua giới thiệu toán cân trường hợp riêng số điều kiện tồn nghiệm toán cân Nội dung chương lấy từ [1], [2], [3], [4] 1.1 1.1.1 Một số khái niệm kết Tập lồi Định nghĩa 1.1.1 Một tập C ⊆ H gọi lồi ∀x, y ∈ C, ≤ λ ≤ ⇒ λx + (1 − λ) y ∈ C Định lý 1.1.1 Tập lồi đóng với phép giao, phép cộng, phép nhân với số thực Tức C D hai tập lồi H tập sau 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 gọi nón ∀x ∈ C, ∀λ > ⇒ λx ∈ C Định nghĩa 1.1.3 Tập C ⊆ H gọi nón lồi C vừa nón vừa tập lồi, tức λ1 x + λ2 y ∈ C, ∀x, y ∈ C, ∀λ1 > 0, ∀λ2 > Định nghĩa 1.1.4 Cho C ⊆ H tập lồi x ∈ C , tập NC (x) = {w ∈ H, w, y − x ≤ 0, ∀y ∈ C} gọi nón pháp tuyến C tập −NC (x) gọi nón pháp tuyến C x 1.1.2 Hàm lồi Định nghĩa 1.1.5 Hàm f : C → R ∪ {+∞} gọi (i) Lồi C f [λx + (1 − λ) y] ≤ λf (x) + (1 − λ) f (y) , ∀x, y ∈ C, < λ < 1; (ii) Lồi chặt C f [λx + (1 − λ) y] < λf (x)+(1 − λ) f (y) , ∀x, y ∈ C, x = y, < λ < 1; (iii) Lồi mạnh C với hệ số γ > f [λx + (1 − λ) y] < λf (x) + (1 − λ) f (y) − γλ (1 − λ) x − y , ∀x, y ∈ C, ∀λ ∈ (0, 1) ; (iv) Tựa lồi C ∀α ∈ R tập mức Lα (f ) = {x ∈ C, f (x) ≤ α} Định lý 1.1.2 Cho f hàm lồi tập lồi C g hàm lồi tập lồi D Khi hàm số sau hàm lồi 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 ∪ {+∞} hàm lồi, khả vi tập lồi C Khi vớ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 tập lồi C , vớ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ố α > , khả vi tập lồi C , với x, y thuộc C ta có: f (x) − f (y) ≤ ∇f (x) , y − x − α x − y Thang Long University Libraty Vậy x∗ nghiệm toán (1.2.1) Bây ta chứng tỏ (i) tương đương với (iii) Thật x∗ cực tiểu f (x∗ , ) C f (x∗ , y) ≥ f (x∗ , x∗) = 0, ∀y ∈ C Mệnh đề 2.1.2 Giả sử f giả đơn điệu mạnh C với hệ số λ thỏa mãn điều kiện kiểu Lipschitz, theo nghĩa sau: ∃L1 > 0, L2 > : ∀x, y, z ∈ C, ta có f (x, y) + f (y, z) ≥ f (x, z) − L1 x − y − L2 y − z Khi với x0 ∈ C , dãy xk xác định theo công thức x k+1 k =s x k = arg ρf x , y + y − xk y2∈C (2.1.1) Có tính chất 2 xk+1 − x∗ ≤ α xk − x∗ , ∀k ≥ Nếu < ρ ≤, x∗ nghiệm toán 2L2 (1.2.1) α = − 2ρ (λ − L1 ) Chứng minh: Đặt , ∀k ≥ x − xk Do f xk , lồi, nên hàm fk lồi mạnh C với hệ số Vậy fk (x) = ρf xk , x + ≤ fk (x) , ∀x ∈ C (2.1.2) > + x − xk+1 Trong wk ∈ ∂fk xk+1 Do xk+1 nghiệm toán (2.1.1) , nên fk x k+1 + < w ,xk − x k+1 wk , x − xk+1 ≥ 0, ∀x ∈ C Từ (2.1.2) ta có fk xk+1 + x − xk+1 (2.1.3) ≤ fk (x) , ∀x ∈ C Thay x = x∗ (2.1.3) theo định nghĩa fk ta xk+1 − x ≤ 2ρ f xk , x∗ − f xk , xk+1 + xk − x∗ 18 − xk+1 − xk (2.1.4) Do f giả đơn điệu mạnh với hệ số λ nên f xk , x∗ ≤ −f x∗ , xk − λ xk − x∗ Thay vào (2.1.4) ta có xk+1 − x∗ +2ρ −f x , x ∗ k ≤ (1 − 2ρλ) xk − x∗ + − f x ,x k k+1 −x k+1 −x k2 Áp dụng tính Lipschitz với x = x∗ , y = xk , z = xk+1 ta −f xk , xk+1 − f x∗, xk ≤ −f x∗, xk+1 + L1 x∗ − xk + L2 xk − xk+1 22 ≤ L1 x∗ − xk + L2 xk − xk+1 Thay vào ta xk+1 − x∗ 2 ≤ [1 − 2ρ (λ − L1 )] xk − x∗ − (1 − 2ρL2 ) xk+1 − xk Theo giả thiết < ρ ≤ nên ta có 2L2 xk+1 − x∗ ≤ [1 − 2ρ (λ − L1 )] xk − x∗ Vậy mệnh đề chứng minh Hệ 2.1.1 Nếu L1 < λ < ρ ≤ 2L2 xk+1 − x∗ ≤ r xk − x∗ , ∀k ≥ Trong < r = − 2ρ (λ − L1 ) < 1 Nhận xét: Do λ ≤ L1 + L2 < ρ ≤ , nên ta có 2ρ (λ − L1 ) < 2L Vậy r đạt giá trị nhỏ ρ = Nếu xk = xk+1, xk nghiệm, 2L2 ta gọi điểm x ∈ C nghiệm τ − xấp xỉ toán (1.2.1) x − x∗ ≤ τ , xk nghiệm xác toán (1.2.1) Dựa vào mệnh đề hệ ta có thuật toán sau để giải toán cân giả đơn điệu mạnh 2.1.1 Thuật toán 1 , lấy x0 ∈ CBước khởi tạo: Chọn sai số τ ≥ < ρ ≤ 2L2 Bước lặp thứ k: k = (0, 1, 2, ) 19 Thang Long University Libraty Tính xk+1 cách giải toán quy hoạch lồi mạnh y − xk xk+1 = arg ρf xk , y + y∈C τk+1 (1 − r) k −x ≤(a) Nếu x, với r = − 2ρ (λ − L1 ), dừng: r xk+1 nghiệm τ − xấp xỉ toán (1.2.1) (b) Trái lại chuyển sang bước lặp thứ k với k thay k + Chú ý: Do xk+1 − x∗ ≤ r xk − x∗ với r < 1, ta có r 1−r xk+1 − x∗ ≤ Do x k+1 −x Có xk+1 → x∗ k → ∞ Vậy, x k+1 −x xk+1 − x∗ ≤ τ ∗ ∗ ≤ xk+1 − xk , rk+1 1−r x0 − x1 , ∀k ≥ ∀k ≥ τ (1 − r)rk+1 ≤x0 − x1hoặc r1−r ≤ τ Trong trường hợp ta nghiệm τ − xấp xỉ toán Dưới ta trình bày phương pháp dựa vào toán tử chiếu để giải toán cân giả đơn điệu mạnh không cần điều kiện Lipschitz Thuật toán 2.1.2 Bước khởi tạo: Chọn dãy số {ak } ⊂ (0, 1) cho a2 < ∞, ak =k , lấy x0 ∈ C k+1k=0 Bước 1: Chọn wk cho ρf xk , y + wk , y − xk ≥ 0,∀y ∈ C, ∞; ∞ ρ > tham số hiệu chỉnh (a) Nếu wk = 0, ρk ≤ τ dừng thuật toán: xk τ − nghiệm toán 20 ∞ k=0 ak = (b) wk = 0, chuyển qua bước Bước 2: Đặt z k+1 = xk + ak wk xk+1 = PC z k+1 , PC toán tử chiếu lên C Nếu xk+1 = xk dừng thuật toán: xk nghiệm toán (1.2.1) Trái lại, quay lại bước với k = k + Chú ý: Bài toán toán phải giải thuật toán toán tìm wk bước Để tìm wk ta giải sau: (i) Giả sử toán quy hoạch lồi: f xk , y có nghiệm cách y∈C đặt mk = − f xk , y < +∞ y∈C Chọn wk cho wk , y − xk ≥ ρmk ,∀y ∈ C Khi wk điểm cần tìm bước thuật toán (ii) Do f (x, ) lồi, khả vi phân C , nên với y thuộc C , g k ∈ ∂2 f xk , xk , ta có f xk , y − f xk , xk ≥ g k , y − xk Vì f xk , xk = nên ta thấy wk = −ρ−1 g k thỏa mãn bất đẳng thức ρf xk , y + wk , y − xk ≥ 0, ∀y ∈ C Do wk điểm cần tìm 2.1.3 Sự hội tụ thuật toán Để chứng minh hội tụ thuật toán, ta cần đến bổ đề sau: Bổ đề 2.1.1 Giả sử {ak }∞ dãy vô hạn không âm thỏa mãn0 ak+1 ≤ ak + σk , ∀k với ∞ σk < ∞ Khi dãy {ak } hội tụ k=0 Định lý 2.1.1 Giả sử f giả đơn điệu mạnh C với hệ số λ xk dãy tạo Thuật toán Khi ta có xk+1 − x∗ ≤ (1 − 2ρλak ) xk − x∗ + a2 w k k 21 Thang Long University Libraty , ∀k ≥ 0, x∗ nghiệm toán (1.2.1) Hơn nữa, dãy wk bị chặn x∗ hội tụ đến nghiệm x∗ toán0 số Do k ∞ ∞ a2 < +∞ ak = +∞; k=0 k=0 22 k (2.1.10) Nên từ (2.1.10) theo Bổ đề 2.1.1 ta có xk+1 − x∗ hội tụ k → +∞ Vậy xk+1 bị chặn, tồn dãy xkj hội tụ đến x với x nghiệm toán cân Tương tự ta chứng minh xkj − x hội tụ, xkj → x nên xkj − x → xk+1 − x∗ → k → +∞ Vậy định lí chứng minh 2.2 Áp dụng vào mô hình cân 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 véc tơ có thành phần xi (i = 1, 2, , ng ) với ng tổng số tất nhà máy phát điện xi lượng điện sản xuất nhà máy phát điện thứ i Giả sử ng giá điện p hàm affine σ với σ = xi tổng điện sản i=1 xuất tất nhà máy phát điện, cụ thể là: ng p (x) = a0 − xi = p (σ) i=1 Ở a0 > số(rất lớn) Khi lợi nhuận công ty thứ i cho fi (x) = p (σ)xj −cj (xj ) j∈Ii j∈Ii Với cj (xj ) chi phí nhà máy thứ j sản xuất lượng điện mức xj Ta giả sử hàm chi phí cj (xj ) cho cj (xj ) = max c0 (xj ) , c1 (xj ) jj Với 00111 βjαj 2−1/βj (βj +1)/βj , 010 10 kkktrong đó: αj , βj , γj tham số cho trước cj (x j ) = xj + βj xj + γj , cj (xj ) = αj xj + 1γ(xj ) Gọi xmin xmax tương ứng lượng điện nhỏ jj lớn có βj + j thể sản xuất nhà máy phát điện thứ j Khi tập chiến lược mô hình xác định sau C = x = (x1, , xng )T : xmin ≤ xj ≤ xmax, ∀j = 1, 2, , ng jj 23 Thang Long University Libraty Ta định nghĩa ma trận A, B sau: nc T − qi qi A=2 , i=1 nc T qi qi B=2 , i=1 iitrong a = −a0 nc q i , c (x) = i=1 ng j ∈ Ii trường hợp khác qi = q1 , ,T qng ivới qj = cj (xj ) Khi mô hình toán j=1 đưa toán cân sau: xx x ∈ C cho 13 x f (x, y) =A + B x + By + a 22 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, A + B không xác định dương, f không đơn điệu C Tuy nhiên thay f f định nghĩa sau f (x, y) = f (x, y) − (y − x)T B (y − x) , f giả đơn điệu mạnh C Thực ta có f (x, y) + f (y, x) = −(y − x)T (A + 2B) (y − x) Vậy, f (x, y) ≥ f (y, x) ≤ −(y − x)T (A + 2B) (y − x) ≤ −λ y − x , với mọiλ > Bổ đề sau hệ trực tiếp nguyên tắc Bổ đề 2.2.1 Bài toán cân Tìm x∗ ∈ C : f (x∗ , y) ≥ 0, ∀y ∈ C tương đương với toán cân 1T f (x∗ , y) + (y − x∗ ) B (y − x∗ ) ≥ 0, Nghĩa chúng có họ nghiệm trùng Tìm x∗ ∈ C : 24 ∀y ∈ C (2.2.11) Từ bổ đề ta áp dụng thuật toán để giải toán cân (2.2.11) Ta minh họa thuật toán cho vấn đề ví dụ sau Ví dụ 1: Nhà máy thủy điện nhiệt điện có hàm chi phí c (y1 ) = 10y1 , c (y2 ) = 30y2 Giá bán điện p = 120 − Q, Q tổng sản lượng điện hai nhà máy Hãy tìm điểm cân Nash mô hình Giải: Ta có lợi nhuận nhà máy 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 hàm hai biến y1 , y2 Do ta lấy đạo hàm hàm lợi nhuận theo biến cho không ta π1 ′ = 120 − 2y1 − y2 − 10 = Hay 2y1 = 110 − y2 Suy y1 = Tương tự 110 − y2 π2 ′ = 120 − 2y2 − y1 − 30 = Hay 2y2 = 90 − y1 Suy y2 = Ta đặt ; 90 − y1 110 − y2 y1 = f1 (y2 ) = 90 − y1 y2 = f2 (y1 ) = Lần lượt hàm sản lượng nhà máy Khi ta có biểu đồ sau 25 Thang Long University Libraty y2 110 y1 = f1 (y2 ) O y1 55 Hình 2.1: Sản lượng tốt nhà máy thủy điện nhà máy nhiệt điện y2 45 y2 = f2 (y1 ) O 90 y1 Hình 2.2: Sản lượng tốt nhà máy nhiệt điện nhà máy thủy điện 26 y2 110 y1 = f1 (y2 ) 45 y2 = f2 (y1 ) O 55 90 y1 Hình 2.3: Sản lượng tốt hai nhà máy Bây ta cần phải tìm điểm (y1 , y2 ) thuộc hai hàm số 110 − y290 − y1 Ta có y1 =và y2 = 22 90 − y1 110 − 220 − 90 + y1 ⇔ 2y1 =Suy y1 = 22 130 90 − 1303 = 70Vậy y1 =⇒ y2 = 323 Khi ta tìm điểm cân Nash sản 13070 130130 130 16900 − 10 π 1= −−là y1 =và nhà máy nhiệt điện =; lượng nhà máy thủy120 điện 333 39 70 70130 70 70 4900 − 30 π 2= 120 −− = Và Lợi nhuận nhà máy lày2 = 333 39 Ví dụ 2: Nhà máy điện A B có hàm chi phí c (x1 ) = lnx1, c (x2 ) = lnx2 Giá bán điện p = 10 − Q , Q tổng sản lượng điện hai nhà máy Dùng thuật toán để tìm điểm cân Nash mô hình 27 Thang Long University Libraty Giải: Ta có lợi nhuận nhà máy là: Nhà máy điện A f1 (x1, x2 ) = x1 10 − (x1 + x2) − lnx1 (2.2.12) Nhà máy điện B f2 (x1, x2 ) = x2 10 − (2.2.13) (x1 + x2) − lnx2 Tập C1 = [5, 100] tức ≤ x1 ≤ 100 Tập C2 = [10, 100] tức 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 ) Ở f1 cho (2.2.12) f2 cho (2.2.13), C = C1 × C2 Áp dụng thuật toán 2: Ta có: 11 f (x, y) = y1 10 − (y1 + x2) − lny1 − x1 10 − (x1 + x2 ) + lnx1+ 22 +y2 11 10 − (x1 + y2 ) − lny2 − x2 10 − (x1 + x2 ) + lnx2 122211 f (x, y) = − y1 + 10 − x2 y1 − lny1 − y2 + 10 − 222 11 + x2 − 10x1 + x1 x2 + lnx1 + x2 − 10x2 + lnx2 12 2101q1q121==và q =Ta có q = 211q20q2 1011 −và − q2 ==−1 − q1 = 1101 010 A=2=1 +0 102 102 B=2=1 +0 010 x1y1 ,x =Lại có y = 28 x2y2 x1 y2 − lny2 + = Suy y − x = y1 y2 Nên (y − x)T B (y − x) = − x1 x2 = y1 − x1 y2 − x2 y1 − x1 y2 − x2 20 02 y1 − x1 y2 − x2 = 2(y1 − x1 )2 + 2(y2 − x2)2 Đặt f (x, y) = f (x, y) − (y − x)T B (y − x) Từ ta có: 111 21 f (x, y) = − y1 + 10 − x2 y1 − lny1 − y2 + 10 − x1 y2 − lny2 + 2222 11 + x2 − 10x1 + x1 x2 + lnx1 + x2 − 10x2 + lnx2 − (y1 − x1)2 − (y2 − x2 )2 12 (k = 0, 1, ), x0 = x0, x0 = (10, 20) vàBước khởi tạo: Chọn ak =1 k+1 ρ=1 Ta có: f x0 , y + ⇔ w 0w, 0y∈− ∂f x0x≥0,0x0 = ∇2 f x0 , x0 Cụ thể: f x0 , y1 , y2 = f (10, 20, y1 , y2 ) = 11 211 = − y1 + 10 − 20 y1 − lny1 − y2 + 10 − 10 y2 − lny2 + 2222 1122+ 102 − 10.10 + 10.20 + ln10 + 202 − 10.20 + ln20 − (y1 − 10) − (y2 − 20) 22 23 = − y1 + 20y1 − lny1 − y2 + 45y2 − lny2 − 350 + ln200 22 Ta có: xx1 −3y1 + 20 − xy1 x ∇2đó: f x , y1 , y2 = x1 x Do −3y2 + 45 − x y2 1x ∂f 00 w0 = x xx xx ∂f ∂y x , x = −3.10 + 20 − 10 = −10, xx 1 29 x x = −15, 05x0, x0 = −3.20 + 45 − ∂y220 Thang Long University Libraty Nhận thấy w0 = ta chuyển qua bước Các bước lặp, thực theo công thức sau: , wk = ∇2 f x0 , xk , z k+1 = xk + ak wk , xk+1 = PC z k+1ak = k+1 Trong đó: x k+1x z , z k+1 ∈ C xk+1 = x(5, ) ; (., 10) ; (5, 10) , z k+1 ∈ C/ k akxkwkz k+1xk+1 TTTT 1(10, 20) (−10, 1; −15, 05)(−0, 1; 4, 95)(5, 10) 1TTTT 1(5, 10)(4, 8; 14, 9)(7, 4; 17, 45)(7, 4; 17, 45) 2(7, 4; 17, 45)T (−2, 33; −7, 40)T (6, 62; 14, 98)T (6, 62; 14, 98)T 1TTTT Bảng 2.1: Kết tính toán Ví dụ theo Thuật toán 3(6, 62; 14, 98)(−0, 02; −0, 01) (6, 61; 14, 97) (6, 61; 14, 97) Bảng 4trên minh họa đến bước lặp Thực bước lặp xk+1 = xk kết luận xk nghiệm 30 Kết luận Bản luận văn trình bày vấn đề sau Các kiến thức tập lồi, hàm lồi, toán tử chiếu Các kiến thức kết toán cân tồn nghiệm, trường hợp riêng quan trọng toán cân Đặc biệt tồn nghiệm toán cân giả đơn điệu mạnh Trình bày hai thuật toán giải toán cân giả đơn điệu mạnh, trường hợp đòi hỏi có tính chất kiểu Lipschitz (Thuật toán 1) trường hợp không đòi hỏi tính Lipschitz (Thuật toán 2) Áp dụng vào mô hình cân kinh tế điện cách chuyển mô hình toán cân giả đơn điệu mạnh Cuối 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 kĩ thuật, Hà Nội [2] Lê Dũng Mưu (1998), Nhập môn phương pháp tối ưu, NXB Khoa học 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 Applications, NXB Viện HLKHCN Việt Nam [Tài liệu tiếng Anh] [6] I Konnov (2001), Combined Relaxation Methods for Variational Inequalities, Springer [7] Le D Muu and N V Quy (Sẽ ra), Existence Solution and Algorithms for Strongly Pseudomonotone Equilibrium Problems, Vietnam Journal of Mathematics 32 [...]... 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. .. (y, x) ≤ −λ x − y , ∀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)... 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 Bằng cách đặt... 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 1 , lấy x0 ∈ CBước khởi tạo: Chọn sai số τ ≥ 0 và 0 < ρ ≤ 2L2 Bước lặp thứ k: k = (0, 1, 2, ) 19 Thang Long University Libraty 2 Tính xk+1 bằng cách giải bài toán quy hoạch lồi mạnh 1 y −... 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, , ng ) 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ử ng giá điện p là một hàm affine của σ với σ = xi là tổng điện năng sản... 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 Thuật toán 2 2.1.2 Bước khởi tạo: Chọn các dãy số {ak } ⊂ (0, 1) sao cho 1 a2 < ∞, ak =k , lấy x0 ∈ C k+1k=0 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. .. 0 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... (2.2.11) 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à... Bước 2: Đặt z k+1 = xk + ak wk và xk+1 = PC z k+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 f xk , y có nghiệm bằng cách y∈C đặt mk = − min... → 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, 12 ∀x, y ∈ C; (v) giả đơn điệu mạnh trên C với hệ số λ