Tài liệu Phương pháp phân rã douglas rachford giải bài toán cân bằng

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG THỊ DIỆU LINH PHƯƠNG PHÁP PHÂN RÃ DOUGLAS-RACHFORD GIẢI BÀI TOÁN CÂN BẰNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG THỊ DIỆU LINH PHƯƠNG PHÁP PHÂN RÃ DOUGLAS-RACHFORD GIẢI BÀI TOÁN CÂN BẰNG Chuyên ngành: Toá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.TS. NGUYỄN BƯỜNG THÁI NGUYÊN - 2016 i Mục lục Lời cảm ơn ii Danh sách ký hiệu iii Mở đầu 1 1 Một số vấn đề cơ bản 4 1.1 Không gian Hilbert thực . . . . . . . . . . . . . . . . . . . 4 1.2 Bài toán cân bằng . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Phương pháp Douglas-Rachford giải 0 ∈ Ax + Bx . . . . . 16 2 Phương pháp phân rã Douglas-Rachford giải bài toán cân bằng 23 2.1 Bao hàm thức đơn điệu và bài toán cân bằng . . . . . . . . . 24 2.2 Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . 29 Kết luận 36 Tài liệu tham khảo 37 ii Lời cảm ơ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ự giúp đỡ và hướng dẫn tận tình của GS.TS. Nguyễn Bường. Qua đây, 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, người đã dành nhiều thời gian và tâm huyết để hướng dẫn và tạo điều kiện cho tác giả trong suốt thời gian làm luận văn. Trong quá trình học tập và làm luận văn, từ bài giảng của các giáo sư, phó giáo sư công tác tại Viện Toán học, Viện Công nghệ Thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam, các thầy cô trong trường Đại học Khoa học - Đại học Thái Nguyên, tác giả đã trau dồi thêm rất nhiều kiến thức phục vụ cho việc nghiên cứu và công tác của bản thân. Tác giả xin gửi lời cảm ơn chân thành đến các thầy cô. Tác giả xin chân thành cảm ơn Ban giám hiệu, Phòng đào tạo, khoa Toán - Tin trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Thái Nguyên, tháng 01 năm 2016 Học viên Dương Thị Diệu Linh iii Danh sách ký hiệu R tập các số thực R++ tập các số thực dương N tập các số tự nhiên H không gian Hilbert thực H∗ không gian liên hợp của H C tập con lồi đóng của H EP(H) bài toán cân bằng với song hàm H EP(F, G) bài toán cân bằng với hai song hàm F và G SH tập nghiệm của bài toán cân bằng EP(H) SF +G tập nghiệm của bài toán cân bằng EP(F, G) hx, yi tích vô hướng của hai vectơ x và y k·k chuẩn sinh bởi tích vô hướng dom A miền xác định của toán tử A gra A đồ thị của toán tử A Fix T tập các điểm bất động của toán tử T xn → x dãy {xn } hội tụ mạnh tới x xn * x dãy {xn } hội tụ yếu tới x proxf toán tử gần kề của hàm f sri C phần trong tương đối của tập C Γ0 (H) họ tất cả các hàm lồi f nửa liên tục dưới từ H đến (−∞, +∞] 1 Mở đầu Sự cân bằng thường được hiểu như là một trạng thái đồng đều nhau giữa những lực lượng đối lập hay những đối tượng có ảnh hưởng qua lại lẫn nhau. Thuật ngữ này được sử dụng rộng rãi trong khoa học và kỹ thuật như trong vật lý, hóa học, kỹ thuật,... Trong hóa học, cân bằng hóa học xảy ra khi tốc độ của phản ứng thuận bằng với tốc độ của phản ứng nghịch. Trong sinh học, cân bằng sinh thái là trạng thái ổn định tự nhiên của hệ sinh thái, hướng tới sự thích nghi cao nhất với điều kiện sống, trạng thái này xảy ra khi tương quan lực lượng giữa con mồi và thú săn mồi trong hệ sinh thái đó có tỷ lệ tương đồng với nhau. Có nhiều bài toán liên quan đến sự cân bằng được nhìn nhận trong một thể thống nhất qua các mô hình toán học khác nhau của nó như bài toán điểm yên ngựa, bài toán điểm bất động Kakutani... Mô hình chung cho bài toán cân bằng đó là Tìm x ∈ C sao cho (∀y ∈ C) H(x, y) ≥ 0, trong đó C là tập con lồi đóng, khác rỗng của không gian Hilbert thực H, và song hàm H : C × C → R thỏa mãn H(x, x) = 0 với mọi x ∈ H được gọi là song hàm cân bằng. Bài toán này lần đầu được đưa ra vào năm 1955 bởi H. Nikaido, K. Isoda khi tổng quát hóa bài toán cân bằng Nash trong trò chơi không hợp tác và vào năm 1972 nó được xét đến dưới dạng một bất đẳng thức minimax bởi 2 tác giả Ky Fan, người đã có nhiều đóng góp quan trọng cho bài toán nên bài toán được gọi là bất đẳng thức Ky Fan, tuy nhiên nó có tên gọi là bài toán cân bằng (equilibrium problem) theo cách gọi của các tác giả L. D. Muu và W. Oettli năm 1992, E. Blum và W. Oettli năm 1994. Bài toán cân bằng là một mô hình toán học thống nhất cho nhiều lớp bài toán quan trọng riêng lẻ. Vì vậy, các kết quả thu được về bài toán cân bằng được áp dụng trực tiếp cho các bài toán đặc biệt của nó, ngược lại, nhiều kết quả của mỗi bài toán riêng lẻ nói trên có thể mở rộng cho bài toán cân bằng với những điều chỉnh phù hợp nhờ đó nó có thể mang lại nhiều ứng dụng hơn. Các hướng nghiên cứu thường được đặt ra đối với bài toán cân bằng là: nghiên cứu những vấn đề định tính như sự tồn tại nghiệm, cấu trúc tập nghiệm, tính ổn định và nghiên cứu định lượng bao gồm xây dựng các thuật toán để giải, tốc độ hội tụ của các thuật toán và áp dụng bài toán này vào trong các bài toán thực tế. Trong các vấn đề nêu trên, thì việc nghiên cứu xây dựng các phương pháp giải chiếm một tỉ trọng lớn trong các hướng nghiên cứu về bài toán cân bằng. Tính đến nay, đã có nhiều kết quả đạt được cho một số lớp bài toán cân bằng lồi và đơn điệu, trong đó phải kể đến các phương pháp: phương pháp hàm đánh giá, phương pháp sử dụng nguyên lý bài toán phụ, phương pháp điểm gần kề, phương pháp hiệu chỉnh Tikhonov, phương pháp điểm trong và các phương pháp chiếu. Trong luận văn này tác giả trình bày phương pháp phân rã giải bài toán cân bằng với tổng hai song hàm thỏa mãn những điều kiện chuẩn. Chứng minh rằng bài toán này tương đương với bài toán tìm không điểm của tổng hai toán tử đơn điệu cực đại tương ứng với điều kiện thích hợp. Thuật toán là hệ quả của phương pháp phân rã Douglas-Rachford ứng dụng cho bao hàm thức đơn điệu bổ trợ. Mục đích của luận văn là tìm hiểu về bài toán cân bằng và phương 3 pháp phân rã Douglas-Rachford để giải bài toán cân bằng trong không gian Hilbert thực trên cơ sở bài báo [3] công bố năm 2012. Nội dung của luận văn được trình bày trong hai chương: Chương 1: Một số vấn đề cơ bản. Tác giả nhắc lại một số kiến thức cơ bản nhất của giải tích hàm và giải tích lồi sẽ được sử dụng ở chương sau. Tiếp theo là giới thiệu về bài toán cân bằng, một số ví dụ và sự tồn tại nghiệm của bài toán này. Cuối cùng trình bày thuật toán Douglas-Rachford giải bài toán tìm không điểm của tổng hai toán tử đơn điệu cực đại và thuật toán phân rã song song giải bài toán tìm không điểm của tổng hữu hạn toán tử đơn điệu cực đại. Chương 2: Phương pháp phân rã Douglas-Rachford giải bài toán cân bằng. Trong chương này, tác giả trình bày mối liên quan mật thiết giữa bao hàm thức đơn điệu và bài toán cân bằng. Đồng thời cũng trình bày về thuật toán và sự hội tụ của phương pháp phân rã Douglas-Rachford. Mặc dù tác giả đã cố gắng hết sức thực hiện luận văn, nhưng với trình độ hạn chế cùng nhiều lý do khác, luận văn chắc chắn không tránh khỏi những thiếu sót. Kính mong sự góp ý của các thầy cô, các bạn và các anh chị đồng nghiệp để luận văn này hoàn chỉnh hơn. 4 Chương 1 Một số vấn đề cơ bản Trong chương này, tác giả trình bày ba mục. Cụ thể đầu tiên nhắc lại một số khái niệm và các kết quả cần thiết về không gian Hilbert thực. Tiếp theo tác giả giới thiệu bài toán cân bằng. Cuối cùng tác giả mô tả thuật toán Douglas-Rachford giải bài toán tìm không điểm của tổng hai toán tử đơn điệu cực đại tương ứng với điều kiện thích hợp. Các kiến thức của chương này được tổng hợp từ các tài liệu [1], [2] và [4]. 1.1 Không gian Hilbert thực Định nghĩa 1.1. Không gian tuyến tính H xác định trên trường số thực R được gọi là không gian tiền Hilbert nếu trong đó xác định một hàm hai biến h·, ·i : H × H → R thỏa mãn các tính chất sau: i) hx, xi ≥ 0, ∀x ∈ H và hx, xi = 0 ⇔ x = 0; ii) hx, yi = hy, xi , ∀x, y ∈ H; iii) hx + y, zi = hx, zi + hy, zi , ∀x, y, z ∈ H; vi) hαx, yi = α hx, yi , ∀x, y ∈ H, ∀α ∈ R. Hàm h·, ·i thỏa mãn bốn tính chất trên gọi là tích vô hướng trên H và hx, yi là tích vô hướng của hai phần tử x và y. 5 Nhận xét 1.1. Mọi không gian tiền Hilbert H là không gian tuyến tính định p chuẩn với chuẩn của x ∈ H xác định bởi kxk = hx, xi. Định nghĩa 1.2. Không gian tiền Hilbert đầy đủ được gọi là không gian Hilbert. Ví dụ 1.1. Trong Cn , với x = (ξ1 , . . . , ξn ), y = (η1 , . . . , ηn ), ta đặt hx, yi = n X ξn ηn , i=1 Khi đó Cn là một không gian Hilbert. Ví dụ 1.2. Trong không gian l2 , ta đưa vào tích vô hướng: hx, yi = ∞ X ξn ηn n=1 (x = (ξ1 , ξ2 , . . .) ∈ l2 , y = (η1 , η2 , . . .) ∈ l2 ). Khi đó kxk = ∞ X ! 21 |ξn |2 . n=1 Không gian l2 đầy đủ với chuẩn đó. Vậy l2 là không gian Hilbert. Định nghĩa 1.3. Tập hợp tất cả các phiếm hàm tuyến tính liên tục trên H gọi là không gian liên hợp (không gian đối ngẫu của H) và ký hiệu là H∗ . Định nghĩa 1.4. Cho không gian Hilbert thực H, một hàm f : H → R. Khi đó i) Một hàm f xác định trên tập H được gọi là nửa liên tục dưới tại điểm x0 ∈ H nếu với mọi ε > 0, tồn tại δ > 0 sao cho f (x) ≥ f (x0 ) − ε, với mọi x thuộc H thỏa mãn kx − x0 k < δ. ii) Hàm f được gọi là nửa liên tục trên trên H tại x0 ∈ H nếu hàm −f 6 nửa liên tục dưới tại x0 ∈ H. iii) Hàm f được gọi là liên tục trên H tại điểm x0 ∈ H nếu hàm f vừa nửa liên tục dưới trên H tại điểm x0 ∈ H và vừa liên tục trên trên H tại điểm x0 ∈ H. vi) Hàm f được gọi là liên tục (nửa liên tục) trên H nếu hàm f liên tục (nửa liên tục) tại mọi điểm trên H. Định nghĩa 1.5. Dãy {xn }∞ n=1 trong không gian Hilbert H được gọi là hội tụ yếu đến phần tử x ∈ H nếu lim hxn , yi = hx, yi với mọi y ∈ H. Dãy n→∞ {xn }∞ n=1 được gọi là hội tụ mạnh nếu lim hxn − xi = 0. n→∞ Ký hiệu xn * x chỉ sự hội tụ yếu, xn → x chỉ sự hội tụ mạnh của dãy xn đến phần tử x ∈ H. Chú ý 1.1. Trong không gian Hilbert H, hội tụ mạnh kéo theo hội tụ yếu, nhưng điều ngược lại là không đúng. Định nghĩa 1.6. Cho H là không gian Hilbert, C là tập con khác rỗng của H được gọi là tập lồi nếu ∀x1 , x2 ∈ C, ∀λ ∈ [0, 1] ta đều có λx1 + (1 − λ)x2 ∈ C. Định nghĩa 1.7. Hàm f : C → R được gọi là hàm lồi trên C nếu với mọi x, y ∈ C và λ ∈ [0, 1] thì f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y). Ví dụ 1.3. Cho S = {x ∈ H : kxk = 1} là một hàm mặt cầu và h : S → R+ là một hàm bất kỳ. Ta định nghĩa hàm f như sau     0 nếu kxk < 1,    h(x) nếu kxk = 1,      +∞ nếu kxk > 1. Hàm f (x) được gọi là hàm mặt cầu và f là hàm lồi trên C. 7 Định nghĩa 1.8. Cho không gian Hilbert thực H, tập C ⊆ H và hàm lồi f : C → R ∪ {+∞}. Khi đó, dưới vi phân của f tại x∗ , ký hiệu là ∂f (x∗ ), được xác định bởi ∂f (x∗ ) = {p ∈ H : f (x) − f (x∗ ) ≥ hp, x − x∗ i , ∀x ∈ C}. Hàm f được gọi là khả dưới vi phân trên C nếu ∂f (x) 6= ∅, ∀x ∈ C. Ví dụ 1.4 (Dưới vi phân của hàm lồi thuần nhất dương). Cho f : Rn → R là hàm lồi thuần nhất dương, tức là hàm lồi f thỏa mãn f (λx) = λf (x), ∀λ > 0, ∀x ∈ Rn . Khi đó, ∂f (x∗ ) = {p ∈ Rn : hp, x∗ i = f (x∗ ), hp, xi ≤ f (x), ∀x ∈ C}. Chứng minh. Nếu p ∈ ∂f (x∗ ) thì hp, x − x∗ i ≤ f (x) − f (x∗ ), ∀x ∈ C (1.1) Thay x = 2x∗ vào (1.1), ta có hp, x∗ i ≤ f (x∗ ). (1.2) Thay x = 0 vào (1.1), ta nhận được − hp, x∗ i ≤ −f (x∗ ). Kết hợp (1.2) và (1.3) ta có hp, x∗ i = f (x∗ ). Hơn nữa hp, x − x∗ i = hp, xi − hp, x∗ i = hp, xi − f (x∗ ) (1.3) 8 Do đó hp, xi ≤ f (x), ∀x ∈ C. Ngược lại, nếu x∗ ∈ Rn thỏa mãn hp, x∗ i = f (x∗ ) và hp, xi ≤ f (x), ∀x ∈ C thì hp, x − x∗ i = hp, xi − hp, x∗ i ≤ f (x) − f (x∗ ), ∀x ∈ C Vậy p ∈ ∂f (x∗ ). Định lí 1.1. Mỗi tập con đóng và bị chặn C của một không gian Hilbert là compact yếu, tức là với mỗi dãy bị chặn trong C có thể trích ra được một dãy con hội tụ yếu tới một phần tử của một không gian này. Tập con C của không gian Hilbert H được gọi là đóng yếu nếu {xn * x} thì x ∈ C. Định lí 1.2 (Định lí Mazur). Mỗi tập con lồi của một không gian Hilbert là đóng yếu. Định nghĩa 1.9. Cho X, Y là hai tập con bất kỳ của H và F : X → 2Y là ánh xạ từ X vào tập hợp toàn bộ các tập con của Y . Khi đó, ta nói F là ánh xạ đa trị từ X vào Y , tức là với mỗi x ∈ X, F (x) là tập con của Y . (F (x) có thể là tập rỗng). Nếu với mọi x ∈ X, tập F (x) chỉ có đúng một phần tử thì ta nói F là ánh xạ đơn trị từ X vào Y . Ví dụ 1.5. Xét phương trình đa thức: xn + a1 xn−1 + · · · + an−1 x + an = 0, trong đó ai ∈ R. Quy tắc cho tương ứng mỗi điểm a = (a1 , a2 , . . . , an ) ∈ Rn với tập nghiệm của phương trình trên, ký hiệu là F (a) cho ta một ánh xạ đa trị F : Rn → C. 9 Định nghĩa 1.10. Cho A : H → 2H là toán tử đa trị. Khi đó dom A = {x ∈ H | Ax 6= ∅} là miền xác định của A, gra A = {(x, u) ∈ H × H | u ∈ Ax} là đồ thị của A. Toán tử A là đơn điệu nếu (∀(x, u) ∈ gra A) (∀(y, v) ∈ gra A) hx − y, u − vi ≥ 0. Ví dụ 1.6. Một ví dụ quan trọng của ánh xạ đa trị đơn điệu là dưới vi phân của hàm lồi. Thật vậy, giả sử h : H → R là hàm lồi chính thường khả dưới vi phân. Khi đó, với mọi x, y ∈ H và u ∈ ∂h(x), v ∈ ∂h(y), theo định nghĩa dưới vi phân ta có h(y) − h(x) ≥ hu, y − xi và h(x) − h(y) ≥ hv, x − yi . Cộng hai vế bất đẳng thức nói trên, ta được hu − v, x − yi ≥ 0. Hay (∀(x, u) ∈ gra A) (∀(y, v) ∈ gra A) hx − y, u − vi ≥ 0. Vậy ∂h : H → 2H đơn điệu trên H. Định nghĩa 1.11. Toán tử đa trị A : H → 2H được gọi là toán tử đơn điệu cực đại nếu A là toán tử đơn điệu và đồ thị của nó không chứa trong đồ thị của toán tử đơn điệu khác trong H. Trong trường hợp này, giải thức của A, JA = (Id + A)−1 được xác định, đơn trị và dom JA = H. Toán tử phản xạ RA = 2 JA − Id là toán tử không giãn. 10 Với toán tử đơn trị T : dom T ⊂ H → H thì tập các điểm bất động được ký hiệu Fix T = {x ∈ H | x = T x}, ta nói T là không giãn nếu (∀x ∈ dom T ) (∀y ∈ dom T ) kT x − T yk ≤ kx − yk , và T là không giãn chặt nếu (∀x ∈ dom T )(∀y ∈ dom T ) kT x − T yk2 ≤ kx − yk2 − k(Id − T )x − (Id − T )yk2 . Định nghĩa 1.12. Cho H là không gian Hilbert và H∗ là không gian liên ∗ hợp của H. Toán tử A : H → 2H được gọi là đơn điệu đều trên H nếu tồn tại một hàm không âm δ(t), không giảm với t ≥ 0 và δ(0) = 0 thỏa mãn hAx − Ay, x − yi ≥ δ(kx − yk), ∀x, y ∈ H. Nếu δ(t) = cA t2 , (t > 0) với cA là một hằng số dương thì toán tử A được gọi là toán tử đơn điệu mạnh. Định nghĩa 1.13. Toán tử A được gọi là toán tử đồng bức với hằng số η > 0 hay η−ngược đơn điệu mạnh trên H nếu hAx − Ay, x − yi ≥ η kAx − Ayk2 1.2 ∀x, y ∈ H. Bài toán cân bằng Trong những năm gần đây, một số công trình đã được đề xuất để nghiên cứu bài toán cân bằng, ký hiệu là EP(H) được phát biểu như sau Tìm x ∈ C sao cho (∀y ∈ C) H(x, y) ≥ 0, trong đó C là tập con lồi đóng, khác rỗng của không gian Hilbert thực H, và H : C × C → R thỏa mãn các điều kiện sau. 11 Điều kiện 1.1. Song hàm H : C × C → R thỏa mãn: (i) (∀x ∈ C) H(x, x) = 0. (ii) (∀(x, y) ∈ C × C) H(x, y) + H(y, x) ≤ 0. (iii) ∀x ∈ C, H(x, ·) : C → R là hàm lồi nửa liên tục dưới. (iv) (∀(x, y, z) ∈ C 3 ) limε→0+ H((1 − ε)x + εz, y) ≤ H(x, y). Tập nghiệm của bài toán cân bằng EP(H) được ký hiệu là SH . Định lí 1.3 (Điểm bất động Kakutani). Cho C là tập lồi compact trong không gian Hilbert H và F : C → 2C là một ánh xạ đa trị nửa liên tục trên và F (x) lồi đóng, khác rỗng với mọi x ∈ C. Khi đó F có điểm bất động, tức là tồn tại x∗ ∈ C, x∗ ∈ F (x∗ ). Một trường hợp riêng của quan trọng của định lí này là Định lí điểm bất động Brouwer sau. Định lí 1.4 (Điểm bất động Brouwer). Cho C là tập lồi compact yếu trong không gian Hilbert thực H và F là một ánh xạ (đơn trị) nửa liên tục từ C vào C. Khi đó tồn tại x∗ ∈ C thỏa mãn x∗ ∈ F (x∗ ). Định lí sau đây là dạng mở rộng của Định lí điểm bất động Kakutani từ trường hợp không gian hữu hạn chiều sang không gian vô hạn chiều. Định lí 1.5 (Định lí điểm bất động Ky Fan). Cho K là tập lồi compact khác rỗng trong không gian Banach X và F : K → 2K là ánh xạ đa trị nửa liên tục trên, có giá trị lồi đóng khác rỗng. Khi đó, F có điểm bất động tức là tồn tại x∗ ∈ K sao cho x∗ ∈ F (x∗ ). 12 Định lí 1.6 (Định lí cực đại của Berge). Cho X, Y là các không gian tôpô, F : X → 2Y là ánh xạ nửa liên tục trên trên X sao cho F (X) compact. Giả sử g : X × Y → R là hàm số nửa liên tục trên trên X. Khi đó hàm giá trị tối ưu h(x) = max {g(x, y) | y ∈ F (x)} nửa liên tục trên và ánh xạ tập nghiệm tối ưu S(x) = {y ∈ F (x) | g(x, y) = h(x)} nửa liên tục trên. Dựa vào Định lí điểm bất động Kakutani và Định lí cực đại của Berge, ta có mệnh đề sau nói về sự tồn tại nghiệm của bài toán cân bằng. Mệnh đề 1.1. Cho C là một tập lồi, compact khác rỗng trong không gian Hilbert thực H và song hàm cân bằng f : C × C → R ∪ {+∞} có các tính chất (i) f (·, y) nửa liên tục trên với mọi y ∈ C; (ii) f (x, ·) lồi, nửa liên tục dưới và khả vi dưới vi phân trên C với mọi x ∈ C. Khi đó bài toán cân bằng EP(H) có nghiệm. Chứng minh. Với mỗi x ∈ C, ta gọi S(x) là tập nghiệm của bài toán min{f (x, y) | y ∈ C}. (1.4) Do C compact và f (x, ·) nửa liên tục dưới, nên theo Định lí Weistrass, bài toán này tồn tại nghiệm. Hơn nữa, do C lồi, compact f (x, ·) lồi nên S(x) lồi, compact. Theo Định lí cực đại của Berge, ánh xạ f nửa liên tục trên. Và 13 S là ánh xạ từ C vào C. Vậy theo Định lí điểm bất động Kakutani, tồn tại x∗ ∈ C thỏa mãn x∗ ∈ S(x∗ ). Bây giờ ta chỉ ra x∗ là nghiệm của bài toán cân bằng EP(H). Thật vậy, do f (x, ·) lồi, khả dưới vi phân, theo điều kiện cần và đủ của tối ưu quy hoạch lồi, ta có 0 ∈ ∂2 f (x∗ , x∗ ) + NC (x∗ ). Theo định nghĩa của dưới vi phân và nón pháp tuyến, từ đây ta có v ∗ ∈ ∂2 f (x∗ , x∗ ) + NC (x∗ ) thỏa mãn hv ∗ , y − x∗ i ≥ 0, ∀y ∈ C. Do v ∗ ∈ ∂2 f (x∗ , x∗ ), nên hv ∗ , y − x∗ i ≤ f (x∗ , y) − f (x∗ , x∗ ) = f (x∗ , y), ∀y ∈ C. Vậy f (x∗ , y) ≥ 0, ∀y ∈ C. Điều này chứng tỏ x∗ là nghiệm của bài toán cân bằng EP(H). Bổ đề 1.1. Cho T : dom T = H → H là một toán tử không giãn sao cho Fix T 6= ∅. Cho (µn )n∈N là một dãy nằm trong (0, 1) và (cn )n∈N là một dãy P P thuộc H sao cho µn (1 − µn ) = +∞ và µn kcn k < +∞. Cho x0 ∈ H n∈N n∈N và xét (∀n ∈ N) xn+1 = xn + µn (T xn + cn − xn ). Khi đó (xn )n∈N hội tụ yếu đến x ∈ Fix T và (xn − T xn )n∈N hội tụ mạnh đến 0. Bây giờ cho F : C × C → R là một song hàm thỏa mãn các Điều kiện 1.1. Giải thức của F là toán tử JF : H → 2C : x 7→ {z ∈ C | (∀y ∈ C)F (z, y) + hz − x, y − zi ≥ 0}, 14 là đơn trị và không giãn chặt [3, Bổ đề 2.12], và toán tử phản xạ RF : H → H : x 7→ 2JF x − x là không giãn. Cho C ⊂ H là tập lồi đóng khác rỗng. Ta nói rằng 0 là điểm trong tương đối chặt của C, được viết như sau 0 ∈ sri C nếu ∪λ>0 λC = span C. Nón pháp tuyến của C là toán tử đơn điệu cực đại.     {u ∈ H | (∀y ∈ C),    NC : H → 2H : x 7→ hy − x, ui ≤ 0}, nếu x ∈ C,      ∅, nếu x ∈ / C. Ta ký hiệu Γ0 (H) là họ tất cả các hàm lồi f nửa liên tục dưới từ H đến (−∞, +∞] và là chính thường với nghĩa dom f = {x ∈ H | f (x) < +∞} là khác rỗng. Dưới vi phân của hàm f ∈ Γ0 (H) là toán tử đơn điệu cực đại ∂f : H → 2H : x 7→ {u ∈ H | (∀y ∈ H) hy − x, ui + f (x) ≤ f (y)}. Bài toán cân bằng khá đơn giản về mặt hình thức nhưng nó bao hàm được nhiều lớp bài toán quan trọng. Các nhà nghiên cứu đã tìm ra nhiều bài toán thực tế như tối ưu, kinh tế và kỹ thuật có thể mô tả được dưới dạng bài toán cân bằng. Điều đó giải thích vì sao bài toán cân bằng ngày càng được nhiều người quan tâm. Sau đây là một số ví dụ điển hình, những bài toán quen thuộc có thể mô tả được dưới dạng bài toán cân bằng. Bài toán 1.1 (Bài toán tối ưu). Cho C là tập lồi đóng, khác rỗng trong không gian Hilbert thực H và g : C → R là một hàm số xác định trên C. Khi đó, bài toán tối ưu được phát biểu như sau Tìm x∗ ∈ C sao cho g(x∗ ) ≤ g(y), y ∈ C. 15 Nếu ta đặt f (x, y) = g(y) − g(x) với mọi x, y ∈ C thì bài toán tối ưu có thể quy về bài toán cân bằng EP(H). Thật vậy, ta giả sử x∗ ∈ C là nghiệm của bài toán (1.4) nên ta có g(x∗ ) ≤ g(y), ∀y ∈ C. Vì f (x, y) = g(y) − g(x), ∀x, y ∈ C. Nên f (x∗ , y) = g(y) − g(x∗ ) ≥ 0, ∀y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán cân bằng EP(H). Ngược lại, nếu x∗ ∈ C là nghiệm của bài toán cân bằng EP(H) thì ta có f (x∗ , y) ≥ 0, ∀y ∈ C. Theo cách đặt ta có f (x∗ , y) = g(y) − g(x∗ ) ≥ 0, ∀y ∈ C. ⇒ g(y) ≥ g(x∗ ), ∀y ∈ C. Vậy x∗ là nghiệm của bài toán cân bằng (1.4). Bài toán 1.2 (Bài toán bất đẳng thức biến phân). Cho C là tập lồi đóng, khác rỗng trong không gian Hilbert thực H và F : C → 2H là một ánh xạ đa trị. Tức là với mỗi x ∈ C thì giá trị F (x) là một tập khác rỗng trong H. Ta xét bài toán bất đẳng thức biến phân   Tìm x∗ ∈ C, δ ∗ ∈ F (x∗ ) sao cho  hδ ∗ , y − x∗ i ≥ 0, ∀y ∈ C. Nếu ta đặt f (x, y) = max hδ, y − xi , ∀x, y ∈ C thì bài toán bất đẳng δ∈F (x) thức biến phân trên có thể quy về bài toán cân bằng EP(H).