Tài liệu Thuật toán lai ghép giải bài toán chấp nhận tách nhiều tập

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐINH THỊ TRANG THUẬT TOÁN LAI GHÉP GIẢI BÀI TOÁN CHẤP NHẬN TÁCH NHIỀU TẬP LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. Nguyễn Bường Thái Nguyên – 2021 ii Lời cảm ơn Luận văn này được hoàn thành dưới sự hướng dẫn của GS.TS. Nguyễn Bường (Viện Công nghệ Thông tin-Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp cao học Toán, nhà trường và các phòng chức năng của trường, 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. Xin chân thành cảm ơn anh chị em trong lớp cao học và bạn bè đồng nghiệp đã 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. iii Mục lục Lời cảm ơn ii Một số ký hiệu và viết tắt iv Mở đầu 1 Chương 1 Một số kiến thức chuẩn bị 2 1.1. Một số đặc trưng của không gian Hilbert . . . . . . . . . . . . . . 2 1.2. Bài toán tìm điểm bất động của ánh xạ không giãn . . . . . . . . 9 1.3. Bất đẳng thức biến phân trong không gian Hilbert . . . . . . . . . 12 1.3.1. Một số vấn đề sơ lược về bất đẳng thức biến phân . . . . . 12 1.3.2. Bất đẳng thức biến phân trên tập điểm bất động của ánh xạ không giãn . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4. Một số bổ đề bổ trợ . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Chương 2 Một số thuật toán lai ghép giải bài toán chấp nhận tách nhiều tập 22 2.1. Phát biểu bài toán và một số cải tiến của phương pháp CQ . . . . 22 2.2. Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 26 Kết luận Tài liệu tham khảo 34 35 iv Một số ký hiệu và viết tắt H không gian Hilbert X không gian Banach h., .i tích vô hướng trên H k.k chuẩn trên H ∪ phép hợp ∩ phép giao R+ tập các số thực không âm I toán tử đồng nhất ∅ tập rỗng ∀x với mọi x ∃x tồn tại x xn → x0 dãy {xn } hội tụ mạnh về x0 xn * x0 dãy {xn } hội tụ yếu về x0 F ix(T ) tập điểm bất động của ánh xạ T 1 Mở đầu “Bất đẳng thức biến phân” được nảy sinh trong quá trình nghiên cứu và giải các bài toán thực tế như bài toán cân bằng trong kinh tế, tài chính, bài toán mạng giao thông, lý thuyết trò chơi, phương trình vật lý toán ... Bài toán này được giới thiệu lần đầu tiên bởi Hartman và Stampacchia vào năm 1966 trong tài liệu [5]. Bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều, cũng như vô hạn chiều cùng với các ứng dụng của nó được giới thiệu khá chi tiết trong cuốn sách “An Introduction to Variational Inequalities and Their Applications” của D. Kinderlehrer và G. Stampacchia xuất bản năm 1980 [7]. Bất đẳng thức biến phan trên tập nghiệm của một bài toán khác thường được gọi là bất đẳng thức biến phân hai cấp. Gần đây đã có nhiều người làm toán trong và ngoài nước quan tâm đến bất đẳng thức biến phân trên tập nghiệm của bài toán chấp nhận tách (đa tập), do lớp bài toán này có thể áp dụng để giải một số lớp bài toán khác, đặc biệt là các bài toán liên quan đến xử lý tín hiệu, xử lý hình ảnh trong Y học. Mục đích của luận văn là trình bày lại các kết quả của Wang và các cộng sự trong tài liệu [14] về một phương pháp lặp xoay vòng tìm nghiệm của bất đẳng thức biến phân trên tập nghiệm của bài toán chấp nhận tách đa tập trong không gian Hilbert. Nội dung chính của luận văn được cấu trúc thành hai chương, trong đó: Chương 1 trình bày một số kiến thức chuẩn bị về không gian Hilbert, ánh xạ không giãn và bất đẳng thức biến phân. Chương 2 trình bày lại chi tiết các kết quả của Wang và các cộng sự về phương pháp lặp kiểu đường dốc nhất kết hợp với phương pháp CQ xấp xỉ nghiệm của bất đẳng thức biến phân trên tập nghiệm của bài toán chấp nhận tách đa tập trong không gian Hilbert. 2 Chương 1 Một số kiến thức chuẩn bị Chương này bao gồm năm mục chính. Mục 1.1 đề cập đến một số đặc trưng cơ bản của không gian Hilbert thực. Mục 1.2 giới thiệu sơ lược một số kết quả về bài toán tìm điển bất động của ánh xạ không giãn. Mục 1.4 và 1.4 đề cập đến bài toán bất đẳng thức biến phân cổ điển và bài toán bất đẳng thức biến phân trong không gian Hilbert. Mục 1.5 giới thiệu một số bổ đề bổ trợ cần sử dụng trong Chương 2 của luận văn. Nội dung của chương này phần lớn được tham khảo từ các tài liệu [1], [2] và [7]. 1.1. Một số đặc trưng của không gian Hilbert Ta luôn giả thiết H là không gian Hilbert thực với tích vô hướng được kí hiệu là h., .i và chuẩn được kí hiệu là k.k. Mệnh đề 1.1. Trong không gian Hilbert thực H ta luôn có đẳng thức sau kx − yk2 + kx − zk2 = ky − zk2 + 2hx − y, x − zi, với mọi x, y, z ∈ H . Chứng minh. Thật vậy, ta có ky − zk2 + 2hx − y, x − zi = hy, yi + hz, zi + 2hx, xi − 2hx, zi − 2hx, yi = [hx, xi − 2hx, yi + hy, yi] + [hx, xi − 2hx, zi + hz, zi] = kx − yk2 + kx − zk2 . Vậy ta được điều phải chứng minh. 3 Mệnh đề 1.2. Cho H là một không gian Hilbert thực. Khi đó, với mọi x, y ∈ H và mọi λ ∈ [0, 1], ta có kλx + (1 − λ)yk2 = λkxk2 + (1 − λ)kyk2 − λ(1 − λ)kx − yk2 . (1.1) Chứng minh. Ta có kλx + (1 − λ)yk2 = λ2 kxk2 + 2λ(1 − λ)hx, yi + (1 − λ)2 kyk2 = λkxk2 + (1 − λ)kyk2 − λ(1 − λ)(kxk2 − 2hx, yi + kyk2 ) = λkxk2 + (1 − λ)kyk2 − λ(1 − λ)kx − yk2 . Ta được điều phải chứng minh. Mệnh đề 1.3. Trong không gian Hilbert thực H , ta luôn có kx + yk2 ≤ kxk2 + 2hy, x + yi với mọi x, y ∈ H . Chứng minh. Với mọi x, y ∈ H , ta có kx + yk2 = kxk2 + 2hx, yi + kyk2 ≤ kxk2 + 2hx, yi + 2kyk2 = kxk2 + 2hy, x + yi. Mệnh đề được chứng minh. Nhắc lại rằng, dãy {xn } trong không gian Hilbert H được gọi là hội tụ yếu về phần tử x ∈ H , nếu lim hxn , yi = hx, yi, n→∞ với mọi y ∈ H . Từ tính liên tục của tích vô hướng, suy ra nếu xn → x, thì xn * x. Tuy nhiên, điều ngược lại không đúng. Chẳng hạn xét không gian  l2 = {xn } ⊂ R : P∞ 2 2 n=1 |xn | < ∞ và {en } ⊂ l , được cho bởi en = (0, ..., 0, 1 , 0, ..., 0, ...), vị trí thứ n 4 với mọi n ≥ 1. Khi đó, en * 0, khi n → ∞. Thật vậy, với mỗi y ∈ H , từ bất đẳng thức Bessel, ta có ∞ X |hen , yi|2 < kyk2 < ∞. n=1 Suy ra limn→∞ hen , yi = 0, tức là en * 0. Tuy nhiên, {en } không hội tụ về 0, vì ken k = 1 với mọi n ≥ 1. Ta biết rằng mọi không gian Hilbert H đều thỏa mãn điều kiện của Opial, tính chất này được thể hiện trong mệnh đề dưới đây: Mệnh đề 1.4. Cho H là một không gian Hilbert thực và {xn } ⊂ H là một dãy bất kỳ thỏa mãn điều kiện xn * x, khi n → ∞. Khi đó, với mọi y ∈ H và y 6= x, ta có lim inf kxn − xk < lim inf kxn − yk. n→∞ n→∞ (1.2) Chứng minh. Vì xn * x, nên {xn } bị chặn. Ta có kxn − yk2 = kxn − xk2 + kx − yk2 + 2hxn − x, x − yi > kxn − xk2 + 2hxn − x, x − yi. Vì x 6= y , nên lim inf kxn − yk2 > lim inf kxn − xk2 + 2hxn − x, x − yi n→∞ n→∞ = lim inf kxn − xk2 . n→∞ Do đó, ta nhận được lim inf kxn − xk < lim inf kxn − yk. n→∞ n→∞ Mệnh đề được chứng minh. Mệnh đề 1.5. Mọi không gian Hilbert thực H đều có tính chất Kadec-Klee, tức là nếu {xn } ⊂ H là một dãy bất kỳ trong H thỏa mãn các điều kiện xn * x và kxn k → kxk, thì xn → x, khi n → ∞. Chứng minh. Ta có kxn − xk2 = kxn k2 − 2hxn , xi + kxk2 5 → 0, n → ∞. Suy ra xn → x, khi n → ∞. Mệnh đề được chứng minh. Mệnh đề 1.6. Cho C là một tập con lồi và đóng của không gian Hilbert thực H . Khi đó, tồn tại duy nhất phần tử x∗ ∈ C sao cho kx∗ k ≤ kxk với mọi x ∈ C. Chứng minh. Thật vậy, đặt d = inf kxk. Khi đó, tồn tại {xn } ⊂ C sao cho x∈C kxn k −→ d, n −→ ∞. Từ đẳng thức hình bình hành, ta có kxn − xm k2 = 2(kxn k2 + kxm k2 ) − 4k xn + xm k 2 ≤ (kxn k2 + kxm k2 ) − 4d2 −→ 0, khi n, m −→ ∞. Do đó {xn } là dãy Cauchy trong H . Suy ra tồn tại x∗ = lim xn ∈ C (do {xn } ⊂ C và C là tập đóng). Do chuẩn là hàm số liên tục nên n→∞ kx∗ k = d. Tiếp theo ta chỉ ra tính duy nhất. Giả sử tồn tại y ∗ ∈ C sao cho ky ∗ k = d. Ta có kx∗ − y ∗ k2 = 2(kx∗ k2 + ky ∗ k2 ) − 4k x∗ + y ∗ 2 k 2 ≤ 2(d2 + d2 ) − 4d2 = 0. Suy ra x∗ = y ∗ . Vậy tồn tại duy nhất một phần tử x∗ ∈ C sao cho kx∗ k = inf x∈C kxk. Từ Mệnh đề 1.6, ta có mệnh đề dưới đây: Mệnh đề 1.7. Cho C là một tập con lồi và đóng của không gian Hilbert thực H . Khi đó, với mỗi x ∈ H , tồn tại duy nhất phần tử PC x ∈ C sao cho kx − PC (x)k ≤ kx − yk với mọi y ∈ C. Chứng minh. Vì C là tập lồi, đóng và khác rỗng nên x − C cũng là tập lồi, đóng và khác rỗng. Do đó, theo Mệnh đề 1.6, tồn tại duy nhất một phần tử PC ∈ C sao cho kx − PC (x)k ≤ kx − yk với mọi y ∈ C. 6 Định nghĩa 1.1. Phép cho tương ứng mỗi phần tử x ∈ H một phần tử PC x ∈ C xác định như trên được gọi là phép chiếu mêtric từ H lên C . Ví dụ 1.1. Cho C = {x ∈ H : hx, ui = y}, với u 6= 0. Khi đó PC x = x + y − hx, ui kuk2 u. Ví dụ 1.2. Cho C = {x ∈ H : kx − ak ≤ R}, trong đó a ∈ H là một phần tử cho trước và R là một số dương. Khi đó, ta có:   x nếu kx − ak ≤ R, PC x =  a + R (x − a) nếu kx − ak > R. kx − ak Mệnh đề dưới đây cho ta một điều kiện cần và đủ để ánh xạ PC : H −→ C là một phép chiếu mêtric. Mệnh đề 1.8. Cho C là tập con lồi, đóng và khác rỗng của không gian Hilbert H . Cho PC : H −→ C là một ánh xạ. Khi đó, các phát biểu sau là tương đương: a) PC là phép chiếu mêtric từ H lên C ; b) hy − PC x, x − PC xi ≤ 0 với mọi x ∈ H và y ∈ C ; Chứng minh. Thật vậy, giả sử PC là phép chiếu mêtric từ H lên C , tức là kx − PC xk = inf u∈C kx − uk. Với mọi x ∈ H , y ∈ C và với mọi α ∈ (0, 1), đặt yα = αy + (1 − α)PC x. Vì C lồi nên yα ∈ C và do đó kx − PC xk ≤ kyα − xk. Điều này tương đương với kx − PC xk2 ≤ kα(y − PC x) − (x − PC x)k2 = α2 ky − PC xk2 + kx − PC xk2 − 2αhy − PC x, x − PC xi. Từ đó, ta nhận được 2hy − PC x, x − PC xi ≤ αky − PC xk2 . 7 Cho α −→ 0+ , ta được hy − PC x, x − PC xi ≤ 0. Ngược lại, giả sử b) đúng. Với mọi x ∈ H và mọi y ∈ C , ta có kx − PC xk2 = kx − y + y − PC xk2 = kx − yk2 + 2hx − y, y − PC xi + ky − PC xk2 = kx − yk2 + 2hx − PC x, y − PC xi − ky − PC xk2 ≤ kx − yk2 . Do đó, kx − PC xk = inf u∈C kx − uk, hay PC là phép chiếu mêtric từ H lên C . Từ mệnh đề trên, ta có hệ quả dưới đây: Hệ quả 1.1. Cho C là một tập con lồi đóng của không gian Hilbert H và PC là phép chiếu mêtric từ H lên C . Khi đó, ta có các khẳng định sau: a) với mọi x, y ∈ H , ta có kPC x − PC yk2 ≤ hx − y, PC x − PC yi; b) với mọi x ∈ H và y ∈ C , ta có kx − yk2 ≥ kx − PC xk2 + ky − PC xk2 . Chứng minh. a) Với mọi x, y ∈ H , từ Mệnh đề 1.8, ta có hx − PC x, PC y − PC xi ≤ 0, hy − PC y, PC x − PC yi ≤ 0. Cộng hai bất đẳng thức trên ta nhận được điều phải chứng minh. b) Với mọi x ∈ H và y ∈ C , từ Mệnh đề 1.8, ta có hx − PC x, y − PC xi ≤ 0. Từ đó, ta có kx − yk2 = k(x − PC x) − (y − PC x)k2 = kx − PC xk2 + ky − PC xk2 − 2hx − PC x, y − PC xi ≥ kx − PC xk2 + ky − PC xk2 . Hệ quả được chứng minh. 8 Mệnh đề 1.9. Nếu C là một tập con lồi và đóng của không gian Hilbert H , thì C là tập đóng yếu. Chứng minh. Trước hết, ta chỉ ra tồn tại một phần tử v ∈ H , v 6= 0 sao cho suphv, yi ≤ hv, xi − kvk2 . y∈C Vì x ∈ / C , nên v = x − PC x 6= 0. Từ Mệnh đề 1.8, ta có hv, y − PC xi ≤ 0, với mọi y ∈ C . Suy ra hv, y − x + x − PC xi ≤ 0, với mọi y ∈ C . Điều này tương đương với hv, yi ≤ hv, xi − kvk2 , với mọi y ∈ C . Do đó suphv, yi ≤ hv, xi − kvk2 . y∈C Bây giờ ta chỉ ra C là tập đóng yếu. Giả sử ngược lại rằng C không là tập đóng yếu. Khi đó, tồn tại dãy {xn } trong C thỏa mãn xn * x, nhưng x ∈ / C . Vì C là tập lồi và đóng, nên theo chứng minh trên, ta có hv, zi < hv, xi − ε, với ε = kvk2 /2 và mọi z ∈ C . Đặc biệt hv, xn i < hv, xi − ε, với mọi n. Cho n → ∞, ta nhận được hv, xi ≤ hv, xi − ε, điều này là vô lý. Do đó, C là tập đóng yếu. Chú ý 1.1. Nếu C là tập đóng yếu trong H thì hiển nhiên C là tập đóng. Từ định lý Banach-Alaoglu, ta có mệnh đề dưới đây: Mệnh đề 1.10. Mọi tập con bị chặn của H đều là tập compact tương đối yếu. 9 1.2. Bài toán tìm điểm bất động của ánh xạ không giãn Định nghĩa 1.2. Cho C là một tập con lồi, đóng và khác rỗng của không gian Hilbert thực H . Ánh xạ T : C −→ H được gọi là một ánh xạ không giãn, nếu với mọi x, y ∈ C , ta có kT x − T yk ≤ kx − yk. Ta ký hiệu tập điểm bất động của ánh xạ không giãn T là F ix(T ), tức là F ix(T ) = {x ∈ C : T x = x}. Mệnh đề dưới đây cho ta mô tả về tính chất của tập điểm bất động F ix(T ). Mệnh đề 1.11. Cho C là một tập con lồi, đóng và khác rỗng của không gian Hilbert thực H và T : C −→ H là một ánh xạ không giãn. Khi đó, F ix(T ) là một tập lồi và đóng trong H . Chứng minh. Giả sử F ix(T ) 6= ∅. Trước hết, ta chỉ ra F ix(T ) là tập đóng. Thật vậy, vì T là ánh xạ không giãn nên T liên tục trên C . Giả sử {xn } là một dãy bất kỳ trong F ix(T ) thỏa mãn xn → x, khi n → ∞. Vì {xn } ⊂ F ix(T ), nên kT xn − xn k = 0, với mọi n ≥ 1. Từ tính liên tục của chuẩn, cho n → ∞, ta nhận được kT x−xk = 0, tức là x ∈ F ix(T ). Do đó, F ix(T ) là tập đóng. Tiếp theo, ta chỉ ra tính lồi của F ix(T ). Giả sử x, y ∈ F ix(T ), tức là T x = x và T y = y . Với λ ∈ [0, 1], đặt z = λx + (1 − λ)y . Khi đó, từ Mệnh đề 1.2 và tính không giãn của T ta có kT z − zk2 = kλ(T z − x) + (1 − λ)(T z − y)k2 = λkT z − xk2 + k(1 − λ)(T z − y)k2 − λ(1 − λ)kx − yk2 = λkT z − T xk2 + (1 − λ)k(T z − T y)k2 − λ(1 − λ)kx − yk2 ≤ λkz − xk2 + (1 − λ)k(z − y)k2 − λ(1 − λ)kx − yk2 = kλ(z − x) + (1 − λ)(z − y)k2 = 0. Suy ra T z = z và do đó z ∈ F ix(T ). Vậy F ix(T ) là một tập lồi. 10 Mệnh đề 1.12 (Nguyên lý nửa đóng). Cho C là tập con lồi, đóng và 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 đó, nếu T có điểm bất động thì T là nửa đóng, tức là với mọi dãy {xn } ⊂ C thỏa mãn xn * x ∈ C và xn − T xn → y , thì x − T x = y . Đặc biệt, nếu y = 0 thì x ∈ F ix(T ). Chứng minh. Giả sử x − T x 6= y . Vì xn * x, nên xn − y * x − y . Do x − y 6= T x, nên từ Mệnh đề 1.4, ta có lim inf kxn − xk < lim inf kxn − y − T xk n→∞ n→∞ ≤ lim inf (kxn − T xn − yk + kT xn − T xk) n→∞ ≤ lim inf kxn − xk. n→∞ Suy ra mâu thuẫn. Do đó, x − T x = y . Đặc biệt, nếu y = 0 thì x = T x hay x ∈ F ix(T ). Bài toán. Cho T : C −→ C là một ánh xạ không giãn từ tập con lồi, đóng và khác rỗng C của không gian Hilbert H vào chính nó là một ánh xạ không giãn với F (T ) 6= ∅. Tìm phần tử x∗ ∈ F (T ). Đã có nhiều phương pháp nổi tiếng được đề xuất để giải bài toán trên, như phương pháp lặp Mann, phương pháp lặp Ishikawa, phương pháp lặp Halpern, phương pháp xấp xỉ mềm, phương pháp sử dụng siêu phẳng cắt ... Chú ý 1.2. Nếu T là ánh xạ co trên C , thì dãy lặp Picard xác định bởi x0 ∈ C và xn+1 = T (xn ) hội tụ mạnh về điểm bất động duy nhất của T . Tuy nhiên điều này không còn đúng đối với lớp ánh xạ không giãn. Phương pháp lặp Mann Năm 1953, W. R. Mann [8] đã nghiên cứu và đề xuất phương pháp lặp sau:   x ∈ C là một phần tử bất kì, 0 (1.3)  xn+1 = αn xn + (1 − αn )T xn , n ≥ 0, ở đây {αn } là một dãy số thực thỏa mãn α0 = 1, 0 < αn < 1, n ≥ 1, P∞ n=0 αn = ∞. Dãy lặp (1.3) được gọi là dãy lặp Mann. Mann W. R. đã chứng minh rằng, nếu P dãy {αn } được chọn thỏa mãn ∞ n=1 αn (1 − αn ) = ∞, thì dãy {xn } xác định bởi 11 (1.3) sẽ hội tụ yếu tới một điểm bất động của ánh xạ T . Chú ý rằng nếu H là không gian Hilbert vô hạn chiều thì dãy lặp (1.3) chỉ cho sự hội tụ yếu. Phương pháp lặp Halpern Năm 1967, B. Halpern [4] đã đề xuất phương pháp lặp   x ∈ C là một phần tử bất kì, 0  xn+1 = αn u + (1 − αn )T xn , (1.4) n≥0 ở đây u ∈ C và {αn } ⊂ (0, 1). Dãy lặp (1.4) được gọi là dãy lặp Halpern. Ông đã chứng minh sự hội tụ mạnh của dãy lặp (1.4) về điểm bất động của ánh xạ không giãn T với điều kiện αn = n−α , α ∈ (0, 1). Phương pháp lặp xấp xỉ mềm Năm 2000, Moudafi [9] đã đề xuất phương pháp xấp xỉ mềm, để tìm điểm bất động của ánh xạ không giãn trong không gian Hilbert và đã chứng minh được các kết quả sau: (1) Dãy {xn } ⊂ C xác định bởi: x0 ∈ C, xn = 1 εn T xn + f (xn ), ∀n ≥ 0, 1 + εn 1 + εn (1.5) hội tụ mạnh về nghiệm duy nhất của bất đẳng thức biến phân: x ∈ F (T ) sao cho h(I − f )(x), x − xi ≤ 0, ∀x ∈ F (T ), trong đó {εn } là một dãy số dương hội tụ về 0. (2) Với mỗi phần tử ban đầu z0 ∈ C , xác định dãy {zn } ⊂ C bởi: zn+1 = 1 εn T zn + f (zn ), ∀n ≥ 0. 1 + εn 1 + εn (1.6)    1  1  Nếu limn→∞ εn = 0, −  = 0, thì {zn } hội tụ n=1 εn = ∞ và limn→∞  ε εn n+1 mạnh về nghiệm duy nhất của bất đẳng thức biến phân: P∞ x ∈ F (T ) sao cho h(I − f )(x), x − xi ≤ 0, ∀x ∈ F (T ), ở đây, f : C → C là một ánh xạ co cho trước với hệ số co c ∈ [0, 1). Tức là kf (x) − f (y)k ≤ ckx − yk ∀x, y ∈ C. Chú ý 1.3. Khi f (x) = u với mọi x ∈ C , thì phương pháp xấp xỉ mềm của Moudafi trở về phương pháp lặp của Halpern. 12 1.3. Bất đẳng thức biến phân trong không gian Hilbert 1.3.1. Một số vấn đề sơ lược về bất đẳng thức biến phân Trong mục trên chúng ta vừa trình bày sự tồn tại nghiệm của bất đẳng thức biến phân cổ điển trong không gian Rn . Các kết quả trên đã được nghiên cứu và mở rộng trong không gian Hilbert. Dưới đây, chúng tôi sẽ trình bày một số phương pháp tìm nghiệm cho bài toán bất đảng thức biến phân trong không gian Hilbert. Cho C là một tập con lồi và đóng của không gian Hilbert H và A : C −→ H là một ánh xạ liên tục. Bài toán bất đẳng thức biến phân được phát biểu như sau: Tìm x∗ ∈ C sao cho hAx∗ , x − x∗ i ≥ 0 với mọi x ∈ C. (1.7) Tập hợp những điểm x∗ ∈ C thỏa mãn (1.7) được gọi là tập nghiệm của bài toán và ký hiệu là V I(A, C). Trước hết chúng ta nhắc lại một số khái niệm sau. Cho H là một không gian Hilbert thực, C là một tập lồi đóng khác rỗng của H và A : C −→ H là một ánh xạ từ C vào H . a) Ánh xạ A được gọi là đơn điệu trên C nếu, với mọi x, y ∈ C ta có: hAx − Ay, x − yi ≥ 0. b) Ánh xạ A được gọi là giả đơn điệu trên C nếu, với mọi x, y ∈ C ta có: hAy, x − yi ≥ 0 suy ra hAx, x − yi ≥ 0. c) Ánh xạ A được gọi là α−đơn điệu mạnh trên C , nếu tồn tại một hằng số α > 0 sao cho với mọi x, y ∈ C ta có: hAx − Ay, x − yi ≥ αkx − yk2 . d) Ánh xạ A được gọi là α-ngược đơn điệu mạnh trên C , nếu tồn tại một hằng số α > 0 sao cho với mọi x, y ∈ C ta có: hAx − Ay, x − yi ≥ αkAx − Ayk2 . 13 e) Ánh xạ A được gọi là h-liên tục trên C nếu A(x + ty) * A(x) khi t −→ 0+ sao cho với mọi x, y ∈ C . f) Ánh xạ A được gọi là L-liên tục Lipschitz trên C , nếu tồn tại một hằng số L > 0 sao cho với mọi x, y ∈ C ta có: kAx − Ayk ≥ Lkx − yk. Nhận xét 1.1. Dễ dàng thấy rằng, nếu ánh xạ A là α-ngược đơn điệu mạnh thì ánh xạ A là một ánh xạ đơn điệu và liên tục Lipschitz với hằng số Lipschitz L= 1 . α Mệnh đề dưới đây cho ta biết về một trường hợp tồn tại nghiệm của bài toán bất đẳng thức biến phân. Mệnh đề 1.13. Cho C là một tập con lồi, đóng, khác rỗng và bị chặn của không gian Hilbert H và cho A : C −→ H là một toán tử đơn điệu, h-liên tục. Khi đó, V I(C, A) 6= ∅. Mệnh đề 1.14. Cho C là một tập con lồi, đóng và khác rỗng của không gian Hilbert H và cho A : C −→ H là một toán tử đơn điệu, h-liên tục. Khi đó, x∗ ∈ V I(C, A) khi và chỉ khi x∗ ∈ C và hAy, y − x∗ i ≥ 0, ∀y ∈ C. Chứng minh. Giả sử x∗ ∈ V I(C, A), tức là hAx∗ , y − x∗ i ≥ 0 với mọi y ∈ C . Khi đó, từ tính đơn điệu của A, ta có hAy, y − x∗ i = hAy − Ax∗ , y − x∗ i + hAx∗ , y − x∗ i ≥ 0 với mọi y ∈ C . Ngược lại, giả sử x∗ ∈ C thỏa mãn hAy, y − x∗ i ≥ 0, ∀y ∈ C. Vì C là tập lồi, nên yt = ty + (1 − t)x∗ ∈ C với mọi y ∈ C và mọi t ∈ (0, 1). Do đó, từ bất đẳng thức trên, ta có hAyt , t(y − x∗ )i ≥ 0, ∀t ∈ (0, 1). 14 tương đương với hAyt , y − x∗ i ≥ 0, ∀t ∈ (0, 1). Từ tính h-liên tục của A, cho t → 0+ , ta nhận được hAx∗ , y − x∗ i ≥, ∀y ∈ C. Mệnh đề được chứng minh. Mệnh đề 1.15. Cho C là một tập con lồi, đóng và khác rỗng của không gian Hilbert H và cho A : C −→ H là một toán tử đơn điệu, h-liên tục. Khi đó, x∗ ∈ V I(C, A) khi và chỉ khi x∗ = PC (x∗ − λAx∗ ) với mọi λ > 0. Chứng minh. Suy ra trực tiếp từ Mệnh đề 1.8. 1.3.2. Bất đẳng thức biến phân trên tập điểm bất động của ánh xạ không giãn Một lớp bất đẳng thức biến phân hai cấp quan trọng và có nhiều ứng dụng trong các lĩnh vực khác nhau của toán học, vật lý, y học hay kinh tế ... là bài toán bất đẳng thức biến phân trên tập điểm bất động của ánh xạ không giãn. Bài toán 1.1. Cho A : H −→ H là một toán tử đơn điệu, liên tục và cho T : H −→ H là một ánh xạ không giãn. Tìm phần tử x∗ ∈ V I(F ix(T ), A), tức là x∗ thỏa mãn hAx∗ , v − x∗ i ≥ 0, ∀v ∈ F ix(T ). Năm 2001, Yamada [10] đã đề xuất phương pháp đường dốc nhất để giải Bài toán 1.1 cho trường hợp A là toán tử Lipschitz và đơn điệu mạnh. Kết quả của Yamada được cho bởi định lý dưới đây: Định lý 1.1. [10] Cho T : H −→ H là một ánh xạ không giãn với F ix(T ) 6= ∅. Giả sử ánh xạ A : H −→ H là L-Lipchitz và η -đơn điệu mạnh trên T (H). Khi đó với u0 ∈ H , µ ∈ (0, 2η ) và dãy {λn } ⊂ (0, 1] thỏa mãn các điều kiện: L2 (L1) limn→∞ λn = 0, (L2) Σ∞ n=1 λn = ∞, 15 (L3) limn→∞ λn − λn+1 = 0, λ2n+1 thì dãy {un } xác định bởi un+1 := T (λn+1 ) un := T un − λn+1 µA(T un ) (1.8) hội tụ mạnh về nghiệm duy nhất u∗ của VIP(F ix(T ), A). Hơn nữa, Yamada cũng đã mở rộng kết quả trên cho trường hợp tập điểm bất động F ix(T ) của ánh xạ không giãn T được thay bằng tập điểm bất động chung của một họ hữu hạn ánh xạ không giãn. Kết quả này được thể hiện trong định lý dưới đây: Định lý 1.2. [10] Cho Ti : H −→ H (i = 1, ..., N ) là các ánh xạ không giãn với F := ∩N i=1 F ix(Ti ) 6= ∅ và F = F ix(TN ...T1 ) = F ix(T1 TN ...T3 T2 ) = ... = F ix(TN −1 TN −2 ...T1 TN ). (1.9) Giả sử rằng một ánh xạ F : H −→ H là L-Lipchitz và η -đơn điệu mạnh trên ∆ := ∪N i=1 Ti (H). Khi đó, với bất kì u0 ∈ H, bất kì µ ∈ (0, 2η ) và bất kì dãy L2 {λn } ⊂ [0, 1] thỏa mãn (B1) limn→∞ λn = 0, (B2) Σ∞ n=1 λn = ∞, (B3) Σ∞ n=1 | λn − λn+N |< ∞. Dãy {un } xác định bởi (λ ) n+1 un+1 := T[n+1] (un ) := T[n+1] (un ) − λn+1 µF (T[n+1] (un )), (1.10) hội tụ mạnh về nghiệm duy nhất của VIP(F, F), tức là u∗ ∈ F sao cho hv − u∗ , F (u∗ )i ≥ 0 với mọi v ∈ F, trong đó [.] là modulo N xác định bởi [i] = {i − kN |k = 0, 1, 2, ...} ∩ {1, 2, ..., N } 16 1.4. Một số bổ đề bổ trợ Bổ đề 1.1 (xem [10]). Cho C là một tập con khác rỗng của không gian Hilbert thực H . Giả sử λ ∈ (0, 1) và µ > 0. Cho F : C −→ H là một ánh xạ k -Lipschitzian và η -đơn điệu mạnh trên C và cho T : C −→ C là một ánh xạ không giãn. Xác định ánh xạ G : C −→ H bởi Gx = (I − λµF )T x, ∀x ∈ C. Khi đó, G là một ánh xạ co nếu µ < 2η/k 2 . Chính xác hơn, với µ ∈ (0, 2η/k 2 ), thì kGx − Gyk ≤ (1 − λτ )kx − yk, ∀x, y ∈ C, trong đó τ = 1 − p 1 − µ(2η − µk 2 ). Chứng minh. Trước hết, với mọi x, y ∈ C , ta có k(I − µF )x − (I − µF )yk2 = k(x − y) − µ(F x − F y)k2 = kx − yk2 − 2µhx − y, F x − F yi + µ2 kF x − F yk2 ≤ (1 − 2µη + µ2 k 2 )kx − yk2 = [1 − µ(2η − µk 2 )]kx − yk2 . Do đó, từ tính không giãn của T , ta có k(I − λµF )T x − (I − λµF )T yk = k(1 − λ)(T x − T y) − λ(I − µF )T x − (I − µF )T y)k ≤ (1 − λ)kx − yk + λ p 1 − µ(2η − µk 2 )kx − yk = (1 − λτ )kx − yk, với τ = p 1 − µ(2η − µk 2 ). Bổ đề được chứng minh. Bổ đề 1.2. Cho {an } là một dãy số các số thực không âm thỏa mãn tính chất an+1 ≤ (1 − sn )an + sn tn + vn , ∀n ≥ 0 trong đó {sn }, {sn } và {vn } thỏa mãn các điều kiện (1.11)