ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC - NGUYỄN THỊ PHƯƠNG LAN PHƯƠNG PHÁP ĐIỂM GẦN KỀ GIẢI MƠ HÌNH CÂN BẰNG NASH - COURNOT LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUN - NĂM 2013 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUN TRƯỜNG ĐẠI HỌC KHOA HỌC - NGUYỄN THỊ PHƯƠNG LAN PHƯƠNG PHÁP ĐIỂM GẦN KỀ GIẢI MÔ HÌNH CÂN BẰNG NASH - COURNOT Chun ngành: TỐN ỨNG DỤNG Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS TSKH LÊ DŨNG MƯU THÁI NGUN - 2013 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Mục lục Mở đầu MƠ HÌNH CÂN BẰNG NASH-COURNOT TUYẾN TÍNH 1.1 Một số kiến thức chuẩn bị 1.1.1 Toán tử không gian Hilbert 1.1.2 Tập lồi hàm lồi 1.1.3 Toán tử đơn điệu 1.1.4 Bất đẳng thức biến phân 1.2 Mơ hình cân Nash-Cournot cổ điển 1.2.1 Phát biểu mơ hình Nash-Cournot 1.2.2 Trường hợp cước phí tuyến tính MƠ HÌNH CÂN BẰNG NASH-COURNOT LÕM 2.1 Mơ hình cân Nash-Cournot 2.2 Phương pháp giải theo thuật tốn điểm gần kề 2.3 Thuật tốn tìm điểm dừng Kết luận Tài liệu tham khảo Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ CƯỚC PHÍ CƯỚC PHI 4 10 14 18 22 22 25 30 30 32 35 41 42 Mở đầu Bài tốn bất đẳng thức biến phân cơng cụ hữu hiệu để nghiên cứu giải toán ứng dụng toán cân kinh tế, tài chính, vận tải, lý thuyết trị chơi, tốn cân mạng Trong có mơ hình cân bán độc quyền Nash-Cournot Mơ hình cân thị trường bán độc quyền Cournot đưa vào năm 1838 nhiều tác giả giới tập trung nghiên cứu Sau mơ tả trường hợp đặc biệt mơ hình cân Nash lý thuyết trị chơi khơng hợp tác gồm n người chơi, gọi mơ hình cân thị trường Nash-Cournot Gần người ta quan tâm nhiều đến việc giải tốn ứng dụng vào thực tiễn sống đa dạng, đặc biệt lĩnh vực kinh tế Mục đích luận văn trình bày mơ hình cân NashCournot cho cước phí tuyến tính đặc biệt trường hợp cước phí lõm Khi cước phí lõm, mơ hình cân Nash-Cournot mơ tả dạng tốn bất đẳng thức biến phân hỗn hợp DC Luận văn mơ tả thuật tốn lặp dựa ý tưởng phương pháp điểm gần kề để tính điểm dừng toán bất đẳng thức biến phân hỗn hợp lõm Ngoài phần mở đầu, kết luận tài liệu tham khảo, kết nghiên cứu luận văn trình bày thành hai chương với tiêu đề sau: Chương 1: Mơ hình cân Nash-Cournot cước phí tuyến tính Chương nhắc lại số kiến thức sở khơng gian Hilbert thực, giải tích lồi số khái niệm ánh xạ đơn điệu, toán tử đơn điệu với số kết liên quan đến tính đơn điệu tốn tử đơn điệu không gian Hilbert Đồng thời giới thiệu toán bất đẳng thức biến phân hỗn hợp mơ hình cân Nash-Cournot với cước phí tuyến tính Chương 2: Mơ hình cân Nash-Cournot cước phí lõm Chương giới thiệu mơ hình cân thị trường Nash-Cournot với cước phí lõm Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ giới thiệu phương pháp giải mơ hình trường hợp hàm chi phí hàm lõm phương pháp tìm điểm dừng theo thuật tốn điểm gần kề Để hồn thành luận văn em xin bày tỏ lòng biết ơn sâu sắc tới GS.TSKH Lê Dũng Mưu (Viện Toán học, Viện Hàn lâm Khoa học Công nghệ Việt Nam), người tận tình hướng dẫn giúp đỡ em suốt tình học tập nghiên cứu để em hồn thiện luận văn Em xin bày tỏ lòng biết ơn chân thành tới quý thầy cô giáo giảng dạy Đại học Thái Nguyên Viện Toán học mang đến cho em nhiều kiến thức bổ ích khơng khoa học mà cịn sống Tơi xin chân thành cảm ơn bạn đồng môn giúp đỡ thời gian học tập Đại học Thái Nguyên q trình hồn thành luận văn Cuối cùng, xin cảm ơn bố mẹ Nhờ có bố mẹ khơng quản gian khó, vất vả sớm khuya tạo điều kiện tốt để có thành ngày hơm Luận văn hồn thành trường Đại học Khoa học, Đại học Thái Nguyên hướng dẫn trực tiếp GS TSKH Lê Dũng Mưu Mặc dù, em cố gắng vấn đề nghiên cứu phức tạp mẻ, lại thời gian có hạn kinh nghiệm nghiên cứu cịn hạn chế nên khó tránh khỏi thiếu sót Em mong nhận góp ý quý thầy cô bạn Thái Nguyên, tháng - 2013 Người viết Luận văn Nguyễn Thị Phương Lan Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Chương MƠ HÌNH CÂN BẰNG NASH-COURNOT CƯỚC PHÍ TUYẾN TÍNH 1.1 Một số kiến thức chuẩn bị Nội dung chương bao gồm: số kiến thức sở khơng gian Hilbert thực giải tích lồi Tiếp sau khái niệm ánh xạ đơn điệu, tốn tử đơn điệu Đồng thời trình bày số kết liên quan đến tính đơn điệu toán tử đơn trị đa trị khơng gian Hilbert Bên cạnh giới thiệu toán bất đẳng thức biến phân hỗn hợp mơ hình cân Nash-Cournot với cước phí tuyến tính Các kiến thức chương chủ yếu lấy từ tài liệu [1], [2], [4], [7] 1.1.1 Toán tử không gian Hilbert Định nghĩa 1.1 Cho không gian véctơ X trường số K(K = R) Một ánh xạ từ X × X → K gọi tích vơ hướng X thỏa mãn điều kiện sau: (i) x, x ≥ 0, ∀x ∈ X, x, x = ⇔ x = 0; (ii) x, y = y, x , ∀x, y ∈ X; (iii) x + x′, y = x, y + x′ , y , ∀x, x′, y ∈ X; (iv) λx, y = λ x, y , ∀x, y ∈ X, λ ∈ K; Số x, y gọi tích vô hướng hai véctơ x, y Chú ý 1.1 Từ định nghĩa tích vơ hướng điều kiện (ii) (iv) ta suy ra: Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ -) x, y + y ′ = x, y + x, y ′ , ∀x, y, y ′ ∈ X, -) x, λy = λ x, y , ∀x, y ∈ X, λ ∈ K Định nghĩa 1.2 Cho X không gian tuyến tính thực, X gọi khơng gian tiền Hilbert với x, y ∈ X xác định số thực kí hiệu x, y tích vơ hướng x,y thỏa mãn tính chất sau: (i) x, x ≥ 0, x = 0; x, x = 0, x = 0; (ii) x, y = y, x ; (iii) x + y, z = x, z + y, z ; (iv) αx, y = α x, y , ∀α ∈ R Định lý 1.1 Trong không gian tiền Hilbert X, với x, y ∈ X ta ln có bất đẳng thức sau: | x, y |2 ≤ x, y y, y gọi bất đẳng thức Schwarz Chứng minh Với y = bất đẳng thức Giả sử y = 0, ∀λ ∈ R ta có: x + λy, x + λy ≥ hay x, x + λ y, x + λ x, y + |λ|2 y, y ≥ Chọn λ = − x, y ta được: y, y | x, y |2 x, y − ≥ y, y Từ suy | x, y |2 ≤ x, y y, y Dấu ′′ =′′ bất đẳng thức Schwarz xảy x, y phụ thuộc tuyến tính Định lý 1.2 Mọi không gian tiền Hilbert X không gian tuyến tính định chuẩn với chuẩn xác định x = Số hóa Trung tâm Học liệu x, x , ∀x ∈ X http://lrc.tnu.edu.vn/ với kí hiệu bất đẳng thức Schwarz viết thành | x, y | ≤ x Chứng minh Từ (i) định nghĩa tích vơ hướng ta suy ra: y ∀x ∈ X, x ≥ 0; x = ⇔ x = Từ (i) (iv) định nghĩa tích vơ hướng ta có: λx = λx, λx = |λ|2 x = |λ| x , ∀x ∈ X, λ ∈ R Mặt khác ∀x, y ∈ X ta có: x+y = x + y, x + y = x + y, x + x, y + y = x + x, y + y ≤ x + | x, y | + y 2 Áp dụng bất đẳng thức Schwarz ta có: x+y ≤ x +2 x y + y ≤ ( x + y )2 , x + y ≤ x + y Như chuẩn H Định lý 1.3 Cho X không gian tiền Hilbert, với x, y ∈ X ta ln có bất đẳng thức hình bình hành sau đây: x+y + x−y =2 x + y Chứng minh Với x, y ∈ X ta có: x+y = x + y, x + y = x + x, y + y, x + y x−y = x − y, x − y = x − x, y − y, x + y , cộng hai bất đẳng thức ta được: x+y + x−y = x =2 x + y 2 + x + y Vậy định lý chứng minh Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ + y 2 Định nghĩa 1.3 Cho X không gian định chuẩn, dãy {xn } ⊂ X gọi dãy X nếu: lim m,n→∞ xn − xm = Nếu X dãy hội tụ, tức xn − xm → 0, kéo theo ∃x0 ∈ X cho xn → x0 X gọi khơng gian đủ Định nghĩa 1.4 Nếu X không gian tiền Hilbert đầy đủ X gọi không gian Hilbert Trong luận văn ta thống kí hiệu H khơng gian Hilbert thực Định lý 1.4 Giả sử {xn}, {yn} hai dãy không gian Hilbert H cho xn → x0, yn → y0 Lúc xn , yn → x0 , y0 , n → ∞ Chứng minh Giả sử lim xn = x0 , lim yn = y0 không gian H n→∞ n→∞ Ta cần chứng minh lim (xn , yn) = (x0, y0) H Thật n→∞ | xn , yn − x0 , y0 | = | xn , yn + xn , y0 − xn , y0 − x0, y0 | ≤ | xn , yn − y0 | + | xn − x0 , y0 | ≤ xn yn − y0 + xn − x0 y0 Vì dãy {xn} hội tụ H nên ∃M > cho xn ≤ M, ∀n ∈ N Khi bất đẳng trở thành: | xn − yn − x0 − y0 | ≤ M yn − y0 + y0 cho n → ∞ theo giả thiết ta suy lim xn , yn = x0 , y0 n→∞ Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ xn − x0 , Định nghĩa 1.5 Hai véctơ x, y ∈ H gọi hai véctơ trực giao với kí hiệu x⊥y x, y = Từ định nghĩa dễ dàng suy tính chất đơn giản sau đây: ⊥ x, ∀x ∈ H; x ⊥ y ⇒ y ⊥ x, ∀x, y ∈ H; x ⊥ {y1 , y2, , yn} ⇒ x⊥α1 y1 + α2 y2 + + αn yn , ∀x ∈ H, n ∈ N∗ , αi ∈ R, i = 1, 2, , n; x ⊥ yn , yn → y n → ∞ x ⊥ y, ∀x, y ∈ H Định nghĩa 1.6 Cho tập M ⊂ H, phần bù trực giao M, kí hiệu M ⊥ , tập hợp sau: M ⊥ = {x ∈ H : x⊥y, ∀y ∈ M } Định lý 1.5 ( Định lý F.Riesz) Với véctơ a cố định thuộc không gian Hilbert H, hệ thức: f (x) = a, x , (1.1) xác định phiếm hàm tuyến tính liên tục f(x) không gian H, với: f = a (1.2) Ngược lại, phiếm hàm tuyến tính liên tục f(x) khơng gian Hilbert H biểu diễn cách dạng (1.1) a véctơ H thỏa mãn (1.2) Chứng minh Phần thứ định lý, ta dễ dàng chứng minh f (x) = a, x , rõ ràng phiếm hàm tuyến tính |f (x)| = | a, x | ≤ a × x ; (1.3) |f (a)| = | a, a | ≤ a × a , (1.4) nên phiếm hàm giới nội thỏa mãn (1.2) Để chứng minh phần ngược lại, ta xét phiếm hàm tuyến tính liên tục f (x) khơng gian Hilbert H Tập hợp M = {x ∈ H : f (x) = 0} , rõ ràng không gian đóng H Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 28 Điều có nghĩa điểm cân Nash hãng lớn với ma trận hệ số giá:  2β β β  β 2β β Q :=  β β β điểm có tổng lợi ích  β β   2β Theo (1.14) (1.19), tổng lợi ích hãng là: n fi (x) = αT x − µT x − xT Gx f (x) := i=1 Ta giải tốn quy hoạch tồn phương lồi mạnh : max αT x − µT x − xT Gx , x∈C (1.29) theo phương pháp có quy hoạch tốn học Ở   β β β β  β β β β  G :=   β β β β gọi ma trận hệ số giá Ví dụ 1.3 Cho n = 3, β = 1, α0 = 10, Ci = [0, ∞], µT = (5, 2, 3), ξ T = (2, 1, 4), αT = (10, 10, 10), i = 1, 2, Hãy viết hàm giá, hàm chi phí, hàm lợi nhuận chuyển mơ hình tốn (1.28) Sau giải tốn để tìm điểm cân Giải Ta có hàm giá pi (σ) = p(σ) := α0 − βσ, với α0 = 10, β = 1, σ = xi , i=1 suy pi( 3 xi ) = 10 − i=1 xi i=1 Vậy p1(x1) = 10 − x1; p2(x1 + x2) = 10 − (x1 + x2); p3(x1 + x2 + x3 ) = 10 − (x1 + x2 + x3) Ta có hàm chi phí hi (xi ) := µi xi + ξi , với µT = (5, 2, 3), ξ T = (2, 1, 4), suy Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 29 h1 (x1) = 5x1 + 2; h2 (x2) = 2x2 + 1; h3 (x3) = 3x3 + Ta có hàm lợi nhuận fi(x1, x2, x3) := xipi( xi) − hi (xi), i=1 suy f1(x1, x2, x3) = x1(10 − x1) − (5x1 + 2) = −x21 + 5x1 − 2; f2(x1, x2, x3) = x2(10 − (x1 + x2)) − (2x2 + 1) = −x22 + 8x2 − x1x2 − 1; f3(x1, x2, x3) =x3(10 − (x1 + x2 + x3)) − (3x3 + 4) = − x23 + 7x3 − x1 x3 − x2x3 − Khi ta đưa tốn sau: max x∈C (α − µ)T x − xT Qx , T với (α − µ) = (5, 8, 7), Q := 1 1 ; xT = (x1, x2, x3) Ta có x1 1 x1 x2 − (x1, x2, x3) x2 x3 1 x3 = 5x1 + 8x2 + 7x3 − x21 − x22 − x23 − x1x2 − x1x3 − x2x3 (α − µ) x − xT Qx = (5, 8, 7) T Giải toán max{5x1 + 8x2 + 7x3 − x21 − x22 − x23 − x1 x2 − x1x3 − x2 x3} x∈C ta thu nghiệm (x1, x2, x3) = (0, 3, 2) ∈ C Vậy điểm cân cần tìm (0, 3, 2) Kết luận: Trong chương tìm hiểu tốn bất đẳng thức biến phân mơ hình cân Nash - Cournot cổ điển với cước phí tuyến tính Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 30 Chương MƠ HÌNH CÂN BẰNG NASH-COURNOT CƯỚC PHI LÕM Mơ hình cân thị trường Cournot đưa nhiều tác giả nghiên cứu Mô hình mơ tả tốn cân Nash lý thuyết trị chơi khơng hợp tác gồm n người chơi Mơ hình cân thị trường liên quan tới n hãng sản xuất, họ tham gia sản xuất loại sảm phẩm Mỗi hãng có hàm lợi nhuận mà giá chi phí khác Trong mơ hình cân Nash-Cournot cước phí lõm, hàm giá hãng khơng giống nhau, chi phí hãng hàm lõm theo số lượng sản phẩm Bài toán đặt tối đa hóa lợi nhuận hãng cách chọn mức sản lượng phù hợp cho tất hãng Các khái niệm kết chương tham khảo [3], [5], [6], [8] 2.1 Mơ hình cân Nash-Cournot Ở mơ hình cân kinh tế Nash-Cournot cổ điển, hàm cước phí giả thiết hàm tăng, aphin theo số lượng sản xuất Tuy nhiên thực tế, giá ban đầu sản phẩm hệ số giảm giá tăng số lượng sản phẩm hãng khác Thật vậy, giả sử hàm chi phí hi , (i = 1, 2, , n) lõm tuyến tính khúc hàm giá p( n i=1 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ xi) thay 31 đổi theo hãng Hàm có cơng thức sau: n pi (σ) := pi n xi , αi ≥ 0, βi > 0, i = 1, n (2.1) = αi − βi xi i=1 i=1 Ta có: n Φ(x, y) = Ψ(x, y) − Ψ(x, x) = n = i=1 n = i=1 n fi(x) − fi(x[yi]) i=1 i=1   n n   xp( xi) − h(x) − yipi ( xj [yi]) + h(y)  i i  i=1 j=i,j=1   n n   x (α − βi xi) − h(x) − yi (αi − βi xj [yi ]) + h(y)  i i  i=1 n j=i,j=1 n ((yi − xi)(βi = n i=1 n yi2 xj − αi )) + βi i=1 j=i,j=1 T x2i + h(y) − h(x) − βi i=1 ˜ − α, y − x + y By − xT Bx + h(y) − h(x), = Bx  β1  B =  0 β2 0   0  ˜   ; B =  βn β2 βn β1 βn β1 β2 βn  β1 β2   n h(x) := hi (xi), i=1 với hi (i = 1, 2, , n) hàm lõm Rõ ràng B ma trận đối xứng xác định dương Cho ˜ − α, F (x) := Bx (2.2) ϕ(x) := xT Bx + h(x) (2.3) Vậy toán cân trở thành toán bất đẳng thức biến phân hỗn hợp sau: Tìm x∗ ∈ C thỏa mãn : Φ(x∗, y) := F (x∗), y−x∗ +ϕ(y)−ϕ(x∗) ≥ 0, ∀y ∈ C, Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 32 F (.) toán tử aphin ϕ(.) hàm D.C cho theo cơng thức (2.2), (2.3) Chú ý ϕ không lồi nên (1.19) không tương đương với tốn tìm điểm x∗ ∈ C thỏa mãn: Φ(x∗, y) := F (x∗ ), y − x∗ + ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ U ∩ C, (2.4) U lân cận x∗ Điểm x∗ ∈ C thỏa mãn (2.4) gọi nghiệm địa phương 2.2 Phương pháp giải theo thuật toán điểm gần kề Trong phần này, ta nghiên cứu tính chất liên quan đến nghiệm toàn cục nghiệm địa phương cho tốn MVIP ϕ hàm DC Tiếp theo ta mở rộng phương pháp điểm gần kề để tìm điểm dừng tốn Cuối cùng, ta chứng minh kết hội tụ ϕ lồi F đơn điệu mạnh Định nghĩa 2.1 Phương pháp điểm gần kề Rockafellar để giải bao hàm thức: ∈ T (z) (P ∗ ) T ánh xạ đơn điệu cực đại Phương pháp phương pháp lặp tức xây dựng dãy lặp xk sau: (-) Xuất phát từ x0 ∈ H (-) Tại bước thứ k điểm lặp xk+1 = (I + cT )−1(xk ), I toán tử đồng (tức Ix = x) Rockafellar chứng minh dãy {xk } hội tụ yếu đến nghiệm z toán (P ∗ ) Ta sử dụng lược đồ phương pháp điểm gần kề để giải tốn mơ hình cân Nash-Cournot với cước phí lõm Cho ∅ = C ⊆ Rn tập lồi đóng, F : C → Rn ánh xạ liên tục, ϕ hàm giá trị thực liên tục (không cần lồi) định nghĩa Rn Ta xét toán bất đẳng thức biến phân hỗn hợp sau (MVIP): Tìm x∗ ∈ C cho : F (x∗)T (y − x∗) + ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ C (2.5) Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 33 Điểm x∗ gọi nghiệm toàn cục với x∗ ∈ C Điểm x∗ ∈ C gọi nghiệm địa phương tồn lân cận U x∗ thỏa mãn: F (x∗)T (y − x∗ ) + ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ U ∩ C (2.6) Chú ý rằng, ϕ lồi C nghiệm địa phương nghiệm tồn cục, ϕ khơng lồi, nghiệm địa phương khơng nghiệm tồn cục Ta gọi C miền cho phép, F tốn tử chi phí ϕ hàm chi phí Khi C tập lồi đóng, dễ dàng thấy với nghiệm địa phương (2.5) nghiệm toàn cục ϕ lồi C Ta gọi tên toán (2.5) bất đẳng thức biến phân hỗn hợp lồi ϕ lồi, ngược lại bất đẳng thức biến phân hỗn hợp khơng lồi hàm chi phí khơng lồi Ta kí hiệu ℵC := (x, U ) : x ∈ C, U lân cận mở x Tiếp ta định nghĩa ánh xạ S : ℵC → 2C hàm m : ℵC → R cách lấy lần lượt: S (x, U) := argmin F (x)T (y − x) + ϕ(y) : y ∈ C ∩ U , (2.7) m (x, U) := F (x)T (y − x) + ϕ(y) − ϕ(x) : y ∈ C ∩ U , (2.8) hàm m(x, U ) hàm khoảng cách toán (2.5) Mệnh đề 2.1 Giả sử S(x, U ) = ∅ với (x, U) ∈ ℵC Khi phát biểu sau tương đương: (a) x∗ nghiệm địa phương (2.5) ; (b) x∗ ∈ C x∗ ∈ S (x∗, U ) ; (c) x∗ ∈ C m (x∗, U ) = Chứng minh *) Ta chứng minh (a) tương đương (b) Giả sử x∗ ∈ C x∗ ∈ S(x∗, U ) Thì ∀y ∈ C ∩ U = F (x∗)T (x∗ − x∗ ) + ϕ(x∗) − ϕ(x∗) ≤ F (x∗)T (y − x∗) + ϕ(y) − ϕ(x∗) Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 34 Vì x∗ nghiệm địa phương toán (2.5) Ngược lại, F (x∗)T (y − x∗) + ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ C ∩ U, (2.9) rõ ràng x∗ ∈ S(x∗, U ) Ta thấy m(x, U ) ≤ 0, ∀x ∈ C∩U Do x∗ ∈ C∩U m(x∗, U ) = F (x∗)T (y − x∗) + ϕ(y) − ϕ(x∗) ≥ 0, ∀y ∈ C ∩ U có nghĩa (a) (c) tương đương Gọi ΓC tập hợp tất hàm lồi, thường, nửa liên tục khả vi phân C Do g h hàm lồi thuộc ΓC Nên cộng vào trừ hàm lồi mạnh h(x), ta kết luận hai hàm g h lồi mạnh C Khi x nghiệm (2.5) x thỏa mãn toán tối ưu hóa sau: F (x)T (y − x) + g(y) − h(y), ∀y ∈ C Định nghĩa 2.2 Một điểm x ∈ C gọi điểm dừng toán (2.5) ∈ F (x) + ∂g(x) − ∂h(x) + NC (x), (2.10) NC (x) := w : wT (y − x) ≤ 0, ∀y ∈ C nón pháp tuyến ngồi C x ∈ C ∂g(x) ∂h(x) vi phân x hàm lồi g h Vì NC (x) nón lồi, với c > 0, (2.10) tương đương với ∈ c {F (x) + ∂g(x) − ∂h(x)} + NC (x) (2.11) Ta đặt g1 (x) := g(x) + δC (x), ∂δC (x) gọi vi phân hàm δC C x Theo định lý Moreau-Rockafellar, ∂g1(x) = ∂g(x) + ∂δC (x) Do theo định nghĩa x điểm dừng ∈ c {F (x) + ∂g(x) − ∂h(x)} + ∂δC (x), (2.12) c > tham số hiệu chỉnh Số hóa Trung tâm Học lieäu http://lrc.tnu.edu.vn/ 35 Từ Mệnh đề 2.1 ta suy nghiệm địa phương toán (2.5) điểm dừng Cho g1 (x) = g(x) + δC (x), g δC lồi đóng thường nên hàm g1 lồi đóng Suy ra, ∂g1(x) = ∂g(x) + NC (x) với x ∈ C Mệnh đề 2.2 Điều kiện cần đủ cho x điểm dừng toán (2.5) x ∈ (I + c∂g1 )−1 (x − cF (x) + c∂h(x)) , (2.13) c > I ánh xạ đồng Chứng minh Vì g1 lồi, đóng thường nên ánh xạ (I + ∂g1)−1 đơn trị điểm Hơn nữa, x thỏa mãn điều kiện (2.13) x − cF (x) + cv(x) ∈ (I + c∂g1 ) (x), ∀v(x) ∈ ∂h(x) Vì NC (x) nón ∂g1(x) = ∂g(x) + ∂δC (x) = ∂g(x) + NC (x), nên x − cF (x) + cv(x) ∈ (I + c∂g1) (x) Tương đương với ∈ F (x) + ∂g(x) − ∂h(x) + NC (x) điều phải chứng minh 2.3 Thuật tốn tìm điểm dừng Nếu ta đặt vế bên phải (2.13) Z(x) (2.13) trở thành x ∈ Z(x) Mệnh đề 2.2 gợi ý phương pháp tìm điểm dừng toán (2.5) thực chất tìm điểm bất động lát cắt điểm gần kề ánh xạ Z Theo phương pháp thuật toán điểm gần kề ta xây dựng dãy lặp sau: *) Lấy tùy ý x0 ∈ C đặt k = Số hóa Trung tâm Học lieäu http://lrc.tnu.edu.vn/ 36 *) Với k = 0, 1, 2, cho xk , tính xk+1 theo cơng thức: xk+1 = (I + ck ∂g1)−1 xk − ck F (xk ) + ck v(xk ) , (2.14) v(xk ) ∈ ∂h(xk ) Nếu định nghĩa y k = xk − ck F (xk ) + ck v(xk ) việc tìm xk+1 trở thành tìm lời giải toán quy hoạch lồi mạnh: x − yk 2ck g (x) + (2.15) :x∈C Thật vậy, theo điều kiện tối ưu hóa biết cho quy hoạch lồi, xk+1 nghiệm tối ưu toán lồi (2.15) nếu: ∈ ∂g(xk+1)+ k+1 (x − y k )+NC (xk+1) ck Chú ý F = h = quy trình (2.14) trở thành thuật tốn điểm gần kề quen thuộc cho toán quy hoạch lồi, F = phương pháp điểm gần kề cho tối ưu hóa DC Mệnh đề 2.3 Giả sử tập điểm dừng S ∗ toán (2.5) khác rỗng, F tự với hệ số σ, g lồi mạnh C với hệ số τ > h khả vi L-Lipschits C Khi với x∗ ∈ S ∗ ta có αk xk − x∗ − βk xk+1 − x∗ 2 ≥ ck (2σ − ck ) F xk − F (x∗) , (2.16) αk = + ck Lt, βk = + 2ck τ − ck L t t > Chứng minh Trước hết ta cần ý rằng, g thường, lồi đóng C lồi đóng khác rỗng nên ánh xạ (I + ck ∂g1)−1 đơn trị định nghĩa ck > Do dãy {xk } xây dựng (2.14) Từ (2.14) suy ra: xk+1 = xk − ck F (xk ) + ck v k − ck z k+1, (2.17) v k = ∇h(xk ) z k+1 ∈ ∂g1(xk+1) = ∂g(xk+1) + NC (xk+1) Theo định nghĩa, x∗ điểm dừng tốn bất đẳng thức biến Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 37 phân hỗn hợp (2.5) = z ∗ + F (x∗) − v ∗, z ∗ ∈ ∂g1(x∗) v ∗ = ∇h(x∗) Theo tính chất F C suy ≤(F (xk ) − F (x∗))T (xk − x∗) − σ F (xk ) − F (x∗) =(F (xk ) − F (x∗))T (xk − x∗ − ck F (xk ) + ck F (x∗)) − ∆k ∆k = (σ − ck ) F (xk ) − F (x∗) Vì F (x∗) = v ∗ − z ∗ xk+1 = xk − ck F (xk ) + ck v k − ck z k+1 , ta thu từ bất đẳng thức ≤(F (xk ) − F (x∗))T (xk − ck F (xk ) + ck v k − ck z k+1 − x∗ ) −ck (F (xk ) − F (x∗))T (v k − v ∗ − z k+1 + z ∗ ) − ∆k (2.18) =(F (xk ) − F (x∗))T (xk+1 − x∗) −ck (F (xk ) − F (x∗))T (v k − v ∗ − z k+1 + z ∗ ) − ∆k Ta lại có, g lồi mạnh với hệ số τ > nên ∂g đơn điệu mạnh với hệ số τ Suy ánh xạ ∂g1 = ∂g + NC đơn điệu mạnh với hệ số τ Vì thế, từ z k+1 ∈ ∂g1(xk+1), ta viết (xk+1 − x∗)(z k+1 − z ∗ ) − τ xk+1 − x∗ (2.19) ≥ Cộng (2.18) (2.19), sử dụng z ∗ + F (x∗) = v ∗ (2.17) ta có: ≤(F (xk ) − F (x∗) + z k+1 − z ∗ )T (xk+1 − x∗) −ck (F (xk ) − F (x∗))T (v k − v ∗ − z k+1 + z ∗ ) − τ xk+1 − x∗ (xk − x∗) − (xk+1 − x∗) k+1 ∗ T k =(x − x ) (v + − v∗) ck − ∆k −ck (F (xk ) − F (x∗))T (v k − v ∗ − z k+1 + z ∗ ) − τ xk+1 − x∗ − ∆k Bây ta định nghĩa xˆk = xk − x∗; xˆk+1 = xk+1 − x∗; vˆk = v k − v ∗ ; zˆk+1 = z k+1 − z ∗ Fˆ (xk ) = F (xk ) − F (x∗) Ta viết bất đẳng thức thành: 2ck (ˆ xk+1)T vˆk −2(xk+1)T (ˆ xk+1 − xˆk ) − 2c2k (Fˆ k )T (ˆ v k − zˆk+1)− − 2ck τ xˆk+1 − 2ck ∆k ≥ (2.20) Từ (2.17) ta có: xˆk+1 − xˆk = c2k Fˆ k + c2k zˆk+1 − vˆk Số hóa Trung tâm Học liệu − 2c2k (Fˆ k )T (ˆ v k − zˆk+1 ) http://lrc.tnu.edu.vn/ 38 Đồng thời ta có: 2(xk+1)T (ˆ xk+1 − xˆk ) = xˆk+1 − xˆk + xˆk+1 2 − xˆk Ta thu từ (2.20) 2ck (ˆ xk+1)T vˆk −2(1 + 2ck τ ) xˆk+1 − c2k k+1 k vˆ − zˆ + xˆk − c2k Fˆ k − (2.21) − 2ck ∆k ≥ Vì ∇h L-Lipschitz, nên ta có vˆk ≤ L xˆk Sử dụng bất đẳng thức Chebyshev dễ dàng chứng minh được: 2(ˆ xk+1)T vˆk ≤2 xˆk+1 ≤L t xˆ Thay 2(ˆ x ) vˆ L t xˆ k+1 T k k vˆk ≤ 2L xˆk k xˆk+1 + t xˆk+1 + t xˆk+1 (2.22) , ∀t > vào (2.21) sử dụng định nghĩa ∆k ta có: αk xˆk − βk xˆk+1 ≥ ck (2σ − ck ) Fˆ k + c2k vˆk − zˆk+1 (2.23) L αk = + ck Lt, βk = (1 + 2ck τ − ck ) t > t Mệnh đề chứng minh Hệ 2.1 Với giả thiết Mệnh đề 2.3, ta giả sử thêm τ ≥ L, dãy {xk } sinh (2.14) hội tụ đến điểm dừng toán (2.5) Hơn nữa, τ > L F µ-đơn điệu mạnh dãy {xk } hội tụ tuyến tính đến điểm dừng toán (2.5) Chứng minh Giả sử τ ≥ L Cho m M hai số thực thỏa mãn < m ≤ ck ≤ M < 2σ Nếu ta chọn t − từ (2.23) ta có: xk − x∗ − xk+1 − x∗ ≥ m(2σ − M) F (xk ) − F (x∗) + ML Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ ≥ 39 Suy {xk } bị chặn dãy { xk − x∗ } hội tụ khơng tăng bị chặn Ngồi ra, ta có lim F (xk ) = F (x∗) Từ (2.17) ta có: k→∞ xk+1 − xk = lim = lim (v k − z k+1 − F k ) = lim (v k − z k+1) − F ∗ , k→∞ k→∞ k→∞ ck thay −F ∗ = z ∗ − v ∗ ta lim (v k − v ∗ − z k+1 + z ∗ ) = k→∞ Cho x điểm giới hạn dãy bị chặn xk {xk : k ∈ V } dãy hội tụ tới x∞ Vì F tự bức, liên tục nên lim F (xk ) = F (x∗) kéo theo ∞ k→∞ F (x ) = F (x ) Theo giả thiết ∇h L-Lipschitz nên v k − v ∗ ≤ L xk − x∗ , dãy {v k } bị chặn ta giả thiết dãy {v k : k ∈ V } hội tụ tới v ∞ Sử dụng tính liên tục ∇h ta có: v ∞ = ∇h(x∞) Lấy z ∈ ∂g1(x) Do tính đơn điệu mạnh ∂g1 ta có: ∞ ∗ ≤τ xk − x ≤ z k − z, xk − x = z k − z, xk − x∞ + z k − z, x∞ − x = z k − z, xk − x∞ + z k − v k−1 − z, x∞ − x + v k−1, x∞ − x Chú ý lim (v k − v ∗ − z k+1 + z ∗ ) = 0, k→∞ k suy z − v → z ∗ − v ∗ = −F (x∗) Lấy giới hạn vế phải bất đẳng thức ta có: k+1 v ∞ − F (x∗) − x, x∞ − x ≥ 0, tính đơn điệu cực đại ∂g1 suy v ∞ − F (x∗) ∈ ∂g1(x∞) Từ F (x∞) = f (x∗) ta có v ∞ − F (x∞) ∈ ∂g1(x∞) Mặt khác, v ∞ = ∇h(x∞ ) nên ∈ ∂g1(x∞) + F (x∞) − ∇h(x∞ ), điều có nghĩa x∞ điểm dừng tốn (2.5) Thế x∗ (2.16) x∞ nhận xét { xk − x∞ } hội tụ, ta suy dãy {xk } hội tụ tới x∞ dãy hội tụ tới x∞ Tiếp theo từ (2.16) ta có: αk xk − x∗ Do L < τ < r := Suy 2 ≥ βk xk+1 − x∗ αk < 1, ∀k ≥ βk xk+1 − x∗ ≤ r xk − x∗ , Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 40 điều chứng tỏ {xk } hội tụ x∗ với tốc độ tuyến tính Nếu F đơn điệu mạnh với hệ số µ > F (xk ) − F (x∗) xk − x∗ ≥ F (xk ) − F (x∗), xk − x∗ ≥ µ xk − x∗ , F (xk ) − F (x∗) ≥ µ2 xk − x∗ Thế bất đẳng thức vào (2.16) xếp lại ta có: αk − µ2 ck (2σ − ck ) xk − x∗ 2 ≥ βk xk+1 − x∗ Sử dụng giả thiết < m ≤ ck ≤ M < 2σ chọn t = ta thu từ bất đẳng thức cuối: + ck L − µ2 (2σ − ck ) xk − x∗ 2 ≥ (1 + 2ck τ − ck L) xk+1 − x∗ m ) > L; + ck L − µ2 ck (2σ − ck ) < + 2ck τ − ck L, nên ta có dãy {xk } hội tụ tuyến tính tới x∗ Vì r + µ2 (σ − Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 41 Kết luận Luận văn trình bày kiến thức tốn bất đẳng thức biến phân hỗn hợp mơ hình cân Nash-Cournot Cụ thể luận văn trình bày tồn nghiệm tốn bất đẳng thức biến phân hỗn hợp Đồng thời luận văn trình bày mơ hình cân Nash-Cournot xét thuật tốn giải mơ hình theo cách tiếp cận bất đẳng thức biến phân hỗn hợp cho trường hợp cước phí hàm aphin, cước phí hàm lõm Trong trường hợp cước phí hàm lõm bất đẳng thức biến phân hỗn hợp tương ứng khơng lồi, theo nghĩa nghiệm địa phương khơng phải nghiệm tồn cục Trong trường hợp luận văn trình bày phương pháp tìm điểm dừng dựa theo phương pháp điểm gần kề Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 42 Tài liệu tham khảo Tài liệu Tiếng Việt [1] Đỗ Văn Lưu Phan Huy Khải, Giải tích lồi, (2000), NXB Khoa học Kỹ thuật, Hà Nội [2] Lê Dũng Mưu Nguyễn Văn Hiền, Nhập mơn giải tích lồi ứng dụng (sẽ ra), NXB Khoa học Tự nhiên Công nghệ [3] Nguyễn Văn Qúy, Tiếp cận bất đẳng thức biến phân tối ưu hóa giải mơ hình cân thị trường độc quyền tập đoàn Nash-Cournot với hàm chi phí lõm, Tạp chí Ứng Dụng Tốn Học, tập IV(số 1), 1-23 [4] Hoàng Tụy, Hàm thực giải tích hàm (2003), NXB Đại học Quốc Gia, Hà Nội Tài liệu Tiếng Anh [5] Le Dung Muu and Tran Dinh Quoc, One step from DC optimization to DC mixed variational inequalities, Optimization, (59), 63 - 76, 2010 [6] Le Dung Muu, Nguyen Van Hien and Nguyen Van Quy, On Nash - Cournot oligopolistic market equilibrium models with concave cost functions”, J Glob Optim, (41), 351 - 364, 2008 [7] Nguyen Van Hien, Optimization and Applied Mathematics, giảng Đại Học Cần Thơ, 2003 [8] R Tyrrell Rockafellar, Monotone operators and the proximal point algorithm, SlAM J Control and optimization, (14), 877 - 898, 1976 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ ... Mơ hình cân Nash -Cournot cổ điển 1.2.1 Phát biểu mơ hình Nash -Cournot 1.2.2 Trường hợp cước phí tuyến tính MƠ HÌNH CÂN BẰNG NASH -COURNOT LÕM 2.1 Mơ hình cân Nash -Cournot 2.2 Phương. .. THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC - NGUYỄN THỊ PHƯƠNG LAN PHƯƠNG PHÁP ĐIỂM GẦN KỀ GIẢI MƠ HÌNH CÂN BẰNG NASH - COURNOT Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60 46 01 12 LUẬN VĂN... Học liệu http://lrc.tnu.edu.vn/ giới thiệu phương pháp giải mơ hình trường hợp hàm chi phí hàm lõm phương pháp tìm điểm dừng theo thuật tốn điểm gần kề Để hoàn thành luận văn em xin bày tỏ lòng