ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN NGỌC HẢO PHƯƠNG PHÁP DOUGLAS - RACHFORD TÌM KHÔNG ĐIỂM CỦA BAO HÀM THỨC ĐƠN ĐIỆU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN NGỌC HẢO PHƯƠNG PHÁP DOUGLAS - RACHFORD TÌM KHÔNG ĐIỂM CỦA BAO HÀM THỨC ĐƠN ĐIỆU 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 - 2015 i Mục lục Mục lục i Lời cảm ơn ii Mở đầu 1 Một số kiến thức 1.1 Không gian Hilbert cực trị phiếm hàm lồi 1.2 Phương pháp điểm gần kề giải bao hàm thức đơn điệu cực đại Thuật toán Douglas - Rachford 21 2.1 Phương pháp Douglas - Rachford 21 2.2 Phương pháp Douglas - Rachford quán tính 29 Kết luận 39 Tài liệu tham khảo 40 ii Lời cảm ơn Luận văn hoàn thành trường Đại học Khoa học - Đại học Thái Nguyên Tác giả xin bày tỏ lòng biết ơn sâu sắc với GS.TS Nguyễn Bường, trực tiếp hướng dẫn tận tình động viên tác giả suốt thời gian nghiên cứu vừa qua Xin chân thành cảm ơn tới thầy, cô giáo Bộ môn Toán - Tin, Phòng Đào tạo Khoa học Quan hệ quốc tế, bạn học viên lớp Cao học Toán K7D trường Đại học Khoa học - Đại học Thái Nguyên, bạn đồng nghiệp tạo điều kiện thuận lợi, động viên tác giả trình học tập nghiên cứu trường Tác giả xin bày tỏ lòng biết ơn sâu sắc tới gia đình người thân khuyến khích, động viên tác giả suốt trình học tập làm luận văn Mặc dù có nhiều cố gắng luận văn khó tránh khỏi thiếu sót hạn chế Tác giả mong nhận ý kiến đóng góp quý báu thầy cô bạn đọc để luận văn hoàn thiện Thái Nguyên, 2015 Trần Ngọc Hảo Học viên Cao học Toán K7D, Trường ĐH Khoa học - ĐH Thái Nguyên Mở đầu Toán tử đơn điệu lĩnh vực giải tích đại nhiều nhà toán học hàng đầu giới nghiên cứu, đặc biệt phải kể đến Browder F E, Rockafellar R T, Minty G J Bài toán xác định không điểm toán tử đơn điệu có nhiều ý nghĩa quan trọng nhiều lĩnh vực khác nhau, khoa học vật lí, tối ưu hóa, toán kinh tế, toán tài Ở đây, ta quan tâm đến toán sau: Tìm x ∈ H cho ∈ A(x) + B(x) Trong A, B toán tử đơn điệu cực đại H Đề tài luận văn "Phương pháp Douglas - Rachford tìm không điểm bao hàm thức đơn điệu" để giải khó khăn việc áp dụng trực tiếp phương pháp điểm gần kề tìm toán tử giải JA+B = (I + r(A + B))−1 , T = A + B Vì đề tài vừa có ý nghĩa mặt lý thuyết, đồng thời vừa có ý nghĩa thực tiễn cao Nội dung luận văn tổng hợp số kết từ hai báo [5] Bot R I, Csetnek E R, Hendrich C (2015), "Inertial Douglas-Rachford splitting for monotone inclusion problems", Applied Mathematics and Computation, Volume 256, P-P 472–487 [12] Svaiter B J (2011), "Weak convergence on Douglas - Rachford method", SIAM Journal on Control and Optimization 49 (1), 280-287 Với ý thức vậy, luận văn chia thành hai chương với nội dung sau: Chương trình bày số kiến thức không gian Hilbert, cực trị phiếm hàm lồi phương pháp điểm gần kề giải bao hàm thức đơn điệu cực đại Chương nội dung luận văn Chương trình bày phương pháp Douglas - Rachford tìm không điểm bao hàm thức đơn điệu phương pháp Douglas - Rachford quán tính Thái Nguyên, ngày 20 tháng 11 năm 2015 Trần Ngọc Hảo Email: tranhaodk10@gmail.com Chương Một số kiến thức Chương ta nhắc lại số kiến thức liên quan tới toán tìm không điểm bao hàm thức đơn điệu Mục 1.1 trình bày kiến thức không gian Hilbert cực trị phiếm hàm lồi Mục 1.2 giới thiệu phương pháp điểm gần kề giải bao hàm thức đơn điệu Các kiến thức chương tổng hợp từ tài liệu [1], [2], [3], [4] 1.1 Không gian Hilbert cực trị phiếm hàm lồi Trước hết ta trình bày số kiến thức không gian Hilbert Định nghĩa 1.1 Cho H không gian véc tơ R, tích vô hướng xác định H ánh xạ , : H × H → R, (x, y) −→ x, y thỏa mãn điều kiện sau đây: (i) x, y = y, x với x, y ∈ H ; (ii) x + y, z = x, z + y, z với x, y, z ∈ H ; (iii) λx, y = λ x, z với x, y ∈ H ; λ ∈ R; (iv) x, x ≥ với x ∈ H x, x = x = Số x, y gọi tích vô hướng hai véc tơ x y H Nhận xét 1.1 Từ định nghĩa suy (i) x, λy = λ y, x ; (ii) x, y + z = x, y + x, z ; (iii) x, = Với x, y, z ∈ H λ ∈ R Định nghĩa 1.2 Cặp (H , , ), H không gian tuyến tính R, , tích vô hướng H gọi không gian tiền Hilbert thực Định lí 1.1 (Bất đẳng thức Cauchy - Schwarz) Trong không gian tiền Hilbert H , với x, y ∈ H ta có bất đẳng thức sau | x, y |2 ≤ x, x y, y (1.1) Chú ý 1.1 Bất đẳng thức định lý gọi bất đẳng thức Schwarz, bất đẳng thức Schwarz dấu xảy x, y phụ thuộc tuyến tính Định lí 1.2 Mọi không gian tiền Hilbert H không gian tuyến tính định chuẩn, với chuẩn xác định công thức x = x, x , x ∈ H (1.2) Chuẩn gọi chuẩn cảm sinh từ tích vô hướng Nhận xét 1.2 Với kí hiệu này, với bất đẳng thức Schwarz viết lại thành | x, y | ≤ x y Như không gian tiền Hilbert xem không gian định chuẩn đầy đủ không đầy đủ Định nghĩa 1.3 Nếu H không gian tiền Hilbert thực đầy đủ chuẩn cảm sinh từ tích vô hướng xác định (1.2) H gọi không gian Hilbert thực Ví dụ 1.1 Rn không gian Hilbert thực với tích vô hướng n xk yk , x, y = k=1 x = (x1 , x2 , , xn ), y = (y1 , y2 , , yn ) ∈ Rn chuẩn cảm sinh n x n = x, x = |xk |2 xk xk = k=1 k=1 Ví dụ 1.2 Xét không gian ∞ L = x = (xn )n ⊂ K| |xn |2 < +∞ , n=1 không gian Hilbert với tích vô hướng ∞ x, y = xn yn n=1 chuẩn cảm sinh ∞ |xn |2 , x = n=1 với x = (xn )n∈N , y = (yn )n∈N ∈ L Ví dụ 1.3 Gọi C[a, b] tập tất hàm giá trị thực liên tục khoảng đóng, hữu hạn [a, b] ⊂ R Trong C[a, b] xét tích vô hướng b x, y = x(t)y(t)dt, a x(t), y(t) ∈ C[a, b] Khi • Không gian C[a, b] với chuẩn x = max |x(t)|, a≤t≤b không gian Banach nên C[a, b] không gian Hilbert • Nhưng không gian C[a, b] với chuẩn  b  21 |x(t)|2 dt , x = a lại không gian Banach nên không gian Hilbert Tiếp theo trình bày định nghĩa tính chất đặc trưng cực trị phiếm hàm lồi Định nghĩa 1.4 Cho C ⊆ Rn khác rỗng f : Rn ⇒ R Một điểm x∗ ∈ C gọi cực tiểu địa phương C tồn lân cận U x∗ cho f (x∗ ) ≤ f (x), ∀x ∈ U ∩ C Điểm x∗ ∈ C gọi cực đại địa phương f (x∗ ) ≥ f (x), ∀x ∈ U ∩ C Nếu f (x∗ ) ≤ f (x), ∀x ∈ C x∗ gọi cực tiểu toàn cục hay cực tiểu tuyệt đối f C Và f (x∗ ) ≥ f (x), ∀x ∈ C x∗ gọi cực đại toàn cục hay cực đại tuyệt đối f C 27 Cùng với (2.12) suy ra: w w ykj −1 − → −b, → x, akj −1 − với j → ∞ Sử dụng hai đẳng thức trên, (2.12) Bổ đề 2.3 (Kết phụ) áp dụng với dãy {(xkj , bkj )}, {(ykj −1 , akj −1 )} ta suy (x, b) ∈ B, (x, −b) ∈ A (x, b) ∈ S(A, B) Chúng ta chứng minh rằng: Dãy {pk } có có nhóm điểm hội tụ yếu tất điểm hội tụ yếu nằm S(A, B) Sử dụng kết Hệ 2.1 Chúng ta suy {pk } có cụm yếu điểm (x, −b) điểm (yếu điểm) thuộc S(A, B) Khi {pk } bị chặn H × H phản xạ, dãy {pk } hội tụ yếu tới điểm (x, −b) tương đương: w w xk − → x, bk − →b với k → ∞ Để kết thúc chứng minh sử dụng đẳng thức (2.12) w w → x, ak − yk − → −b, với k → ∞ Kết phụ Cho X không gian Banach thực với tôpô đối ngẫu X ∗ Cho x ∈ X, x∗ ∈ X ∗ sử dụng kí hiệu x, x∗ = x∗ (x) Một toán tử T : X ⇒ X ∗ gọi đơn điệu x − y, x∗ − y ∗ ≥ với (x, x∗ ), (y, y ∗ ) ∈ T đơn điệu cực đại đơn điệu cực đại họ toán tử đơn điệu với bậc riêng bao hàm thức Bổ đề 2.2 Cho X không gian Banach thực vơi tôpô kép X ∗ Nếu ánh xạ T : X ⇒ X đơn điệu cực đại, (xi , x∗i )i∈I lưới T mà hội tụ theo tô pô yếu tới (x, x∗ ) lim inf xi , x∗i ≥ x, x∗ i→∞ Nếu dấu xảy (x, x∗ ) ∈ T 28 Chứng minh Cho ϕ : X × X ∗ −→ R ϕ(x, x∗ ) = sup x, y ∗ + y, x∗ − y, y ∗ (y,y ∗ )∈T Hàm ϕ hàm cực đại Fitzpatrick [8] T nửa liên tục yếu theo tôpô yếu ϕ(x, x∗ ) ≥ x, x∗ với (x, x∗ ) dấu xảy (x, x∗ ) ∈ T Do xi , x∗i = ϕ(xi , x∗i ) với i ∈ I lim inf xi , x∗i = lim inf ϕ(xi , x∗i ) ≥ ϕ(x, x∗ ) ≥ x, x∗ i→∞ i→∞ Để kết thúc chứng minh, sử dụng ϕ bị chặn tính đối ngẫu kết hợp với tính đối ngẫu tích (x, x∗ ) ∈ T Bổ đề 2.3 Cho X không gian Banach thực Nếu T1 , T2 , ., Tm : X ⇒ X ∗ toán tử đơn điệu cực đại {(xk,i , x∗k,i )}i∈I lưới bị chặn cho (xk,i , x∗k,i ) ∈ Tk với k = 1, , m i ∈ I m x∗k,i −→ x∗ , xk,i − xj,i −→ j, k = 1, .m k=1 w∗ w x∗k,i −→ x∗k →x xk,i − k = 1, ., m, i −→ ∞ (x, x∗k ∈ Tk ) với k = 1, ., m Chứng minh Theo giả thiết m x∗k = x∗ k=1 Đặt αk,i = xk,i , x∗k,i − x, x∗ , với k = 1, , m Thao tác trực trường đại số: m m xk,i , x∗k,i αk,i = k=1 k=0 − x, x∗ i∈I 29 m m xk,i − = x1,i , x∗k,i + x∗k,i x1,i , − x∗ k=0 k=0 + x1,i − x, x∗ Để suy theo giả thuyết bổ đề, m αk,i = lim k=1 Sử dụng phần đầu Bổ đề 2.2 ta có lim sup αk,i ≥ 0, với k = 1, ., m i→∞ Kết hợp hai bất đẳng thức có lim αk,i = với k = 1, , m i→∞ m xk,i , x∗k,i = x, x∗ k=0 Để kết thúc chứng minh, ta sử dụng đẳng thức phần thứ hai bổ đề 2.2 2.2 Phương pháp Douglas - Rachford quán tính Bổ đề 2.4 Cho D ⊆ H tập không rỗng, lồi đóng, T : D → H ánh xạ không giãn cho (xn )n∈N dãy thuộc D x ∈ H cho xn x T xn − xn → n → +∞ Khi x ∈ F ixT Tổng song song hai toán tử A, B : H ⇒ H xác định A B : H ⇒ H , A B = (A−1 + B −1 )−1 Nếu A B đơn điệu, có đặc trưng tập không điểm, tổng Zer(A + B) = JγB (F ix RγA RγB ) ∀γ > (2.13) Kết sau bổ đề trực tiếp sử dụng chứng minh hội tụ thuật toán tách quán tính Douglas - Rachford 30 Bổ đề 2.5 Cho A, B : H ⇒ H toán tử đơn điệu cực đại dãy (xn , un )n∈N ∈ GrA, (yn , )n∈N ∈ GrB cho xn y, x, un u, yn v, un + → xn − yn → n → +∞ Khi x = y ∈ Zer(A + B), (x, u) ∈ GrA (y, v) ∈ GrB Chúng ta khép lại mục với hai kết hội tụ mà có tính định cho chứng minh kết phần sau Bổ đề 2.6 Cho (ϕn )n∈N , (δn )n∈N (αn )n∈N dãy thuộc [0; +∞) cho ϕn+1 ≤ ϕn + αn (ϕn − ϕn−1 ) + δn với n ≥ 1, δn < +∞ tồn n∈N số thực α với ≤ αn ≤ α < với n ∈ N Khi (i) n≥1 [ϕn − ϕn−1 ]+ < +∞, [t]+ = max{t, 0}; (ii) Tồn ϕ∗ ∈ [0; +∞) cho limn→+∞ ϕn = ϕ∗ Cuối cùng, lấy lại kết tiếng hội tụ yếu không gian Hilbert Bổ đề 2.7 Cho C tập không rỗng H (xn )n∈N dãy H cho thỏa mãn hai điều kiện sau: (a) Với x ∈ C, lim n→+∞ xn − x tồn tại; (b) Mọi dãy thứ tự (xn )n∈N hội tụ đến C Khi đó,(xn )n∈N hội tụ yếu tới điểm thuộc C Định lí 2.2 Cho M tập đóng khác rỗng affine H T : M → M toán tử không giãn cho F ixT = ∅ Ta xét sơ đồ lặp sau xn+1 = xn + αn (xn − xn−1 ) + λn [T (xn + αn (xn − xn−1 )) − xn − αn (xn − xn−1 )], ∀n ≥ (2.14) 31 x0 , x1 chọn tùy ý M, (αn )n≥1 không giảm với α1 = ≤ αn ≤ α < với n ≥ λ, σ, δ > cho α2 (1 + α) + ασ δ> − α2 < λ ≤ λn ≤ δ − α[α(1 + α) + ασ + σ] δ[1 + α(1 + α) + ασ + σ] ∀n ≥ (2.15) Khi phát biểu sau đúng: xn+1 − xn (i) < +∞; n∈N (ii) (xn )n∈N hội tụ yếu tới điểm F ixT Chứng minh Chú ý rằng, lựa chọn δ, λn ∈ (0, 1) với n ≥ Hơn nữa, ta nhận thấy rằng, M affine, công thức lặp cung cấp dãy M (i) Ta kí hiệu wn := xn + αn (xn − xn−1 )∀n ≥ Khi công thức lặp trở thành với n ≥ : (2.16) xn+1 = wn + λn (T wn − wn ) Ta cố định phần tử y ∈ F ixT n ≥ Ta có αx + (1 − α)y =α x + α(1 − α) x − y + (1 − α) y , ∀α ∈ R, ∀(x, y) ∈ H × H Kết hợp với tính không giãn T ta có xn+1 −y = (1−λn ) wn −y +λn T wn −T y −λn (1−λn ) T wn −wn ≤ wn − y (2.17) − λn (1 − λn ) T wn − wn Suy wn − y = (1 + αn )(xn − y) − αn (xn−1 − y) 2 32 = (1 + αn ) xn − y − αn xn−1 − y) + αn (1 + αn ) xn − xn−1 , theo (2.17) ta thu xn+1 − y 2 + αn xn−1 − y) + αn (1 − αn ) xn − xn−1 ) − (1 + αn ) xn − y ≤ −λn (1 − λn ) T wn − wn (2.18) Hơn nữa, ta có T wn − w n = ≥ λ2n λ2n = λn (xn+1 − xn ) + xn+1 − xn xn+1 − xn + + + αn2 λ2n αn2 λ2n λn (xn−1 − xn ) xn − xn−1 ) xn − xn−1 αn (−ρn xn+1 − xn λ2n ta kí hiệu ρn = αn − +2 αn λ2n xn+1 − xn , xn−1 − xn (2.19) xn − xn−1 ), ρn αn + δλn Từ (2.18) (2.19) suy bất đẳng thức ( lưu ý λn ∈ (0, 1)) xn+1 − y ≤ − (1 + αn ) xn − y (1 − λn )(αn ρn − 1) λn xn+1 − xn 2 + αn xn−1 − y) + γn xn − xn−1 , (2.20) γn := αn (1 + αn ) + αn (1 − λn ) Lại tính đến lựa chọn ρn ta có δ= − ρn αn ρn λ n − ρn αn ρn λ n > (2.21) 33 theo (2.21) suy γn := αn (1 + αn ) + αn (1 − λn )δ ≤ α(1 + α) + αδ ∀n ≥ (2.22) Sau ta sử dụng vài kỹ thuật, kết hợp với thiết lập Ta định nghĩa dãy ϕn := xn − y γn xn − xn−1 2 với n ∈ N µn := ϕn − αn ϕn−1 + với n ≥ Sử dụng tính đơn điệu (αn )n≥1 thực tế ϕn ≥ với n ∈ N, ta có µn+1 −µn ≤ ϕn+1 −(1+αn )ϕn +αn ϕn−1 +γn+1 xn+1 −xn −γn xn −xn−1 , mà theo (2.20)  µn+1 − µn ≤  (1 − λn )(αn ρn − 1) λn  + γn+1  xn − xn−1 ∀n ≥ (2.23) Ta đánh giá (1 − λn )(αn ρn − 1) λn + γn+1 ≤ −σ ∀n ≥ (2.24) Cho n ≥ Thật theo cách chọn ρn , ta có (1 − λn )(αn ρn − 1) λn + γn+1 ≤ −σ ⇔ λn (γn+1 + σ) + (αn ρn − 1)(1 − λn ) ≤ ⇔ λn (γn+1 + σ) + δλn (1 − λn ) αn + δλn ≤0 ⇔ (αn + δλn )(γn+1 + σ) + δλn ≤ δ Do sử dụng (2.22) ta có (αn + δλn )(γn+1 + σ) + δλn ≤ (α + δλn )(α(1 + α) + αδ + σ) + δλn ≤ δ, 34 bất đẳng thức cuối suy cách tính đến cận xét với (λn )n≥1 (2.15) Do đánh giá (2.24) Từ (2.23) (2.24) ta thu µn+1 − µn ≤ −σ xn+1 − xn (2.25) ∀n ≥ Dãy (µn )n≥1 không tăng ràng buộc (αn )n≥1 suy (2.26) − αϕn−1 ≤ ϕn − αϕn−1 ≤ µn ≤ µ1 ∀n ≥ Ta thu n−1 n k ϕn ≤ α ϕ0 + µ n α ≤ α ϕ0 + k=0 µ1 ∀n ≥ 1, 1−α ta lưu ý µ1 = α1 ≥ (do α1 = 0) Kết hợp (2.25) (2.26), với ∀n ≥ ta có n xk+1 − xk σ ≤ µ1 − µn+1 ≤ µ1 + αϕn ≤ α n+1 ϕ0 + k=1 Chứng tỏ n∈N xn+1 − xn µ1 1−α , < +∞ (ii) Ta chứng minh điều cách sử dụng kết Opial Bổ đề 2.7 Ta chứng minh với y ∈ F ixT tùy ý, biểu thức (2.20) Theo (i), (2.22) Bổ đề 2.6 ta suy lim n→+∞ xn − y tồn Mặt khác cho x điểm yếu dãy (xn )n∈N , tức có dãy (xnk )k∈N cho xnk x k → +∞ Theo (i) định nghĩa wn cận cho (αn )n≥1, ta có (wnk ) x k → +∞ Theo (2.16) ta có T w n − wn = λn xn+1 − wn ≤ λ xn+1 − wn 35 ≤ ( xn+1 − xn + α xn − xn−1 ) λ (2.27) Do theo (i) ta thu T wnk − wnk → k → +∞ Áp dụng Bổ đề 2.4 cho dãy (wnk )k∈N ta suy x ∈ F ixT Vì hai khẳng định Bổ đề 2.7 kiểm chứng, suy (wnk )k∈N hội tụ yếu tới điểm F ixT Chú ý 2.1 Điều kiện α1 = sử dụng để chắn µ1 ≥ 0, mà cần chứng minh Sự thay x0 = x1 trường hợp giả định α1 = không cần thiết Chú ý 2.2 Giả sử α = ( bắt buộc αn = 0∀n ≥ 1), sơ đồ lặp định lý trước tầm thường xn+1 = xn + λn (T xn − xn ) ∀n ≥ (2.28) Ta nhớ hội tụ sơ đồ lặp chứng minh giả thiết tổng quát hơn, cụ thể M tập đóng, khác rỗng lồi λn (1 − λn ) = +∞ n∈N Định lí 2.3 (Thuật toán tách Douglas - Rachford quán tính) Cho A, B : H ⇒ H toán tử đơn điệu cực đại cho (A + B) = φ Xét thuật toán lặp sau (∀n ≥ 1)    y = JγB [xn + αn (xn − xn−1 )]   n zn = JγA [2yn − xn − αn (xn − xn−1 )]     xn+1 = xn + αn (xn − xn−1 ) + λn (zn − yn ) γ > 0, x0 , x1 chọn tùy ý H , (αn )n≥1 không giảm với α1 = ≤ αn ≤ α < với n ≥ λ, σ, δ cho α2 (1 + α) + ασ δ> − α2 < λ ≤ λn ≤ δ − α[α(1 + α) + ασ + σ] δ[1 + α(1 + α) + ασ + σ] ∀n ≥ 36 Khi tồn x ∈ F ix(RγA RγB ) cho phát biểu sau đúng: (i) JγB x ∈ zer(A + B); (ii) n∈N xn+1 − xn < +∞ (iii) (xn )n∈N hội tụ yếu tới x; (iv) yn − zn → n → +∞; (v) (yn )n≥1 hội tụ yếu tới JγB x; (vi) (zn )n≥1 hội tụ yếu tới JγB x; (vii) Nếu A B đơn điệu, (yn )n≥1 (zn )n≥1 hội tụ mạnh tới điểm zer(A + B) Chứng minh Ta lại sử dụng ký hiệu wn = xn +αn (xn −xn−1 ) với n ≥ Sơ đồ lặp phát biểu định lý trình bày sau với n ≥ xn+1 = wn + λn [JγA ◦ (2JγB − Id)wn − JγB wn ]    Id + RγA Id + RγB    = w n + λn ◦ RγB wn − wn  2 = wn + λn (T wn − wn ), (2.29) T := RγA ◦ RγB : H → H toán tử không giãn Từ (2.13) ta có zer(A + B) = JγA (F ixT ), ta có F ixT = φ Áp dụng Định lý 2.2, tồn x ∈ F ixT cho (i)- (iii) (iv) từ Định lý 2.2 (2.29) suy zn −yn = (T wn −wn ) với n ≥ (v) ta chứng minh (yn )n≥1 bị chặn JγB x điểm yếu (yn )n≥1 Từ suy điều sau cách sử dụng JγB không giãn, với n ≥ ta có yn −y1 = JγB wn −JγB w1 ≤ wn −w1 = xn −x1 +αn (xn −xn−1 ) 37 Vì (xn )n≤1 bị chặn (iii) (αn )n≥1 bị chặn, nên dãy (yn )n≥1 dãy bị chặn Bây cho y điểm dãy (yn )n≥1 , tức có dãy (ynk )k∈N cho ynk y k → +∞ Ta sử dụng ký hiệu un := 2yn − wn − zn := wn − yn ∀n ≥ Từ định nghĩa suy (zn , un ) ∈ Gr(γA), (yn , ) ∈ Gr(γB) un + = yn − zn , ∀n ≥ (2.30) Hơn nữa, (ii), (iii) (iv) ta suy znk y, wnk x, unk y − x vnk x − y k → ∞ Lại sử dụng (ii) Bổ đề 2.5 ta suy y ∈ zer(γA + γB) = zer(A + B), (y, y − x) ∈ Gr(γA) (y, x − y) ∈ GrγB Như hệ quả, y = JγB x (vi) Suy từ (iv) (v) (vii) Ta chứng minh phát biểu trường hợp A đơn điệu đều, trường hợp B hoàn thành, điều kiện tương tự Ký hiệu y = JγB x Tồn hàm tăng φA : [0, +∞] → [0, +∞] mà triệt tiêu γφA( zn − y ) ≤ zn − y, un − y + x ∀n ≥ Hơn nữa, B đơn điệu ta có ≤ yn − y, − x + y = yn − y, yn − zn − un − x + y ∀n ≥ Lấy tổng hai biểu thức ta thu γφA( zn −y ) ≤ zn −yn , un −yn +x = zn −yn , yn −zn −wn +x ∀n ≥ 38 Vì zn − yn → wn x n → +∞, từ bất đẳng thức ta có lim φA( zn − y ) = 0, zn − y yn → y n → +∞ n→+∞ Chú ý 2.3 Trong trường hợp α = 0, bắt buộc αn = ∀n ≥ 1, sơ đồ lặp Định lý 2.3 trở thành phương pháp Douglas - Rachford cổ điển    y = JγB xn   n (∀n ≥ 1) zn = JγA (2yn − xn )     xn+1 = xn + λn (zn − yn ) hội tụ xảy giả thiết n∈N λn (1 − λn ) = +∞ Chú ý 2.4 Trong trường hợp Bx = ∀x ∈ H , sơ đồ lặp Định lý 2.3 trở thành xn+1 = λn JγA (xn +αn (xn −xn−1 ))+(1−λn )(xn +αn (xn −xn−1 )) ∀n ≥ 1, thuật toán điểm xấp xỉ bối cảnh giải toán đơn điệu ∈ Ax Kết luận chương Chương trình bày phương pháp phân rã Douglas-Rachford tìm không điểm bao hàm thức đơn điệu để chứng minh dãy sinh phương pháp hội tụ yếu tới nghiệm toán bao hàm thức 39 Kết luận Những vấn đề luận văn • Nhắc lại số khái niệm tính chất không gian Hilbert, đồng thời trình bày cực trị phiếm hàm lồi thuật toán điểm gần kề tìm nghiệm bao hàm thức đơn điệu • Phần trọng tâm luận văn trình bày thuật toán Douglas-Rachford, chứng minh dãy sinh phương pháp hội tụ yếu tới nghiệm toán bao hàm thức phương pháp Douglas-Rachford quán tính Mặc dù tác giả cố gắng nghiêm túc trình học tập tìm hiểu thời gian có hạn khả hạn chế nên chắn luận văn có nhiều thiếu sót Tác giả mong nhận nhiều ý kiến đóng góp quý thầy giáo, cô giáo bạn bè đồng nghiệp để luận văn hoàn thiện 40 Tài liệu tham khảo Tiếng Việt [1] Nguyễn Văn Hiền, Lê Dũng Mưu (2003), Nhập môn Giải tích lồi Ứng dụng, Viện toán học, Hà Nội [2] Đỗ Văn Lưu, Nguyễn Đức Lạng (2010), Giáo trình Giải tích hàm, NXB Đại học Quốc gia, Hà Nội [3] Nguyễn Thị Na (2013), Về toán tử đơn điệu không gian Hilbert, luận văn thạc sĩ, trường Đại học Sư phạm - Đại học Thái Nguyên [4] Hoàng Tụy (2003), Hàm thực Giải tích hàm, NXB Đại học Quốc gia, Hà Nội Tiếng Anh [5] Bot R I, Csetnek E R, Hendrich C (2015), "Inertial DouglasRachford splitting for monotone inclusion problems", Applied Mathematics and Computation, Volume 256, P-P 472–487 [6] Jr, Douglas J and Rachford H H (1965), "On the numerical solution of heat conduction problems in two and three space variables" Trans Amer Math Soc., 82:421-439 41 [7] J Eckstein and F Svaiter (2008), "A family of projective splitting methods for the sum of two maximal monotone operators" Math Program., 111 (1-2, Ser B): 173-199 [8] Fitzpatrick S (1988), "Representing monotone operators by convex function", In Workshop-Miniconference on Functional Analysis and Optimization, volume 20 of Proc Centre Math Anal Austral Nat Univ pages 59-65 Austral Nat Univ Canberra [9] Lions P L and Mercier B (1979), "Splitting algorithms for the sum of the sum of two nonlinear operators" SIAM J Anal., 16 (6): 964-979 [10] Minty G J (1962), "Monptone (nonlinear) operators in Hilbert space" Duke Math J., 29:341-346 [11] Opial Z (1967), "Weak convergence of the sequence of successive approximations for nonexpansive mappings", Bull Amer Math Soc, 73:591-597 [12] Svaiter B J (2011), "Weak convergence on Douglas - Rachford method", SIAM Journal on Control and Optimization 49 (1), 280-287 ... phương pháp phân rã Douglas - Rachford 21 Chương Thuật toán Douglas - Rachford Trong chương trình bày phương pháp Douglas - Rachford tìm không điểm bao hàm thức đơn điệu Mục 2.1 giới thiệu phương. .. thức không gian Hilbert, cực trị phiếm hàm lồi phương pháp điểm gần kề giải bao hàm thức đơn điệu cực đại Chương nội dung luận văn Chương trình bày phương pháp Douglas - Rachford tìm không điểm bao. .. quan tới toán tìm không điểm bao hàm thức đơn điệu Mục 1.1 trình bày kiến thức không gian Hilbert cực trị phiếm hàm lồi Mục 1.2 giới thiệu phương pháp điểm gần kề giải bao hàm thức đơn điệu Các kiến