Phương pháp lặp giải bài toán tìm nghiệm có chuẩn nhỏ nhất

Chia sẻ: ViWashington2711 ViWashington2711 | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

31
lượt xem 2
download

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

Bài viết trình bày việc nghiên cứu bài toán hai cấp trong không gian Hilbert thực: tìm nghiệm có chuẩn nhỏ nhất trên tập nghiệm của bài toán bất đẳng thức biến phân. Chúng tôi đề xuất một phương pháp lặp mới giải bài toán hai cấp này, đồng thời thiết lập sự hội tụ mạnh của phương pháp.

Chủ đề:

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

Lưu

Nội dung Text: Phương pháp lặp giải bài toán tìm nghiệm có chuẩn nhỏ nhất

ISSN: 1859-2171 TNU Journal of Science and Technology 208(15): 169 - 175 e-ISSN: 2615-9562 PHƯƠNG PHÁP LẶP GIẢI BÀI TOÁN TÌM NGHIỆM CÓ CHUẨN NHỎ NHẤT Nguyễn Tất Thắng Đại học Thái Nguyên TÓM TẮT Trong bài báo này chúng tôi nghiên cứu bài toán hai cấp trong không gian Hilbert thực: tìm nghiệm có chuẩn nhỏ nhất trên tập nghiệm của bài toán bất đẳng thức biến phân. Chúng tôi đề xuất một phương pháp lặp mới giải bài toán hai cấp này, đồng thời thiết lập sự hội tụ mạnh của phương pháp. Từ khóa: Bất đẳng thức biến phân; không gian Hilbert; chuẩn nhỏ nhất; bài toán hai cấp; toán tử đơn điệu. Ngày nhận bài: 23/9/2019; Ngày hoàn thiện: 23/10/2019; Ngày đăng: 27/11/2019 ITERATIVE METHOD FOR SOLVING A MINIMUM NORM PROBLEM Nguyen Tat Thang Thai Nguyen University ABSTRACT In this paper we study the problem of finding a minimum norm solution over the set of solutions of a variational inequality in Hilbert spaces. In order to solve this bilevel problem, we propose a new iterative method and establish a strong convergence theorem for it. Keywords: Variational inequality; Hilbert space; minimum norm; bilevel problem; monotone operator. Received: 23/9/2019; Revised: 23/10/2019; Published: 27/11/2019 Email: thangnt@tnu.edu.vn http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn 169 1 Giới thiệu Cho H là một không gian Hilbert thực với tích vô hướng h·, ·i và chuẩn k · k. Cho C là một tập con lồi đóng khác rỗng của H. Cho ánh xạ G : C → H (thường được gọi là ánh xạ giá). Bài toán bất đẳng thức biến phân (đơn trị) trong H được phát biểu như sau: Tìm x∗ ∈ C sao cho hG(x∗ ), x − x∗ i ≥ 0 ∀x ∈ C. (1) Ký hiệu ΩG là tập nghiệm của bài toán (1). Bài toán bất đẳng thức biến phân (1) được giới thiệu lần đầu tiên vào năm 1966 khi Philip Hartman và Guido Stampacchia công bố những nghiên cứu đầu tiên của mình về bất đẳng thức biến phân liên quan đến việc giải các bài toán biến phân, bài toán điều khiển tối ưu và các bài toán biên trong lý thuyết phương trình đạo hàm riêng. Bài toán bất đẳng thức biến phân đã và đang thu hút được nhiều sự quan tâm của các nhà toán học vì các mô hình của nó chứa nhiều bài toán quan trọng của một số lĩnh vực khác nhau trong toán học ứng dụng như tối ưu hóa, bài toán điểm bất động, lý thuyết trò chơi, cân bằng mạng lưới giao thông . . . (xem [2,4,5,10]). Nhiều phương pháp giải bài toán bất đẳng thức biến phân đã xây dựng, trong đó phương pháp chiếu đóng vai trò quan trọng vì sự đơn giản và thuận lợi trong quá trình tính toán . . . (xem [1, 6, 7]). Bài toán tìm nghiệm có chuẩn nhỏ nhất là bài toán tìm phần tử x∗ ∈ C sao cho kx∗ k ≤ kxk ∀x ∈ C. (2) Trong bài báo này, chúng tôi đề xuất một phương pháp lặp mới giải bài toán (2) trong trường hợp C là tập nghiệm của bài toán bất đẳng thức biến phân (1), nghĩa là tìm phần tử x∗ ∈ ΩG sao cho kx∗ k ≤ kxk ∀x ∈ ΩG . (3) Ký hiệu Ω là tập nghiệm của bài toán (3). Giả thiết rằng Ω 6= ∅. 2 Một số kiến thức bổ trợ Để xây dựng dãy lặp và chứng minh định lý hội tụ mạnh, ta cần một số kiến thức bổ trợ sau. Cho C là một tập con, lồi, đóng, khác rỗng của không gian Hilbert thực H. Hình chiếu của một điểm x ∈ H trên C, ký hiệu PC (x), là một điểm thuộc C và gần điểm x nhất, được xác định bởi PC (x) = arg min {kx − yk : y ∈ C}. (4) Hình chiếu PC (x) của x trên C luôn tồn tại và duy nhất và PC là một ánh xạ không giãn, nghĩa là kPC (x) − PC (y)k ≤ kx − yk. Một ánh xạ G : C → H được gọi là η-đơn điệu mạnh ngược trên C, nếu hG(x) − G(y), x − yi ≥ ηkG(x) − G(y)k2 ∀x, y ∈ C, η > 0. (5) Ký hiệu Fix(S) là tập điểm bất động của ánh xạ S : C → C, nghĩa là Fix(S) = {x∗ ∈ C : S(x∗ ) = x∗ }. Bổ đề 2.1 (xem [3]) Cho C là một tập con lồi đóng trong không gian Hilbert thực H, S : C → H là một ánh xạ không giãn. Khi đó nếu Fix(S) 6= ∅ thì ánh xạ I H − S là ánh xạ nửa đóng tại y ∈ H, nghĩa là với mọi dãy {xk } ⊂ C hội tụ yếu đến phần tử x¯ ∈ C và dãy {(I H − S)(xk )} hội tụ mạnh đến y thì (I H − S)(¯x) = y. Bổ đề 2.2 (xem [8]) Cho {sn } là dãy số thực không âm thỏa mãn sn+1 ≤ (1 − βn )sn + γn với mọi n ≥ 0, trong đó {βn } và {γn } là các dãy số thực thỏa mãn các điều kiện sau: P∞ (i) {βn } ⊂ (0, 1) và n=0 βn = ∞, γn P∞ (ii) lim supn→∞ βn ≤ 0 hoặc n=0 |βn γn | < ∞. Khi đó limn→∞ sn = 0. 3 Kết quả chính Cho H là một không gian Hilbert thực, C là một tập con lồi đóng khác rỗng của H, G : H → H là một ánh xạ. Ta xây dựng dãy lặp {xk } như sau: y k = PC (xk − λG(xk )), xk+1 = (1 − µαk )y k , (6) trong đó λ, µ là các số thực không âm và {αk } là dãy tham số thực. Sự hội tụ của phương pháp lặp (6) được cho trong định lý sau đây. Định lý 3.1 Cho C là một tập con, lồi, đóng, khác rỗng của không gian Hilbert thực H và ánh xạ G : H → H là ánh xạ η-đơn điệu mạnh ngược trên H. Nếu các số thực λ, µ và dãy tham số thực {αk } thỏa mãn các điều kiện (C1) 0 < λ ≤ 2η, 0 < µ < 2, (C2) 0 < αk ≤ min{1, τ1 }, τ = 1 − |1 − µ|, ∞ 1 1 − αk = ∞, P (C3) lim αk = 0, lim αk+1 = 0, αk k→∞ k→∞ k=0 thì dãy {xk } được xác định bởi (6) hội tụ mạnh đến nghiệm duy nhất của bài toán (3). Chứng minh. Ta xây dựng ánh xạ Sk : H → H như sau Sk (x) = PC (x − λG(x)) − µαk [PC (x − λG(x))] ∀x ∈ H. (7) Sử dụng tính η-đơn điệu mạnh ngược của ánh xạ G, tính chất không giãn của phép chiếu PC ta nhận được kPC (x − λG(x)) − PC (y − λG(y))k2 ≤ kx − λG(x) − y + λG(y)k2 = kx − yk2 + λ2 kG(x) − G(y)k2 − 2λhx − y, G(x) − G(y)i ≤ kx − yk2 + λ(λ − 2η)kG(x) − G(y)k2 ≤ kx − yk2 ∀x, y ∈ H. (8) Từ đây suy ra kSk (x)−Sk (y)k = kPC (x−λG(x))−µαk [PC (x−λG(x))]−PC (y −λG(y))+µαk [PC (y −λG(y))]k ≤ (1 − αk τ )kx − yk, (9) với τ = 1 − |1 − µ| ∈ (0, 1] (xem [9]). Do đó, Sk là ánh xạ co trên H. Theo Nguyên lý ánh xạ co Banach, tồn tại điểm bất động ξ k thỏa mãn Sk (ξ k ) = ξ k . Với mỗi xˆ ∈ ΩG , đặt ( ) xk µkˆ C = x ∈ H : kx − xˆk ≤ , τ kết hợp với tính chất không giãn của phép chiếu PC , suy ra ánh xạ Sk PC là ánh xạ co trên H. Do vậy, tồn tại duy nhất điểm z k thỏa mãn Sk [PC (z k )] = z k . Đặt z¯k = PC (z k ), từ (7) và (9) ta suy ra kz k − xˆk = kSk (¯ z k ) − xˆk ≤ kSk (¯ z k ) − Sk (ˆ x)k + kSk (ˆ x) − xˆk z k ) − Sk (ˆ = kSk (¯ x)k + kSk (ˆ x) − PC (ˆ x − αk G(ˆ x))k xk µkˆ xk µkˆ z k − xˆk + µαk kPC (ˆ ≤ (1 − αk τ )k¯ x − αk G(ˆ x))k ≤ (1 − αk τ ) + µαk kˆ xk = . τ τ Điều này chỉ ra rằng z k ∈ C và Sk [PC (z k )] = Sk (z k ) = z k . Do vậy, ξ k = z k ∈ C. Mặt khác, với bất kỳ dãy con {ξ ki } của dãy {ξ k } thỏa mãn ξ ki * ξ¯ , lim αk = 0, k→∞ khi i → ∞ kPC (ξ ki −λG(ξ ki ))−ξ ki k = kPC (ξ ki −λG(ξ ki ))−Ski (ξ ki )k = µαki kPC (ξ ki −λG(ξ ki ))k → 0 (10) ¯ Theo (8), ánh xạ PC (· − αk G(·)) là không giãn trên H, kết hợp với (10), Bổ đề 2.1 và ξ ki * ξ, suy ra PC (ξ¯ − λG(ξ)) ¯ = ξ.¯ Vậy ξ¯ ∈ ΩG . Tiếp theo, ta chứng minh lim ξ kj = x∗ ∈ Ω. j→∞ Thật vậy, đặt z¯k = PC (ξ k − λG(ξ k )), v ∗ = (µ − 1)(x∗ ), v k = (µ − 1)(¯ z k ). Vì Skj (ξ kj ) = ξ kj và x∗ = PC (x∗ − λG(x∗ )) nên ta có (1 − αkj )(ξ kj − z¯kj ) + αkj (ξ kj + v kj ) = 0 và (1 − αkj )[I − PC (· − λG(·))](x∗ ) + αkj (x∗ + v ∗ ) = αkj (x∗ + v ∗ ). Khi đó, −αkj hx∗ +v ∗ , ξ kj −x∗ i = (1−αkj )hξ kj −x∗ −(¯ z kj −x∗ ), ξ kj −x∗ i+αkj hξ kj −x∗ +v kj −v ∗ , ξ kj −x∗ i. (11) Theo bất đẳng thức Schwarz, ta có hξ kj − x∗ − (¯ z kj − x∗ ), ξ kj − x∗ i ≥ kξ kj − x∗ k2 − k¯ z kj − x∗ kkξ kj − x∗ k ≥ kξ kj − x∗ k2 − kξ kj − x∗ k2 = 0, (12) và hξ kj − x∗ + v kj − v ∗ , ξ kj − x∗ i ≥ kξ kj − x∗ k2 − kv kj − v ∗ kkξ kj − x∗ k ≥ kξ kj − x∗ k2 − (1 − τ )kξ kj − x∗ k2 = τ kξ kj − x∗ k2 . (13) Kết hợp (11), (12) và (13), ta được ¯ −τ kξ kj −x∗ k2 ≥ hx∗ +v ∗ , ξ kj −x∗ ) = µhx∗ , ξ kj −x∗ i = µhx∗ , ξ kj −ξi+µhx ∗ ¯ ¯ , ξ−x∗ i ≥ µhx∗ , ξ kj −ξi. Vậy τ kξ kj − x∗ k2 ≤ µhx∗ , ξ¯ − ξ kj i. Cho j → ∞, dãy {ξ kj } hội tụ mạnh đến x∗ . Khi đó, tồn tại một dãy con {ξ kj } của dãy {ξ k } thỏa mãn 0 ≤ lim inf kξ k − x∗ k ≤ lim sup kξ k − x∗ k = lim kξ kj − x∗ k = 0. k→∞ k→∞ j→∞ Vậy, dãy {ξ k } hội tụ mạnh đến điểm x∗ ∈ Ω. Mặt khác, theo (9), ta xét kxk − ξ k k ≤ kxk − ξ k−1 k + kξ k−1 − ξ k k = kSk−1 (xk−1 ) − Sk−1 (ξ k−1 )k + kξ k−1 − ξ k k ≤ (1 − αk−1 τ )kxk−1 − ξ k−1 k + kξ k−1 − ξ k k. (14) Từ đánh giá kξ k−1 − ξ k k = kSk−1 (ξ k−1 ) − Sk (ξ k )k = k(1 − αk )¯ z k − αk v k − (1 − αk−1 )¯ z k−1 + αk−1 v k−1 k z k − z¯k−1 ) − αk (v k − v k−1 ) + (αk−1 − αk )(¯ = k(1 − αk )(¯ z k−1 + v k−1 )k z k − z¯k−1 k + αk kv k − v k−1 k + |αk−1 − αk |µk¯ ≤ (1 − αk )k¯ z k−1 k z k − z¯k−1 k + αk |1 − µ|kξ k − ξ k−1 k + |αk−1 − αk |µk¯ ≤ (1 − αk )k¯ z k−1 k, ta suy ra αk τ kξ k−1 − ξ k k ≤ |αk−1 − αk |µk¯ z k−1 k, hay z k−1 k µ|αk−1 − αk |k¯ kξ k − ξ k−1 k ≤ . (15) αk τ Thay (15) vào (14), ta được z k−1 k µ|αk−1 − αk |k¯ kxk − ξ k k ≤ (1 − αk−1 τ )kxk−1 − ξ k−1 k + . αk τ Đặt µ|αk − αk+1 |k¯ zk k δk = , k ≥ 0. αk αk+1 τ 2 Khi đó kxk − ξ k k ≤ (1 − αk−1 τ )kxk−1 − ξ k−1 k + αk−1 τ δk−1 ∀k ≥ 1. z k } bị chặn, giả sử k¯ Vì dãy {¯ z k k ≤ M với mọi k ≥ 0, ta có µ|αk − αk+1 |k¯ zk k µM 1 1 lim δk = lim ≤ lim − = 0. (16) αk αk+1 τ 2 τ 2 k−→∞ αk+1 αk k→∞ k→∞ Do đó, theo Bổ đề 2.2 suy ra lim kxk − ξ k k = 0. k→∞ Mặt khác, theo chứng minh trên, dãy {ξ k } hội tụ mạnh đến nghiệm x∗ , suy ra dãy {xk } cũng hội tụ mạnh đến nghiệm duy nhất x∗ của bài toán (3). http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn 5 TÀI LIỆU THAM KHẢO [1]. Y. Censor, A. Gibali, S. Reich, "The subgradient extragradient method for solving variational inequalities in Hilbert space", J. Optim. Theory Appl., 148(2), pp. 318–335, 2011. [2]. R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer, New York, NY, 1984. [3]. K. Goebel, W.A. Kirk, Topics on metric fixed point theory, Cambridge University Press, Cambridge, England, 1990. [4]. P. Jaillet, D. Lamberton, B. Lapeyre, “Variational Inequalities and the Pricing of American Options”, Acta Applicandae Mathematica, 21, pp. 263–289, 1990. [5]. D. Kinderlehrer, and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, NY, 1980. [6]. R. Kraikaew, S. Saejung, "Strong convergence of the Halpern subgradient extra-gradient method for solving variational inequalities in Hilbert spaces", J. Optim. Theory Appl., 163(2), pp. 399–412, 2014. [7]. Y.V. Malitsky, "Projected reflected gradient methods for monotone variational inequalities.", SIAM J. Optim., 25(1), pp. 502–520, 2015. [8]. H.K. Xu, "Iterative algorithms for nonliner operators", J. London Math. Soc., 66, pp. 240–256, 2002. [9]. I. Yamada, "The hybrid steepest descent method for the variational inequality problem over the variational inequality problem over the intersection of fixed point sets of nonexpansive mappings", In inherently parallel algorithm for feasibility and optimization and their applications edited by: D. Butnariu, Y. Censor, and S. Reich, Elsevier., 473–504, 2001. [10]. E. Zeidler, Nonlinear Functional Analysis and Its Applications, III: Variational Methods and Applications, Springer, New York, 1985. 176 http://jst.tnu.edu.vn; Email: jst@tnu.edu.vn