Luận văn Phương pháp chiếu giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh (Chuyên ngành: Toán ứng dụng)

lời cảm ơn tới gia đình, các bạn, các anh, các chị của lớp cao học Toán khóa 2013 - 2015 và giành riêng lời cảm ơn cho gia đình Toán Ứng Dụng. Là em út của nhóm, nên luôn được mọi người quan tâm nhiều hơn. Thời gian học cùng các anh chị đã cho em những kỷ niệm đẹp, được học những điều hay cũng như những kiến thức thú vị. Mặc dù đã có nhiều cố gắng, nhưng luận văn không tránh khỏi những thiếu sót. Em mong nhận được ý kiến đóng góp của các thầy, cô và bạn đọc để luận văn được hoàn thiện hơn. Hà Nội, ngày 3 tháng 10 năm 2015 Học viên Ngô Thị Tho 2 LỜI MỞ ĐẦU Năm 1966, Hatman và Stampacchia đã công bố những nghiên cứu đầu tiên của mình về bài toán bất đẳng thức biên phân, liên quan tới việc giải các bài toán biến phân, bài toán điều kiển tối ưu và các bài toán biên có dạng của phương trình đạo hàm riêng. Năm 1980, Kinderlehrer và Stampacchia cho xuất bản cuốn sách "An Introduction to Variational Inequalities and Their Applications", giới thiệu bài toán biến phân trong không gian vô hạn chiều và ứng dụng của nó. Năm 1984, cuốn sách "Variational and Quasivariational Inequalities: Applications to Free Boundary Problems" của C. Baiocci và A. Capelo đã áp dụng bất đẳng thức biến phân và tựa biến phân để giải các bài toán không có biên. Hiện nay bài toán bất đẳng thức biến phân đã phát triển thành nhiều dạng khác nhau,như là: bất đẳng thức biến phân vectơ, tựa bất đẳng thức biến phân, giả bất đẳng thức biến phân, bất đẳng thức biến phân ẩn, bất đẳng thức biến phân suy rộng.... Bài toán này đã thu hút được sự quan tâm của nhiều nhà toán học. Vì 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 trong toán học cũng như thực tế như tối ưu hóa, bài toán bù, lý thuyết trò chơi, cân bằng Nash, cân bằng mạng giao thông, cân bằng di trú.... Một trong những hướng nghiên cứu quan trọng của bất đẳng thức biến phân là việc xây dựng các phương pháp giải. Dựa trên tính chất của kiểu đơn điệu G. Cohen đã nghiên cứu phương pháp nguyên lý bài toán phụ. Ngoài ra còn có phương pháp hiệu chỉnh Tikhonov, phương pháp chiếu, phương pháp điểm trong. Những phương pháp này khá hiệu quả, dễ thực hiện trên máy tính nhưng sự hội tụ của chúng chỉ được đảm bảo trên cơ sở các giả thiết khác về tính chất đơn điệu. Có nhiều phương pháp chiếu khác nhau, như là: phương pháp chiếu cơ bản, phương pháp chiếu dưới đạo hàm, và phương pháp chiếu siêu phẳng. Mỗi phương pháp giải quyết một lớp các bài toán bất đẳng thức biến phân nhất định. Do đó sự hội tụ của thuật toán được đảm bảo. Luận văn trình bày phương pháp chiếu dưới đạo hàm tăng cường và chiếu cơ bản cải biên để giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh. Các phương pháp này tạo ra một dãy hội tụ của các điểm lặp dễ dàng tính được. Chúng đều hội tụ 3 tới nghiệm duy nhất của bài toán. Luận văn gồm hai chương: Chương 1: Bài toán bất đẳng thức biến phân, được chia làm hai phần: • Phần 1: Nhắc lại một số kiến thức trong Giải tích hàm và Giải tích lồi, như là: hội tụ mạnh và yếu trong không gian Hilbert, toán tử chiếu, tính liên tục của hàm lồi, đạo hàm và dưới vi phân của hàm lồi. • Phần 2: Phát biểu bài toán, trình bày một số khái niệm và mô hình minh họa cho bài toán. Sau đó, chứng minh sự tồn tại và tính duy nhất nghiệm của bài toán. Chương 2: Phương pháp chiếu giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh. Nội dung chính của chương là trình bày hai thuật toán chiếu dưới đạo hàm tăng cường và thuật toán chiếu cơ bản cải biên để giải bài toánVI(K,F). Phát biểu và chứng minh các định lý về sự hội tụ của dãy lặp tạo bởi các thuật toán đó. Đưa ra một số ví dụ chứng minh rằng các điều kiện của định lý tồn tại nghiệm là cần thiết. Nếu bỏ đi một trong các điều kiện đó, dãy lặp sẽ không hội tụ tới nghiệm duy nhất của bài toán. 4 Chương 1 Bài toán bất đẳng thức biến phân Trong chương này, chúng ta sẽ nhắc lại một số kết quả của Giải tích hàm có liên quan tới sự hội tụ mạnh và hội tụ yếu của một dãy số. Nhắc lại một số khái niệm và định lý cơ bản của Giải tích lồi, như là: định nghĩa và tính chất của toán tử chiếu, tính liên tục, đạo hàm và dưới vi phân của một hàm lồi, Định lý tách, Định lý Moreau- Rockafellar. Phần sau ta sẽ giới thiệu bài toán bất đẳng thức biến phân (VIP) và nhấn mạnh bài toán bất đẳng thức biến phân giả đơn điệu mạnh. Chỉ ra các ví dụ về bài toán bất đẳng thức biến phân thường gặp trong thực tế cũng như trong các mô hình toán học. Cuối chương phát biểu và chứng minh định lý về sự tồn tại và tính duy nhất nghiệm của bài toán. Nội dung chủ yếu được trích dẫn từ tài liệu [1], [2], [3], [6], [10]. Trong luận văn này, chúng ta sẽ làm việc trên không gian Hilbert thực trang bị một tô pô yếu, với tích vô hướng 〈 ., . 〉 và chuẩn tương ứng của nó là ||.||. 5 1.1. Kiến thức chuẩn bị 1.1.1. Hội tụ mạnh và yếu trong không gian Hilbert Định nghĩa 1.1.1. Giả sử H là không gian tuyến tính thực, với mọi x ∈ H xác định một số gọi là chuẩn của x ( kí hiệu ||x||) thỏa mãn ba tiên đề sau: 1. Xác định dương: ∀x ∈ H ||x|| ≥ 0; ||x||= 0⇔ x= 0. 2. Thuần nhất dương: ∀x ∈ H;∀λ ∈ R ||λx||= |λ | ||x||. 3. Bất đẳng thức tam giác: ∀x,y ∈ H ||x+ y|| ≤ ||x||+ ||y||. Định nghĩa 1.1.2. Giả sử H là không gian tuyến tính thực, cặp (H, 〈 , 〉 ) với〈 , 〉 : H×H→ R (x,y) 7→ 〈x,y〉 thỏa mãn các điều kiện: 1. Xác định dương: 〈 x,x 〉≥ 0 ∀x ∈ H; 〈x,x〉= 0⇔ x= 0. 2. Đối xứng: 〈 x,y 〉 = 〈 y,x 〉 ∀x,y ∈ H. 3. Song tuyến tính: 〈 αx+βy,z 〉 = α 〈 x,z 〉 +β 〈 y,z 〉 ∀α, β ∈ R, ∀x,y,z ∈ H. được gọi là không gian tiền Hilbert. Không gian tiền Hilbert, đầy đủ được gọi là không gian Hilbert, kí hiệu là H. Định nghĩa 1.1.3. 1) Ta nói dãy {xk} hội tụ mạnh đến x ( kí hiệu xk→ x) nếu lim k→∞ ||xk− x||= 0. 2) Dãy {xk} hội tụ yếu đến x ( kí hiệu xk ⇀ x) nếu {xk} hội tụ về x theo tô pô yếu σ tức là ∀ f ∈ H∗ f (xk)→ f (x). Khi H là không gian hữu hạn chiều thì tô pô yếu và tô pô thông thường trên H trùng nhau. Đặc biệt, một dãy hội tụ mạnh khi và chỉ khi nó hội tụ yếu. 6 1.1.2. Toán tử chiếu Định nghĩa 1.1.4. Giả sử C là một tập lồi, khác rỗng trong không gian Hilbert thực H và x0 ∈C. 1. Nón pháp tuyến (ngoài) của C tại x0 kí hiệu là NC(x0) được định nghĩa bởi: NC(x0) := {ω ∈ H| ωT (x− x0)≤ 0 ∀x ∈C}. Tập −NC(x0) được gọi là nón pháp tuyến (trong) của C tại x0 . 2. Nón pháp tuyến ε của C tại x0 được định nghĩa bởi: NεC(x 0) := {ω ∈ H| ωT (x− x0)≤ ε ∀x ∈C}. Định nghĩa 1.1.5. Giả sửC 6= /0 (không nhất thiết lồi) là một tập con của không gian Hilbert H và y là một véc-tơ bất kỳ, khoảng cách từ y đếnC được định nghĩa bởi dC(y) := inf x∈C ||x− y||. Nếu tồn tại pi ∈C sao cho dC(y) := ||pi−y||, thì ta nói pi là hình chiếu (khoảng cách) của y trênC, kí hiệu pi = pC(y). Mệnh đề 1.1.1. ChoC là một tập lồi đóng khác rỗng. Khi đó: 1. Với mọi y ∈ H,pi ∈C hai tính chất sau là tương đương: a) pi = pC(y), b) y−pi ∈ NC(pi). 2. Với mọi y ∈ H, hình chiếu pC(y) của y trênC luôn tồn tại và duy nhất. 3. Nếu y /∈C, thì 〈pC(y)− y,x− pC(y)〉 = 0 là siêu phẳng tựa của C tại pC(y) và tách hẳn y khỏiC, tức là〈 pC(y)− y,x− pC(y) 〉≥ 0 ∀x ∈C, và 〈 pC(y)− y,y− pC(y) 〉 < 0. 4. Ánh xạ y 7→ pC(y) có các tính chất sau: a) ||pC(x)− pC(y)|| ≤ ||x− y|| ∀x,∀y. (tính không giãn), b) 〈 pC(x)− pC(y),x− y 〉≥ ||pC(x)− pC(y)||2, (tính đồng bức). 7 Toán tử chiếu là một công cụ hữu hiệu nhằm giải bài toán cân bằng và các trường hợp đặc biệt của nó như: Bài toán tối ưu, bất đẳng thức biến phân, điểm bất động, bài toán điểm yên ngựa.... Trong luận văn này, ta sẽ vận dụng giải quyết bài toán bất đẳng thức biến phân giả đơn điệu mạnh. 1.1.3. Tính liên tục của hàm lồi ChoC ⊆ H là tập lồi và f :C→ R∪{+∞}, ta sẽ kí hiệu: dom f := {x ∈C : f (x)<+∞}. Tập dom f được gọi là miền hữu dụng của tập f. Tập epi f := {(x,µ) ∈C×R : f (x)≤ µ}, được gọi là trên đồ thị của hàm f. Hàm f gọi là chính thường nếu dom f 6= /0 và f (x)>−∞ với mọi x ∈ dom f . Định nghĩa 1.1.6. Hàm f được gọi là lồi nếu epi f là một tập lồi. Hàm f là hàm lõm nếu − f là hàm lồi. Nếu f vừa lồi vừa lõm thì ta nói f là hàm afin. Định nghĩa 1.1.7. Cho f : H → R, hàm f được gọi là nửa liên tục dưới tại x0 ∈ H nếu ∀{xk} ⊂ H : xk→ x0⇒ limk→∞ f (xk)≥ f (x0). Hàm f được gọi là nửa liên tục dưới trên D ⊆ H nếu nó liên tục dưới tại mọi x ∈ D. Hàm f là nửa liên tục trên nếu − f là nửa liên tục dưới. Nếu hàm f vừa liên tục trên vừa liên tục dưới thì nó liên tục. 1.1.4. Đạo hàm và dưới vi phân của hàm lồi Tính khả vi của hàm lồi đóng vai trò quan trọng trong các phương pháp tối ưu hóa. Lớp các hàm lồi có những tính chất rất đẹp mà các lớp hàm khác không có. Giả sử f : H→ R là hàm lồi. Ta có các khái niệm sau Định nghĩa 1.1.8. Vectơ ω ∈ H∗ được gọi là dưới đạo hàm của f tại x0 ∈ H nếu:〈 ω,x− x0〉≤ f (x)− f (x0), ∀x ∈ H. Tập hợp tất cả các dưới đạo hàm của hàm f tại x0 được gọi là dưới vi phân của hàm f tại x0, kí hiệu là ∂ f (x0) := {ω ∈ H∗ : 〈ω,x− x0〉≤ f (x)− f (x0), ∀x ∈ H}. 8 Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂ f (x0) 6= /0. Định nghĩa 1.1.9. Cho ε > 0, một vectơ ω ∈ H∗ được gọi là ε-dưới đạo hàm của f tại x0 ∈ H nếu: 〈 ω,x− x0〉≤ f (x)− f (x0)+ ε, ∀x ∈ H. Tập hợp tất cả các ε-dưới đạo hàm của hàm f tại x0 được gọi là ε-dưới vi phân của hàm f tại x0, kí hiệu là ∂ε f (x0) := {ω ∈ H∗ : 〈 ω,x− x0〉≤ f (x)− f (x0)+ ε, ∀x ∈ H}. Hàm f được gọi là ε-khả dưới vi phân tại x0 nếu ∂ε f (x0) 6= /0. Định nghĩa 1.1.10. Giả sử x ∈ H,d ∈ H\{0}, hàm f được gọi là: a) Khả vi Frechet tại x0 nếu tồn tại ω ∈ H∗ sao cho lim x→x0 f (x)− f (x0)−〈ω,x− x0〉 ||x− x0|| = 0, ∀x ∈ H. Một điểm ω như thế nếu tồn tại, sẽ duy nhất và được gọi là đạo hàm của f tại x0, kí hiệu là f ′(x0) hoặc ∇ f (x0). b) Có đạo hàm theo hướng d tại x0 nếu tồn tại giới hạn lim t→0+ f (x0+ td)− f (x0) t . ta gọi giới hạn đó là đạo hàm theo hướng d của f tại x0, kí hiệu là f ′(x0,d). Nói chung một hàm lồi không nhất thiết khả vi tại mọi điểm. Dưới vi phân là một khái niệm mở rộng của đạo hàm trong trường hợp hàm không khả vi. Trong trường hợp ∂ f (x∗) chỉ gồm duy nhất một điểm thì f khả vi tại x∗. 1.2. Bài toán bất đẳng thức biến phân 1.2.1. Các khái niệm Định nghĩa 1.2.1. Cho K ⊂H là một tập đóng, khác rỗng, F : K→H là một ánh xạ đơn trị. Bài toán bất đẳng thức biên phân (đơn trị) là bài toán Tìm x∗ ∈ K sao cho 〈F(x∗),y− x∗〉≥ 0, ∀y ∈ K. (VIP) Tập nghiệm của bài toán kí hiệu là S(K, F). 9 Định nghĩa 1.2.2. Giả sử K ⊂H là một tập lồi đóng, khác rỗng và toán tử F :K→H được gọi là a) đơn điệu mạnh trên K nếu tồn tại γ > 0 sao cho〈 F(x)−F(y),x− y〉≥ γ||x− y||2 ∀x,y ∈ K, b) đơn điệu trên K nếu 〈 F(x)−F(y),x− y〉≥ 0 ∀x,y ∈ K, c) giả đơn điệu mạnh trên K nếu tồn tại γ > 0 sao cho〈 F(x),y− x〉≥ 0⇒ 〈F(y),y− x〉≥ γ||y− x||2 ∀x,y ∈ K, d) giả đơn điệu trên K nếu〈 F(x),y− x〉≥ 0⇒ 〈F(y),y− x〉≥ 0 ∀x,y ∈ K. Theo định nghĩa trên các kéo theo (a)⇒ (b),(a)⇒ (c),(c)⇒ (d),(b)⇒ (d), là hiển nhiên. Chú ý rằng một toán tử giả đơn điệu mạnh có thể không đơn điệu. Định nghĩa 1.2.3. Giả sử toán tử F là toán tử giả đơn điệu mạnh thì bài toán bất đẳng thức biến phân (VIP) trở thành bài toán bất đẳng thức biến phân giả đơn điệu mạnh. Kí hiệu là VI(K, F). Mệnh đề 1.2.1. Cho K ⊂ H là một tập lồi đóng và toán tử F : K→ H liên tục. a) Nếu F giả đơn điệu mạnh thì VI(K, F) nếu có thì có duy nhất một nghiệm. b) Nếu F giả đơn điệu thì S(K, F) là một tập lồi. Định nghĩa 1.2.4. Ánh xạ F được gọi là liên tục Lipschitz trên K nếu tồn tại hằng số L> 0 sao cho: ||F(u)−F(v)|| ≤ L||u− v||, ∀u,v ∈ K. PK(.) là một ánh xạ liên tục Lipschitz với hằng số Lipschitz L=1. Ví dụ 1.2.1. Bài toán điểm bất động Brouwer 10 Cho K là một tập lồi, đóng, khác rỗng, compăc yếu trong H và ánh xạ T : K→ K là ánh xạ liên tục. Bài toán điểm bất động được phát biểu như sau Tìm x∗ ∈ K : x∗ = T (x∗). Bài toán điểm bất động được đưa về bài toán bất đẳng thức biến phân (VIP) thông qua mệnh đề sau Mệnh đề 1.2.2. Giả sử ánh xạ F được xác định bởi F(x) = x−T (x), ∀x ∈ K. Khi đó, nghiệm của bài toán điểm bất động trùng với nghiệm của bài toán bất đẳng thức biến phân (VIP). Tức là bài toán bất đẳng thức biến phân tương đương với bài toán điểm bất động. 1.2.2. Sự tồn tại nghiệm Trong phần này, trình bày chứng minh theo tài liệu [9] rằng bài toán bất đẳng thức biến phân giả đơn điệu mạnh luôn tồn tại một nghiệm và đó là nghiệm duy nhấtcủa bái toán. Bổ đề 1.2.1. Giả sử K là một tập lồi đóng, khác rỗng trong không gian Hilbert H. Cho F : K → H là một toán tử sao cho 〈F(∗),y−∗〉 là nửa liên tục trên với mỗi y ∈ K . Giả sử ∃ tập compăc W : ∀x ∈ K\W, ∃y ∈ K : 〈F(x),y− x〉< 0. Thì bài toán bất đẳng thức biến phân (VI) có một nghiệm. Mệnh đề 1.2.3. Giả sử F là β− giả đơn điệu mạnh trên K. Nếu 〈F(∗),y−∗〉 là nửa liên tục trên với mỗi y ∈ K thì bài toán bất đẳng thức biến phân (VI) có một nghiệm duy nhất. 11 Chương 2 Phương pháp chiếu giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh Chương này, trình bày các thuật toán chiếu giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh VI(K,F). Phần đầu, trình bày thuật toán chiếu dưới đạo hàm tăng cường (mỗi bước lặp có hai lần chiếu) với độ dài bước được lấy từ một khoảng đóng của các số thực dương, không yêu cầu phụ thuộc vào hằng số Lipschitz. Dãy lặp tổng quát thu được từ thuật toán này hội tụ tới nghiệm duy nhất của bài toán. Phần sau, trình bày thuật toán chiếu cơ bản cải biên (mỗi bước lặp chỉ có một lần chiếu) với độ dài bước được lấy tùy ý từ một khoảng đóng cố định của các số thực dương. Trình bày chứng minh dãy lặp tổng quát thu được từ thuật toán này hội tụ tuyến tính tới nghiệm duy nhất của bài toán. Phương pháp này đòi hỏi hằng số Lipschitz và môđun của giả đơn điệu mạnh trong việc lựa chọn khoảng đóng cố định chứa độ dài bước. Nội dung chủ yếu của chương được trích dẫn từ tài liệu [7], [8]. 12 Đề tiện cho việc theo dõi, em xin phát biểu lại bài toán bất đẳng thức biến phân giả đơn điệu manh như sau: Định nghĩa 2.0.5. Cho K ⊂H là một tập đóng, khác rỗng, F : K→H là toán tử giả đơn điệu mạnh trên K. Bài toán bất đẳng thức biến phân giả đơn điệu mạnh là bài toán Tìm x∗ ∈ K sao cho 〈F(x∗),y− x∗〉≥ 0, ∀y ∈ K. (VI) Tập nghiệm của bài toán được ký hiệu là VI(K, F). 2.1. Phương pháp chiếu dưới đạo hàm tăng cường Thuật toán 2.1.1 Chọn một điểm đầu u0 ∈ K và một dãy các độ dài bước {λk}∞k=0 ⊂ R+ với ∞ ∑ k=0 λk =+∞, lim k→∞ λk = 0. Bước 1: Đặt k=0. Bước 2: Tính uk = PK(uk−λkF(uk)), uk+1 = PK(uk−λkF(uk)). Bước 3: Nếu uk = uk thì dừng lại. Ngược lại thì đặt k+1= k và quay lại bước 2. Nếu thuật toán dừng ở bước thứ k, thì ta đặt uk ′ = uk với mọi k′ ≥ k+ 1. Vì thế, Thuật toán 2.1.1 tạo ra một dãy lặp vô hạn. Định lý 2.1.1. Cho K là một tập lồi, đóng, khác rỗng trong không gian Hilbert thực H. Giả sử F : K→ H là liên tục Lipschitz và giả đơn điệu mạnh trên K, thì dãy lặp {uk} được tạo bởi Thuật toán 2.1.1 hội tụ mạnh tới nghiệm u∗ của bài toán. Hơn nữa, tồn tại một chỉ số k0 ∈ N sao cho γλk < 1 với mọi k ≥ k0 và ||uk+1−u∗|| ≤ √√√√ k∏ j=k0 (1− γλ j)||uk0 −u∗||, trong đó γ > 0 là hằng số giả đơn điệu mạnh của F. Ngoài ra, lim k→∞ √√√√ k∏ j=k0 (1− γλ j) = 0. 13 Trong phần tiếp theo, ta sẽ chứng minh giả thiết hàm F là giả đơn điệu mạnh và hai điều kiện ∞ ∑ k=0 λk =+∞, lim k→∞ λk = 0 là cần thiết cho khẳng định của Định lý 2.1.1. Ví dụ 2.1.1. Cho K =R và F(u) = u. Dễ thấy, F là liên tục Lipschitz, đơn điệu mạnh trên K và S(K,F) = {0}. Chọn u0 = 1 ∈ K và định nghĩa dãy {λk} bằng cách đặt λk = 1 (k+1)2 ∀k ∈ N. Từ đó ∞ ∑ k=0 λk <+∞, và dãy lặp {uk} được tạo bởi Thuật toán 2.1.1 được cho bởi uk+1 = PK(uk−λkF(PK(uk−λkF(uk)))) = uk−λkF(uk−λkF(uk)) = uk−λk(uk−λkuk) = (1−λk+λ 2k )uk. Vì u0 = 1, ta có uk+1 = k ∏ j=0 (1−λ j+λ 2j ) = k ∏ j=0 ( 1− 1 ( j+1)2 + 1 ( j+1)4 ) ≥ k ∏ j=1 ( 1− 1 ( j+1)2 ) = k ∏ j=1 j( j+2) ( j+1)2 = k+2 2(k+1) ∀k ∈ N. Do đó, {uk} là dãy giảm và bị chặn dưới nên nó hội tụ. lim k→∞ uk ≥ lim k→∞ k+2 2(k+1) = 1 2 . Ta được lim k→∞ uk = u∗ với u∗ ≥ 1 2 .Do vậy, dãy {uk} không hội tụ tới nghiệm duy nhất của bài toán VI(K,F). Ví dụ 2.1.2. Cho K,F,u0 như trong Ví dụ 2.1.1 và λk = 1 với mọi k ∈ N. Do đó ∞ ∑ k=0 λk = +∞. Tuy nhiên như đã tính toán ở trên uk = k−1 ∏ j=0 (1−λ j+λ 2j ) = 1 với mọi k ∈ N. Do vậy lim k→∞ uk = 1 không hội tụ tới nghiệm duy nhất của bài toán. Ví dụ 2.1.3. Cho K =R2 và F(u) = (−u2,u1) với mọi u= (u1,u2)∈K. Dễ thấy hàm F liên tục Lipschitz và đơn điệu trên K, và nghiệm của bài toán VI(K,F) là (0,0)T . 14 Cho u0 = (u01,u 0 2) T ∈ K\{(0,0)T} bất kỳ và {λk} được cho bởi λk = 1 k+1 ∀k ∈ N. Khi đó ∞ ∑ k=0 λk =+∞, lim k→∞ λk = 0. Để chứng minh F không giả đơn điệu mạnh trên K, ta chỉ cần chọn u= (1,0)T ,v= (2,0)T , khi đó 〈 F(u),v−u〉= 0 và 〈F(v),v−u〉= 0. Dãy lặp {uk} được tạo bởi Thuật toán 2.1.1 được cho bởi u0 = (u01,u 0 2) T uk+11 = ( 1− 1 (k+1)2 ) uk1+ 1 k+1 uk2 uk+12 = ( 1− 1 (k+1)2 ) uk2− 1 k+1 uk1 Ta có ||uk+1|| = √ (uk+11 ) 2+(uk+12 ) 2 = √ (uk1) 2+(uk2) 2 √ 1− 1 (k+1)2 + 1 (k+1)4 =||uk|| √ 1− 1 (k+1)2 + 1 (k+1)4 =||u0|| √√√√ k∏ j=0 ( 1− 1 ( j+1)2 + 1 ( j+1)4 ) . Khi đó lim k→∞ ||uk||= ||u0|| lim k→∞ √√√√ k∏ j=0 ( 1− 1 ( j+1)2 + 1 ( j+1)4 ) ≥ ||u0|| lim k→∞ √ k+2 2(k+1) ≥ √ 2 2 ||u0|| = µ||u0|| (µ ≥ √ 2 2 ). Do đó, {uk} không hội tụ đến nghiệm duy nhất của bài toán VI(K,F). Qua các ví dụ trên ta thấy rằng, nếu bỏ đi bất kỳ một trong ba đều kiện trên thì dãy lặp {uk} đều không hội tụ tới nghiệm duy nhất của bài toán VI(F,K). 15 2.2. Phương pháp chiếu cơ bản cải biên Thuật toán 2.2.1. Cho trước u0 ∈ K và {λk} ⊂ (0,+∞). Bước 1: Đặt k=0. Bước 2: Tính u′k = PK(uk − λkF(uk)), nếu u′k = uk thì dừng lại. Nếu không thì chuyển sang bước tiếp theo. Bước 3: Đặt uk+1 = u′k, sau đó quay lại bước 2. Nếu thuật toán chấm dứt ở bước thứ k, thì ta đặt uk ′ = uk với mọi k′ ≥ k+1. Như vậy, đối với một dãy các độ dài bước thay đổi {λk} ⊂ (0,+∞), Thuật toán 2.2.1 tạo ra cho mỗi điểm ban đầu u0 ∈ K một dãy lặp vô hạn {uk}. Mệnh đề 2.2.1. Cho K là một tập lồi, đóng, khác rỗng trong không gian Hilbert thực H và ánh xạ F : K → H là giả đơn điệu mạnh trên K với mô-đun γ và liên tục Lipschitz trên K với hằng số L. Cho {uk} là dãy lặp được tạo ra bởi Thuật toán 2.2.1 và u∗ là nghiệm duy nhất của bài toán VI(K, F) thì [1+λk(2γ−λkL2)] ||uk+1−u∗||2 ≤ ||uk−u∗||2, ∀k ∈ N. Bài toán VI(K,F) luôn có duy nhất một nghiệm, và dãy lặp được tạo bởi Thuật toán 2.2.1, với độ dài bước được chọn từ một khoảng đóng của các số thực dương, hội tụ tuyến tính tới nghiệm duy nhất đó. Cụ thể, ta có định lý sau: Định lý 2.2.1. Cho K là một tập lồi, đóng, khác rỗng trong không gian Hilbert thực H, F : K→ H là ánh xạ giả đơn điệu mạnh trên K với môđun γ và liên tục Lipschitz trên K với hằng số L. Giả sử rằng 0< a≤ λk ≤ b< 2γL2 , ∀k ∈ N, (2.4) trong đó a, b là các hằng số dương. Cho {uk} là dãy lặp tạo ra bởi Thuật toán 2.2.1. Khi đó, dãy {uk} hội tụ tuyến tính tới nghiệm duy nhất u∗ của bài toán. Hơn nữa, các sai số tiên nghiệm và hậu nghiệm là ||uk+1−u∗|| ≤ µ k+1 1−µ ||u 1−u0||, và ||uk+1−u∗|| ≤ µ 1−µ ||u k+1−uk||, 16 đúng với mọi k ∈ N. Ở đây µ = 1√ 1+a(2γ−bL2) ∈ (0,1). Chú ý 2.2.1 Khi a = b = λ , độ dài bước là cố định. Do đó phương pháp chiếu cơ bản cải biên trở thành phương pháp chiếu cơ bản và µ trở thành µ = 1√ 1+λ (2γ−λL2) . Ta có λ ∈ ( 0, 2γ L2 ) . Các ước tính sai số là chặt chẽ khi µ là nhỏ nhất. Xét µ như một hàm của λ ∈ ( 0, 2γ L2 ) , ta tìm được giá trị nhỏ nhất của µ là µ∗ := L√ L2+ γ2 tại điểm λ∗ := γ L2 . Chú ý 2.2.2 Ngoài ra giá trị µ có thể được xem như một hàm µ = µ(a,b) của biến (a,b) thuộc miền { (a,b) ∈ R2 : 0< a≤ b< 2γ L2 } . Đặt b = ta, với t ∈ [1, +∞) cố định, tương tự như trên ta tính được hàm µ(a,b) = µ(a, ta) đạt giá trị nhỏ nhất là 1√ 1+ γ2 tL2 tại a= γ tL2 . Từ đó min  1√ 1+ γ2 tL2 : 1≤ t <+∞ = L√ L2+ γ2 . Vậy suy ra min { µ(a,b) : 0< a≤ b< 2γ L2 } = L√ L2+ γ2 . Do đó, giá trị nhỏ nhất của µ là µ∗ = L√ L2+ γ2 đạt được tại điểm duy nhất (a∗,b∗) = ( γ L2 , γ L2 ). 17 Chú ý 2.2.3 Ước lượng sai số trong Định lý 2.2.1 là hữu ích trong việc áp dụng Thuật toán 2.2.1 để giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh.Ví dụ, công thức ||uk+1−u∗|| ≤ µ k+1 1−µ ||u 1−u0|| cho phép chúng ta ước tính số lượng bước lặp cần để đạt được một độ chính xác nhất định. Cụ thể, với ε > 0 bất kỳ, nếu µk+1 1−µ ||u 1−u0|| ≤ ε thì ta có ||uk+1−u∗|| ≤ ε . Hệ quả 2.2.1. Trong các kí hiệu của Định lý 2.2.1, nếu F là đơn điệu mạnh và liên tục Lipschitz trên K thì dãy {uk} tạo ra bởi Thuật toán 2.2.1 hội tụ tuyến tính tới nghiệm duy nhất của bài toán VI(K,F) và các ước tính sai số nêu trên được thỏa mãn. Ví dụ 2.2.1 Cho H = l2 là không gian Hilbert thực mà các thành phần là các dãy bình phương khả tổng của các vô hướng thực. Ví dụ H = {u = (u1,u2, · · · ,ui, · · ·) : ∞ ∑ i=1 |ui|2 <+∞}. Định nghĩa 〈 u,v 〉 = ∞ ∑ i=1 uivi và ||u||= √〈 u,u 〉 là tích vô hướng và chuẩn của hai vectơ u,v trênH, với u=(u1,u2, · · · ,ui, · · ·),v=(v1,v2, · · · ,vi, · · ·)∈H bất kỳ. Cho α,β ∈ R sao cho β > α > β 2 > 0. Đặt Kα = {u ∈ H : ||u|| ≤ α}, Fβ (u) = (β −||u||)u, trong đó α,β là các tham số. Dễ thấy S(Kα ,Fβ ) = {0}. Hàm Fβ là liên tục Lipschitz và giả đơn điệu mạnh trên Kα . Thật vậy, với u,v ∈ Kα bất kỳ, ||Fβ (u)−Fβ (v)||= ||(β −||u||)u− (β −||v||)v|| = ||β (u− v)−||u||(u− v)− (||u||− ||v||)v|| ≤ β ||u− v||+ ||u|| ||u− v||+ | ||u||− ||v|| | ||v|| ≤ β ||u− v||+α ||u− v||+α||u− v|| = (β +2α)||u− v||. Do đó Fβ là liên tục Lipschitz trên Kα với hằng số Lipschitz L := β +2α . Cho u,v ∈ Kα sao cho 〈 Fβ (u),v− u 〉 ≥ 0. Theo giả thiết ||u|| ≤ α < β . Suy ra 〈u,v− u〉 ≥ 0. Do đó 〈 Fβ (v),v−u 〉 = (β −||v||)〈v,v−u〉 ≥ (β −||v||)(〈v,v−u〉−〈u,v−u〉) ≥ (β −α)||u− v||2 = γ||u− v||2, 18 ở đây γ := β −α > 0. Suy ra Fβ là giả đơn điệu mạnh trên Kα . Hơn nữa Fβ không thể đơn điệu mạnh cũng không thể đơn điệu trênKα . Thật vậy, ta chọn u= ( β 2 ,0, · · · ,0, · · · ) ,v= (α,0, · · · ,0, · · ·) ∈ Kα . Ta có〈 Fβ (u)−Fβ (v),u− v 〉 = ( β 2 −α )3 < 0. Lấy u0 ∈ Kα bất kỳ, và λ ∈ ( 0, 2γ L2 ) = ( 0, 2(β −α) (β +2α)2 ) tùy ý, đặt λk = λ với mọi k ∈ N. Theo Định lý 2.2.1, dãy {uk} được tạo bởi Thuật toán 2.2.1 hội tụ tuyến tính tới 0. Hơn nữa, ||uk+1−0|| ≤ µ k+1 1−µ ||u 1−u0|| và ||uk+1−0|| ≤ µ 1−µ ||u k+1−uk|| với mọi k ∈ N, trong đó µ = 1√ 1+λ [2(β −α)−λ (β +2α)2] . Theo Chú ý 2.2.1 giá trị nhỏ nhất của µ là µ∗ = β +2α√ (β −α)2+(β +2α)2] tại điểm λ = λ∗ = β −α (β +2α)2 . Nếu các độ dài bước tạo thành một dãy không khả tổng của các số thực dương thì Thuật toán 2.2.1 cũng tạo ra một dãy lặp hội mạnh tới nghiệm duy nhất của bài toán. Ta có: Định lý 2.2.2. Cho K là một tập lồi đóng khác rỗng trong không gian Hilbert thực H và F : K → H là một ánh xạ giả đơn điệu mạnh trên K với mô-đun γ và liên tục Lipschitz trên K với hằng số L. Giả sử {λk} là một dãy các vô hướng dương với ∞ ∑ k=0 λk =+∞, lim k→∞ λk = 0. (2.5) Dãy lặp {uk} được tạo thành từ Thuật toán 2.2.1 sẽ hội tụ mạnh tới u∗ là nghiệm duy nhất của bài toán VI(K, F). Hơn nữa, tồn tại một chỉ số k0 ∈ N sao cho với mỗi k ≥ k0,λk(2γ−λkL2)> 0, và ||uk+1−u∗|| ≤ 1√ ∏ki=k0 [1+λi(2γ−λiL2] ||uk0 −u∗||. 19 Hệ quả 2.2.2. Cho {λk} như trong Định lý 2.2.2. Cho F là đơn điệu mạnh trên K với mô-đun γ và liên tục Lipschitz trên K với một hằng số L. Thì dãy {uk} bất kỳ được tạo ra từ Thuật toán 2.2.1 hội tụ theo chuẩn tới nghiệm duy nhất của bài toán VI(K, F) và tồn tại một chỉ số k0 ∈ N sao cho ||uk+1−u∗|| ≤ 1√ ∏ki=k0 [1+λi(2γ−λiL2] ||uk0 −u∗||, đúng với mỗi k ≥ k0. Ví dụ 2.2.2. Cho H = l2,α,β ∈ R sao cho β > α > β2 > 0. Đặt Kα = {u ∈ H : ||u|| ≤ α}, Fβ (u) = (β −||u||)u, trong đó α,β là các tham số, và λk = 1 k+1 ,∀k ∈N. Khi đó ∞ ∑ k=0 λk =+∞, lim k→∞ λk = 0. Cho {uk} là một dãy lặp được tạo bởi Thuật toán 2.2.1. Suy ra dãy {uk} hội tụ mạnh tới 0 là nghiệm duy nhất của bài toán VI(Kα ,Fβ ). Đặt k0 = (β +2α)2 2(β −α) , thì λk(2γ−λkL2)> 0, với mọi k ≥ k0. Ta có ||uk+1−0|| ≤ 1√ ∏ki=k0 [ 1+ ( 2(β −α) i+1 − (β +2α) 2 (i+1)2 )] ||uk0 −0||, ∀k ≥ k0. Chúng ta sẽ xét xem điều gì sẽ xảy ra nếu bỏ điều kiện (2.4) và (2.5) lần lượt được đưa ra ở Định lý 2.2.1 và Định lý 2.2.2 thông qua ví dụ sau: Ví dụ 2.2.3. Đặt K = R và F(u) = u. Rõ ràng F liên tục Lipschitz, đơn điệu mạnh trên K và S(K,F) = 0. Chọn u0 = 1 ∈ K và λk = 1 (k+2)2 , ∀k ∈ N. Từ đó lim k→∞ λk = 0 và ∞ ∑ k=0 λk <+∞, cả hai điều kiện (2.4) và (2.5) đều bị lược bỏ. Dãy lặp uk được tạo bởi Thuật toán 2.2.1 với u0 = 1 được cho bởi uk+1 = PK(uk−λkF(uk)) = uk−λkuk = (1−λk)uk. 20 Do đó, uk+1 = k ∏ i=0 (1−λi) = k ∏ i=0 ( 1− 1 (i+2)2 ) = k ∏ i=0 (i+1)(i+3) (i+2)2 = k+3 2(k+2) , ∀k ∈ N. Vậy lim k→∞ uk = 1 2 . Nghĩa là {uk} không hội tụ đến nghiệm duy nhất c