Luận văn Phương pháp lặp Banach cho bài toán bất đẳng thức biến phân - Phan Thế Nghĩa

0đại học thái nguyên trường đại học khoa học ---------------------------- Phan Thế Nghĩa phương pháp lặp Banach cho BàI TOáN BấT ĐẳNG THứC BIếN PHÂN luận văn thạc sĩ toán học ứng dụng Thái Nguyên-2009 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 0đại học thái nguyên trường đại học khoa học ---------------------------- Phan Thế Nghĩa phương pháp lặp Banach cho BàI TOáN BấT ĐẳNG THứC BIếN PHÂN Chuyên ngành: Toán ứng dụng Mã số: 60.46.36 luận văn thạc sĩ toán học ứng dụng NGUờI HướNG DẫN KHOA HọC: TS. PHạM NGọC ANH Thái Nguyên-2009 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 01 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 2Mục lục Trang phụ bìa Mục lục 2 Lời cảm ơn 3 Một số ký hiệu và chữ viết tắt 4 Lời nói đầu 5 Chương 1. Bài toán Bất đẳng thức biến phân 1.1. Một số khái niệm cơ bản 7 1.2. Phát biểu bài toán và ví dụ 10 1.3. Sự tồn tại nghiệm của bài toán VI 18 Chương 2. Phương pháp lặp Banach giải bài toán (VI) đơn điệu mạnh 2.1. Tính không giãn của ánh xạ nghiệm 23 2.2. Mô tả thuật toán và sự hội tụ 27 Chương 3. Phương pháp lặp Banach giải bài toán đồng bức 3.1. Tính không giãn của ánh xạ nghiệm 30 3.2. Mô tả thuật toán và sự hội tụ 35 3.3. Kết quả tính toán thử nghiệm 3.3.1. Mô hình cân bằng bán độc quyền 38 3.3.2. Kết quả tính toán thử nghiệm 43 Tài liệu tham khảo 44 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 3Lời cảm ơn Bản luận văn này được hoàn thành tại trường Đại học Khoa học-Đại học Thái Nguyên dưới sự hướng dẫn của TS. Phạm Ngọc Anh. Tác giả xin bày tỏ lòng kính trọng và biết ơn sâu sắc tới thầy về sự tận tình hướng dẫn trong suốt thời gian tác giả làm luận văn. Trong quá trình học tập và làm luận văn, thông qua các bài giảng và xêmina, tác giả thường xuyên nhận được sự quan tâm giúp đỡ và đóng góp những ý kiến quý báu của PGS. TS. Lê Thị Thanh Nhàn, TS. Nguyễn Thị Thu Thủy và các thầy các cô trong trường Đại học Khoa học-Đại học Thái Nguyên. Từ đáy lòng mình, tác giả xin bày tỏ lòng biết ơn sâu sắc đến các thầy các cô. Tác giả xin bày tỏ lòng biết ơn tới các thầy, các cô khoa Khoa học Cơ bản, Ban Chấp Hành Đoàn trường Cao đẳng Công nghiệp Thái Nguyên đã đã tạo điều kiện giúp đỡ tác giả trong thời gian làm cao học. Xin chân thành cảm ơn anh chị em học viên cao học và bạn bè đồng nghiệp gần xa đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Luận văn sẽ không hoàn thành được nếu không có sự thông cảm, giúp đỡ của những người thân trong gia đình tác giả. Đây là món quà tinh thần, tác giả xin kính tặng gia đình thân yêu của mình với tấm lòng biết ơn chân thành và sâu sắc. Tác giả Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 4Một số ký hiệu và chữ viết tắt R n không gian Euclide n-chiều |β| trị tuyệt đối của số thực β x := y x được định nghĩa bằng y ∀x với mọi x ∃x tồn tại x I ánh xạ đồng nhất A ⊂ B tập A là tập con thực sự của tập B A ⊆ B tập A là tập con của tập B A ∪B A hợp với B A ∩B A giao với B AìB tích Đề-các của hai tập A và B convD bao lồi của tập D argmin{f(x) | x ∈ C} tập các điểm cực tiểu của hàm f trên C AT ma trận chuyển vị của ma trận A xk → x dãy {xk} hội tụ mạnh tới x V I bài toán bất đẳng thức biến phân Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 5Lời nói đầu Theo Harker và Pang, bài toán bất đẳng thức biến phân được giới thiệu lần đầu tiên vào năm 1966 bởi Hartman và Stampacchia. Những nghiên cứu đầu tiên về bất đẳng thức biến phân liên quan tới việc giải các bài toán biến phân, bài toán điều khiển tối ưu và các bài toán biên có dạng của phương trình đạo hàm riêng. Bài toán biến phân trong không gian vô hạn chiều và các ứng dụng của nó được giới thiệu trong cuốn sách "An introduction to variational inequalities and their application" của Kinderlehrer và Stampacchia xuất bản năm 1980 và trong cuốn sách "Variational and quasivariational inequalities: Application to free boundary problems" của Baiocchi và Capelo xuất bản năm 1984. Năm 1979 Michael J. Smith đưa ra bài toán cân bằng mạng giao thông và năm 1980 Defermos chỉ ra rằng: Điểm cần bằng của bài toán này là nghiệm của bài toán bất đẳng thức biến phân. Từ đó bài toán bất đẳng thức biến phân được phát triển và trở thành một công cụ hữu hiệu để nghiên cứu và giải các bài toán cân bằng trong kinh tế tài chính, vận tải, lý thuyết trò chơi và nhiều bài toán khác (xem [7]). Bài toán bất đẳng thức biến phân có quan hệ mật thiết với các bài toán tối ưu khác. Bài toán bù phi tuyến, xuất hiện vào năm 1964 trong luận án tiến sĩ của Cottle, là một trường hợp đặc biệt của bài toán bất đẳng thức biến phân (xem [5]). Gần đây, bài toán bất đẳng thức biến phân cũng là một đề tài được nhiều người quan tâm nghiên cứu vì vai trò của nó trong lý thuyết toán học và trong các ứng dụng thực tế (xem [5, 7]). Một trong các hướng nghiên cứu quan trọng của bài toán bất đẳng thức biến phân là việc xây dựng các phương pháp giải. Thông thường các phương pháp giải được chia thành các loại sau: Loại thứ nhất là các phương pháp chuyển bài toán về hệ phương trình và dùng các phương pháp thông dụng như phương pháp Newton, phương pháp điểm trong để giải hệ phương trình này. Loại thứ hai là phương pháp có tính chất kiểu đơn điệu. Điển hình của phương pháp này là các phương pháp gradient sau này được tổng quát bởi Cohen thành nguyên Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 6lý bài toán phụ (xem [5]), phương pháp điểm gần kề của Rockafellar (xem [3]), phương pháp hiệu chỉnh Tikhonov (xem [5]),.... Các phương pháp này khá hiệu quả, dễ thực thi trên máy tính nhưng các điều kiện hội tụ chỉ được đảm bảo dưới các giả thiết khác nhau về tính chất đơn điệu. Loại thứ ba là các phương pháp được dựa trên kỹ thuật hàm chắn (xem [5]). Nội dung chính của phương pháp này là chuyển bài toán bất đẳng thức biến phân về cực tiểu của hàm chắn và sau đó sử dụng kỹ thuật tối ưu trơn hoặc không trơn để tìm cực tiểu của hàm chắn. Phương pháp này có thể giải được các bài toán với các giả thiết rất nhẹ. Tuy nhiên, tốc độ hội tụ của thuật toán được đề xuất là chậm (xem [5]). Loại thứ tư là các phương pháp dựa trên cách tiếp cận điểm bất động. Nội dung chính của phương pháp này là chuyển bài toán bất đẳng thức biến phân về tìm điểm bất động của ánh xạ nghiệm. Luận văn này trình bày phương pháp giải bài toán bất đẳng thức biến phân thông qua tìm điểm bất động của ánh xạ nghiệm được viết trong bài báo "P. N. Anh, L. D. Muu, V. H. Nguyen and J. J. Strodiot (2005), On the contrac- tion and nonexpansiveness properties of the marginal mapping in generalized variational inequalities involving cocoercive operators, in: Generalized Con- vexity and Generalized Monotonicity and Applications. Eds A. Eberhard, N. Hadjisavvas and D. T. Luc, Springer, pp. 89-111". Ngoài lời nói đầu và phần tài liệu tham khảo, luận văn được chia làm ba chương. Chương 1 có tiêu đề là "bài toán bất đẳng thức biến phân". Chương này nhắc lại các kiến thức cơ bản về bài toán bất đẳng thức biến phân, các ví dụ, các kiến thức liên quan và các ứng dụng của bài toán bất đẳng thức biến phân. Chương 2 gồm hai phần cơ bản: Phần thứ nhất trình bày mối quan hệ giữa nghiệm của bài toán bất đẳng thức biến phân và ánh xạ nghiệm. Phần thứ hai chỉ ra ánh xạ nghiệm là co khi hàm giá là đơn điệu mạnh và Lipschitz. Chương 3 trình bày phương pháp lặp Banach cho ánh xạ đồng bức và một vài tính toán ứng dụng của thuật toán được đề xuất. Khi đó, ánh xạ nghiệm chỉ là không giãn và việc tìm điểm bất động của ánh xạ không giãn được tìm theo kiểu điểm bất động của Nadler. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 7CHƯƠNG I BàI TOáN BấT ĐẳNG THứC BIếN PHÂN 1.1. Một số khái niệm cơ bản Cho hai véc tơ x := (x1, x2, ..., xn) T , y := (y1, y2, ..., yn) T ∈ Rn 〈x, y〉 = n∑ i=1 xiyi được gọi là tích vô hướng của hai véc tơ x và y. Chuẩn Euclide và khoảng cách được xác định tương ứng bởi ||x|| := √ 〈x, x〉, d(x, y) := ||x− y||. Ta nhắc lại một số kiến thức cơ bản của giải tích lồi sẽ được dùng cho các chương tiếp theo. Định nghĩa 1.1. • Tập con C ⊂ Rn được gọi là tập lồi, nếu λx + (1− λ)y ∈ C ∀x, y ∈ C, λ ∈ (0, 1). • Tập con C ⊂ Rn được gọi là nón, nếu λx ∈ C ∀x ∈ C, λ ≥ 0. • Cho C ⊂ Rn là một tập lồi và x ∈ C , nón pháp tuyến ngoài của C tại x, ký hiệu NC(x), được xác định bởi công thức NC(x) := {w ∈ R n : 〈w, y − x〉 ≤ 0 ∀y ∈ C}. Cho C ⊂ Rn là một tập lồi, ánh xạ f : C → Rn. Khi đó, Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 8Định nghĩa 1.2. • Miền hữu hiệu của f , ký hiệu dom f , được xác định bởi domf := {x ∈ Rn : f(x) < +∞}. • f được gọi là chính thường, nếu domf 6= ∅, f(x) > −∞ ∀x ∈ C. • f được gọi là hàm lồi trên C , nếu f(λx1 + (1− λ)x2) ≤ λf(x1) + (1− λ)f(x2) ∀x1, x2 ∈ C, λ ∈ [0, 1]. • f được gọi là hàm lồi chặt trên C , nếu f(λx1 + (1− λ)x2) < λf(x1) + (1− λ)f(x2) ∀x1 6= x2 ∈ C, λ ∈ (0, 1). • f được gọi là hàm lồi mạnh với hệ số β > 0 trên C , nếu ∀x1 6= x2 ∈ C, λ ∈ (0, 1), ta có f(λx1 + (1− λ)x2) < λf(x1) + (1− λ)f(x2)− λ(1− λ)β||x1 − x2||2. Bây giờ ta giả sử rằng f là một hàm lồi trên tập lồi C trong không gian Rn. Khi đó, véc tơ w ∈ Rn được gọi là dưới gradient của hàm f tại x ∈ C , nếu f(y)− f(x) ≥ 〈w, y − x〉 ∀y ∈ C. Tập tất cả các dưới gradient của hàm f tại x được gọi là dưới vi phân của f , ký hiệu ∂f(x), hay ∂f(x) := {w ∈ Rn : f(y)− f(x) ≥ 〈w, y − x〉 ∀y ∈ C}. Khi đó, f được gọi là khả dưới vi phân trên C , nếu ∂f(x) 6= ∅ ∀x ∈ C. Ví dụ 1.1. Cho C là một tập lồi khác rỗng của không gian Rn. Xét hàm chỉ trên tập C δ(x) :=   0 nếu x ∈ C, +∞ nếu x /∈ C. Khi đó ∂δC(x) = NC(x). Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 9Thật vậy, nếu x ∈ C thì δC(x) = 0 và ∂δC(x) = {w ∈ R n : δC(y) ≥ 〈w, y − x〉 ∀y ∈ C}. Hay ∂δC(x) = {w ∈ R n : 0 ≥ 〈w, y − x〉 ∀y ∈ C} = NC(x). Ví dụ 1.2. Trong không gian R n cho hàm chuẩn f(x) := ||x|| x ∈ Rn. Khi đó, ∂f(x) :=   {w ∈ Rn : ||w|| = 1, 〈w, x〉 = ||x||} nếu x 6= 0, B¯(0, 1) nếu x = 0, trong đó B¯(0, 1) là hình cầu đóng, tâm tại 0 và bán kính 1. Thật vậy, ta xét các trường hợp sau: Trường hợp 1. Với x 6= 0, ta cần chứng minh ∂f(x) = {w ∈ Rn : ||w|| = 1, 〈w, x〉 = ||x||}. Nếu w thỏa mãn ||w|| = 1, 〈w, x〉 = ||x|| thì 〈w, x〉 ≤ ||w||.||x|| = ||x||. Do đó 〈w, x− y〉 ≤ ||x|| − ||y||. Hay w ∈ ∂f(x). Ngược lại, nếu w ∈ ∂f(x), thì −||x|| = ||0|| − ||x|| ≥ 〈w, 0− x〉 = −〈w, x〉, ||x|| = ||2x|| − ||x|| ≥ 〈w, 2x− x〉 = 〈w, x〉 suy ra ||x|| = 〈w, x〉. (∗) Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 10 Mặt khác ||λz + x|| − ||x|| ≥ 〈w, λz + x− x〉 = 〈w, λz〉 ∀λ > 0, z ∈ Rn. Suy ra ||z + x λ || − 1 λ ||x|| ≥ 〈w, x〉. Cho λ → ∞, ta nhận được ||z|| ≥ 〈w, z〉 ∀z ∈ Rn. Do vậy ||w|| ≤ 1. Hơn nữa nếu ||w|| < 1 thì với mọi z ∈ Rn, ||z|| = 1 ta có |〈w, z〉| < 1. Khi đó, thay z = x||x|| ta có |〈w, z〉| = |〈w, x ||x|| 〉| < 1. Do đó 〈w, x〉 < ||x||. Điều này mâu thuẫn với (∗). Vậy ||w|| = 1. Trường hợp 2. Với x = 0. Ta có ∂f(x) = {w ∈ Rn : 〈w, y〉 ≤ ||y|| ∀y} = {w ∈ Rn : ||w|| ≤ 1} = B¯(0, 1). 1.2. Phát biểu bài toán và ví dụ "Bài toán bất đẳng thức biến phân" là một trong những bài toán được quan tâm nhiều trong toán học nói chung và đặc biệt trong ngành tối ưu tính toán nói riêng. Luận văn này sẽ trình bày một phương pháp giải bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều. Chương này bao gồm việc nhắc lại các kiến thức cơ bản nhất về bài toán bất đẳng thức biến phân sẽ được sử dụng cho các chương sau. Bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều có thể được phát biểu như sau: Cho C là một tập con lồi, đóng khác rỗng của không gian Euclidean n-chiều R n , F : C → Rn là ánh xạ liên tục. Bài toán bất đẳng thức biến phân Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 11 (viết tắt là: VI) là bài toán tìm điểm x∗ ∈ C , sao cho: 〈F (x∗), x− x∗〉 ≥ 0 ∀x ∈ C. (1.1) Tập nghiệm của VI ký hiệu là S∗. Định nghĩa 1.3. Cho C là tập lồi, đóng trong Rn, và cho F : C → Rn là một ánh xạ. Khi đó, F được gọi là: (a) đơn điệu trên C , nếu: 〈F (u)− F (v) , u− v〉 ≥ 0 ∀u, v ∈ C (b) đơn điệu ngặt trên C , nếu: 〈F (u)− F (v) , u− v〉 > 0 ∀u, v ∈ C, u 6= v. (c) đơn điệu mạnh trên C với hằng số τ > 0 (viết tắt là:τ -đơn điệu mạnh) nếu: 〈F (u)− F (v) , u− v〉 ≥ τ ‖u− v‖2 ∀u, v ∈ C. (d) đồng bức với mô đun δ (viết tắt là:δ-đồng bức) trên C nếu tồn tại một số δ > 0 sao cho: 〈F (u)− F (v), u− v〉 ≥ δ||F (u)− F (v)||2 u, v ∈ C. Ta nhắc lại kết quả tương đương sau: Nhận xét 1.1. Cho C là một tập lồi và F : C → Rn là một ánh xạ khả vi liên tục trên tập mở chứa C . Khi đó, i) F đơn điệu trên C khi và chỉ khi ∇F (x) là nửa xác định dương trên C hay 〈y,∇F (x)y〉 ≥ 0 ∀y ∈ C. ii) F đơn điệu chặt trên C khi và chỉ khi ∇F (x) là xác định dương trên C hay 〈y,∇F (x)y〉 > 0 ∀y ∈ C, y 6= 0. iii) F đơn điệu mạnh trên C khi và chỉ khi ∇F (x) là xác định dương đều trên C hay tồn tại β > 0 sao cho 〈y,∇F (x)y〉 > β||y||2 ∀y ∈ C, y 6= 0. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 12 Các ví dụ dưới đây cho ta thấy được cách tiếp cận của bài toán bất đẳng thức biến phân Ví dụ 1.3. Cho f(x) là một hàm thực khả vi trên tập mở chứa C = [a, b]. Tìm x0 ∈ C sao cho f(x0) = min x∈C f(x). x0 ∈ [a, b], suy ra có 3 trường hợp xảy ra: TH1: Nếu x0 ∈ (a, b), theo định lý Fermat, ta có f ′(x0) = 0. TH2: Nếu x0 = a, f ′(x0) = lim x→x0+ f(x)−f(x0) x−x0 ≥ 0. TH2: Nếu x0 = b, f ′(x0) = lim x→x0 − f(x)−f(x0) x−x0 ≤ 0. Kết hợp lại, ta có thể viết: x0 là nghiệm của bài toán f ′(x0).(x− x0) ≥ 0 ∀x ∈ C. Như vậy x0 là nghiệm của bài toán bất đẳng thức biến phân VI với F = f ′ trên C = [a, b]. Bây giờ, ta xét ví dụ tổng quát hơn Ví dụ 1.4. Cho f(x) là một hàm thực khả vi trên tập mở chứa C ⊆ IRn. Tìm x0 ∈ C sao cho f(x0) = min x∈C f(x). Mệnh đề 1.1. Nếu x0 là nghiệm của bài toán trên, thì x0 là nghiệm của bài toán bất đẳng thức biến phân VI với F (x) := ∇f(x). Chứng minh. Với mọi y ∈ C , do C lồi nên (1− t)x0 + ty ∈ C ∀t ∈ [0, 1]. Đặt ϕ(t) := f(x0 + t(y − x0)). Giả thiết cho x0 là nghiệm hay t = 0 là nghiệm của ϕ(t) trên [0, 1]. Theo Ví dụ 1.3, ta có ϕ′(t0).(t− t0) ≥ 0 ∀t ∈ [0, 1]. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 13 Hay 〈∇f(x0), x− x0〉 ≥ 0 ∀x ∈ C. 2 Mệnh đề 1.2. Cho f là hàm lồi khả vi trên tập lồi C ⊆ Rn. Khi đó, x0 ∈ C là nghiệm của bài toán min x∈C f(x) khi và chỉ khi x0 là nghiệm của bài toán bất đẳng thức VI với F (x) := ∇f(x). Chứng minh. Điều kiện cần được suy ra từ Mệnh đề 1.1. Do f là hàm lồi trên C , nên f(x)− f(x0) ≥ 〈∇f(x0), x− x0〉 ∀x ∈ C. Giả thiết cho 〈∇f(x0), x− x0〉 ≥ 0 ∀x ∈ C. Do đó f(x) ≥ f(x0) ∀x ∈ C. Hay x0 là nghiệm của bài toán min x∈C f(x). 2 Ví dụ 1.5. (Bài toán bù, ký hiệu CP) Cho C = Rn+ và F : C → R n . Bài toán được đặt ra là: Tìm điểm x0 ∈ C sao cho F (x0) ∈ C, 〈F (x0), x0〉 = 0. Mệnh đề 1.3. x0 ∈ C = Rn+ là nghiệm của bài toán bù CP khi và chỉ khi x 0 là nghiệm của bài toán VI hay 〈F (x0), x− x0〉 ≥ 0 ∀x ∈ C. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 14 Chứng minh. (⇒) Giả sử x0 là nghiệm của bài toán bù CP hay F (x0) ∈ C, 〈F (x0), x0〉 = 0. Khi đó 〈F (x0), x− x0〉 = 〈F (x0), x〉 − 〈F (x0), x0〉 = 〈F (x0), x〉 ≥ 0 ∀x ∈ C. (⇐) Giả sử x0 là nghiệm của bài toán bất đẳng thức biến phân VI hay x0 ∈ C : 〈F (x0), x− x0〉 ≥ 0 ∀x ∈ C. Gọi ei = (0, 0, ..., 0, 1, 0, ...0) T (1 ở vị trí thứ i). Khi đó, x1 = x0 + ei ∈ C . Thay x1 vào bất đẳng thức biến phân, ta có 〈F (x0), x1 − x0〉 ≥ 0. Hay 〈F (x0), ei〉 ≥ 0 ∀i = 1, 2, ...n. Vậy F (x0) ∈ C . Từ 0 ∈ C và 〈F (x0), x− x0〉 ≥ 0 ∀x ∈ C. suy ra −〈F (x0), x0〉 ≥ 0. Do đó 〈F (x0), x0〉 = 0. 2 Dưới đây ta xét hai ví dụ thực tế của bài toán VI. Ví dụ 1.6. Bài toán cân bằng mạng giao thông Xét một mạng giao thông được cho bởi một mạng luồng hữu hạn. Gọi •N : tập hợp các nút của mạng. •A: là tập hợp các cạnh (mỗi cạnh được gọi là một đoạn đường). Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 15 Giả sử O ⊆ N , D ⊆ N sao cho O ∩ D = ∅. Mỗi phần tử của O được gọi là điểm nguồn, còn mỗi phần tử của D được gọi là điểm đích. Mỗi điểm nguồn và điểm đích được nối với nhau bởi một tập hợp liên tiếp các cạnh (được gọi là một tuyến đường). Ký hiệu: •f ia là mật độ giao thông của phương tiện i trên đoạn đường a ∈ A. Đặt f là véc tơ có các thành phần là f ia với i ∈ I và a ∈ A (I là tập hợp các phương tiện giao thông. •cia là chi phí khi sử dụng phương tiện giao thông i trên đoạn đường A. Đặt c là véc tơ có các thành phần là cia với i ∈ I, a ∈ A. •diw là nhu cầu sử dụng loại phương tiện i ∈ I trên tuyến đường w = (O,D) với O ∈ O, D ∈ D. Giả sử rằng chi phí giao thông phụ thuộc vào lưu lượng, tức là c = c(f) là một hàm của f . •λiw là mức độ chi phí trên tuyến đường w của phương tiện giao thông i. •xiw là mật độ giao thông của phương tiện i ∈ I trên tuyến w ∈ O ìD. Giả sử trong mạng trên, phương trình cân bằng sau được thoả mãn diw = ∑ p∈Pw xip ∀i ∈ I, w ∈ O ìD, (1.2) trong đó, Pw ký hiệu tập hợp các tuyến đường của w = (O,D) (nối điểm nguồn O và điểm đích D). Theo phương trình (2.18), thì nhu cầu sử dụng loại phương tiện i trên tuyến đường w bằng đúng tổng mật độ giao thông của phương tiện đó trên mọi tuyến đường nối điểm nguồn và điểm đích của tuyến đường đó. Khi đó ta có f ia = ∑ p∈Pw xipδap ∀i ∈ I, w ∈ O ìD, (1.3) trong đó δap :=   1 nếu a ∈ p, 0 nếu a /∈ p. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 16 Với mỗi tuyến đường p nối một điểm nguồn và một điểm đích, đặt cip = ∑ a∈A ciaδap. (1.4) Như vậy, cip là một chi phí khi sử dụng phương tiện i trên tuyến đường p. Đặt d là véc tơ có các thành phần là diw (i ∈ I, w ∈ O ìD) và đặt f là véc tơ có các thành phần là dia (i ∈ I, a ∈ O ìD). Một cặp (d ∗, f ∗) thoả mãn các điều kiện (2.18) và (2.21) được gọi là điểm cân bằng của mạng giao thông nếu cip(f ∗) =   λiw(d ∗) khi xip > 0, > λiw(d ∗) khi xip = 0, với mỗi i ∈ I và mỗi tuyến đường p. Theo định nghĩa này, tại điểm cân bằng đối với mọi loại phương tiện giao thông và mọi tuyến đường, chi phí sẽ thấp nhất khi có lưu lượng giao thông trên tuyến đó. Trái lại, chi phí sẽ không phải thấp nhất. Đặt K = {(f, d) | ∃ x ≥ 0 sao cho (2.18) và (2.21) đúng}. Khi đó, ta có định lý sau. Định lý 1.1. Một cặp véc tơ (f ∗, d∗) ∈ K là một điểm cân bằng của mạng giao thông khi và chỉ khi nó là nghiệm của bất đẳng thức biến phân sau: Tìm (f ∗, d∗) ∈ K sao cho 〈 ( c(f ∗)), λ(d∗) ) , (f, d)−(f ∗, d∗)〉 ≥ 0 ∀(f, d) ∈ K. Ví dụ 1.7. Bài toán kinh tế bán độc quyền Giả sử có n công ty cùng sản xuất một loại sản phẩm và lợi nhuận pi của mỗi công ty i phụ thuộc vào tổng số lượng sản phẩm của tất cả các công ty σ := ∑n i=1 xi. Ký hiệu hi(xi) là chi phí của công ty i khi sản xuất ra lượng hàng hoá xi. Giả sử rằng lợi nhuận của công ty i được cho bởi fi(x1, ..., xn) = xipi( n∑ i=1 xi)− hi(xi) (i = 1, ..., n), (1.5) Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 17 trong đó p( ∑n j=1 xj) là giá của một đơn vị sản phẩm, phụ thuộc vào tổng sản phẩm, còn hàm chi phí của mỗi công ty i chỉ phụ thuộc vào mức độ sản xuất của công ty đó. Đặt Ui ⊂ IR, (i = 1, ..., n) là tập chiến lược của công ty i. Lẽ dĩ nhiên, mỗi công ty cần xác định cho mình một mức độ sản xuất để đạt được lợi nhuận cao nhất. Tuy nhiên, trong trường hợp tổng quát, việc tất cả các công ty đều có lợi nhuận cực đại là khó có thể được. Vì vậy người ta dùng đến khái niệm cân bằng: Một điểm x∗ = (x∗1, ..., x ∗ n) ∈ U := U1 ì ... ì Un được gọi là điểm cân bằng Nash nếu fi(x ∗ 1, ..., x ∗ i−1, yi, x ∗ i+1, ..., x ∗ n) 6 fi(x ∗ 1, ..., x ∗ n) ∀yi ∈ Ui, ∀i = 1, ..., n. Trong mô hình cân bằng Cournot cổ điển, hàm chi phí và hàm lợi nhuận của mỗi công ty là affine có dạng pi(σ) ≡ p(σ) = α0 − βσ, α0 ≥ 0, β > 0, với σ = ∑n i=1 xi, hi(xi) = àixi + ξi, ài ≥ 0, ξi ≥ 0 (i = 1, ..., n). Ta đặt A =   β 0 0 ... 0 0 β 0 ... 0 ... ... ... ... ... 0 0 0 0 β   , A˜ =   0 β β ... β β 0 β ... β ... ... ... ... ... β β β ... 0   và αT = (α0, ..., α0), à T = (à1, ..., àn). Điểm x∗ là điểm cân bằng Nash khi và chỉ khi x∗ là nghiệm của bài toán bất đẳng thức biến phân:  Tìm điểm x ∈ U sao cho 〈A˜x + à− α, y − x〉+ yTAy − xTAx ≥ 0 ∀y ∈ U. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 18 1.3. Sự tồn tại nghiệm của bài toán VI Sự tồn tại nghiệm của bài toán VI phụ thuộc vào hàm giá F và miền ràng buộc C . Trong mục này, ta chỉ xét hàm F là liên lục trên tập mở chứa C và miền ràng buộc C là một tập lồi đóng trong không gian Rn. Định lý 1.2. Nếu C ⊆ Rn là một tập lồi, compact và F liên tục trên C , thì bài toán bất đẳng thức biến phân VI có nghiệm. Chứng minh. Đặt ánh xạ f = PrC(I − F ), trong đó PrC là phép chiếu trên C được xác định bởi công thức PrC(x) = inf{||x− y|| : y ∈ C} và I là ánh xạ đồng nhất. Bổ đề 1.1. (định lý Browder, xem [8]) Cho C ⊆ Rn là một tập lồi, compact và F : C → C liên tục trên C . Khi đó, tồn tại ít nhất một điểm bất động của ánh xạ F . Dễ dàng thấy rằng F liên tục trên C nên f cũng liên tục trên C . Theo Bổ đề 1.1, ánh xạ f có điểm bất động, hay tồn tại x∗ ∈ C sao cho x∗ = f(x∗), hay x∗ = PrC(x ∗ − F (x∗)). Theo định nghĩa của phép chiếu PrC , ta có 〈x∗, y − x∗〉 ≥ 〈(I − F )(x∗), y − x∗〉 ∀y ∈ C. Do vậy, 〈x∗, y − x∗〉 ≥ 〈x∗ − F (x∗), y − x∗〉 ∀y ∈ C. Hay x∗ là nghiệm của bài toán VI 〈F (x∗), y − x∗〉 ∀y ∈ C. 2 Bây giờ ta xét sự tồn tại nghiệm của bài toán VI trong trường hợp miền chấp nhận được C không bị chặn. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 19 Định nghĩa 1.4. Cho C ⊆ Rn Một ánh xạ F : C → Rn được gọi là có điều kiện bức trên C , nếu tồn tại x∗ ∈ C sao cho 〈F (y)− F (x∗), y − x∗〉 ||x− x∗|| → +∞ khi x ∈ C và ||x|| → ∞. Định lý 1.3. Cho C ⊆ Rn là một tập lồi, đóng. F liên tục và thỏa mãn điều kiện bức trên C . Khi đó bài toán bất đẳng thức biến phân VI có nghiệm. Chứng minh. Từ giả thiết 〈F (y)− F (x∗), y − x∗〉 ||x− x∗|| → +∞ khi x ∈ C và ||x|| → ∞ suy ra với mọi H > 0 tồn tại R > ||x∗|| sao cho 〈F (y) − F (x∗), y − x∗〉 ||x− x∗|| ≥ H ∀||y|| ≥ R. Hay 〈F (y) − F (x∗), y − x∗〉 ≥ H||x− x∗|| ∀||y|| ≥ R. Do đó 〈F (y), y − x∗〉 ≥ H||x− x∗||+ 〈F (x∗), y − x∗〉 ∀||y|| ≥ R. Suy ra 〈F (y), y − x∗〉 ≥ H||x− x∗|| − ||F (x∗)||.||y − x∗|| ∀||y|| ≥ R. Hay 〈F (y), y − x∗〉 ≥ (H − ||F (x∗)||).||y − x∗|| > 0 ∀||y|| ≥ R. (1.6) Bây giờ, ta giả sử x0 là nghiệm của bài toán VI trên C0 := B¯(0, R)∩C compact, hay 〈F (x0), y − x0〉 ≥ 0 ∀y ∈ C0. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 20 Từ x∗ ∈ C0 suy ra 〈F (x0), x∗ − x0〉 ≥ 0. Kết hợp điều này với bất đẳng thức 1.6, ta có ||x0|| 6= R hay ||x0|| < R. Khi đó, tồn tại  ∈ (0, 1) sao cho x := x0 + (1− )x∗ ∈ C0. Thay x vào bài toán bất đẳng thức biến phân VI, ta nhận được 〈F (x0), x − x0〉 ≥ 0 ∀x ∈ C. Hay 〈F (x0), x− x0〉 ≥ 0 ∀x ∈ C. 2 Định lý 1.4. Cho C là một tập lồi đóng trong không gian Rn, ánh xạ F : C → R n đơn điệu và liên tục trên C . Khi đó, x∗ ∈ C là nghiệm của bài toán bất đẳng thức biến phân VI 〈F (x∗), x− x∗〉 ≥ 0 ∀x ∈ C khi và chỉ khi 〈F (x), x− x∗〉 ≥ 0 ∀x ∈ C. Chứng minh. (⇒) Từ các giả thiết đơn điệu của F , x∗ ∈ C và x∗ ∈ C là nghiệm của bài toán bất đẳng thức biến phân VI 〈F (x∗), x− x∗〉 ≥ 0 ∀x ∈ C. Ta có 0 ≤ 〈F (y) − F (x∗), y − x∗〉 = 〈F (y), y − x∗〉 − 〈F (x∗), y − x∗〉 ∀y ∈ C. Như vậy 0 ≤ 〈F (x∗), y − x∗〉 ≤ 〈F (y), y − x∗〉 ∀y ∈ C. (⇐) Với mọi z ∈ C, λ ∈ (0, 1), ta có y = x∗ + λ(z − x) ∈ C . Do đó, 〈F (y), y − x∗〉 ≥ 0 ∀y ∈ C. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 21 Hay 〈F (x∗ + λ(z − x∗)), x∗ + λ(z − x∗)− x∗〉 ≥ 0 ∀z ∈ C. Rút gọn, ta có 〈F (x∗ + λ(z − x∗)), z − x∗〉 ≥ 0 ∀z ∈ C. Cho λ → 0+, do tính liên tục của F nên 〈F (x∗), z − x∗〉 ≥ 0 ∀z ∈ C. 2 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 22 2 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 22 Chương 2 Phương pháp lặp Banach giải bài toán (VI) đơn điệu mạnh Như ta đã biết, phương pháp lặp theo nguyên lý ánh xạ co Banach là một kết quả nổi tiếng và là phương pháp cơ bản, rất hiệu quả để tính điểm bất động của một ánh xạ co. Nguyên lý này sau đó được mở rộng Nadler (xem [2], Định lý 14). Trong chương này, chúng ta sẽ dùng cách tiếp cận điểm bất động theo phương pháp lặp của nguyên lý ánh xạ co Banach để giải bài toán bất đẳng thức biến phân VI được định nghĩa ở Chương 1. Ta sẽ xét trường hợp khi F là ánh xạ đơn điệu mạnh. Các thuật toán thu được ở chương này khá đơn giản so với các thuật toán giải bài toán bất đẳng thức biến phân ở [5]. Cách tiếp cận này còn cho phép đánh giá được tốc độ hội tụ của thuật toán một cách đơn giản nhờ vào nguyên lý ánh xạ co Banach. Để tiện theo dõi việc trình bày phương pháp giải bài toán bất đẳng thức biến phân VI bằng nguyên lý ánh xạ co Banach, ta nhắc lại một số định nghĩa sau: Định nghĩa 2.1. Cho C ⊆ Rn ánh xạ F : C → Rn • F được gọi là đơn điệu mạnh với hệ số β > 0 trên C nếu 〈F (x)− F (x′), x− x′〉 ≥ β||x− x′||2 ∀x, x′ ∈ C. • F được gọi là Lipschitz với hằng số L > 0 (được viết tắt là L-Lipschitz) trên C nếu ||F (x)− F (x′)|| ≤ L||x− x′|| ∀x, x′ ∈ C. Nếu hệ số L < 1 thì F được gọi là co trên C . Nếu L = 1 thì F được gọi là không giãn trên C . Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 23 2.1. Tính co của ánh xạ nghiệm Khi xét bài toán VI, Auslender đã đưa ra hàm chắn (gap, merit) bằng cách với mỗi x ∈ C , đặt g1(x) = sup{〈F (x), x− y〉 | y ∈ C}. Ta dễ nhận thấy rằng g(x) ≥ 0 với mọi x ∈ C . Bài toán VI có thể được viết dưới dạng bài toán tối ưu inf{g1(x) | x ∈ C}. (2.7) Tuy nhiên, một khó khăn của bài toán này là trong trường hợp tổng quát, hàm g1 có thể không khả vi. Để giải quyết khó khăn này, Fukushima đã đề xuất hàm chắn mới có dạng g2(x) = max{− 1 2 〈y − x,G(y − x)〉 − 〈F (x), y − x〉 | y ∈ C}, (2.8) trong đó, G là một ma trận đối xứng, xác định dương. Cũng như đối với hàm chắn g1, ta có g2(x) ≥ 0 với mọi x ∈ C và bài toán VI có thể được viết dưới dạng bài toán tối ưu inf{g2(x) | x ∈ C}. (2.9) Hàm g2 được xác định bởi công thức (2.8) là khả vi trên C với F là hàm khả vi. Khi đó, có thể dùng phương pháp tối ưu để giải bài toán VI thông qua việc giải bài toán trơn (2.8). Dựa vào cách xây dựng các hàm chắn ở trên, với mỗi x ∈ C , đặt y = h(x) là nghiệm duy nhất của bài toán qui hoạch lồi mạnh min{ 1 2 〈y − x,G(y − x)〉+ 〈F (x), y − x〉 | y ∈ C}, (2.10) trong đó G là một ma trận đối xứng, xác định dương. Do C khác rỗng, lồi, đóng và hàm mục tiêu của bài toán (2.10) lồi mạnh, nửa liên tục dưới trên C , nên h(x) được xác định và duy nhất. Kết quả sau đây chỉ ra rằng điểm x∗ là nghiệm của bài toán VI khi và chỉ khi x∗ là điểm bất động của ánh xạ h. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 24 Bổ đề 2.1. x∗ là nghiệm của bài toán VI (1.1) khi và chỉ khi x∗ = h(x∗). Chứng minh. Giả sử x∗ là nghiệm của bài toán VI. Điều đó có nghĩa rằng 〈F (x∗), x− x∗〉 ≥ 0 ∀x ∈ C. (2.11) Do h(x∗) là nghiệm duy nhất của bài toán (2.10), nên h(x∗) ∈ C . Thay thế x bởi h(x∗) trong bất đẳng thức (2.11), ta được 〈F (x∗), h(x∗)− x∗〉 ≥ 0. (2.12) Mặt khác, h(x∗) là nghiệm duy nhất của bài toán (2.10), theo điều kiện cần và đủ của tối ưu, ta có 〈F (x∗) + G(h(x∗)− x∗), y − h(x∗)〉 ≥ 0 ∀y ∈ C. (2.13) Thay thế y bởi x∗ ∈ C trong bất đẳng thức (2.13), ta có 〈F (x∗) + G(h(x∗)− x∗), x∗ − h(x∗)〉 ≥ 0. (2.14) Từ bất đẳng thức (2.12) và (2.14) suy ra 〈G(h(x∗)− x∗), x∗ − h(x∗)〉 ≥ 0. (2.15) Từ bất đẳng thức (2.15) và do ma trận G là đối xứng, xác định dương, ta có h(x∗) = x∗. Suy ra x∗ = h(x∗). Bây giờ, ta xét chiều ngược lại. Giả sử rằng x∗ = h(x∗).Với mọi x ∈ C , ta luôn có 〈F (x) + G(h(x)− x), y − h(x)〉 ≥ 0 ∀y ∈ C. (2.16) Thay thế x bởi x∗ = h(x∗) trong bất đẳng thức (2.16) ta được 〈F (x∗), y − x∗〉 ≥ 0 ∀y ∈ C. Điều này có nghĩa rằng x∗ là nghiệm của bài toán VI. 2 Hãy trở lại bài toán (2.8) với C lồi, đóng. Để tiện cho việc trình bày, ta viết bài toán này dưới dạng tương đương là: g2(x) = −min{ 1 2 〈y − x,G(y − x)〉+ 〈F (x), y − x〉 | y ∈ C}. (2.17) Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 25 Vì G là ma trận đối xứng và xác định dương, nên (2.17) là một bài toán quy hoạch lồi mạnh và do đó nó có duy nhất nghiệm. Dưới đây để đơn giản, ta giả sử G = αI , trong đó α > 0 và I là ma trận đồng nhất. Khi đó, chúng ta sẽ đưa ra cách điều chỉnh tham số α phù hợp, sao cho ánh xạ nghiệm h có tính chất co trên C . Tham số α được gọi là tham số chính quy hoá. Định lý dưới đây sẽ khẳng định tính chất co của ánh xạ nghiệm h trong trường hợp F là ánh xạ đơn điệu mạnh trên C . Định lý 2.1. Giả sử rằng F (x) là lồi, đóng, khác rỗng với mỗi x ∈ C , F là một ánh xạ đơn điệu mạnh với hệ số β > 0 và Lipschitz với hằng số L > 0 trên C . Khi đó, với α > L 2 2β , ánh xạ h là co trên C với hệ số δ := √ 1− 2β α + L 2 α2 . Cụ thể, ta có ||h(x)− h(x′)|| ≤ δ||x− x′|| ∀x, x′ ∈ C. Chứng minh. Bài toán (2.10) có thể được viết dưới dạng min y { 1 2 α||y − x||2 + 〈F (x), y − x〉+ δC(y)}, ở đây δC là hàm chỉ của C . Đây là một quy hoạch toàn phương lồi mạnh, do đó nó có duy nhất nghiệm và nghiệm này được ký hiệu bởi h(x). Theo Mệnh đề 1.2, ta có 0 ∈ α(h(x)− x) + F (x) + NC(h(x)). Điều này có nghĩa rằng tồn tại z ∈ NC(h(x)) sao cho α(h(x)− x) + F (x) + z = 0. Do vậy h(x) = x− 1 α F (x)− 1 α z. (2.18) Tương tự với x′ ∈ C , ta có h(x′) = x′ − 1 α F (x′)− 1 α z′, (2.19) Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 26 ở đây z′ ∈ NC(h(x′)). Do ánh xạ đa trị NC là đơn điệu, ta có 〈z − z′, h(x)− h(x′)〉 ≥ 0. (2.20) Thay thế z của công thức (2.18) và z′ của công thức (2.19) vào công thức (2.20), ta nhận được 〈x− x′ − 1 α (F (x)− F (x′))− (h(x)− h(x′)), h(x)− h(x′)〉 ≥ 0, điều này tương đương với ||h(x)− h(x′)||2 ≤〈x− x′ − 1 α (F (x)− F (x′)), h(x)− h(x′)〉 =〈x− x′ − 1 α (F (x)− F (x′)), h(x)− h(x′)〉. (2.21) Như vậy là ||h(x)− h(x′)||2 ≤ ||x− x′ − 1 α (F (x)− F (x′))||2. (2.22) Do giả thiết ánh xạ F là L-Lipschitz và đơn điệu mạnh trên C , ta có ||x− x′ − 1 α (h(x)− h(x′)||2 ≤ (1− 2β α + L2 α2 )||x− x′||2. (2.23) Nếu chọn hệ số α > L 2 2β , thì 1 − 2β α + L 2 α2 > 0. Cuối cùng, từ hai bất đẳng thức (2.22) và (2.23) ta được ||h(x)− h(x′)|| ≤ √ 1 − 2β α + L2 α2 ||x− x′||. Đặt δ := √ 1− 2β α + L 2 α2 , khi đó ||h(x)− h(x′)|| ≤ δ||x− x′|| ∀x, x′ ∈ C. Do đó ||h(x)− h(x′)|| ≤ δ||x− x′|| ∀x, x′ ∈ C. Chú ý rằng nếu α > L 2 2β thì δ ∈ (0, 1). Như vậy, ánh xạ h là co trên C với hệ số δ. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 27 2 Theo Định lý 2.1 với các giả thiết ánh xạ F là đơn điệu mạnh và Lipschitz trên C , ta có thể chọn tham số chính quy α phù hợp sao cho ánh xạ nghiệm h là co trên C . Trong trường hợp này, theo nguyên lý ánh xạ co Banach, được mở rộng bởi Nadler, nghiệm của bài toán VI có thể được xấp xỉ bởi quá trình lặp xk+1 = h(xk), k = 0, 1, ... với x0 là một điểm tuỳ ý của C . Theo định nghĩa của ánh xạ h, điểm xk+1 chính là nghiệm duy nhất của quy hoạch toàn phương lồi mạnh. 2.2. Mô tả thuật toán và sự hội tụ Khi thực hiện các thuật toán vô hạn, việc tìm ra một nghiệm tối ưu chính xác là khó thực hiện được. Vì vậy, người ta thường phải lấy nghiệm xấp xỉ với độ chính xác nào đó. Giả sử x∗ là nghiệm chính xác của bài toán VI, khi đó x ∈ C được gọi là - nghiệm của bài toán VI nếu ||x − x∗|| ≤ . Thuật toán lặp Banach cho ánh xạ F đơn điệu mạnh trên C được miêu tả chi tiết như sau: Thuật toán 2.1. Bước đầu. Chọn sai số  ≥ 0. Chọn tham số chính quy α > L 2 2β , khi F là β-đơn điệu mạnh, ở đây L là hằng số Lipschitz của F . Chọn x0 ∈ C . Bước lặp k(k = 0, 1, 2, ...). Giải bài toán quy hoạch lồi mạnh P (xk) : min{ 1 2 α||x− xk||2 + 〈F (xk), x− xk〉 | x ∈ C}, thu được nghiệm duy nhất xk+1. Xét hai trường hợp: -Trường hợp 1: Nếu ||xk+1 − xk|| ≤ (1−δ) δk , thì thuật toán dừng: xk là một -nghiệm của bài toán VI. -Trường hợp 2: Nếu ||xk+1 − xk|| > (1−δ) δk , thì ta thay thế k := k + 1 và Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 28 chuyển sang Bước lặp k. Theo Định lý 2.1 và nguyên lý lặp Banach, ta có mối quan hệ giữa điểm xk và nghiệm chính xác x∗ của bài toán VI được xác định bởi công thức sau: ||xk+1 − x∗|| 6 δk+1 1− δ ||x0 − x1|| ∀k, ở đây 0 < δ < 1 là hệ số co của ánh xạ nghiệm H . Theo Định lý 2.1 δ = √ 1− 2β α + L2 α2 , khi F là β-đơn điệu mạnh. Định lý 2.2. Dưới giả thiết của Định lý 2.1, dãy {xk} được xây dựng bởi Thuật toán 2.1 thoả mãn ||xk+1 − x∗|| 6 δk+1 1− δ ||x0 − x1|| ∀k, (2.24) ở đây x∗ là nghiệm chính xác của bài toán VI. Chứng minh. Trước hết, ta giả sử các giả thiết của Định lý 2.1 được thoả mãn. Theo Bổ đề 2.1, ta có x∗ = h(x∗). Từ giả thiết Lipschitz của F , ta có ||F (xk+1) − F (xk)|| ≤ L||xk+1 − xk|| ∀k = 0, 1, ... Khi đó theo Định lý 2.1 ta nhận được ||h(xk+1)− h(xk)|| ≤ δ||xk+1 − xk|| ∀k = 0, 1, ... Từ h(xk+1) = xk+2 suy ra ||xk+2 − xk+1|| ≤ δ||xk+1 − xk|| ∀k = 0, 1, ... Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 29 Theo nguyên lý ánh xạ co Banach, ta có ||xk − x∗|| ≤ δk+1 1− δ ||x0 − x1|| ∀k = 0, 1, ... Như vậy, xk → x∗ khi k → +∞. Hơn nữa, sử dụng tính chất co của ánh xạ nghiệm h, ta đạt được ||xp+k − xk|| ≤ δk(1− δp) 1 − δ ||xk+1 − xk|| ∀k, p. Cho p → +∞, ta được ||xk − x∗|| ≤ δk 1− δ ||xk+1 − xk|| ∀k = 0, 1, ... Nếu Trường hợp 1 của Thuật toán 2.1 xảy ra ||xk+1 − xk|| ≤ (1− δ) δk và do đó ||xk − x∗|| ≤ . Điều đó có nghĩa là xk là một -nghiệm của bài toán VI. 2 Kết luận Trong chương này ta đã dùng cách tiếp cận điểm bất động cho bài toán bất đẳng thức biến phân với ánh xạ giá là đơn điệu mạnh. Ta đã chứng tỏ rằng việc tìm nghiệm của bài toán VI được qui về tìm điểm bất động của một ánh xạ nghiệm h. Bằng cách sử dụng kỹ thuật điều chỉnh, ta đã chứng tỏ rằng ánh xạ nghiệm h có tính chất co. Cụ thể, khi ánh xạ giá là đơn điệu mạnh, tính chất co này cho phép ta xây dựng một thuật toán lặp theo kiểu nguyên lý ánh xạ co Banach để giải bài toán VI. Cách tiếp cận này cho phép thiết lập dễ dàng tốc độ hội tụ của phương pháp lặp. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 30 3 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 30 Chương 3 Phương pháp lặp Banach giải bài toán VI đồng bức Trong chương này, ta xét bài toán VI với giả thiết F là ánh xạ đồng bức trên C . Trong trường hợp này, bài toán VI có thể không duy nhất nghiệm. Chúng ta sẽ chỉ ra cách chọn tham số chính quy hoá α sao cho ánh xạ nghiệm h là không giãn trên C . Trên cơ sở đó xây dựng thuật toán giải bài toán VI với F là ánh xạ đồng bức. 3.1. Tính không giãn của ánh xạ nghiệm Định lý 3.1. Giả sử rằng ánh xạ F là đồng bức với hệ số γ > 0 trên C . Khi đó, nếu α ≥ 12γ thì ánh xạ nghiệm h là không giãn trên C . Chứng minh. Bài toán (2.10) có thể được viết dưới dạng min y { 1 2 α||y − x||2 + 〈F (x), y − x〉+ δC(y)}, ở đây δC là hàm chỉ của C . Đây là một quy hoạch toàn phương lồi mạnh, do đó nó có duy nhất nghiệm và nghiệm này được ký hiệu bởi h(x). Theo Mệnh đề 1.2, ta có 0 ∈ α(h(x)− x) + F (x) + NC(h(x)). Điều này có nghĩa rằng tồn tại z ∈ NC(h(x)) sao cho α(h(x)− x) + F (x) + z = 0. Do vậy h(x) = x− 1 α F (x)− 1 α z. (3.25) Tương tự với x′ ∈ C , ta có h(x′) = x′ − 1 α F (x′)− 1 α z′, (3.26) Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 31 ở đây z′ ∈ NC(h(x′)). Do ánh xạ đa trị NC là đơn điệu, ta có 〈z − z′, h(x)− h(x′)〉 ≥ 0. (3.27) Thay thế z của công thức (3.25) và z′ của công thức (3.26) vào công thức (3.27), ta nhận được 〈x− x′ − 1 α (F (x)− F (x′))− (h(x)− h(x′)), h(x)− h(x′)〉 ≥ 0, điều này tương đương với ||h(x)− h(x′)||2 ≤〈x− x′ − 1 α (F (x)− F (x′)), h(x)− h(x′)〉 =〈x− x′ − 1 α (F (x)− F (x′)), h(x)− h(x′)〉. (3.28) Như vậy là ||h(x)− h(x′)||2 ≤ ||x− x′ − 1 α (F (x)− F (x′))||2. (3.29) Từ tính đồng bức của F trên C với hệ số γ suy ra γ||F (x)− F (x′)||2 ≤ 〈x− x′, F (x)− F (x′)〉 ∀x, x′ ∈ C. Vậy, ||x− x′ − 1 α (F (x)− F (x′))||2 = ||x− x′||2 − 2 α 〈x− x′, F (x)− F (x′)〉+ 1 α2 ||F (x)− F (x′)||2 6 ||x− x′||2 − 2γ α ||F (x)− F (x′)||2 + 1 α2 ||F (x)− F (x′)||2 ∀x, x′ ∈ C. 6 ||x− x′||2 − ( 2γ α − 1 α2 )||F (x)− F (x′)||2. Từ α ≥ 1 2γ suy ra ||x− x′ − 1 α (F (x)− F (x′))||2 6 ||x− x′||2 ∀x, x′ ∈ C. (3.30) Kết hợp (3.29) và (3.30), ta nhận được ||h(x)− h(x′)|| ≤ ||x− x′|| ∀x, x′ ∈ C. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 32 2 Như vậy, tuy rằng bài toán VI có thể không duy nhất nghiệm trong trường hợp ánh xạ F là đồng bức, nhưng, Định lý 3.1 chỉ ra rằng ta có thể tìm được một nghiệm của bài toán này thông qua việc tìm điểm bất động của ánh xạ không giãn h. Để tìm điểm bất động của ánh xạ h, ta sẽ sử dụng định lý sau. Định lý 3.2. Cho C ⊂ Rn là một tập lồi, compact, khác rỗng và S : C → C . Giả sử rằng không giãn trên C . Với mỗi λ ∈ (0, 1), ta đặt Sλ := (1− λ)I + λS. Khi đó, các dãy {xk}, {yk} được xác định bởi xk+1 := (1− λ)xk + λyk, yk = S(xk), ||yk+1 − yk|| 6 ||xk+1 − xk|| ∀k = 0, 1, 2, ... sẽ thoả mãn ||xk − yk|| → 0 khi k → +∞. Hơn nữa, bất kỳ một điểm tụ nào của dãy {xk} đều là điểm bất động của ánh xạ S. Để chứng minh định lý này, ta cần tới bổ đề sau: Bổ đề 3.1. Dưới giả thiết của Định lý 3.1, với mọi i,m = 0, 1, ..., ta có ||yi+m − xi|| ≥ (1− λ)−m[||yi+m − xi+m|| − ||yi − xi||] + (1 + λm)||yi − xi||. (3.31) Chứng minh của Bổ đề 3.1. Ta sẽ chứng minh bằng quy nạp toán học theo m. Với m = 0, thì (3.31) hiển nhiên đúng với mọi i. Giả sử (3.31) đúng với m và với mọi i. Thay thế i bởi i + 1 trong (3.31), suy ra ||yi+m+1 − xi+1|| ≥(1− λ)−m[||yi+m+1 − xi+m+1|| − ||yi+1 − xi+1||] + (1 + λm)||yi+1 − xi+1||. (3.32) Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 33 Từ xk+1 := (1− λ)xk + λyk với yk ∈ S(xk) với mọi k = 0, 1, ... suy ra ||yi+m+1 − xi+1|| = ||yi+m+1 − [(1− λ)xi + λyi]|| 6 λ||yi+m+1 − yi||+ (1− λ)||yi+m+1 − xi|| 6 (1− λ)||yi+m+1 − xi||+ λ m∑ k=0 ||xi+k+1 − xi+k||. (3.33) Kết hợp (3.32) và (3.33), ta nhận được ||yi+m+1 − xi|| ≥(1− λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi+1 − xi+1||] + (1− λ)−1(1 + λm)||yi+1 − xi+1|| − λ(1− λ)−1 n∑ k=0 ||xi+k+1 − xi+k||. Do ||xi+k+1 − xi+k|| = λ||yk+i − xk+i||, nên dãy {||ym − xm||} là giảm vì λ||ym − xm|| = ||xm+1 − xm|| = ||(1− λ)xm + λym − [(1− λ)xm−1 − λym−1]|| 6 (1− λ)||xm − xm−1||+ λ||ym − ym−1|| 6 ||xm − xm−1|| = λ||ym−1 − xm−1||. Từ 1 + mλ 6 (1− λ)−m, suy ra ||yi+m+1 − xi|| ≥(1− λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi+1 − xi+1||] + (1− λ)−1(1 + λm)||yi+1 − xi+1|| − λ2(1− λ)−1(m + 1)||yi − xi|| =(1− λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi − xi||] + [(1− λ)−1(1 + λm) − (1− λ)−(m+1)]||yi+1 − xi+1|| + [(1− λ)−(m+1) − λ2(1− λ)−1(m + 1)]||yi − xi|| ≥(1− λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi − xi||] Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 34 + [(1− λ)−1(1 + λm) − (1− λ)−(m+1)]||yi − xi|| + [(1− λ)−(m+1) − λ2(1− λ)−1(m + 1)]||yi − xi|| =(1− λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi − xi||] + [1 + λ(m + 1)]||yi − xi||. Như vậy, bất đẳng thức (3.31) đúng với m + 1. Theo quy nạp toán học, Bổ đề 3.1 được chứng minh. 2 Chứng minh của Định lý 3.2. Ta chứng minh bằng phản chứng. Giả sử rằng lim m→∞ ||ym − xm|| = r > 0. Chọn  là một số dương đủ nhỏ sao cho (1− λ)−m < r. Từ dãy {||ym − xm||} giảm, suy ra tồn tại một số tự nhiên i sao cho 0 6 ||yi − xi|| − ||ym+i − xm+i|| 6 . Bổ đề 3.1 dẫn đến sự mâu thuẫn sau r 6 (1 + mλ)r 6 (1 + mλ)||yi − xi|| 6 ||ym+i − xi||+ (1− λ)−m[||yi − xi|| − ||ym+i − xm+i||] 6 ||ym+i − xi||+ (1− λ)−m < r. Do vậy, r = 0, cụ thể hơn là lim m→∞ ||xm − ym|| = 0. (∗∗) Do xk ∈ C với mọi k và C compact, nên tồn tại một dãy con xkj hội tụ tới x∗. Khi đó, do (**) nên ykj = S(xkj) cũng hội tụ tới x∗. Vậy x∗ = S(x∗). 2 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 35 3.2. Mô tả thuật toán và sự hội tụ Bây giờ, áp dụng Định lý 3.1 cho ánh xạ không giãn h, ta có thể tìm một nghiệm của bài toán VI với F là ánh xạ đồng bức với hệ số γ trên C bằng cách tìm điểm bất động của ánh xạ h. Như trên đã thấy, nếu xk lại chính là nghiệm của bài toán P (xk), thì xk là nghiệm của bài toán VI. Do đó, trong thuật toán dưới đây, nếu yk là nghiệm của bài toán P (xk) và ||xk − yk|| ≤  thì ta có thể coi yk là một -nghiệm của bài toán VI và dừng thuật toán. Thuật toán cụ thể được trình bày như sau. Thuật toán 3.1. Bước 0. Chọn sai số  ≥ 0 và λ ∈ (0, 1), α ≥ 12γ và tìm x0 ∈ C . Đặt k = 0. Bước 1. Giải bài toán quy hoạch lồi mạnh P (xk) : min{ 1 2 α||y − xk||2 + 〈F (xk), y − xk〉 | y ∈ C} để được nghiệm duy nhất yk. Nếu ||yk − xk|| ≤ , thì dừng thuật toán. Ngược lại chuyển sang Bước 2. Bước 2. Lấy xk+1 := (1− λ)xk + λyk. Gán k := k + 1 và trở lại Bước 1. Định lý 3.3. Ngoài các giả thiết của Định lý 3.1, ta giả sử thêm rằng C là tập compact. Khi đó, nếu Thuật toán 3.1 không dừng, thì dãy {xk} bị chặn và mọi điểm tụ của nó đều là nghiệm của bài toán VI. Hơn nữa, ||xk − h(xk)|| → 0 khi k → ∞. Chứng minh. Theo tính chất đồng bức của F trên C với hệ số γ, ta có γ||F (xk)− F (xk+1)||2 ≤ 〈xk − xk+1, F (xk)− F (xk+1)〉. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 36 Do đó, ||xk − xk+1 − 1 α (F (xk)− F (xk+1))||2 = ||xk − xk+1||2 − 2 α 〈xk − xk+1, F (xk)− F (xk+1)〉 + 1 α2 ||F (xk)− F (xk+1)||2 ≤ ||xk − xk+1||2 − 2γ α ||F (xk)− F (xk+1)||2 + 1 α2 ||F (xk)− F (xk+1)||2 = ||xk − xk+1||2 − ( 2γ α − 1 α2 )||F (xk)− F (xk+1)||2. Vì α > 12γ , ta có ||xk − xk+1 − 1 α (F (xk)− F (xk+1))||2 6 ||xk − xk+1||2. Kết hợp điều này với tính chất không giãn của ánh xạ nghiệm h, ta được ||yk+1 − yk|| ≤ ||xk+1 − xk||, trong đó yk = h(xk), yk+1 = h(xk+1). Từ điều kiện bức của F với hệ số β > 0 hay với mọi x, x′ ∈ C , ta có 〈F (x)− F (x′), x− x′〉 ≥ β||F (x)− F (x′)||2, suy ra ||F (x)− F (x′)|| ≤ 1 β ||x− x′||. Từ các giả thiết C là tập compact và Định lý 3.2, mọi điểm tụ x∗ của dãy {xk} là điểm bất động của ánh xạ nghiệm h và cũng là nghiệm của bài toán VI. Trong Thuật toán 3.1, ta luôn có yk − h(xk), do vậy ||xk − h(xk)|| ≤ ||xk − yk|| ∀k = 0, 1, ... Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 37 Theo Định lý 3.2, ||xk − yk|| → 0 khi k → ∞, nên ||xk − h(xk)|| → 0 khi k → ∞. 2 3.3. Kết quả tính toán thử nghiệm 3.3.1. Mô hình cân bằng bán độc quyền Ta dùng Thuật toán BFP để giải mô hình cân bằng bán độc quyền. Giả sử cho n công ty cùng sản xuất một sản phẩm và giá sản phẩm p phụ thuộc vào lượng sản phẩm σ. Ký hiệu hi(xi) là tổng chi phí của công ty thứ i cho xi đơn vị sản phẩm. Khi đó, lợi nhuận của công ty thứ i là xip(σ) − hi(xi). Như vậy, mỗi công ty cần tìm cho mình một mức độ sản xuất tương thích để đạt lợi nhuận cao nhất. Bài toán này còn được gọi là bài toán cân bằng thị trường. Tập chiến lược chơi của mọi người là C := {x = (x1, x2, ..., xn) | 0 6 Li 6 xi 6 Ui ∀i = 1, 2, ..., n}, (3.34) và hàm lợi nhuận fi(x1, x2, ..., xn) = xip( n∑ j=1 xj)− hi(xi). Như thường lệ, ta nói rằng một điểm x∗ = (x∗1, x ∗ 2, ..., x ∗ n) ∈ C là điểm cân bằng, nếu fi(x ∗ 1, x ∗ 2, ..., x ∗ i−1, yi, x ∗ i+1, ..., x ∗ n) 6 fi(x ∗ 1, x ∗ 2, ..., x ∗ n) ∀yi ∈ [Li, Ui], ∀i = 1, 2, ..., n. Quan hệ giữa mô hình bài toán cân bằng bán độc quyền và bài toán VIP được phát biểu qua mệnh đề sau. Mệnh đề 3.1. Một điểm x∗ là điểm cân bằng bán độc quyền khi và chỉ khi nó là nghiệm của bài toán VIP, ở đây C được cho bởi (3.34) và F (x) = H(x)− p(σx)− p ′(σx)x, với H(x) = (h′1(x1), h ′ 2(x2), ..., h ′ n(xn), e = (1, 1, ..., 1) ∈ IR n, σx = 〈x, e〉. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 38 Mệnh đề 3.2. Cho p : C → IR+ là một hàm lồi, khả vi liên tục 2 lần, không giảm, và hàm àτ : IR+ → IR+ được xác định bởi àτ (σ) = σp(σ + τ), là một hàm lõm với mọi τ ≥ 0. Giả sử hi : IR+ → IR, ∀i = 1, 2, ..., n, là các hàm lồi và khả vi liên tục hai lần. Khi đó, ánh xạ F (x) = H(x)− p(σx)− p ′(σx)x là đơn điệu trên C . Chú ý rằng, do C là một hình hộp, nên tại mỗi bước lặp k, nghiệm của bài toán P(xk) trong Thuật toán 2.1 được cho dưới dạng hiển như sau. Cho x ∈ IRn và y = PC(x), ở đây C là hình hộp cho bởi công thức (3.34). Khi đó, toạ độ thứ i của điểm y được xác định bởi công thức yi =   Li nếu xi ≤ Li, Ui nếu xi ≥ Ui, Li nếu Li ≤ xi ≤ Ui. 3.3.2. Kết quả tính toán thử nghiệm Chúng tôi đã viết chương trình thực nghiệm Thuật toán BFP bằng ngôn ngữ Matlab 7.0 và đã thử nghiệm trên máy tính Intel 845w. Celeron 1.7 GHZ. Ram 256 Mb cho các ví dụ sau đây. Ví dụ 3.1. Cho C := {(x1, ..., xn) T | 2− 1 i 6 xi 6 15 + i 3i− 2 , ∀i = 1, ..., n} H(x) := (α1x1 + β1, ..., αnxn + βn) T , p(t) := ξ t , t ∈ (0,+∞), ở đây ξ > 0 là hằng số cho trước. Ta chọn ck = 1 và sai số  = 10 −6 . Các số αi, βi (i = 1, ..., n) và ξ được chọn ngẫu nhiên trong khoảng (0, 20). Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 39 Theo Mệnh đề 3.1 và 3.2, ta nhận thấy rằng ánh xạ giá F cho bởi Ví dụ 3.1 là đơn điệu và Lipschitz trên C với hằng số L < 1. Do đó, ta có thể chọn αk = ck = 1 với mọi k. Dựa trên kết quả tính toán thu được, ta rút ra một số nhận xét sau đây. • Giống như phương pháp Newton, tính hiệu quả của thuật toán phụ thuộc rất nhiều vào điểm chọn ban đầu. Thực tế, nếu điểm xuất phát ban đầu gần nghiệm của bài toán, thì thuật toán chạy rất nhanh. Ngược lại, nếu điểm bắt đầu xa với nghiệm, thì thuật toán chạy mất nhiều thời gian đặc biệt là ở bước lặp xuất phát vòng ngoài. • Tính hiệu quả của thuật toán còn phụ thuộc rất nhiều vào việc chọn hằng số Lipschitz L và các tham số αk, ck, k (chẳng hạn như, dãy {k} đủ lớn cho vòng lặp ngoài). Trong ví dụ với n = 100, αk = ck = 1, chúng ta chọn k = 10 k2 hoặc k = 1 k2 . Trong trường hợp này, chương trình chạy nhanh hơn rất nhiều so với trường hợp thứ hai. Tương tự với n = 1000 chương trình chạy rất lâu khi k = 1 k2 , nhưng nó chạy rất nhanh trong trường hợp k = 30 k2 . • Ta khẳng định rằng tại bước lặp k với k đủ lớn (k = 180 cho ví dụ này) thuật toán chạy chậm hơn. Như vậy, ta phải mất một khoảng thời gian dài để đạt được một k-nghiệm của bài toán con (VIPk). Để khắc phục vấn đề này, ta phải bắt đầu chạy lại chương trình với điểm bắt đầu là điểm lặp hiện tại xk. Bảng 1, Bảng 2 và Bảng 3 có các ký hiệu như sau: • j: số vòng lặp trung bình của vòng lặp trong. • k: số vòng lặp ngoài của mỗi bài toán. • k: số vòng lặp trung bình của vòng lặp ngoài. • j1: số vòng lặp trung bình của vòng lặp trong trong vòng lặp ngoài k. • t: thời gian CPU trung bình của mỗi bài toán (tính bằng giây). • fk: số vòng lặp trong của bước lặp ngoài đầu tiên. • fk: số bước lặp trung bình của vòng lặp trong ở vòng lặp ngoài đầu tiên. Hai ký hiệu cuối chỉ dùng cho Bảng 1. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 40 Kết quả trong Bảng 1 được tính với dãy số dương k = 1 k2 , trong Bảng 2, k = 10 k2 , và trong Bảng 3, k = 30 k2 . Trong tất cả các ví dụ được tính toán, điểm bắt đầu được chọn là điểm chính giữa của hình chữ nhật C , tức là toạ độ thứ i của điểm bắt đầu là Li+Ui 2 . Bài toán k j1 CPU-thời gian fk 1 3 112.4667 2 3371 2 4 386.75 1 1543 3 3 89 0.8 264 4 5 198.4 1 987 5 3 304.3333 1 910 6 5 363.2 1 1811 7 4 389.25 1 1554 8 2 876 1 1751 9 4 95,25 0.8 378 10 3 131 0.8 390 11 4 114.75 0.9 455 12 5 223.6 0.8 1114 13 4 21 0.7 81 14 3 38.6667 0.5 113 15 2 23.5 0.5 46 16 3 73 0.8 216 17 4 273 0.7 1089 18 3 325 0.8 972 19 4 24.25 0.7 93 20 6 166.6667 0.9 994 k = 3.7 j = 211.4792 t = 0.885 fk = 906.6 Bảng 1 (với n = 100, k = 1 k2 , αk = ck = 1). Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 41 Bài toán k j1 CPU-thời gian 1 4 1.5 0.5 2 3 2 0.4 3 3 1.6667 0.5 4 6 1.1667 0.7 5 5 1.6 0.9 6 5 1.8 0.7 7 3 2.6667 0.7 8 4 1.25 0.8 9 5 1.6 0.7 10 9 1.1111 0.6 11 5 1.2 0.6 12 8 1.25 0.9 13 6 1.1667 0.8 14 5 1.4 0.7 15 3 2.3333 0.8 16 9 1.2222 0.7 17 3 1.6666 0.5 18 4 2 0.8 19 6 1.3333 0.7 20 7 1.4286 0.9 k = 5.15 j = 1.7431 t = 0.695 Bảng 2 (với n = 100, k = 10 k2 , αk = ck = 1). Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 42 Bài toán k j1 CPU-thời gian 1 12 1.1666 1 2 196 1.0102 2 3 38 1.0526 0.8 4 97 1.0206 1 5 110 1.0182 1 6 44 1.0455 0.8 7 5 1.4 0.9 8 61 1.0328 0.9 9 8 1.25 0.8 10 283 1.0071 2 11 95 1.0316 1 12 94 1.0213 0.8 13 197 1.0152 2 14 151 1.0132 1 15 147 1.0136 1 16 230 1.0087 2 17 90 1.0222 0.8 18 11 1.1818 0.8 19 175 1.0114 1 20 31 1.0645 0.8 k = 101.5 j = 1.0739 t = 1.12 Bảng 3 (với n = 1000, k = 30 k2 , αk = ck = 1). Từ kinh nghiệm và kết quả tính toán, ta có thể khẳng định rằng Thuật toán BFP khá hiệu quả cho bài toán cân bằng bán độc quyền với số biến khoảng vài trăm. Với bài toán cân bằng bán độc quyền khoảng vài nghìn biến, thuật toán cũng có thể hiệu quả với việc chọn dãy số dương {k} phù hợp. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 43 Kết luận Trong luận văn này ta đã dùng cách tiếp cận điểm bất động cho bài toán bất đẳng thức biến phân với ánh xạ giá là đơn điệu mạnh hoặc đồng bức. Ta đã chứng tỏ rằng việc tìm nghiệm của bài toán VI được quy về tìm điểm bất động của một ánh xạ h. Bằng cách sử dụng kỹ thuật điều chỉnh, ta đã chứng tỏ rằng ánh xạ nghiệm h có tính chất co. Cụ thể, khi ánh xạ giá là đơn điệu mạnh, tính chất co này cho phép ta xây dựng một thuật toán lặp theo kiểu nguyên lý ánh xạ co Banach để giải bài toán VI. Cách tiếp cận này cho phép thiết lập dễ dàng tốc độ hội tụ của phương pháp lặp. Khi giảm nhẹ điều kiện đơn điệu mạnh bằng điều kiện đồng bức, ta đã chỉ ra rằng ánh xạ nghiệm h có tính chất không giãn. Tính chất này cho phép ta bổ sung phương pháp lặp theo nguyên lý ánh xạ co Banach để thu được một phương pháp giải cho bài toán VI. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 43 Tài liệu Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com 44 Tài liệu tham khảo Tài liệu tiếng Việt [1] L. D. Mưu, Nhập môn các phương pháp tối ưu, Viện Toán học, Hà Nội, 1998. [2] H. Tụy, Hàm thực và giải tích hàm, Viện Toán học, Hà Nội, 2003. Tài liệu tiếng Anh [3] P. N. Anh and L. D. Muu (2004), "Coupling the Banach contraction map- ping principle and the proximal point algorithm for solving monotone vari- ational inequalites", Acta Mathematica Vietnamica, 29, pp. 119-133. [4] P. N. Anh, L. D. Muu, V. H. Nguyen and J. J. Strodiot (2005), "On the contraction and nonexpansiveness properties of the marginal mapping in generalized variational inequalities involving cocoercive operators", in: Generalized Convexity and Generalized Monotonicity and Applications. Eds A. Eberhard, N. Hadjisavvas and D. T. Luc, Springer, pp. 89-111. [5] F. Facchinei and J. S. Pang (2002), Finite Dimesional Variational Inequal- ities and Complementarity Problems, Springer Verlag. [6] D. Kinderlehrer and G. Stampacchia (1980), An Introduction to Varia- tional Inequalities and Their Applications, Academic Press. [7] A. Narguney (1983), Network Economics: a Variational Inequality Ap- proach, Kluwer Academic Publishers. [8] H. Tuy (1997), Convex Analysis and Global Optimization, Kluwer Aca- demic Publishers. Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn www.VNMATH.com