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

− y||2−||x−PC(x)||2. Chứng minh. Cho x ∈ H và y ∈C, ta có ||x− y||2 =||(x−PC(x))− (y−PC(x))||2 =||x−PC(x)||2+ ||y−PC(x)||2−2 〈 x−PC(x),y−PC(x) 〉 . Do 〈 x−PC(x),y−PC(x) 〉≤ 0, suy ra ||x− y||2 ≥ ||x−PC(x)||2+ ||y−PC(x)||2. Hệ quả được chứng minh.  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. 13 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.11. 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. Hình 1.3: Hàm lồi Tính chất 1.1.1. ChoC⊂H là một tập lồi, khác rỗng. Hàm f :H→R∪{+∞} được gọi là i) lồi trên C nếu: f (λx+(1−λ )y)≤ λ f (x)+(1−λ ) f (y), ∀x,y ∈C,λ ∈ [0,1], ii) lồi thực sự (chặt) trên C nếu: f (λx+(1−λ )y)< λ f (x)+(1−λ ) f (y), ∀x,y ∈C,x 6= y,λ ∈ (0,1), 14 iii) lồi mạnh trên C nếu: f (λx+(1−λ )y)≤ λ f (x)+(1−λ ) f (y)− 1 2 βλ (1−λ )||x− y||2 với hệ số β > 0, nếu ∀x,y ∈C,λ ∈ [0,1]. Mệnh đề 1.1.4. Cho C là một tập lồi trong không gian Hilbert thực H. Khi đó: 1. Nếu f và g là các hàm lồi trên C thì f +g cũng là hàm lồi trên C. Nếu f hoặc g là hàm lồi thực sự thì f +g cũng là hàm lồi thực sự. 2. Nếu f là hàm lồi (lồi thực sự) trên C, λ là một số thực dương thì λ f là một hàm lồi (lồi thực sự) trên C. 3. Nếu f là hàm lồi (lồi thực sự) trên C, B là tập con lồi của C thì hạn chế f |B của hàm f trên C cũng là một hàm lồi (lồi thực sự) trên C. Định nghĩa 1.1.12. Một điểm x ∈C được gọi là điểm trong tương đối của C nếu nó là điểm trong của C theo tô-pô cảm sinh bởi aff(C) (tập afin nhỏ nhất chứa C). Tập hợp các điểm trong tương đối của C ký hiệu là riC. Định nghĩa 1.1.13. 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. Định nghĩa 1.1.14. Một hàm số thực f được gọi là tựa lồi trên tập lồi C nếu mọi số thực β tập mức dưới {x ∈C | f (x)≤ β} lồi. Tương tự, hàm f là tựa lõm trên C nếu − f là hàm tựa lồi trên C. Nếu f tựa lồi trênC thì ∀x,y ∈C và λ ∈ [0,1] ta có f (λx+(1−λ )y)≤max( f (x), f (y)). Tương tự, nếu f tựa lõm trênC thì ∀x,y ∈C và λ ∈ [0,1] ta có f (λx+(1−λ )y)≥min( f (x), f (y)). 15 Định lý 1.1.3. Giả sử f là hàm lồi chính thường trên H và x0 ∈H. Khi đó, các khẳng định sau là tương đương: a) f liên tục tại điểm x0. b) f bị chặn trên trong một lân cận của x0. c) int(epi f ) 6= /0. d) int(dom f ) 6= /0. và f liên tục trong int(dom f ). trong đó intC là kí hiệu phần trong của tập 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.15. 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.16. 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. 16 Mệnh đề 1.1.5. 1. ∀α ≥ 0 ta có ∂ (α f )(x) = α∂ f (x). 2. Giả sử f là một hàm lồi, h(x) = f (Ax+b). Khi đó ∂h(x) = AT∂ f (Ax+b). Mệnh đề 1.1.6. (Định lý Moreau-Rockafellar). Cho fi, i= 1,2, · · · ,n là các hàm lồi chính thường trên H. Khi đó n ∑ i=1 ∂ fi(x)⊆ ∂ ( n ∑ i=1 fi(x)), ∀x ∈ H. Nếu ∩ri(dom fi) 6= /0 thì n ∑ i=1 ∂ fi(x) = ∂ ( n ∑ i=1 fi(x)), ∀x ∈ H. Định nghĩa 1.1.17. 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). Định lý 1.1.4. Giả sử f là hàm lồi chính thường trên H và x ∈ dom f . Khi đó a) f có đạo hàm theo mọi hướng tại x và f ′(x,d) = inf λ>0 f (x+λd)− f (x) λ . b) x∗ ∈ ∂ f (x)⇔ f ′(x,d)≥ 〈x∗,d〉, ∀d ∈ H. c) ∂ f (x) 6= /0⇔ f nửa liên tục dưới tại 0. d) Nếu f khả vi tại x ∈ H thì ∂ f (x) = f ′(x). 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∗. 17 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). Đị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. Ví dụ 1.2.1. Cho 0< r < R, đặt K = B(r) := {x ∈ H : ||x|| ≤ r} và F được cho bởi〈 F(x),y− x〉 := 〈K(x),y− x〉+(R−||x||)〈G(x),y− x〉. Trong đó K và G thỏa mãn các điều sau: 18 i) 〈 K(x),y− x〉≤ 0, ∀x,y ∈ K và G là β−đơn điệu mạnh trên K, ii) ∃ y0 ∈ K :  〈 K(0),y0 〉 + 〈 K(y0),−y0〉= 0 R 〈 G(0),y0 〉 +(R−||y0||)〈G(y0),−y0〉> 0 Giả sử 〈 F(x),y− x〉 ≥ 0, do 〈K(x),y− x〉 ≤ 0 nên ta có: 〈G(x),y− x〉 ≥ 0. Suy ra〈 G(y),x−y〉≤−β ||y−x||2 (doG là đơn điệu mạnh). Theo định nghĩa của 〈F(x),y− x 〉 ta có: ∀x,y ∈ K,〈 F(y),x− y〉= 〈K(y),x− y〉+(R−||y||)〈G(y),x− y〉≤−(R− r)β ||y− x||2. Suy ra F giả đơn điệu mạnh trên K. Hơn nữa theo (ii) ta có: 〈 F(0),y0 〉 + 〈 F(y0),−y0〉= 〈K(0),y0〉+R〈G(0),y0〉+ + 〈 K(y0),−y0〉+(R−||y0||)〈G(y0),−y0〉> 0. Do đó F 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. Chứng minh. Giả sử F là toán tử giả đơn điệu mạnh và u∗,v∗ ∈ S(K,F), thì〈 F(v∗),u∗− v∗〉 ≥ 0 và 〈F(v∗),v∗− u∗〉 ≥ γ||v∗− u∗||2. Cộng từng vế của hai bất đẳng thức ta được γ||v∗−u∗||2 ≤ 0. Suy ra u∗ = v∗. Cho F liên tục và giả đơn điệu. Để chứng minh S(K,F) là một tập lồi ta chỉ cần chứng minh rằng S(K,F) = ⋂ u∈K {u∗ ∈ K : 〈F(u),u−u∗〉≥ 0}. Thật vậy, nếu u∗ ∈ S(K,F) thì 〈F(u∗),u−u∗〉≥ 0 với mọi u ∈ K. Do hàm F giả đơn điệu nên 〈 F(u),u− u∗〉 ≥ 0 với mọi u ∈ K. Do vậy u∗ thuộc vế phải của đẳng thức 19 trên. Ngược lại, giả sử u∗ ∈ ⋂ u∈K {u∗ ∈ K : 〈F(u),u−u∗〉≥ 0}. Cho u ∈ K tùy ý, vectơ u= τu∗+(1− τ)v ∈ K với mọi τ ∈ (0,1),u∗,v ∈ K. Do đó, ta có:〈 F(τu∗+(1− τ)v),u−u∗〉≥ 0, ∀τ ∈ (0,1). Cho τ → 1 thì 〈F(u∗),u− u∗〉 ≥ 0. Do đó, u∗ ∈ S(K,F). Vì với mỗi u ∈ K, tập {u∗ ∈ K : 〈F(u),u−u∗〉≥ 0} là lồi và giao của các tập lồi là một tập lồi nên S(K,F) là một tập lồi. Mệnh đề được chứng minh.  Đị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. 1.2.2. Các ví dụ minh họa Nhiều bài toán trong tối ưu hóa, phương trình vật lý toán và nhiều vấn đề trong kinh tế, kỹ thuật, cân bằng giao thông đô thị... đều có thể mô tả dưới dạng bài toán bất đẳng thức biến phân. Ví dụ 1.2.2. (Bài toán cân bằng giao thông đô thị) Xét một mạng giao thông được cho bởi một luồng mạng hữu hạn. Gọi + I là tập hợp các phương tiện giao thông, + P là tập hợp các điểm nút giao thông, + E là tập hợp các cạnh (tuyến đường). Giả sử A ⊆ P và B ⊆ P, sao cho A∩B 6= /0. Mỗi phần tử thuộc A gọi là một điểm nguồn. Mỗi phần tử thuộc B gọi là một điểm đích. Mỗi điểm nguồn và điểm đích được nối với nhau bởi một tập hợp liên tiếp các cạnh (tuyến đường). Kí hiệu: + f ie là mật độ giao thông của phương tiện i trên đoạn đường e ∈ E. Đặt f là vectơ có các thành phần là f ie với i ∈ I, và e ∈ E. + cie là chi phí sử dụng phương tiện giao thông i trên đoạn đường E. Đặt c là vectơ có các thành phần là cie với i ∈ I, và e ∈ E. + diω là nhu cầu sử dụng loại phương tiện i trên tuyến đường ω = (A,B).Đặt d là vectơ có các thành phần là diω với i ∈ I, và ω ∈ A×B. Giả sử chi phí giao thông phụ thuộc vào lưu lượng, tức là c = c( f ) là một hàm của f . 20 + λ iω là mức độ chi phí trên tuyến đường ω của phương tiện giao thông i. + xiω : là mật độ giao thông của phương tiện i ∈ I trên tuyến đường ω = (A,B) Giả sử trong mạng trên, phương trình cân bằng sau được thỏa mãn: diω = ∑ p∈Pω xip, ∀i ∈ I,ω ∈ A×B. (1.1) Trong đó, Pω kí hiệu là tập các tuyến đường của ω = (A,B) (nối điểm nguồn A và điểm đích B). Theo phương trình (1.1), thì nhu cầu sử dụng loại phương tiện i trên tuyến đường ω đúng bằng mật độ giao thông của phương tiện đó trên tuyến đường nối điểm nguồn và điểm đích của tuyến đường đó. Khi đó ta có: f ie = ∑ p∈Pω xipδep, ∀i ∈ I,ω ∈ A×B. (1.2) Trong đó: δep = 1 khi e ∈ P0 khi e /∈ P. Với mỗi tuyến đường p nối một điểm nguồn và một điểm đích, đặt cip = ∑ e∈E cieδep. Như vậy, cip là chi phí sử dụng phương tiện i trên tuyến đường p. Mỗi cặp (d ∗, f ∗) thỏa mãn (1.1) và (1.2) được gọi là điểm cân bằng mạng giao thông nếu: cip = = λω i(d∗) khi xip > 0> λω i(d∗) khi xip = 0. Với mỗi i ∈ I và mỗi tuyến đường P. Theo định nghĩa này, tại điểm cân bằng đối với một loại phương tiện giao thông và mọi tuyến đường, chi phí sẽ thấp nhất khi có lưu lượng giao thông trên tuyến đó. Ngược lại, chi phí sẽ không phải là thấp nhất. Đặt K = {( f ,d) | ∃ x≥ 0 sao cho (1.1) và (1.2) đúng }. Khi đó, ta có định lý sau: Định lý 1.2.1. Mỗi cặp vectơ ( f ∗,d∗) ∈ K là một điểm cân bằng của mạng giao thông khi và chỉ khi nó là nghiệm của bài toán bất đẳng thức biến phân sau Tìm ( f ∗,d∗) ∈ K : 〈( c( f ∗),λ (d∗) ) ,( f ,d)− ( f ∗,d∗) 〉 ≥ 0, ∀( f ,d) ∈ K. 21 Ví dụ 1.2.3. (Bài toán cân bằng di trú) Bài toán cân bằng di trú bao gồm một tập hữu hạn các điểm X. Với mỗi i, j ∈ X , gọi + bi là mật độ cố định tại vị trí i, + hi j là trọng số của dòng di trú từ vị trí đầu i đến đích j, + xi là mật độ hiện tại tại vị trí i, + ui là tiện ích di trú, + ci j là chi phí di trú. Đặt x= {xi | i ∈ X} và h= {hi j | i, j ∈ X, i 6= j}, ta định nghĩa X= { (x,h) ∣∣∣∣ h> 0, ∑ i 6= j hi j ≤ bi, xi = bi+∑ i 6= j h ji−∑ i 6= j hi j, ∀i ∈ X } . (1.3) Từ ràng buộc h > 0, ∑ i 6= j hi j ≤ bi, những luồng h là bị chặn . Do đó, mật độ xi = bi+∑ i6= j h ji−∑ i 6= j hi j, i ∈ X , là bị chặn nên X bị chặn. Quy luật trong (1.3) phản ánh sự bảo toàn của dòng và ngăn cản dòng di trú. Rõ ràng, các dòng di trú là không âm. Điều kiện không âm cho mô hình di trú vô hướng là phức tạp hơn mô hình cân bằng mạng. Giả sử rằng tính tiện ích phụ thuộc mật độ, nghĩa là ui = ui(x), và chi phí di trú phụ thuộc và dòng di trú, nghĩa là ci j = ci j(h). Chúng ta nói rằng cặp (x∗,h∗) ∈ X là cân bằng nếu ui(x∗)−u j(x∗)+ ci j(h∗)+µi = 0 nếu h∗i j > 0,≥ 0 nếu h∗i j = 0, ∀i, j ∈ N; (1.4) Trong đó µ j  ≥ 0 nếu ∑ s 6=i h∗is = bi, = 0 nếu ∑ s 6=i h∗is < bi, với mỗi i ∈ N. (1.5) 22 Tập các điều kiện cân bằng (1.4), (1.5) có thể được viết lại tương đương với bất đẳng thức biến phân. Tìm một cặp (x∗,h∗) sao cho ∑ i∈N (x∗i − xi)ui(x∗)+ ∑ i, j∈N,i 6= j (hi j−h∗i j)ci j(h∗)≥ 0, ∀(x,h) ∈ H. Ngoài những vấn đề thực tế, như hai bài toán trên được đưa về bài toán bất đẳng thức biến phân thì ta còn có nhiều bài toán điển hình khác cũng được đưa về bài toán này. Ví dụ 1.2.4. Bài toán điểm bất động Brouwer 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. Chứng minh. Giả sử x∗ là nghiệm của bài toán bất đẳng thức biến phân (VIP) và F(x) = x−T (x), với mọi x ∈ K, tức là〈 F(x∗),x− x∗〉≥ 0, ∀x ∈ K. Do F(x∗) = x∗−T (x∗), ∀x ∈ K. Suy ra〈 x∗−T (x∗),x− x∗〉≥ 0, ∀x ∈ K. Do T (x∗) ∈ K nên thay x ở trên bởi T (x∗) thì〈 x∗−T (x∗),T (x∗)− x∗〉≥ 0. 23 Hay −||x∗−T (x∗)|| ≥ 0. Từ đó, ta được x∗ = T (x∗). Ngược lại, giả sử x∗ là nghiệm của bài toán điểm bất động. Khi đó x∗ = T (x∗). Suy ra F(x∗) = x∗−T (x∗) = 0. Hay 〈 F(x∗),x− x∗〉= 0 Suy ra điều phải chứng minh.  Ví dụ 1.2.5. Bài toán bù phi tuyến Trước khi phát biểu bài toán, ta sẽ trình bày mối quan hệ giữa bài toán (VIP) và nón pháp tuyến của một tập lồi. Mệnh đề 1.2.3. Cho K ⊂H là một tập lồi, đóng, khác rỗng và ánh xạ F : K→H, x∗ là nghiệm của bài toán bất đẳng thức biến phân (VIP) khi và chỉ khi −F(x∗) thuộc nón pháp tuyến của K tại x∗, tức là x∗ ∈ S(K,F)⇔−F(x∗) ∈ NK(x∗). Nói cách khác, x∗ là nghiệm của bài toán bất đẳng thức biến phân khi và chỉ khi 0 ∈ F(x∗)+NK(x∗). Chứng minh. Theo định nghĩa ta có x∗ ∈ S(K,F)⇔ 〈F(x∗),x− x∗〉≥ 0, ∀x ∈ K ⇔ 〈−F(x∗),x− x∗〉≤ 0, ∀x ∈ K ⇔−F(x∗) ∈ NK(x∗). Suy ra điều phải chứng minh.  Định nghĩa 1.2.5. Cho K ⊂ H là một tập lồi, đóng, khác rỗng, nón đối ngẫu của K, kí hiệu là K∗, là một tập được định nghĩa bởi K∗ = {y : 〈y,x〉≥ 0, ∀x ∈ K}. 24 Về mặt hình học, K∗ là tập hợp bao gồm tất cả các vectơ y ∈H tạo thành một góc không tù với mọi vectơ x∈K. Sau đây, chúng ta sẽ đi phát biểu bài toán bù phi tuyến: Cho K ⊂ H là một tập lồi, đóng, khác rỗng và K∗ là nón đối ngẫu của K, ánh xạ F : K→ H. Bài toán bù phi tuyến là bài toán Tìm x∗ ∈ K : F(x∗) ∈ K∗;〈x∗,F(x∗)〉= 0. (NCP) Tập các nghiệm của bài toán (NCP) kí hiệu là S∗(K,F). Mối quan hệ giữa bài toán (VIP) và bài toán (NCP) được thể hiện qua mệnh đề sau: Mệnh đề 1.2.4. Nếu K là một nón lồi, đóng trong H thì tập nghiệm của bài toán (NCP) và bài toán (VIP) là trùng nhau, tức là: S∗(K,F) = S(K,F). Chứng minh. Giả sử x∗ ∈ S(K,F). Theo định nghĩa, ta có: ∃x∗ ∈ K : 〈F(x∗),x− x∗〉≥ 0, ∀x ∈ K. Bằng cách lấy x= 0 ∈ K, suy ra 〈 F(x∗),−x∗〉≥ 0. Bằng cách lấy x= 2x∗ ∈ K, suy ra〈 F(x∗),x∗ 〉≥ 0. Từ đó, ta thu được 〈 F(x∗),x∗ 〉 = 0. Mặt khác, từ định nghĩa ta có: 0≤ 〈F(x∗),x− x∗〉= 〈F(x∗),x〉−〈F(x∗),x∗〉= 〈F(x∗),x〉, ∀x ∈ K. Vậy F(x∗) ∈ K∗. Suy ra x∗ ∈ S∗(K,F). Hay S(K,F)⊂ S∗(K,F). Ngược lại, giả sử x∗ ∈ S∗(K,F). Theo định nghĩa, ta có: F(x∗) ∈ K∗ : 〈F(x∗),x∗〉= 0. Mặt khác, vì F(x∗) ∈ K∗, nên với mọi x ∈ K ta có:〈 F(x∗),x− x∗〉= 〈F(x∗),x〉−〈F(x∗),x∗〉= 〈F(x∗),x〉≥ 0. Suy ra x∗ ∈ S(K,F). Hay S∗(K,F)⊂ S(K,F). Vậy S∗(K,F) = S(K,F). Suy ra điều phải chứng minh.  25 1.2.3. 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.5. 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. Chứng minh. Giả sử K không bị chặn. Theo Bổ đề (1.2.1) ta có: ∃ hình cầu đóng B : ∀x ∈ K\B, ∃y ∈ K∩B : 〈F(x),y− x〉< 0. (1.6) Thật vậy, nếu không, với mọi hình cầu đóng Br tâm O, bán kính r, tồn tại xr ∈ K\Br sao cho 〈 F(xr),y0− x〉≥ 0, ∀y ∈ K∩Br. Cố định r0 > 0, thì với mọi r > r0, tồn tại xr ∈ K\Br sao cho 〈 F(xr),y0− xr〉 ≥ 0, với y0 ∈ K∩Br0 . Do đó, vì F là β−giả đơn điệu mạnh, ta có:〈 F(y0),xr− y0〉+β ||xr− y0||2 ≤ 0 ∀r. (1.7) Mặt khác, do tập K lồi và 〈 F(y0),∗− y0〉 lồi trên K, với εr := 1r tồn tại x0 ∈ K sao cho ∂ εr2 〈 F(y0),x0− y0〉 6= /0, trong đó ∂ εr2 〈F(y0),x0− y0〉 là viết tắt của εr-khả dưới vi phân của hàm lồi 〈 F(y0),∗− y0〉 tại x0. Lấy w∗ ∈ ∂ εr2 〈F(y0),x0− y0〉, theo định nghĩa của εr-khả dưới vi phân ta có:〈 F(y0),x− y0〉+ 1 r ≥ 〈w∗,x− x0〉+〈F(y0),x0− y0〉 ∀x. Thay x= xr ta thu được 〈 F(y0),xr− y0〉+β ||xr− y0||2+ 1 r ≥ 〈F(y0),x0− y0〉+〈w∗,xr− x0〉+β ||xr− y0||2 ≥ 〈F(y0),x0− y0〉−||w∗|| ||xr− x0||+β ||xr− y0||2. 26 Cho r→ ∞, từ đó ||xr|| → ∞, suy ra 〈F(y0),xr− y0〉+β ||xr− y0||2→ ∞ mâu thuẫn với (1.7). Do đó, điều kiện bức (1.6) phải đúng. Theo Bổ để 1.2.1, bài toán bất đẳng thức biến phân (VI) thừa nhận một nghiệm. Trong trường hợp K bị chặn, mệnh đề là một hệ quả của Định lý Ky Fan.[5] Tính duy nhất nghiệm được suy luận trực tiếp từ Mệnh đề 1.2.1. Mệnh đề được chứng minh.  27 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]. 28 Đề 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.6. 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. 29 Chứng minh. Do F liên tục Lipschitz nên tồn tại L> 0 sao cho ||F(u)−F(v)|| ≤ L||u− v||, ∀u,v ∈ K. Theo Hệ quả 1.1.1 ta có: ||v−PK(u)||2 ≤ ||u− v||2−||u−PK(u)||2, ∀v ∈ K,u ∈ H. Thay v = u∗ ∈ K,u = uk−λkF(uk) và uk+1 = PK(uk−λkF(uk)) vào bất đẳng thức trên ta được ||u∗−uk+1||2 ≤ ||uk−λkF(uk)−u∗||2−||uk−λkF(uk)−uk+1||2 = ||(uk−u∗)−λkF(uk)||2−||(uk−uk+1)−λkF(uk)||2 = ||uk−u∗||2−||uk−uk+1||2+2λk 〈 F(uk),u∗−uk+1〉. Vì u∗ ∈ S(K,F), nên 〈F(u∗),u−u∗〉≥ 0, với mọi u ∈ K. Theo tính chất giả đơn điệu mạnh của F ta có 〈 F(u),u− u∗〉 ≥ γ||u− u∗||2 với mọi u ∈ K. Cho u = uk ∈ K, ta được bất đẳng thức mới 〈 F(uk),u∗−uk〉≤−γ||uk−u∗||2. Do đó〈 F(uk),u∗−uk+1〉= 〈F(uk),u∗−uk〉+〈F(uk),uk−uk+1〉 ≤−γ||uk−u∗||2+〈F(uk),uk−uk+1〉. Suy ra ||uk+1−u∗||2 ≤ ||uk−u∗||2−||uk−uk+1||2−2γλk||uk−u∗||2+2λk 〈 F(uk),uk−uk+1〉 = ||uk−u∗||2−||uk−uk||2−||uk−uk+1||2−2〈uk−uk,uk−uk+1〉 −2γλk||uk−u∗||2+2λk 〈 F(uk),uk−uk+1〉 = ||uk−u∗||2−||uk−uk||2−||uk−uk+1||2−2γλk||uk−u∗||2 +2 〈 uk−uk−λkF(uk),uk+1−uk 〉 . Mặt khác〈 uk−uk−λkF(uk),uk+1−uk 〉 = 〈 uk−uk−λkF(uk),uk+1−uk 〉 + 〈 λkF(uk)−λkF(uk),uk+1−uk 〉 ≤ λk 〈 F(uk)−F(uk),uk+1−uk〉> ≤ λk||F(uk)−F(uk)|| ||uk+1−uk|| ≤ λkL||uk−uk|| ||uk+1−uk||. 30 Suy ra ||uk+1−u∗||2 ≤ ||uk−u∗||2−||uk−uk||2−||uk−uk+1||2 +2λkL||uk−uk|| ||uk+1−uk||−2γλk||uk−u∗||2. Hơn nữa 2λkL||uk−uk|| ||uk+1−uk|| ≤ λ 2k L2||uk−uk||2+ ||uk+1−uk||2, nên ta thu được ||uk+1−u∗||2 ≤ ||uk−u∗||2−||uk−uk||2+λ 2k L2||uk−uk||2−2γλk||uk−u∗||2 ≤ ||uk−u∗||2− (1−λ 2k L2)||uk−uk||2−2γλk||uk−u∗||2. Cho λk → 0, khi đó tồn tại k0 ∈ N sao cho 2γλk ≤ 1−λ 2k L2 với mọi k ≥ k0. Do đó với k ≥ k0, ta có γλk ≤ 12 − 1 2 λ 2k L 2 < 1 và ||uk+1−u∗||2 ≤ ||uk−u∗||2−2γλk(||uk−uk||2+ ||uk−u∗||2) ≤ ||uk−u∗||2− γλk(||uk−uk||+ ||uk−u∗||)2 ≤ ||uk−u∗||2− γλk||uk−u∗||2. Lấy tổng của các bất đẳng thức ||uk+1−u∗||2 ≤ ||uk−u∗||2−γλk||uk−u∗||2 từ k0 tới n. Ta được ||un+1−u∗||2 ≤ ||uk0 −u∗||2− n ∑ k=k0 γλk||uk−u∗||2. Vì thế n ∑ k=k0 γλk||uk−u∗||2 ≤ ||uk0 −u∗||2−||un+1−u∗||2. Vì ||uk+1−u∗||2 ≤ ||uk−u∗||2− γλk||uk−u∗||2 ≤ ||uk−u∗||2 với k ≥ k0. Do vậy γ ( n ∑ k=k0 λk ) ||un−u∗||2 ≤ n ∑ k=k0 γλk||uk−u∗||2 ≤ ||uk0 −u∗||2−||un+1−u∗||2 ≤ ||uk0 −u∗||2. Vì ∞ ∑ k=0 λk = +∞ và γ > 0 nên limn→∞ ||u n−u∗|| = 0. Do đó dãy {uk} hội tụ theo chuẩn tới u∗. 31 Tiếp theo ta sẽ chứng minh tồn tại k0 ∈ N sao cho γλk < 1 với mọi k ≥ k0 và ||uk+1−u∗|| ≥ √ ∏kj=k0(1− γλ j)||uk0 −u∗||. Với k ≥ k0 ||uk+1−u∗||2 ≤ (1− γλk)||uk−u∗||2 ≤ (1− γλk)(1− γλk−1)||uk−1−u∗||2 ... ≤ k ∏ j=k0 (1− γλ j)||uk0 −u∗||2. Suy ra ||uk+1−u∗|| ≤ √√√√ k∏ j=k0 (1− γλ j)||uk0 −u∗||. Mặt khác, ta thấy rằng 1− γλ j ≤ 11+ γλ j ∀ j ≥ k0, do đó k ∏ j=k0 (1− γλ j)≤ 1k ∏ j=k0 (1+ γλ j) ≤ 1 1+ γ k ∑ j=k0 λ j −→ 0 khi k −→ ∞. Định lý được chứng minh.  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. 32 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 . 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 ,