Dự thảo tóm tắt Luận án Tiến sĩ Toán học: Các phương pháp giải một vài lớp bài toán cân bằng có tính lồi và đơn điệu suy rộng

Chia sẻ: Acacia2510 _Acacia2510 | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

39
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án nghiên cứu và đề xuất phương pháp giải một vài lớp bài toán bất đẳng thức biến phân với tập ràng buộc là tập nghiệm của bài toán chấp nhận tách suy rộng. Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận án được chia thành bốn chương.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Dự thảo tóm tắt Luận án Tiến sĩ Toán học: Các phương pháp giải một vài lớp bài toán cân bằng có tính lồi và đơn điệu suy rộng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ——————— TRẦN VIỆT ANH CÁC PHƯƠNG PHÁP GIẢI MỘT VÀI LỚP BÀI TOÁN CÂN BẰNG CÓ TÍNH LỒI VÀ ĐƠN ĐIỆU SUY RỘNG Chuyên ngành: Toán giải tích Mã số: 62460102 DỰ THẢO TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2018
MỞ ĐẦU Trong thực tế, bên cạnh những mô hình toán học đòi hỏi phải tìm nghiệm chung của hai bài toán trên cùng một không gian, có những mô hình, chẳng hạn mô hình IMRT (Intensity-Modulated Radiation Therapy) trong bức xạ trị liệu yêu cầu tìm nghiệm của một bài toán trong không gian này sao cho ảnh của nó qua một toán tử tuyến tính bị chặn là nghiệm của một bài toán trong không gian khác. Bài toán chấp nhận tách (SFP - Split Feasibility Problem) được phát biểu như sau: Tìm x∗ ∈ C sao cho Ax∗ ∈ Q, (SF P ) trong đó C, Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 , H2 và A : H1 −→ H2 là một toán tử tuyến tính bị chặn. Bài toán chấp nhận tách có nhiều ứng dụng thực tế trong các bài toán xử lý tín hiệu và khôi phục ảnh, liệu pháp xạ trị với cường độ điều chỉnh (intensity- modulated radiation therapy) và trong các bài toán khác. Bài toán chấp nhận tách trong các không gian Hilbert hữu hạn chiều được giới thiệu lần đầu tiên bởi Censor và Elfving. Để giải bài toán chấp nhận tách trong không gian hữu hạn chiều, Byrne đã đề xuất thuật toán CQ bằng cách xét dãy, với mọi k ≥ 0, xk+1 = PC (xk + γAT (PQ − I)Axk ), trong đó C, Q lần lượt là hai tập lồi đóng khác rỗng trong Rn và Rm , A là một ma 2 trận thực m × n, L là giá trị riêng lớn nhất của ma trận AT A và γ ∈ 0, . L Gần đây, Xu đã giải bài toán chấp nhận tách trong không gian Hilbert vô hạn chiều trong đó thuật toán CQ có dạng xk+1 = PC (xk + γA∗ (PQ − I)Axk ), 2 với γ ∈ 0, và A∗ là toán tử liên hợp của A. Tác giả chứng minh được dãy kAk2 {xk } hội tụ yếu đến nghiệm của bài toán chấp nhận tách với điều kiện bài toán chấp nhận tách có nghiệm. Thuật toán CQ để giải bài toán chấp nhận tách đòi hỏi phải tìm được hình chiếu trên các tập C và Q, tuy nhiên trong các trường hợp các tập C, Q được cho dưới dạng ẩn, ví dụ như tập điểm bất động của một ánh xạ, tập nghiệm của một bài toán bất đẳng thức biến phân, tập nghiệm của một bài toán cân bằng,...thì ta không thể tìm được hình chiếu trên nó. Bài toán chấp nhận tách trong trường hợp này được gọi là bài toán chấp nhận tách suy rộng. Một số dạng cơ bản của bài toán chấp nhận tách suy rộng được nghiên cứu trong luận án đó là bài toán điểm bất động tách, bài toán bất đẳng thức biến phân tách, bài toán cân bằng tách, 1
bài toán chấp nhận tách đa tập hợp. Tất cả các dạng này đều được giả thiết là có nghiệm. Luận án nghiên cứu và đề xuất phương pháp giải một vài lớp bài toán bất đẳng thức biến phân với tập ràng buộc là tập nghiệm của bài toán chấp nhận tách suy rộng. Ngoài phần mở đầu, kết luận và tài liệu tham khảo, luận án được chia thành bốn chương, trong đó các kết quả chính của luận án nằm ở Chương 2, Chương 3 và Chương 4. Bố cục của luận án Mở đầu Chương 1. Kiến thức chuẩn bị Chương 2. Bài toán bất đẳng thức biến phân với ràng buộc điểm bất động tách Chương 3. Bài toán bất đẳng thức biến phân với ràng buộc bất đẳng thức biến phân tách và chấp nhận tách đa tập hợp Chương 4. Bài toán tìm nghiệm có chuẩn nhỏ nhất của bài toán cân bằng tách Kết luận Danh mục công trình khoa học của tác giả liên quan đến luận án. Tài liệu tham khảo 2
Chương 1 Kiến thức chuẩn bị Trong chương này, chúng ta nhắc lại một số khái niệm và kết quả được sử dụng trong các chương tiếp theo của luận án. 1.1 Hàm lồi và dưới vi phân của hàm lồi Cho H là không gian Hilbert thực và f : H −→ R ∪ {±∞}. Tập dom f := {x ∈ H : f (x) < +∞} được gọi là miền hữu hiệu của hàm f . Ta nói f là hàm chính thường nếu dom f 6= ∅ và f (x) > −∞ với mọi x ∈ H. Định nghĩa 1.1. f : H −→ R ∪ {+∞} được gọi là hàm lồi nếu f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) với mọi x, y ∈ dom f và mọi λ ∈ (0, 1). Định nghĩa 1.2. Cho f : H −→ R ∪ {+∞} là hàm lồi chính thường. Ta nói p ∈ H là dưới đạo hàm của f tại x0 ∈ H nếu hp, x − x0 i + f (x0 ) ≤ f (x) ∀x ∈ H. Tập hợp tất cả các dưới đạo hàm của f tại x0 được gọi là dưới vi phân của f tại x0 và được ký hiệu là ∂f (x0 ). Như vậy ∂f (x0 ) = {p ∈ H : hp, x − x0 i + f (x0 ) ≤ f (x) ∀x ∈ H}. Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂f (x0 ) 6= ∅. Định lý 1.1. (Định lý Moreau-Rockafellar) Cho f1 , f2 : H −→ R ∪ {+∞} là hai hàm lồi chính thường. Khi đó ∂(f1 + f2 )(x) ⊃ ∂f1 (x) + ∂f2 (x) ∀x ∈ H. Ngoài ra, nếu một trong hai hàm f1 , f2 liên tục tại một điểm thuộc miền hữu hiệu của hàm kia thì ∂(f1 + f2 )(x) = ∂f1 (x) + ∂f2 (x) ∀x ∈ H. 3
1.2 Toán tử chiếu trong không gian Hilbert Định lý 1.2. Cho C là tập lồi đóng khác rỗng trong không gian Hilbert thực H. Khi đó với mọi x ∈ H, tồn tại duy nhất y ∈ C sao cho kx − yk = min kx − zk. z∈C Khi đó điểm y ∈ C được gọi là hình chiếu của x trên C và được ký hiệu là PC (x). Định nghĩa 1.3. Cho C là tập lồi đóng khác rỗng trong không gian Hilbert thực H, ánh xạ PC : H −→ C xác định bởi kx − PC (x)k = min kx − zk z∈C được gọi là toán tử chiếu trên C. Bổ đề 1.1. 1.3 Bài toán điểm bất động Định nghĩa 1.4. Cho C là một tập khác rỗng của H và T : C −→ C là một ánh xạ. Điểm x ∈ C được gọi là điểm bất động của ánh xạ T nếu T (x) = x. Ta ký hiệu Fix(T ) là tập điểm bất động của T , tức là Fix(T ) = {x ∈ C : T (x) = x}. Định nghĩa 1.5. Bổ đề 1.2. Giả sử C là tập lồi đóng và khác rỗng trong không gian Hilbert thực H và T : C −→ C là ánh xạ không giãn. Nếu T có điểm bất động thì Fix(T ) là tập lồi đóng. 1.4 Bài toán bất đẳng thức biến phân Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H, F là ánh xạ đi từ Ω vào H, trong đó Ω là một tập trong H chứa C. Bài toán bất đẳng thức biến phân V IP (C, F ) được phát biểu như sau: Tìm x∗ ∈ C sao cho hF (x∗ ), x − x∗ i ≥ 0 ∀x ∈ C. (1.1) Tập nghiệm của bài toán bất đẳng thức biến phân V IP (C, F ) được ký hiệu là Sol(C, F ). 4
Bổ đề 1.3. Cho x∗ ∈ C và λ > 0. Khi đó x∗ ∈ Sol(C, F ) ⇐⇒ x∗ ∈ Fix(T ). Định lý 1.3. Nếu C là tập lồi compact và F là liên tục trên C thì V IP (C, F ) có nghiệm. Định nghĩa 1.6. Định lý 1.4. Nếu F : Ω −→ H là β-đơn điệu mạnh trên C và L-liên tục Lipschitz trên C thì V IP (C, F ) có nghiệm duy nhất. Bổ đề 1.4. Cho ánh xạ F : Ω −→ H là η-đơn điệu mạnh ngược trên C và µ ∈ (0, 2η]. Xét ánh xạ T : C −→ C cho bởi T (x) = PC (x − µF (x)) ∀x ∈ C. Khi đó ánh xạ T là không giãn và Fix(T ) = Sol(C, F ). Bổ đề 1.5. Giả sử C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H và Ω là một tập trong H chứa C. Cho ánh xạ F : Ω −→ H giả đơn điệu trên C và một trong hai điều kiện sau thỏa mãn: (i) lim suphF (xk ), yi ≤ hF (x), yi với mọi y ∈ H và mọi dãy {xk } ⊂ C hội tụ k−→∞ yếu đến x. (ii) F liên tục Lipschitz trên C với hệ số L > 0. Giả sử tập nghiệm Sol(C, F ) của bài toán bất đẳng thức biến phân V IP (C, F ) khác rỗng, khi đó Sol(C, F ) là tập lồi đóng. 1.5 Bài toán cân bằng Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H, f : C×C −→ R là một song hàm sao cho f (x, x) = 0 với mọi x ∈ C. Bài toán cân bằng (EP - Equilibrium Problem) cho song hàm f trên C là bài toán Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0 với mọi y ∈ C. (1.2) Ta ký hiệu bài toán cân bằng (1.2) và tập nghiệm của nó lần lượt bởi EP (C, f ), Sol(C, f ). Định nghĩa 1.7. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H. Song hàm f : C × C −→ R ∪ {+∞} được gọi là: (i) đơn điệu trên C nếu f (x, y) + f (y, x) ≤ 0 với mọi x, y ∈ C; (ii) giả đơn điệu trên C nếu từ f (x, y) ≥ 0, ta suy ra f (y, x) ≤ 0 với mọi 5
x, y ∈ C; (iii) liên tục kiểu Lipschitz trên C với hằng số c1 > 0 và c2 > 0 nếu f (x, y) + f (y, z) ≥ f (x, z) − c1 kx − yk2 − c2 ky − zk2 ∀x, y, z ∈ C; (iv) liên tục yếu đồng thời trên C × C nếu với hai dãy {xk }, {y k } ⊂ C hội tụ yếu lần lượt đến x, y ∈ C thì f (xk , y k ) −→ f (x, y) khi k −→ ∞. Bổ đề 1.6. Cho f : C × C −→ R thỏa mãn đồng thời các điều kiện: (A1 ) f (x, x) = 0 với mọi x ∈ C; (A2 ) f đơn điệu; (A3 ) với mọi x, y, z ∈ C lim sup f (λz + (1 − λ)x, y) ≤ f (x, y); λ−→0+ (A4 ) với mọi x ∈ C, hàm y 7−→ f (x, y) lồi và nửa liên tục dưới trên C. Khi đó với mọi r > 0 và x ∈ H, tồn tại duy nhất z ∈ C sao cho 1 f (z, y) + hy − z, z − xi ≥ 0 ∀y ∈ C. r Bổ đề 1.7. Cho f : C × C −→ R thỏa mãn các điều kiện (A1 ) − (A4 ). Với mọi r > 0, ta xác định ánh xạ Trf : H −→ C bởi f n 1 o Tr (x) = z ∈ C : f (z, y) + hy − z, z − xi ≥ 0 ∀y ∈ C r với mọi x ∈ H. Khi đó ta có (i) Trf là đơn trị; (ii) kTrf (x) − Trf (y)k2 ≤ hTrf (x) − Trf (y), x − yi ∀x, y ∈ H; (iii) Fix(Trf ) = Sol(C, f ); (iv) Sol(C, f ) lồi đóng. Mệnh đề 1.1. Cho song hàm f : H × H −→ R ∪ {+∞}. Giả sử rằng các điều kiện (A0 ) − (A4 ) được thỏa mãn đồng thời (A0 ) ít nhất một trong hai điều kiện int C 6= ∅ và điều kiện với mỗi x ∈ C thì hàm f (x, ·) liên tục tại một điểm thuộc C được thỏa mãn; (A1 ) với mỗi x ∈ C thì hàm f (x, ·) lồi, nửa liên tục dưới trên H và khả dưới vi phân trên C; (A2 ) f giả đơn điệu trên C và C ⊂ dom f (x, ·), f (x, x) = 0 với mọi x ∈ C; (A3 ) f liên tục kiểu Lipschitz trên C với hằng số c1 > 0 và c2 > 0. Xét ánh xạ Tf : C −→ C cho bởi n 1 2 o Tf (x) := argmin λf (s(x), y) + ky − xk : y ∈ C , 2 với mọi x ∈ C, trong đó λ > 0 và n 1 o s(x) := argmin λf (x, y) + ky − xk2 : y ∈ C . 2 6
Khi đó với x∗ ∈ Sol(C, f ), ta có λ[f (x, y) − f (x, s(x))] ≥ hs(x) − x, s(x) − yi ∀y ∈ C, kTf (x) − x∗ k2 ≤ kx − x∗ k2 − (1 − 2λc1 )kx − s(x)k2 − (1 − 2λc2 )ks(x) − Tf (x)k2 . Mệnh đề 1.2. Dưới các giả thiết (A0 ) − (A3 ) của Mệnh đề 1.1 và 0 < λ < n 1 1 o min , thì tập điểm bất động của ánh xạ Tf trùng với tập nghiệm của bài 2c1 2c2 toán cân bằng EP (C, f ), với điều kiện tập nghiệm Sol(C, f ) của EP (C, f ) khác rỗng. Mệnh đề 1.3. Giả sử song hàm f thỏa mãn các điều kiện (A0 ) − (A3 ) trong Mệnh đề 1.1 và các điều kiện (A4 ) f liên tục yếu đồng thời trên C × C; (A5 ) tập nghiệm Sol(C, f ) của bài toán cân bằng EP (C, f ) khác rỗng. n 1 1 o Khi đó ánh xạ Tf là tựa không giãn trên C với 0 < λ < min , và bán 2c1 2c2 đóng tại 0 ∈ H. Bổ đề 1.8. Cho {an } là một dãy các số thực không âm thỏa mãn điều kiện an+1 ≤ (1 − αn )an + αn ξn , ∀n ≥ 0, trong đó {αn }, {ξn } là hai dãy số thực thỏa mãn đồng thời các điều kiện ∞ X (i) {αn } ⊂ (0, 1) và αn = ∞. n=0 (ii) lim sup ξn ≤ 0. n−→∞ Khi đó lim an = 0. n−→∞ Bổ đề 1.9. Cho {an } là một dãy các số thực không âm. Giả sử với mỗi số tự nhiên m, tồn tại số tự nhiên p ≥ m sao cho ap ≤ ap+1 . Gọi n0 là số tự nhiên sao cho an0 ≤ an0 +1 . Với mỗi n ≥ n0 , ta đặt τ (n) = max{k ∈ N : n0 ≤ k ≤ n, ak ≤ ak+1 }. Khi đó dãy {τ (n)}n≥n0 là một dãy không giảm thỏa mãn lim τ (n) = ∞ và n−→∞ aτ (n) ≤ aτ (n)+1 , an ≤ aτ (n)+1 ∀n ≥ n0 . Kết luận chương 7
Chương 2 Bài toán bất đẳng thức biến phân với ràng buộc điểm bất động tách Trong chương này, chúng ta nghiên cứu và đề xuất thuật toán giải bài toán bất đẳng thức biến phân với tập ràng buộc là tập nghiệm của bài toán điểm bất động tách. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 . Giả sử F : C −→ H1 là ánh xạ đơn điệu mạnh, A : H1 −→ H2 là một toán tử tuyến tính bị chặn, T : C −→ C, S : Q −→ Q là các ánh xạ không giãn. Xét bài toán bất đẳng thức biến phân với ràng buộc điểm bất động tách sau: Tìm x∗ ∈ Ω sao cho hF (x∗ ), x − x∗ i ≥ 0 ∀x ∈ Ω, (V ISF P P ) trong đó Ω là tập nghiệm của bài toán điểm bất động tách (SFPP - Split Fixed Point Problem) Tìm x∗ ∈ Fix(T ) sao cho Ax∗ ∈ Fix(S), (SF P P ) với Fix(T ), Fix(S) lần lượt là tập điểm bất động của T, S. 2.1 Định lý hội tụ Trong mục này chúng ta phát biểu và chứng minh định lý hội tụ cho VISFPP. Kỹ thuật chính để chứng minh là sự kết hợp giữa phương pháp chiếu để giải bài toán bất đẳng thức biến phân và kỹ thuật lặp Krasnoselskii-Mann để tìm điểm bất động của ánh xạ không giãn. Định lý 2.1. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 , A : H1 −→ H2 là toán tử tuyến tính bị chặn với toán tử liên hợp A∗ . Giả sử ánh xạ F : C −→ H1 là β-đơn điệu mạnh và L-liên tục Lipschitz trên C, T : C −→ C, S : Q −→ Q là các ánh xạ không giãn. Với x0 ∈ C 8
bất kỳ, xét các dãy {xk }, {uk }, {y k } và {z k } như sau    uk = PQ (Axk ),  y k = P (xk + δA∗ (Suk − Axk )),  C   z k = PC (y k − λk µF (y k )),    k+1 x = αk xk + (1 − αk )T (z k ) ∀k ≥ 0, 1 2β trong đó δ ∈ 0, 2 , 0 < µ < 2 , {λk } và {αk } là hai dãy số nằm trong kAk + 1 L khoảng (0, 1) và thỏa mãn đồng thời các điều kiện sau: (a) lim λk = 0, k−→∞ ∞ X (b) λk (1 − αk ) = ∞, k=0 (c) lim αk = α ∈ (0, 1). k−→∞ Giả sử tập nghiệm Ω của SFPP khác rỗng, khi đó dãy {xk } hội tụ mạnh đến nghiệm duy nhất của bài toán bất đẳng thức biến phân V IP (Ω, F ). 2.2 Một số hệ quả Hệ quả 2.1. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 , A : H1 −→ H2 là toán tử tuyến tính bị chặn với toán tử liên hợp A∗ . Giả sử F : C −→ H1 là β-đơn điệu mạnh và L-liên tục Lipschitz trên C, F1 : C −→ H1 là ánh xạ η1 -đơn điệu mạnh ngược trên C và F2 : Q −→ H2 là ánh xạ η2 -đơn điệu mạnh ngược trên Q. Với x0 ∈ C bất kỳ, xét các dãy {xk }, {uk }, {v k }, {y k }, {z k } và {tk } như sau     uk = PQ (Axk ),  v k = PQ (uk − ξ2 F2 (uk )),       y k = P (xk + δA∗ (v k − Axk )),  C   z k = PC (y k − λk µF (y k )),   tk = PC (z k − ξ1 F1 (z k )),        k+1 x = αk xk + (1 − αk )tk ∀k ≥ 0, 1 2β trong đó δ ∈ 0, , 0 < ξ 1 ≤ 2η 1 , 0 < ξ 2 ≤ 2η2 , µ ∈ 0, 2 , {λk } và kAk2 + 1 L {αk } là hai dãy số trong khoảng (0, 1) thỏa mãn đồng thời các điều kiện (a), (b), (c) ở Định lý 2.1. Khi đó dãy {xk } hội tụ mạnh đến nghiệm duy nhất của bài toán bất đẳng thức biến phân V IP (Ω, F ) với điều kiện tập nghiệm Ω = {x∗ ∈ Sol(C, F1 ) : Ax∗ ∈ Sol(Q, F2 )} của bài toán bất đẳng thức biến phân tách khác rỗng. 9
Hệ quả 2.2. Giả sử f : C × C −→ R và g : Q × Q −→ R là hai song hàm thỏa mãn các điều kiện (A1 ) − (A4 ) trong Bổ đề 1.6. Với x0 ∈ C bất kỳ, xét các dãy {xk }, {uk }, {y k } và {z k } xác định bởi     uk = PQ (Axk ),  y k = P (xk + δA∗ (T g (uk ) − Axk )),  C r2    z k = PC (y k − λk µF (y k )),    k+1 x = αk xk + (1 − αk )Trf1 (z k ) ∀k ≥ 0, 1 2β trong đó δ ∈ 0, 2 , r1 > 0, r2 > 0, 0 < µ < 2 , {λk } và {αk } là hai dãy kAk + 1 L trong khoảng (0, 1) thỏa mãn đồng thời các điều kiện sau: (a) lim λk = 0, k−→∞ ∞ X (b) λk (1 − αk ) = ∞, k=0 (c) lim αk = α ∈ (0, 1). k−→∞ Khi đó dãy {xk } hội tụ mạnh đến nghiệm duy nhất x∗ của bài toán bất đẳng thức biến phân V IP (Ω, F ) với giả thiết tập nghiệm Ω = {x∗ ∈ Sol(C, f ) : Ax∗ ∈ Sol(Q, g)} của bài toán cân bằng tách khác rỗng. Hệ quả 2.3. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 , A : H1 −→ H2 là toán tử tuyến tính bị chặn với toán tử liên hợp A∗ , F1 : C −→ H1 là ánh xạ η1 -đơn điệu mạnh ngược trên C và F2 : Q −→ H2 là ánh xạ η2 -đơn điệu mạnh ngược trên Q. Giả sử tập nghiệm Ω = {x∗ ∈ Sol(C, F1 ) : Ax∗ ∈ Sol(Q, F2 )} của bài toán bất đẳng thức biến phân tách khác rỗng. Với x0 ∈ C bất kỳ, xét các dãy {xk }, {uk }, {v k }, {y k }, {z k } và {tk } như sau     uk = PQ (Axk ),  v k = PQ (uk − ξ2 F2 (uk )),       y k = P (xk + δA∗ (v k − Axk )),  C    z k = PC (y k − λk y k ),   tk = PC (z k − ξ1 F1 (z k )),        k+1 x = αk xk + (1 − αk )tk ∀k ≥ 0, 1 trong đó δ ∈ 0, , 0 < ξ1 ≤ 2η1 , 0 < ξ2 ≤ 2η2 , {λk } và {αk } là hai dãy kAk2 + 1 số trong khoảng (0, 1) thỏa mãn đồng thời các điều kiện (a), (b), (c) ở Định lý 2.1. Khi đó dãy {xk } hội tụ mạnh đến x∗ ∈ Ω, trong đó kx∗ k = min{kxk : x ∈ Ω}. 10
Hệ quả 2.4. Giả sử f : C × C −→ R và g : Q × Q −→ R là hai song hàm thỏa mãn các điều kiện (A1 )−(A4 ) trong Bổ đề 1.6 và tập nghiệm Ω = {x∗ ∈ Sol(C, f ) : Ax∗ ∈ Sol(Q, g)} của bài toán cân bằng tách khác rỗng. Với x0 ∈ C bất kỳ, xét các dãy {xk }, {uk }, {y k } và {z k } cho bởi     uk = PQ (Axk ),  y k = P (xk + δA∗ (T g (uk ) − Axk )),  C r2 k k k    z = PC (y − λk y ),    k+1 x = αk xk + (1 − αk )Trf1 (z k ) ∀k ≥ 0, 1 trong đó δ ∈ 0, , r1 > 0, r2 > 0, {λk } và {αk } là hai dãy trong khoảng kAk2 + 1 (0, 1) thỏa mãn đồng thời các điều kiện sau: (a) lim λk = 0, k−→∞ ∞ X (b) λk (1 − αk ) = ∞, k=0 (c) lim αk = α ∈ (0, 1). k−→∞ Khi đó dãy {xk } hội tụ mạnh đến x∗ ∈ Ω, trong đó kx∗ k = min{kxk : x ∈ Ω}. 2.3 Thử nghiệm số Kết luận chương 11
Chương 3 Bài toán bất đẳng thức biến phân với ràng buộc bất đẳng thức biến phân tách và chấp nhận tách đa tập hợp Trong phần đầu chương, chúng tôi trình bày thuật toán giải bài toán bất đẳng thức biến phân hai cấp (bài toán bất đẳng thức biến phân với tập ràng buộc là tập nghiệm của bài toán bất đẳng thức biến phân). Mục tiếp theo là thuật toán giải bài toán bất đẳng thức biến phân tách hai cấp (bài toán bất đẳng thức biến phân với tập ràng buộc là tập nghiệm của bài toán bất đẳng thức biến phân tách). Ở phần cuối chương, chúng tôi đề xuất thuật toán giải bài toán bất đẳng thức biến phân với tập ràng buộc là tập nghiệm của bài toán chấp nhận tách đa tập hợp. 3.1 Bài toán bất đẳng thức biến phân hai cấp Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H và hai ánh xạ F : H −→ H, G : H −→ H, ta xét bài toán bất đẳng thức biến phân hai cấp (BVIP - Bilevel Variational Inequality Problem) Tìm x∗ ∈ Sol(C, G) sao cho hF (x∗ ), y − x∗ i ≥ 0 ∀y ∈ Sol(C, G), (BV IP ) trong đó Sol(C, G) = {y ∗ ∈ C : hG(y ∗ ), z − y ∗ i ≥ 0 ∀z ∈ C} là tập nghiệm của V IP (C, G). Trong trường hợp G là ánh xạ không thì tập nghiệm Sol(C, G) của V IP (C, G) chính là C. Khi đó, BVIP trở thành bài toán bất đẳng thức biến phân V IP (C, F ). Khi F là ánh xạ đồng nhất thì BVIP trở thành bài toán tìm nghiệm có chuẩn nhỏ nhất của V IP (C, G). Ta xét các ánh xạ F, G : H −→ H thỏa mãn đồng thời các điều kiện sau: (A1 ): F là β-đơn điệu mạnh trên H và L-liên tục Lipschitz trên H. (A2 ): G giả đơn điệu trên C và γ-liên tục Lipschitz trên H. (A3 ): lim suphG(xk ), y − y k i ≤ hG(x), y − yi với mọi y ∈ H và mọi dãy {xk }, k−→∞ {y k } nằm trong H hội tụ yếu lần lượt đến x, y ∈ H. 12
3.1.1 Thuật toán và định lý hội tụ 2β Thuật toán 3.1. Chọn x0 ∈ H bất kỳ, 0 < µ < và các dãy số {αk } ⊂ (0, 1), L2 {ηk }, {λk } thỏa mãn đồng thời các điều kiện ∞   X    lim αk = 0, αk = ∞,   k−→∞  k=0 0 ≤ ηk ≤ 1 − αk ∀k ≥ 0, lim ηk = η < 1, k−→∞   1   {λk } ⊂ [a, b] với a, b ∈ 0, .   γ Với mỗi k ≥ 0, ta tính y k = PC (xk − λk G(xk )), z k = PTk (xk − λk G(y k )), và xk+1 = ηk xk + (1 − ηk )z k − αk µF (z k ), trong đó Tk = {ω ∈ H : hxk − λk G(xk ) − y k , ω − y k i ≤ 0}. Nhận xét 3.1. Bổ đề 3.1. Giả sử F : H −→ H là β-đơn điệu mạnh trên H và L-liên tục Lipschitz 2β trên H, 0 < α < 1, 0 ≤ η ≤ 1 − α, 0 < µ < 2 . Khi đó L k(1 − η)x − αµφ(x) − [(1 − η)y − αµφ(y)]k ≤ (1 − η − ατ )kx − yk ∀x, y ∈ H, trong đó p τ =1− 1 − µ(2β − µL2 ) ∈ (0, 1]. Bổ đề 3.2. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert H, G : H −→ H giả đơn điệu trên C, L-liên tục Lipschitz trên H và Sol(C, G) 6= ∅. Xét x ∈ H, λ > 0 và xác định y = PC (x − λG(x)), z = PT (x − λG(y)), trong đó T = {ω ∈ H : hx − λG(x) − y, ω − yi ≤ 0}. Khi đó với mọi x∗ ∈ Sol(C, G), ta có kz − x∗ k2 ≤ kx − x∗ k2 − (1 − λL)kx − yk2 − (1 − λL)ky − zk2 . Định lý 3.1. Giả sử Sol(C, G) 6= ∅ và các điều kiện (A1 ) − (A3 ) được thỏa mãn. Khi đó dãy {xk } trong Thuật toán 3.1 hội tụ mạnh đến nghiệm duy nhất của BVIP. Nhận xét 3.2. • Vì G là γ-liên tục Lipschitz trên H nên G là liên tục. Do đó khi không gian Hilbert H là hữu hạn chiều thì điều kiện (A3 ) luôn thỏa mãn. • Nếu điều kiện G giả đơn điệu trên C được thay bằng điều kiện G đơn điệu trên H thì điều kiện (A3 ) có thể được bỏ đi. 13
3.1.2 Một số hệ quả Hệ quả 3.1. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H, G : H −→ H giả đơn điệu trên C và L-liên tục Lipschitz trên H. Giả sử Sol(C, G) 6= ∅ và lim suphG(xk ), y − y k i ≤ hG(x), y − yi với mọi dãy {xk }, {y k } k−→∞ nằm trong H hội tụ yếu lần lượt tới x và y. Xét dãy {xk } cho bởi    x0 ∈ H,  y k = P (xk − λ G(xk )),  C k (3.1)   Tk = {ω ∈ H : hxk − λk G(xk ) − y k , ω − y k i ≤ 0},    k+1 x = αk x0 + (1 − αk )PTk (xk − λk G(y k )) ∀k ≥ 0, ∞ X trong đó dãy số {αk } ⊂ (0, 1) thỏa mãn lim αk = 0, αk = ∞ và {λk } ⊂ k−→∞ k=0 1 [a, b] ⊂ 0, . Khi đó dãy {xk } hội tụ mạnh đến PSol(C,G) (x0 ). L Hệ quả 3.2. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H, G : H −→ H đơn điệu trên H và L-liên tục Lipschitz trên H sao cho Sol(C, G) 6= ∅. Xét dãy {xk } cho bởi    x0 ∈ H,  y k = P (xk − λ G(xk )),  C k (3.2)   Tk = {ω ∈ H : hxk − λk G(xk ) − y k , ω − y k i ≤ 0},    k+1 x = αk x0 + (1 − αk )PTk (xk − λk G(y k )) ∀k ≥ 0, ∞ X 1 trong đó {αk } ⊂ (0, 1), lim αk = 0, αk = ∞ và {λk } ⊂ [a, b] với a, b ∈ 0, . k−→∞ L k=0 Khi đó dãy {x } cho bởi (3.2) hội tụ mạnh đến PSol(C,G) (x0 ). k 3.1.3 Thử nghiệm số 3.2 Bài toán bất đẳng thức biến phân tách hai cấp Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 . Giả sử A : H1 −→ H2 là một toán tử tuyến tính bị chặn và các ánh xạ F1 : H1 −→ H1 và F2 : H2 −→ H2 . Bài toán bất đẳng thức biến phân tách (SVIP - Split Variational Inequality Problem) được mô tả như sau Tìm x∗ ∈ C : hF1 (x∗ ), x − x∗ i ≥ 0 ∀x ∈ C (3.3) 14
sao cho y ∗ = Ax∗ ∈ Q : hF2 (y ∗ ), y − y ∗ i ≥ 0 ∀y ∈ Q. (3.4) Nếu tập nghiệm của các bài toán bất đẳng thức biến phân (3.3) và (3.4) lần lượt được ký hiệu bởi Sol(C, F1 ) và Sol(Q, F2 ) thì bài toán bất đẳng thức biến phân tách là bài toán tìm x∗ ∈ Sol(C, F1 ) sao cho Ax∗ ∈ Sol(Q, F2 ). Ta xét bài toán bất đẳng thức biến phân tách hai cấp (BSVIP - Bilevel Split Variational Inequality Problem) Tìm x∗ ∈ Ω sao cho hF (x∗ ), x − x∗ i ≥ 0 ∀x ∈ Ω, (BSV IP ) trong đó F : H1 −→ H1 và Ω = {x∗ ∈ Sol(C, F1 ) : Ax∗ ∈ Sol(Q, F2 )} là tập nghiệm của SVIP. Ta giả thiết các ánh xạ F, F1 : H1 −→ H1 , F2 : H2 −→ H2 thỏa mãn đồng thời các điều kiện sau: (B1 ): F : H1 −→ H1 là β-đơn điệu mạnh và L-liên tục Lipschitz trên H1 . (B2 ): F1 : H1 −→ H1 là giả đơn điệu trên C và L1 -liên tục Lipschitz trên H1 . (B3 ): lim suphF1 (xk ), y − y k i ≤ hF1 (x), y − yi với mọi y ∈ H1 và mọi dãy {xk }, k−→∞ {y k } nằm trong H1 hội tụ yếu lần lượt đến x, y ∈ H1 . (B4 ): F2 : H2 −→ H2 là giả đơn điệu trên Q và L2 -liên tục Lipschitz trên H2 . (B5 ): lim suphF2 (uk ), v − v k i ≤ hF2 (u), v − vi với mọi v ∈ H2 và mọi dãy {uk }, k−→∞ k {v } nằm trong H2 hội tụ yếu lần lượt đến u, v ∈ H1 . Từ điều kiện (B2 ), (B3 ), (B4 ), (B5 ) và Bổ đề 1.5, ta có Sol(C, F1 ) và Sol(Q, F2 ) là các tập lồi đóng. Do đó Ω = {x∗ ∈ Sol(C, F1 ) : Ax∗ ∈ Sol(Q, F2 )} cũng là tập lồi đóng. 3.2.1 Thuật toán và định lý hội tụ 2β Thuật toán 3.2. Chọn x0 ∈ H1 , 0 < µ < và các dãy số {αk } ⊂ (0, 1), {ηk }, L2 {δk }, {λk }, {µk } thỏa mãn đồng thời các điều kiện ∞  X αk = ∞,     lim αk = 0,  k−→∞ k=0     0 ≤ ηk ≤ 1 − αk ∀k ≥ 0, lim ηk = η < 1,    k−→∞   1 {δk } ⊂ [a, b] với a, b ∈ 0, ,   kAk2 + 1 1   {λk } ⊂ [c, d] với c, d ∈ 0,    ,   L 1 1    {µk } ⊂ [e, f ] với e, f ∈ 0,  . L2 Với mỗi k ≥ 0, ta tính uk = Axk , v k = PQ (uk − µk F2 (uk )), wk = PQk (uk − µk F2 (v k )), 15
trong đó Qk = {ω2 ∈ H2 : huk − µk F2 (uk ) − v k , ω2 − v k i ≤ 0}. Tiếp theo, ta tính y k = xk + δk A∗ (wk − uk ), tk = PC (y k − λk F1 (y k )), z k = PCk (y k − λk F1 (tk )), trong đó A∗ là toán tử liên hợp của A, Ck = {ω1 ∈ H1 : hy k − λk F1 (y k ) − tk , ω1 − tk i ≤ 0}, và xk+1 = ηk xk + (1 − ηk )z k − αk µF (z k ). Định lý 3.2. Giả sử tập nghiệm Ω = {x∗ ∈ Sol(C, F1 ) : Ax∗ ∈ Sol(Q, F2 )} của SVIP khác rỗng và các điều kiện (B1 ) − (B5 ) được thỏa mãn. Khi đó dãy {xk } trong Thuật toán 3.2 hội tụ mạnh đến nghiệm duy nhất của BSVIP. 3.2.2 Một số hệ quả Hệ quả 3.3. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 , A : H1 −→ H2 là một toán tử tuyến tính bị chặn với toán tử liên hợp A∗ , F1 : H1 −→ H1 , F2 : H2 −→ H2 thỏa mãn các điều kiện (B2 ) − (B5 ). Xét các dãy số {αk }, {ηk }, {δk }, {λk }, {µk } thỏa mãn đồng thời các điều kiện như trong Thuật toán 3.2. Xét dãy {xk } cho bởi x0 ∈ H1 tùy ý và xk+1 = ηk xk + (1 − ηk − αk )z k ∀k ≥ 0, trong đó z k được xác định như trong Định lý 3.2. Giả sử tập nghiệm Ω = {x∗ ∈ Sol(C, F1 ) : Ax∗ ∈ Sol(Q, F2 )} của SVIP khác rỗng. Khi đó dãy {xk } hội tụ mạnh đến x∗ ∈ Ω, trong đó kx∗ k = min{kxk : x ∈ Ω}. Hệ quả 3.4. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 . Giả sử A : H1 −→ H2 là một toán tử tuyến tính bị chặn với toán tử liên hợp A∗ , F : H1 −→ H1 là β-đơn điệu mạnh và L-liên tục 2β Lipschitz trên H1 . Giả sử 0 < µ < 2 và các dãy số {αk }, {ηk }, {δk } thỏa mãn L đồng thời các điều kiện ∞   X    {αk } ⊂ (0, 1), lim αk = 0, αk = ∞,   k−→∞  k=0 0 ≤ ηk ≤ 1 − αk ∀k ≥ 0, lim ηk = η < 1,   k−→∞   1 {δk } ⊂ [a, b] ⊂ 0, .   kAk2 + 1 16
Xét dãy {xk } cho bởi x0 ∈ H1 tùy ý và  y k = P (xk + δ A∗ (P (Axk ) − Axk )), C k Q xk+1 = ηk xk + (1 − ηk )y k − αk µF (y k ) ∀k ≥ 0, Giả sử tập nghiệm Γ = {x∗ ∈ C : Ax∗ ∈ Q} của SFP là khác rỗng. Khi đó dãy {xk } hội tụ mạnh đến nghiệm duy nhất của bài toán bất đẳng thức biến phân Tìm x∗ ∈ Γ sao cho hF (x∗ ), x − x∗ i ≥ 0 ∀x ∈ Γ. Hệ quả 3.5. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 . Giả sử A : H1 −→ H2 là một toán tử tuyến tính bị chặn với toán tử liên hợp A∗ . Giả sử các dãy số dương {αk }, {δk } thỏa mãn đồng thời các điều kiện  ∞  X {αk } ⊂ (0, 1), lim αk = 0, αk = ∞,   k−→∞ k=0  1 {δ  k  } ⊂ [a, b] ⊂ 0, . kAk2 + 1 Xét dãy {xk } cho bởi x0 ∈ H1 tùy ý và xk+1 = (1 − αk )PC (xk + δk A∗ (PQ (Axk ) − Axk )) ∀k ≥ 0. (3.5) Khi đó dãy {xk } hội tụ mạnh đến nghiệm có chuẩn nhỏ nhất của SFP với điều kiện tập nghiệm Γ = {x∗ ∈ C : Ax∗ ∈ Q} của SFP khác rỗng. 3.3 Bài toán bất đẳng thức biến phân với ràng buộc chấp nhận tách đa tập hợp Bài toán chấp nhận tách đa tập hợp (MSSFP - Multiple-Sets Split Feasibility Problem) được mô tả như sau: M \ N \ ∗ ∗ Tìm x ∈ Ci sao cho Ax ∈ Qj i=1 j=1 trong đó Ci , i = 1, 2, . . . , M là các tập lồi đóng khác rỗng trong không gian Hilbert thực H1 và Qj , j = 1, 2, . . . , N là các tập lồi đóng khác rỗng trong không gian Hilbert thực H2 , A : H1 −→ H2 là một toán tử tuyến tính bị chặn. Trong mục này, chúng ta sẽ trình bày thuật toán giải bài toán bất đẳng thức biến phân với tập ràng buộc là tập nghiệm của MSSFP. Cụ thể, ta giả sử F : H1 −→ H1 là β-đơn điệu mạnh và L-liên tục Lipschitz trên H1 , C1 , C2 , . . . , CM là M tập lồi 17
đóng khác rỗng trong không gian Hilbert thực H1 và Q1 , Q2 ,. . ., QN là N tập lồi đóng khác rỗng trong không gian Hilbert thực H2 . Ta xét bài toán bất đẳng thức biến phân với ràng buộc chấp nhận tách đa tập hợp (VIMSSFP) Tìm x∗ ∈ Ω sao cho hF (x∗ ), x − x∗ i ≥ 0 ∀x ∈ Ω, (V IM SSF P ) trong đó Ω là tập nghiệm của MSSFP M \ N \ ∗ ∗ Tìm x ∈ Ci sao cho Ax ∈ Qj . (M SSF P ) i=1 j=1 3.3.1 Thuật toán và định lý hội tụ Thuật toán 3.3. 2β 2 Bước 0. Chọn 0 < µ < , 0 < δ ≤ δk ≤ δ < , {αk } ⊂ (0, 1) sao L2 kAk2 + 1 ∞ X cho lim αk = 0, αk = ∞, {ηk } ⊂ [0, 1) sao cho 0 ≤ ηk ≤ 1 − αk ∀k ≥ 0, k−→∞ k=0 lim ηk = η < 1. k−→∞ Bước 1. Chọn x0 ∈ H1 . Đặt k := 0. Bước 2. Tính uk = A(xk ) và PQj (uk ), j = 1, 2, . . . , N . Bước 3. Tìm phần tử PQj (uk ), j = 1, 2, . . . , N có khoảng cách đến uk xa nhất, tức là jk = argmax{kPQj (uk ) − uk k : j = 1, 2, . . . , N }, v k := PQjk (uk ). Bước 4. Tính y k = xk − δk A∗ (uk − v k ), trong đó A∗ là toán tử liên hợp của A. Bước 5. Tính PCi (y k ), i = 1, 2, . . . , M . Bước 6. Tìm phần tử PCi (y k ), i = 1, 2, . . . , M có khoảng cách đến y k xa nhất, tức là ik = argmax{kPCi (y k ) − y k k : i = 1, 2, . . . , M }, z k := PCik (y k ). Bước 7. Tính xk+1 = ηk xk + (1 − ηk )z k − αk µF (z k ). Bước 8. Gán k := k + 1 và quay trở lại Bước 2. Định lý 3.3. Giả sử Ci , i = 1, 2, . . . , M là các tập lồi đóng khác rỗng trong không gian Hilbert thực H1 và Qj , j = 1, 2, . . . , N là các tập lồi đóng khác rỗng trong không gian Hilbert thực H2 . Cho F : H1 −→ H1 là β-đơn điệu mạnh và L-liên tục Lipschitz trên H1 . Khi đó dãy {xk } ở Thuật toán 3.3 hội tụ mạnh đến nghiệm duy nhất của VIMSSFP, với điều kiện tập nghiệm Ω của MSSFP khác rỗng. 3.3.2 Một số hệ quả Hệ quả 3.6. Giả sử tập nghiệm Ω của MSSFP là khác rỗng. Chọn x0 ∈ H1 , ∞ 2 X 0 < δ ≤ δk ≤ δ < , {αk } ⊂ (0, 1) sao cho lim αk = 0, αk = ∞, kAk2 + 1 k−→∞ k=0 18
{ηk } ⊂ [0, 1) sao cho 0 ≤ ηk ≤ 1 − αk ∀k ≥ 0, lim ηk = η < 1. k−→∞ Với mỗi k ≥ 0, tính uk = A(xk ), v k := PQjk (uk ), trong đó jk = argmax{kPQj (uk ) − uk k : j = 1, 2, . . . , N }. Tiếp theo, ta tính y k = xk − δk A∗ (uk − v k ), z k := PCik (y k ), trong đó A∗ là toán tử liên hợp của A, ik = argmax{kPCi (y k ) − y k k : i = 1, 2, . . . , M } và xk+1 = ηk xk + (1 − ηk − αk )z k . Khi đó đó dãy {xk } hội tụ mạnh đến nghiệm có chuẩn nhỏ nhất của MSSFP. Hệ quả 3.7. Cho C và Q lần lượt là các tập lồi đóng khác rỗng trong các không gian Hilbert thực H1 và H2 , F : H1 −→ H1 là β-đơn điệu mạnh và L-liên tục Lipschitz trên H1 . Giả sử A : H1 −→ H2 là một toán tử tuyến tính bị chặn với toán tử liên hợp A∗ . Xét dãy {xk } cho bởi  0 x ∈ H1 được chọn bất kỳ,    y k = PC (xk − δk A∗ (Axk − PQ (Axk ))),   xk+1 = ηk xk + (1 − ηk )y k − αk µF (y k ) ∀k ≥ 0,  2β trong đó 0 < µ < và các dãy số {ηk }, {λk }, {δk } thỏa mãn đồng thời các điều L2 kiện ∞   X   {αk } ⊂ (0, 1), lim αk = 0, αk = ∞,   k−→∞  k=0 {ηk } ⊂ [0, 1), 0 ≤ ηk ≤ 1 − αk ∀k ≥ 0, lim ηk = η < 1,   k−→∞   2 {δk } ⊂ [δ, δ] ⊂ 0, .   kAk2 + 1 Giả sử tập nghiệm Γ = {x∗ ∈ C : Ax∗ ∈ Q} của SFP là khác rỗng. Khi đó dãy {xk } hội tụ mạnh đến x∗ ∈ Γ, là nghiệm duy nhất của bất đẳng thức biến phân hF (x∗ ), x − x∗ i ≥ 0 ∀x ∈ Γ. 3.3.3 Thử nghiệm số Kết luận chương 19