Tài liệu Luận văn một số phương pháp giải bài toán bất đẳng thức biến phân

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI LÊ THỊ HUỆ MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội, 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI LÊ THỊ HUỆ MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán giải tích Mã số: 60460102 Người hướng dẫn khoa học TS. Nguyễn Thế Vinh HÀ NỘI, 2017 Mục lục Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1. Một số kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1. Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 1.1.1. Tập lồi và nón pháp tuyến của một tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2. Siêu phẳng và nửa không gian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3. Phép chiếu metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.4. Sự hội tụ yếu, hội tụ mạnh trong không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6 8 8 1.2. Định lý điểm bất động Banach, Brouwer . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3. Tính đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4. Ánh xạ hemi-liên tục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5. Bất đẳng thức biến phân và sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . 13 1.5.1. Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.2. Các bài toán liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3. Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.4. Phương pháp chiếu gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 14 17 22 Chương 2. Phương pháp extragradient giải bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1. Giới thiệu phương pháp và minh họa hình học . . . . . . . . . . . . . . . . . . 26 2.2. Sự hội tụ của phương pháp extragradient . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1. Kết quả hội tụ mạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2. Kết quả hội tụ yếu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 3. Các dạng cải tiến của phương pháp extragradient . . . . . . . 3.1. Phương pháp subgradient extragradient . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Giới thiệu phương pháp và minh họa hình học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2. Sự hội tụ của thuật toán subgradient extragradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 34 37 37 38 39 3.2. Phương pháp Popov subgradient extragradient. . . . . . . . . . . . . . . . . . 3.3. Phương pháp chiếu gradient đối xứng . . . . . . . . . . . . . . . . . . . . . . . . . 48 52 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS Nguyễn Thế Vinh đã định hướng chọn đề tài và tận tình hướng dẫn, giúp đỡ tôi hoàn thành luận văn này. Tôi cũng xin chân thành cảm ơn hai Thầy phản biện, TS Lê Anh Dũng và TS Dương Việt Thông đã cho tác giả nhiều nhận xét quý báu và xác đáng. Tôi xin chân thành cảm ơn tới các thầy cô giáo phòng Sau Đại học, các thầy cô giáo giảng dạy lớp Cao học K25 chuyên ngành Toán giải tích trường Đại học Sư phạm Hà Nội đã giúp đỡ tôi trong suốt quá trình học tập. Nhân dịp này tôi xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè, đồng nghiệp đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và hoàn thành luận văn này. Do thời gian và khả năng có hạn, chắc chắn bản luận văn không tránh khỏi thiếu sót, tác giả mong nhận được sự góp ý sửa chữa của Quý Thầy Cô để có thể nâng cao chất lượng của luận văn này. Hà Nội, tháng 06 năm 2017 Tác giả Lê Thị Huệ Lời cam đoan Tôi xin cam đoan, dưới sự hướng dẫn của TS Nguyễn Thế Vinh, luận văn thạc sĩ chuyên ngành Toán giải tích với đề tài "Một số phương pháp giải bài toán bất đẳng thức biến phân" được hoàn thành bởi chính sự nhận thức của bản thân tác giả. Trong suốt quá trình nghiên cứu thực hiện luận văn, tác giả đã kế thừa những thành tựu của các nhà khoa học với sự trân trọng và biết ơn. Hà Nội, tháng 06 năm 2017 Tác giả Lê Thị Huệ Mở đầu 1. Lý do chọn đề tài Năm 1966, Hartman và Stampacchia [7] đã công bố những nghiên cứu đầu tiên của mình về bài toán bất đẳng thức biến phân, liên quan đến 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 trong lý thuyết phương trình đạo hàm riêng. Năm 1980, trong cuốn sách "An Introduction to Variational Inequalities and Their Applications", Kinderlehrer và Stampacchia [11] đã nghiên cứu bài toán bất đẳng thức biến phân trong không gian vô hạn chiều và ứng dụng của nó. Năm 1984, trong cuốn sách "Variational and Quasivariational Inequalities " của Baiocchi và Capelo [3] đã áp dụng bất đẳng thức biến phân và tựa biến phân để giải các bài toán biên tự do. Hiện nay bài toán bất đẳng thức biến phân đã được mở rộng và phát triển cho nhiều dạng khác nhau như bất đẳng thức biến phân véctơ, bất đẳng thức tựa biến phân, bất đẳng thức biến phân ẩn, bất đẳng thức biến phân suy rộng. Bài toán này đã thu hút được sự quan tâm của đông đảo các nhà toán học trên thế giới vì nó là mô hình hợp nhất của nhiều bài toán quan trọng trong lý thuyết và thực tiễn như tối ưu hóa, bài toán bù, lí tuyết trò chơi, cân bằng Nash, cân bằng mạng giao thông,. . . Một trong những hướng nghiên cứu quan trọng của lý thuyết 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. Để hiểu sâu sắc hơn về vấn đề này, em chọn đề tài nghiên cứu của luận văn là "Một số phương pháp giải bài toán bất đẳng thức biến phân." 2. Mục đích nghiên cứu Nghiên cứu một số phương pháp chiếu giải bài toán bất đẳng thức biến phân. Đặc biệt đi sâu vào việc tìm hiểu, giới thiệu và trình bày các kết quả hội tụ của phương pháp chiếu gradient (phương pháp chiếu đạo hàm), phương pháp extragradient (phương pháp đạo hàm tăng cường) và các dạng cải tiến của nó. 3. Nhiệm vụ nghiên cứu • Nghiên cứu sự hội tụ của phương pháp chiếu gradient. 1 • Nghiên cứu sự hội tụ yếu và hội tụ mạnh của phương pháp extragradient và phương pháp subgradient extragradient. • Nghiên cứu sự hội tụ yếu của phương pháp gradient đối xứng và phương pháp Popov subgradient extragradient. 4. Đối tượng và phạm vi nghiên cứu • Đối tượng nghiên cứu: Bài toán bất đẳng thức biến phân. • Phạm vi nghiên cứu: Sự tồn tại nghiệm và các thuật toán giải bài toán bất đẳng thức biến phân. 5. Phương pháp nghiên cứu Nghiên cứu tổng quan tài liệu, phân tích, tổng hợp, hệ thống lại các kết quả lý thuyết về sự tồn tại nghiệm và phương pháp giải bất đẳng thức biến phân. 6. Đóng góp của luận văn • Luận văn đã trình bày một cách hệ thống và chi tiết một số phương pháp giải bài toán bất đẳng thức biến phân. • Luận văn trình bày các thuật toán quan trọng được sử dụng nhiều để giải bài toán bất đẳng thức biến phân trong vòng 50 năm trở lại đây như thuật toán chiếu gradient, thuật toán extragradient, thuật toán subgradient extragradient, thuật toán Popov subgradient extragradient và thuật toán chiếu gradient đối xứng cùng với các kết quả hội tụ của chúng. • Luận văn sẽ là tài liệu tham khảo hữu ích cho những ai quan tâm đến các phương pháp giải bài toán bất đẳng thức biến phân để áp dụng vào các lĩnh vực liên quan như điểm bất động, tối ưu, phương trình đạo hàm riêng,... 7. Tổng quan và bố cục của luận văn Bài toán bất đẳng thức biến phân là bài toán Tìm x ∈ K sao cho hF (x) , y − xi ≥ 0 với mọi y ∈ K, (VIP(K, F )) trong đó K là tập con lồi, đóng, khác rỗng của không gian Hilbert thực H và F : K → H là ánh xạ đơn trị. 2 Lý thuyết bài toán bất đẳng thức biến phân đóng vai trò quan trọng trong nhiều lĩnh vực như quy hoạch toán học, nghiên cứu mạng giao thông, lý thuyết trò chơi,... và đã trở thành một lĩnh vực nghiên cứu quan trọng trong vòng 50 năm trở lại đây (xem Ansari [2], Giannessi [6], Kinderlehrer và Stampacchia [11], Konnov [12]). Nhờ vào tính chất của phép chiếu, ta biết rằng bài toán VIP(K, F ) tương đương với bài toán điểm bất động sau: Tìm x̄ sao cho x = PK (x − λF (x)) , (1) trong đó λ > 0. Vấn đề quan tâm trước hết là sự tồn tại nghiệm của bài toán bất đẳng thức biến phân. Khi K compact và F liên tục, sự tồn tại nghiệm của bài toán VIP(K, F ) là hệ quả của định lý điểm bất động Schauder. Nếu K compact và F là giả đơn điệu và hemi-liên tục thì sự tồn tại nghiệm của VIP(K, F ) được thiết lập bằng kỹ thuật KKM. Một trong những vấn đề thú vị và quan trọng nhất trong lý thuyết bất đẳng thức biến phân là nghiên cứu các thuật toán lặp hữu hiệu để tìm nghiệm xấp xỉ của bài toán. Nhiều thuật toán lặp đã được đề xuất để giải bất đẳng thức biến phân ở cả không gian hữu hạn chiều và vô hạn chiều, chẳng hạn xem trong [2, 5, 12, 13, 14, 15, 17, 18] và các tài liệu tham khảo liên quan. Trong các phương pháp lặp giải bài toán VIP(K, F ) thì phương pháp đơn giản nhất là phương pháp chiếu gradient được bắt nguồn từ phương trình điểm bất động (1): ( x0 ∈ K, xm+1 = PK (xm − γF (xm )), m ≥ 0, trong đó PK là phép chiếu metric của H lên K, γ là số thực dương. Sự hội tụ của phương pháp này đòi hỏi F là ánh xạ đơn điệu mạnh (hoặc đơn điệu mạnh ngược) và liên tục Lipschitz. Để giảm nhẹ tính đơn điệu mạnh, Korpelevich [13] đề xuất phương pháp extragradient, trong đó tại mỗi bước lặp thuật toán đòi hỏi thêm một phép chiếu lên tập chấp nhận được. Với điều kiện F đơn điệu và liên tục Lipschitz, thuật toán extragradient cho sự hội tụ yếu trong không gian Hilbert. Nhiều nhà nghiên cứu đã đề xuất các cải tiến của phương pháp extragradient như Popov [19] (1980), Khobotov [10] (1987), Iusem-Svaiter [8] (1997), Malitsky và Semenov [14] (2014), Solodov-Svaiter [21] (1999), Censor và cộng sự [5] (2011), Malitsky [15] (2015), Maingé [17] (2016), Maingé và Gobinddass [18] (2016). Mục đích của luận văn này nhằm trình bày tổng quan các kết quả quan trọng liên quan đến thuật toán chiếu gradient và extragradient. Ngoài phần mở đầu và phần tài liệu tham khảo, luận văn được chia làm 3 chương. Chương 1: nhắc lại một số kiến thức cơ bản về giải tích lồi, giới thiệu bài 3 toán bất đẳng thức biến phân và các ứng dụng, đồng thời trình bày sự tồn tại nghiệm của bài toán và phương pháp chiếu gradient. Chương 2: trình bày phương pháp extragradient, phân tích sự hội tụ yếu và hội tụ mạnh của phương pháp này. Chương 3: trình bày các dạng cải tiến của phương pháp extragradient, cụ thể trình bày về phương pháp subgradient extragradient, phương pháp Popov subgradient extragradient, phương pháp chiếu gradient đối xứng, đồng thời xét đến sự hội tụ của các phương pháp trong không gian Hilbert. 4 Chương 1 Một số kiến thức chuẩn bị Trong chương này, chúng ta nhắc lại khái niệm cũng như các kết quả bổ trợ cần thiết được sử dụng ở các chương sau. Các kết quả chủ yếu tham khảo trong [1, 2]. 1.1. Các khái niệm 1.1.1. Tập lồi và nón pháp tuyến của một tập lồi Định nghĩa 1.1. Cho H là một không gian Hilbert thực, tập hợp C ⊂ H được gọi là tập lồi nếu ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. Ví dụ 1.1. Hình cầu đóng B (x, r) = {a ∈ H : ka − xk ≤ r} là tập lồi. Mệnh đề 1.1. Nếu A, B là các tập lồi trong không gian Hilbert thực H thì các tập hợp sau là tập lồi: A ∩ B := {x | x ∈ A, x ∈ B} , αA + βB := {x | x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R} , A × B := {x | x = (a, b) : a ∈ A, b ∈ B} . Định nghĩa 1.2. Cho C ⊂ H là một tập lồi, khác rỗng và x0 ∈ C. Nón pháp tuyến của C tại x0 là tập hợp được ký hiệu và xác định như sau:   NC (x0 ) := d ∈ H : d, y − x0 ≤ 0 ∀y ∈ C . Định nghĩa 1.3. Cho C ⊂ H là một tập lồi, đóng, khác rỗng. Nón đối ngẫu của C, kí hiệu là C ∗ , là tập hợp được xác định C ∗ = {y ∈ H : hy, xi ≥ 0 ∀x ∈ C} . Về mặt hình học, C ∗ là tập hợp bao gồm tất cả các véctơ y ∈ H tạo thành một góc không tù với mọi véctơ x ∈ C. 5 Hình 1.1: Một tập lồi và nón pháp tuyến tại một điểm của nó. Hình 1.2: Một tập lồi và nón đối ngẫu của nó 1.1.2. Siêu phẳng và nửa không gian Định nghĩa 1.4. Cho một véctơ khác không a ∈ H và λ ∈ R, tập hợp H = {x ∈ H : ha, xi = λ} được gọi là một siêu phẳng trong H. Véctơ a được gọi là véctơ pháp tuyến của siêu phẳng H. Ví dụ 1.2. Trong R3 siêu phẳng là mặt phẳng, trong R2 siêu phẳng là đường thẳng. Hình 1.3: Một siêu phẳng và véctơ pháp tuyến của nó. 6 Định nghĩa 1.5. Cho a ∈ H là một vectơ khác không và λ ∈ R. a) H ++ = {x ∈ H : ha, xi > λ} được gọi là nửa không gian mở trên. b) H −− = {x ∈ H : ha, xi < λ} được gọi là nửa không gian mở dưới. c) H + = {x ∈ H : ha, xi ≥ λ} được gọi là nửa không gian đóng trên. d) H − = {x ∈ H : ha, xi ≤ λ} được gọi là nửa không gian đóng dưới. Hình 1.4: Nửa không gian đóng. Nhận xét 1.1. a) Một siêu phẳng sẽ chia không gian thành hai nửa không gian. b) Các nửa không gian là các tập lồi. Định nghĩa 1.6. Cho S ⊂ H khác rỗng và x nằm trên biên của S. Siêu phẳng H = {x ∈ H : ha, x − xi = 0, a 6= 0, a ∈ H} được gọi là siêu phẳng tựa của S tại x nếu S ⊆ H + , tức là ha, x − xi ≥ 0 ∀x ∈ S, hoặc S ⊆ H − , tức là ha, x − xi ≤ 0 ∀x ∈ S. Nhận xét 1.2. Định nghĩa 1.6 có thể phát biểu tương đương như sau: Siêu phẳng H = {x ∈ H : ha, x − xi = 0} là siêu phẳng tựa của S tại x nằm trên biên của S nếu ha, xi = inf {ha, xi : x ∈ S} , hoặc ha, xi = sup {ha, xi : x ∈ S} . Nhận xét 1.3. Mỗi điểm biên của một tập lồi đều có một siêu phẳng tựa đi qua. 7 1.1.3. Phép chiếu metric Cho H là không gian Hilbert thực và K là tập con lồi, đóng, khác rỗng của H. Với mọi x ∈ H, tồn tại duy nhất một điểm trong K, ký hiệu là PK (x) sao cho kx − PK (x)k = inf {kx − yk : y ∈ K} . Ánh xạ PK : H → K x 7→ PK (x) được gọi là phép chiếu metric của H lên K. Mệnh đề 1.2. Phép chiếu metric PK có các tính chất sau: a) hx − PK (x) , y − PK (x)i ≤ 0 ∀x ∈ H và y ∈ K; b) kPK (x) − PK (y)k ≤ kx − yk ∀x, y ∈ H (tính không giãn); c) hx − y, PK (x) − PK (y)i ≥ kPK (x) − PK (y)k2 đồng bức); d) kx − yk2 ≥ kx − PK (x)k2 + ky − PK (x)k2 ∀x, y ∈ H (tính ∀x ∈ H và y ∈ K. Hình 1.5: Tính không giãn của phép chiếu metric. 1.1.4. Sự hội tụ yếu, hội tụ mạnh trong không gian Hilbert Định nghĩa 1.7. Cho không gian Hilbert thực H.  k a) Dãy x ⊂ H được gọi là hội tụ yếu tới điểm x ∈ H nếu∀y ∈ H dãy   k y, x hội tụ tới hy, xi. Ta  gọi x là giới hạn yếu của dãy xk và viết xk * x. Nếu dãy {xnk } ⊆ xk hội tụ yếu tới x thì x được gọi là điểm  con tụ yếu của dãy xk . 8  b) Ta nói xk hội tụ mạnh tới x nếu lim xk − x = 0. k→∞ Mệnh đề 1.3. Dãy hội tụ yếu có các tính chất sau:  a) Nếu dãy xk ⊂ H hội tụ yếu thì nó có đúng một giới hạn yếu,  b) Nếu dãy xk ⊂ H hội tụ yếu thì nó bị chặn,  c) Nếu dãy xk ⊂ H bị chặn thì nó chứa một dãy con hội tụ yếu,  d) Nếu dãy xk ⊂ H bị chặn và có đúng một điểm tụ yếu x ∈ H thì xk * x,  e) Nếu dãy xk hội tụ mạnh tới x ∈ H thì nó hội tụ yếu tới x ∈ H,  f) Nếu dãy xk hội tụ yếu trong không gian Hilbert H hữu hạn chiều thì nó cũng hội tụ mạnh. Chiều ngược lại của e) không đúng. Ta xét phản ví dụ sau:  Ví dụ 1.3. Cho H = `2 và xk ⊂ H sao cho: xk = (0, 0, 0, · · · , 1, 0, · · · ) ∀k ∈ N. ↑ Vị k
trí thứ 1 2 k ∗ Với mọi y = y , y , · · · , y , · · · ∈ H = `2 , ta có: k  x , y = y k → 0 khi k → ∞. k  k k Do đó x * 0 khi k → ∞. Tuy nhiên x không hội tụ mạnh vì x = 1 với mọi k ∈ N. 1.2. Định lý điểm bất động Banach, Brouwer Định lí 1.1. (Banach, 1922) Cho X là một không gian metric đầy đủ và T : X → X là một ánh xạ co. đó T có một điểm bất động duy nhất x∗ ∈ X.  Khi Hơn nữa, với mọi x ∈ X, T k x → x∗ khi k → ∞. Định lý Banach đúng với mọi không gian metric đầy đủ do đó trong trường hợp đặc biệt nó đúng cho tất cả các tập con đóng của một không gian Hilbert. Định lý Banach có những ưu điểm nổi bật: ngoài sự tồn tại, nó còn cho ta tính duy nhất, phương pháp tìm điểm bất động và đánh giá được độ chính xác tại mỗi bước lặp. Tuy nhiên, điều kiện co là khá ngặt. Việc nghiên cứu về điểm bất động của ánh xạ không giãn sẽ phức tạp hơn nhiều so với ánh xạ co. Nó đòi hỏi phải có những công cụ đặc biệt. Dưới đây, chúng tôi xin trình bày một số định lý điểm bất động cổ điển. 9 Định lí 1.2. (Brouwer, 1912) Cho C là một tập con lồi, compact, khác rỗng của một không gian Hilbert hữu hạn chiều H và T : C → C là một ánh xạ liên tục. Khi đó T có một điểm bất động. Định lý điểm bất động Brouwer tương đương với nguyên lý ánh xạ KKM sau đây. Định lí 1.3. Cho C là một tập hợp trong không gian véctơ tôpô tách X và F : C → 2X là ánh xạ đa trị thỏa mãn: a) F (x) đóng với mọi x ∈ C,  b) F là ánh xạ KKM, tức là với mọi tập hợp hữu hạn x1 , x2 , x3 , · · · , xk ⊂ C ta có k  1 2 3
[
k co x , x , x , · · · , x ⊂ F xi i=1
 T 2 3 , x , · · · , xk ⊂ C. Ngoài ra nếu tồn Khi đó ki=1 F xi 6= ∅
với mọi x1 , xT F (x) 6= ∅. tại x0 ∈ C sao cho F x0 compact thì x∈C Định lý điểm Brouwer được mở rộng cho trường hợp không gian vô hạn chiều như sau. Định lí 1.4. (Schauder, 1930) Cho C là một tập con lồi, compact khác rỗng của một không gian Banach và T : C → C là một ánh xạ liên tục. Khi đó T có một điểm bất động. Đối với các ánh xạ không giãn trong một không gian Hilbert H, tính compact của C ⊂ H trong định lý Schauder có thể thay thế bởi tính bị chặn của C. Định lí 1.5. (Browder–Göhde–Kirk, 1965) Cho C là một tập con lồi, đóng, bị chặn, khác rỗng của không gian Hilbert thực H và T : C → C là một ánh xạ không giãn. Khi đó T có một điểm bất động. Khác với định lý Banach, các định lý Browder–Göhde–Kirk, Schauder và Brouwer chỉ cho ta sự tồn tại của điểm bất động. 1.3. Tính đơn điệu Định nghĩa 1.8. Giả sử K là một tập con lồi, đóng, khác rỗng trong không gian Hilbert thực H. Toán tử F : K → H được gọi là 10 a) đơn điệu mạnh trên K nếu tồn tại δ > 0 sao cho hF (x) − F (y) , x − yi ≥ δ kx − yk2 ∀x, y ∈ K. b) đơn điệu trên K nếu hF (x) − F (y) , x − yi ≥ 0 ∀x, y ∈ K. c) đơn điệu chặt trên K nếu hF (x) − F (y) , x − yi > 0 ∀x, y ∈ K, x 6= y. d) giả đơn điệu mạnh trên K nếu tồn tại δ > 0 sao cho với mọi x, y ∈ K hF (x) , y − xi ≥ 0 ⇒ hF (y) , y − xi ≥ δ ky − xk2 . e) giả đơn điệu trên K nếu với mọi x, y ∈ K hF (x) , y − xi ≥ 0 ⇒ hF (y) , y − xi ≥ 0. Ví dụ 1.4. a) Hàm F (x) = x, ∀x ∈ R là đơn điệu mạnh với δ = 21 . b) Hàm F (x) = x3 , ∀x ∈ R là đơn điệu chặt. c) Hàm F (x) = c, ∀x ∈ R là đơn điệu. Theo định nghĩa trên các kéo theo (a) ⇒ (b), (a) ⇒ (c), (a) ⇒ (d), (c) ⇒ (e), (d) ⇒ (e) là hiển nhiên. Chú ý một toán tử giả đơn điệu mạnh có thể không đơn điệu. Ví dụ 1.5. Cho 0 < r < R, đặt K = B (r) : {x ∈ H : kxk ≤ r} và F được cho bởi hF (x) , y − xi := hK (x) , y − xi + (R − kxk) hG (x) , y − xi , trong đó K và G thỏa mãn các điều kiện sau: a) hK (x) , y − xi ≤ 0, ∀x, y ∈ K và G là β− đơn điệu mạnh trên K, b) ∃y 0 ∈ K sao cho ( 
 K (0) , y 0 + K y 0 , −y 0 = 0,

 R G (0) , y 0 + R − y 0 G y 0 , −y 0 > 0. 11 Giả sử hF (x) , y − xi ≥ 0, do hK (x) , y − xi ≤ 0 nên ta có: hG (x) , y − xi ≥ 0. Suy ra hG (y) , x − yi ≤ −β ky − xk2 (do G đơn điệu mạnh). Theo định nghĩa của hF (x) , y − xi ta có: ∀x, y ∈ K, hF (y) , x − yi = hK (y) , x − yi + (R − kyk) hG (y) , x − yi ≤ − (R − r) β ky − xk2 . Suy ra F giả đơn điệu mạnh trên K. Hơn nữa, theo (ii) ta có: 
   F (0) , y 0 + F y 0 , −y 0 = K (0) , y 0 + R G (0) , y 0 +


 + K y 0 , −y 0 + R − y 0 G y 0 , −y 0 > 0. Do đó F không đơn điệu. 1.4. Ánh xạ hemi-liên tục Định nghĩa 1.9. Giả sử K là một tập con lồi, đóng, khác rỗng trong không gian Hilbert thực H và F : K → H là một ánh xạ. Khi đó F được gọi là hemi-liên tục nếu với mọi x, y ∈ K và z ∈ H, hàm λ 7→ hz, F (λx + (1 − λ) y)i từ [0, 1] vào R là hàm liên tục. Ví dụ 1.6. Cho K = H = R2 và ánh xạ F : K → H xác định bởi F (x, y) = (f1 (x, y) , 0) trong đó    0, nếu x = 0 hoặc y ≤ 0, y f1 (x, y) = nếu 0 < y ≤ x2 , x2 ,   x2 nếu 0 < x2 ≤ y. y , Dễ thấy f1 (x, y) liên tục khắp nơi trừ gốc tọa độ, tại đó nó liên tục theo bất kỳ đường thẳng nào đi qua gốc tọa độ. Do đó F hemi-liên tục nhưng không liên tục tại gốc tọa độ. Hơn nữa dễ thấy F là giả đơn điệu nhưng không đơn điệu. Để
1 thấy F không đơn điệu ta lấy u = (1, 2) và v = (2, 1) khi đó F (1, 2) = , 0 , 2
1 F (2, 1) = 4 , 0 và   1 F (1, 2)−F (2, 1) = , 0 , (1, 2)−(2, 1) = (−1, 1) , (2, 1)−(1, 2) = (1, −1) . 4 12 Do đó 1 > 0, 2 1 hF (2, 1) , (2, 1) − (1, 2)i = > 0, 4 hF (1, 2) , (2, 1) − (1, 2)i = hF (1, 2) − F (2, 1) , (1, 2) − (2, 1)i = −1 < 0. 4 Suy ra F giả đơn điệu nhưng không đơn điệu. 1.5. Bất đẳng thức biến phân và sự tồn tại nghiệm 1.5.1. Mô tả bài toán Cho K là một tập con khác rỗng của H và ánh xạ F : K → H. Bài toán tìm x ∈ K sao cho hF (x) , y − xi ≥ 0 ∀y ∈ K (1.1) được gọi là bài toán bất đẳng thức biến phân và được ký hiệu là VIP(K, F ). Về mặt hình học, véctơ x là nghiệm của VIP(K, F ) nếu và chỉ nếu F (x) tạo thành một góc không tù với véctơ y − x với mọi y ∈ K. Tập hợp các nghiệm của VIP(K, F ) được kí hiệu là Sol(K, F). Ví dụ 1.7. Trong R, xét tập K = [1; 5] ⊂ R và ánh xạ F : [1; 5] → R được xác định bởi: F (y) = y − 1 ∀y ∈ [1; 5] . Khi đó, VIP(K, F ) là bài toán tìm x ∈ [1; 5] sao cho hx − 1, y − xi ≥ 0 ∀y ∈ [1; 5] . (1.2) Ta chứng tỏ rằng: Sol(K, F) = {1}. Thật vậy, hiển nhiên x = 1 là một nghiệm. Nếu 0 < x < 1 thì (1.2) chỉ thỏa mãn với y ≤ x. Ngược lại, nếu x > 1 thì (1.2) chỉ thỏa mãn với y ≥ x. Điều đó chứng tỏ x = 1 là nghiệm duy nhất. Sau đây chúng ta sẽ trình bày mối quan hệ giữa VIP(K, F ) và nón pháp tuyến của một tập lồi. Mệnh đề 1.4. Cho K là một tập con lồi, đóng, khác rỗng của H và cho ánh xạ F : K → H. Khi đó x là nghiệm của bất đẳng thức biến phân VIP(K, F ) khi và chỉ khi −F (x) ∈ NK (x), trong đó NK (x) là nón pháp tuyến của K tại x. Nói cách khác, x là nghiệm của bất đẳng thức biến phân VIP(K, F ) khi và chỉ khi: 0 ∈ F (x) + NK (x). 13 Mệnh đề 1.5. Cho ánh xạ F : H → H. Véctơ x ∈ H là nghiệm của bất đẳng thức biến phân VIP(K, F ) khi và chỉ khi F (x) = 0. Chứng minh. Giả sử F (x) = 0 khi đó hF (x) , y − xi = 0 ∀y ∈ K. Suy ra x ∈ Sol(K, F). Ngược lại, giả sử x ∈ Sol(K, F). Khi đó hF (x) , y − xi ≥ 0 ∀y ∈ K. Thay y = x − F (x) vào bất đẳng thức trên ta có: hF (x) , x − F (x) − xi = hF (x) , −F (x)i ≥ 0. Do đó − kF (x)k2 ≥ 0. Suy ra F (x) = 0. 1.5.2. Các bài toán liên quan Bất đẳng thức biến phân có liên hệ mật thiết với nhiều bài toán khác như: bài toán bù phi tuyến, bài toán tối ưu, bài toán điểm bất động,... Bài toán bù phi tuyến Định nghĩa 1.10. Cho K là một nón lồi, đóng trong H và ánh xạ F : K → H. Bài toán bù phi tuyến (nonlinear complementarity problem) là bài toán sau đây: Tìm x ∈ K sao cho F (x) ∈ K ∗ và hF (x), xi = 0. trong đó K ∗ là nón đối ngẫu của K. Ký hiệu bài toán là NCP(K, F ). Mệnh đề 1.6. Nếu K là một nón lồi, đóng trong H thì bài toán NCP(K, F ) tương đương với bài toán VIP(K, F ) theo nghĩa tập nghiệm của các bài toán này trùng nhau. Chứng minh. Giả sử x ∈ K là nghiệm của bài toán VIP(K, F ). Theo định nghĩa ta có: hF (x) , y − xi ≥ 0 ∀y ∈ K. (1.3) Do K là nón lồi đóng nên với mọi x ∈ K ta có x + x ∈ K. Thay y trong bất đẳng thức (1.3) bởi x + x ta được hF (x) , xi ≥ 0 ∀x ∈ K. 14 (1.4) Suy ra F (x) ∈ K ∗ . Mặt khác, cũng vì K là nón và x ∈ K nên 2x ∈ K. Thay y trong bất đẳng thức (1.3) bởi 2x ta được (1.5) hF (x) , xi ≥ 0. Thay y trong bất đẳng thức (1.3) bởi 0 ta được hF (x) , −xi ≥ 0. (1.6) Từ (1.5) và (1.6) ta kết luận: hF (x) , xi = 0, hay x là nghiệm của bài toán NCP(K, F ). Ngược lại, giả sử x ∈ K là nghiệm của bài toán NCP(K, F ). Theo định nghĩa ta có: F (x) ∈ K ∗ và hF (x), xi = 0. Vì F (x) ∈ K ∗ nên hF (x) , yi ≥ 0 với mọi y ∈ K. Do đó hF (x) , y − xi = hF (x) , yi − hF (x), xi ≥ 0 ∀y ∈ K. Hay x là nghiệm của bài toán VIP(K, F ). Bài toán tối ưu Cho K ⊂ H là tập lồi, đóng, khác rỗng và f : K → R là một ánh xạ khả vi. Bài toán tối ưu được phát biểu như sau: Tìm x ∈ K sao cho f (x) = min {f (x) : x ∈ K} . (1.7) Mệnh đề 1.7. Nếu x ∈ K là nghiệm của bài toán tối ưu (1.7) thì x là nghiệm của bài toán VIP(K, F ) với F = ∇f (đạo hàm của f ). Chứng minh. Với y ∈ K bất kỳ, do K lồi nên x + λ (y − x) ∈ K với λ ∈ [0; 1]. Xét hàm ϕ: [0; 1] → R xác định bởi ϕ (λ) = f (x + λ (y − x)) ∀λ ∈ [0; 1] . Vì ϕ (λ) đạt cực tiểu tại λ = 0 nên ϕ0 (0) ≥ 0, tức là hF (x), y − xi = h∇f (x), y − xi ≥ 0 ∀y ∈ K. Do đó x là nghiệm của bài toán VIP(K, F ) với F = ∇f . Mệnh đề 1.8. Cho K ∈ H là tập lồi, đóng, khác rỗng và f : K → R là hàm giả lồi. Nếu x ∈ K là nghiệm của bài toán VIP(K, F ) với F (x) = ∇f (x) thì x cũng là nghiệm của bài toán tối ưu (1.7). 15