Luận văn Một tiếp cận tối ưu hai cấp cho hiệu chỉnh bài toán cân bằng giả đơn điệu (chuyên ngành: Toán ứng dụng)

ợi cho em hoàn thành khóa học này. Tác giả xin gửi lời cám ơn chân thành tới gia đình, đồng nghiệp, các anh chị, bạn bè trong lớp cao học khóa 2013 - 2015 đã luôn động viên, khích lệ tác giả cố gắng trong suốt khóa học để luôn đạt được kết quả học tập cao nhất. Em xin chân thành cảm ơn! 3 MỞ ĐẦU Lớp các bài toán cân bằng đang ngày càng được áp dụng nhiều vào các lĩnh vực trong cuộc sống như kinh tế, xã hội,... Chính vì vậy mà ngày càng được các nhà khoa học quan tâm, nghiên cứu. Hơn nữa, bài toán cân bằng còn là sự mở rộng của lớp các bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán cân bằng Nash, bài toán điểm yên ngựa,... Mô hình chung cho bài toán cân bằng là Tìm x∗ ∈C sao cho f (x∗,y)≥ 0 với mọi y ∈C (EP(C, f )) trong đóH là không gian Hilbert, C ⊆H là một tập lồi và f :C×C→ R∪{+∞} là một song hàm. Bài toán hiệu chỉnh được xây dựng bằng cách thay song hàm ban đầu bằng song hàm fε := f +εg, trong đó ε,g lần lượt là tham số hiệu chỉnh và song hàm hiệu chỉnh, thông thường ta chọn g là một song hàm đơn điệu mạnh. Luận văn nghiên cứu và trình bày một số phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu và thông qua bài toán tối ưu hai cấp để tìm điểm giới hạn của các quỹ đạo nghiệm hiệu chỉnh. Dựa trên ý tưởng của phương pháp hiệu chỉnh Tikhonov, trong [4] các tác giả đã đưa ra phương pháp hiệu chỉnh với bài toán hiệu chỉnh như sau{ Tìm x ∈C sao cho fk(x,y) := f (x,y)+ εkg(x,y)≥ 0 với mọi y ∈C, trong đó εk > 0 là tham số hiệu chỉnh, g(x,y) là một song hàm đơn điệu mạnh gọi là song hàm hiệu chỉnh. Năm 1970 Martine đưa ra phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đơn điệu và sau này được mở rộng bởi Rockafellar (1976) cho toán tử đơn điệu cực đaị. Bài toán hiệu chỉnh có dạng{ Tìm xk ∈C sao cho fk(xk,y) := f (xk,y)+ ck〈xk− xk−1,y− xk〉 ≥ −δk với mọi y ∈C, trong đó ck > 0,δk > 0 lần lượt là các tham số hiệu chỉnh và sai số cho trước. Sự khác biệt giữa hai phương pháp này là ở phương pháp hiệu chỉnh điểm gần kề tại 4 MỞ ĐẦU mỗi bước lặp bài toán hiệu chỉnh phụ thuộc vào điểm lặp ở bước trước và tham số hiệu chỉnh ck 6→ 0 khi k→ ∞. Nội dung của luận văn gồm ba chương • Chương 1: Kiến thức chuẩn bị. • Chương 2: Bài toán cân bằng. • Chương 3: Hiệu chỉnh dựa trên tối ưu hai cấp. Chương 1 trình bày một số kiến thức cơ sở như không gian tuyến tính, không gian Hilbert; các kiến thức về giải tích lồi như tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới. Chương 2 phát biểu bài toán cân bằng, một số trường hợp có thể đưa về bài toán cân bằng và sự tồn tại nghiệm của bài toán. Chương 3 trình bày phương pháp hiệu chỉnh bài toán cân bằng giả đơn điệu, thuật toán tiếp cận dựa trên bài toán tối ưu hai cấp và sự hội tụ của thuật toán. Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế nên luận văn khó tránh khỏi những thiếu sót. Vì vậy em rất mong nhận được sự góp ý của các thầy cô và các bạn để luận văn được hoàn thiện hơn. Hà Nội, ngày 28 tháng 09 năm 2015 Tác giả Nguyễn Thị Thanh Hải 5 Chương 1 Kiến thức chuẩn bị Chương này chúng ta nhắc lại một số kiến thức về không gian tuyến tính, không gian Hilbert, tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới. Các kiến thức này được lấy ra từ các tài liệu [1], [2]. 1.1 Không gian Hilbert 1.1.1 Không gian tuyến tính định chuẩn. Định nghĩa 1.1.1. Cho X là một không gian tuyến tính thực. Một chuẩn trên X, kí hiệu là ‖.‖, là một ánh xạ ‖.‖ : X → R thỏa mãn các tính chất sau 1. ‖x‖ ≥ 0, ∀x ∈ X ;‖x‖= 0⇔ x= 0; 2. ‖αx‖= |α|‖x‖, ∀x ∈ X , α ∈ R; 3. ‖x+ y‖ ≤ ‖x‖+‖y‖, ∀x,y ∈ X . Khi đó (X ,‖.‖) được gọi là không gian tuyến tính định chuẩn. Định nghĩa 1.1.2. Cho X là không gian tuyến tính thực, X được gọi là không gian tiền Hilbert nếu với mọi x,y ∈ X , xác định một tích vô hướng, kí hiệu là 〈x,y〉, thỏa mãn các tính chất 1. 〈x,y〉= 〈y,x〉, ∀x,y ∈ X ; 2. 〈x+ y,z〉= 〈x,z〉+ 〈y,z〉, ∀x,y,z ∈ X ; 3. 〈αx,y〉= α〈x,y〉, ∀x,y ∈ X , α ∈ R; 4. 〈x,x〉 ≥ 0, ∀x ∈ X ; 〈x,x〉= 0⇔ x= 0. 6 Chương 1. Kiến thức chuẩn bị 1.1.2 Không gian Hilbert Định nghĩa 1.1.3. Cho X là không gian định chuẩn. Dãy {xn} ⊆ X được gọi là dãy cơ bản trong X nếu lim n,m→∞‖xn− xm‖= 0. Nếu trong X, mọi dãy cơ bản đều hội tụ, tức là ‖xn− xm‖ → 0 kéo theo sự tồn tại xo ∈ X sao cho xn→ xo thì X được gọi là không gian đủ. Định nghĩa 1.1.4. Không gian tiền Hilbert và đủ được gọi là không gian Hilbert. Trong luận văn này ta thống nhất kí hiệuH là một không gian Hilbert trên trường số thực. 1.2 Tập lồi, nón lồi, hàm lồi 1.2.1 Tập lồi Định nghĩa 1.2.1. Một tập C ⊆H được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi ∀x,y ∈C,∀λ ∈ [0,1]⇒ λx+(1−λ )y ∈C. 1.2.2 Nón lồi Định nghĩa 1.2.2. Tập C được gọi là nón nếu với mọi λ > 0 và với mọi x ∈C suy ra λx ∈C.Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi. Định nghĩa 1.2.3. ChoC 6= /0 (không nhất thiết lồi) và y là một vectơ bất kỳ, đặt dC(y) := inf x∈C ‖x− y‖. Ta nói dC(y) là khoảng cách từ y đến C. Nếu tồn tại pi ∈C sao cho dC(y) = ‖pi−y‖, thì ta nói pi là hình chiếu của y trên C, kí hiệu pC(y). Theo định nghĩa trên ta thấy rằng, hình chiếu pC(y) của y trên C sẽ là nghiệm của bài toán tối ưu min x {1 2 ‖x− y‖2|x ∈C}. 7 Chương 1. Kiến thức chuẩn bị 1.2.3 Hàm lồi Định nghĩa 1.2.4. 1. Cho /0 6=C ⊆H lồi và f :C→ R∪{+∞}. Ta nói f là hàm lồi trên C nếu f ( λx+(1−λ )y)≤ λ f (x)+(1−λ ) f (y) ∀x,y ∈C,∀λ ∈ [0,1]. 2. Hàm f :H → R∪{+∞} được gọi là lồi chặt trên C nếu f ( λx+(1−λ )y)< λ f (x)+(1−λ ) f (y) ∀x,y ∈C,∀λ ∈ (0,1). 3. Hàm f :H → R∪{+∞} được gọi là lồi mạnh trên C với hệ số η nếu với mọi x,y ∈C và với mọi λ ∈ (0,1) f ( λx+(1−λ )y)≤ λ f (x)+(1−λ ) f (y)− 1 2 ηλ (1−λ )‖x− y‖2. 4. Hàm f được gọi là hàm lõm trên C nếu − f là hàm lồi trên C. 8 Chương 2 Bài toán cân bằng Chương này chúng ta nhắc lại các khái niệm về song hàm cân bằng, toán tử cân bằng và phát biểu bài toán cân bằng. Một số bài toán có thể đưa về dạng bài toán cân bằng và sự tồn tại nghiệm của bài toán. Các kiến thức này được tham khảo từ các tài liệu [2], [3]. 2.1 Bài toán cân bằng và các khái niệm Trong kinh tế và nhiều lĩnh vực khác bài toán cân bằng có nhiều ý nghĩa quan trọng. Hơn nữa, bài toán là sự mở rộng của nhiều bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash, bài toán điểm yên ngựa,... Vì vậy mà lớp các bài toán cân bằng được nhiều nhà toán học quan tâm, nghiên cứu. 2.1.1 Phát biểu bài toán Định nghĩa 2.1.1. Giả sử C ⊆H là một tập lồi, đóng, khác rỗng và f :H ×H → R∪{+∞} thỏa mãn f (x,x) = 0 với mọi x ∈C. Khi đó ta gọi hàm f là một song hàm cân bằng trênC. Cho f là một song hàm cân bằng trênC. Ta xét bài toán Tìm x∗ ∈C sao cho f (x∗,y)≥ 0, ∀y ∈C. (EP(C, f )) Ta kí hiệu bài toán này là EP(C, f ) và gọi là bài toán cân bằng, tập nghiệm của nó được kí hiệu là S(C, f ). 2.1.2 Các khái niệm Định nghĩa 2.1.2. Song hàm f :H ×H → R∪{+∞} được gọi là 9 Chương 2. Bài toán cân bằng 1. đơn điệu mạnh trên C với hệ số γ > 0 nếu f (x,y)+ f (y,x)≤−γ‖x− y‖2,∀x,y ∈C; 2. đơn điệu trên C nếu f (x,y)+ f (y,x)≤ 0,∀x,y ∈C; 3. giả đơn điệu trên C nếu f (x,y)≥ 0⇒ f (y,x)≤ 0,∀x,y ∈C. Từ định nghĩa trên ta suy ra: 1)⇒ 2)⇒ 3). Điều ngược lại chưa chắc đã đúng.Thật vậy, để làm rõ vấn đề này ta xét một số ví dụ sau. Ví dụ 2.1.1. Xét song hàm f (x,y) = ε〈x,y− x〉, ∀x,y ∈H , trong đó ε > 0. Với hằng số γ > 0 nào đó thỏa mãn γ ≤ ε ta có f (x,y)+ f (y,x) = ε〈x,y− x〉+ ε〈y,x− y〉; = ε〈−x+ y,x− y〉; =−ε‖x− y‖2 ≤−γ‖x− y‖2. Chứng tỏ f là song hàm đơn điệu mạnh trênH . Do γ > 0 nên từ đẳng thức f (x,y)+ f (y,x)≤−γ‖x− y‖2 ta suy ra f (x,y)+ f (y,x)≤ 0 ∀x,y ∈H , chứng tỏ f là đơn điệu trênH . Giả sử f (x,y)≥ 0 với mọi x,y ∈H . Khi đó, do f (x,y)+ f (y,x)≤ 0, suy ra f (y,x)≤− f (x,y)≤ 0, ∀x,y ∈H . Vậy f là song hàm giả đơn điệu. 10 Chương 2. Bài toán cân bằng Ví dụ 2.1.2. Cho không gian Hilbert thực H = l2 := { x= (x1,x2, ...,xi, ...) := ∞ ∑ i=1 |xi|2 <+∞, ∀xi ∈ R } . Tích vô hướng và chuẩn trênH tương ứng được xác định bởi 〈x,y〉 := ∞ ∑ i=1 xiyi, ‖x‖ := √ 〈x,x〉 với mọi x= (x1,x2, ...,xi, ...) = (x1, x̂) ∈H , y= (y1,y2, ...,yi, ...) = (y1, ŷ) ∈H , trong đó x̂ := (x2, ...,xi, ...), ŷ := (y2, ...,yi, ...). Kí hiệu 〈x̂, ŷ〉 := ∞ ∑ i=2 xiyi, ‖x̂‖ := √ 〈x̂, x̂〉. Xét tậpC = {x ∈H : ‖x‖ ≤ √2} và hàm f :C×C→ R được cho bởi f (x,y) = (2−‖x̂‖)〈x̂, ŷ− x̂〉. Nhận thấy, tập nghiệm của bài toán EP(C, f ) là C˜ := S(C, f ) = {(x1,0, ...,0, ...) : x1 ∈ R)}. Với x,y ∈C ta có 2−‖x̂‖> 0 và 2−‖ŷ‖> 0. Do đó f (x,y) = (2−‖x̂‖)〈x̂, ŷ− x̂〉 ≥ 0; ⇒ 〈x̂, ŷ− x̂〉 ≥ 0; ⇒ 〈ŷ, x̂− ŷ〉 ≤ 0; ⇒ f (y,x) = (2−‖ŷ‖)〈ŷ, x̂− ŷ〉 ≤ 0. Chứng tỏ f là song hàm giả đơn điệu trên C. Lấy x= (0,1,0, ...,0, ...), y= (0, √ 2,0, ...,0, ...) ∈C. Khi đó x̂= (1,0, ...,0, ...), ŷ= ( √ 2,0, ...,0, ...) và ‖x̂‖= 1, ‖ŷ‖= √ 2. Nhận thấy f (x,y)+ f (y,x) = (2−1)×1× ( √ 2−1)+(2− √ 2)× √ 2× (1− √ 2) = ( √ 2−1)× (2 √ 2−1)> 0. Vậy, f không đơn điệu trênC. 11 Chương 2. Bài toán cân bằng 2.2 Các trường hợp riêng của bài toán cân bằng 2.2.1 Bài toán tối ưu Cho hàm số ϕ :C→ R. Xét bài toán tối ưu Tìm x∗ ∈C sao cho ϕ(x∗)≤ ϕ(y), ∀y ∈C. (OP) Đặt f (x,y) := ϕ(y)−ϕ(x). Rõ ràng f (x,x) = ϕ(x)−ϕ(x) = 0. Vậy f là một song hàm cân bằng. Khi đó bài toán tối ưu (OP) tương đương với bài toán Tìm x∗ ∈C sao cho ϕ(y)−ϕ(x∗)≥ 0, ∀y ∈C hay Tìm x∗ ∈C sao cho f (x∗,y)≥ 0, ∀y ∈C. Đây chính là bài toán cân bằng. 2.3 Sự tồn tại nghiệm của bài toán cân bằng Trong mục này chúng ta sẽ xét tới sự tồn tại nghiệm của bài toán cân bằng trong các trường hợp compact và trường hợp có điều kiện bức. Ta xét sự tồn tại nghiệm của bài toán cân bằng dựa trên các giả thiết sau đây ChoC ⊆H là một tập lồi, đóng, khác rỗng và f :H ×H → R∪{+∞} Giả thiết (A1) f (.,y) là hàm nửa liên tục trên, yếu trênH đối với mỗi y ∈C; (A2) f (x, .) là hàm lồi, nửa liên tục dưới yếu trênH và khả vi trên dom f (x, .) đối với mỗi x ∈C; (A3) Tồn taị một tập compact B⊂H và một vectơ y0 ∈ B∩C sao cho f (x,y0)< 0 ∀x ∈C \B. Giả thiết (A3) còn được gọi là điều kiện bức. Ta xét định lý sau. Định lý 2.3.1. (Ky Fan’theorem). Giả sử C là một tập lồi đóng, khác rỗng trong không gian HilbertH và f :C×C→R∪{+∞} là một song hàm cân bằng xác định trên C. Nếu f thỏa mãn giả thiết A1 và f (x, .) là tựa lồi trên C với mỗi x ∈C cố định. Khi đó nếu C là tập compact hoặc điều kiện bức (A3) được thỏa mãn thì bài toán EP(C, f ) có nghiệm. 12 Chương 2. Bài toán cân bằng Mệnh đề 2.3.1. 1. Nếu hàm f đơn điệu mạnh trên C và thỏa mãn các giả thiết (A1),(A2), thì EP(C, f ) có nghiệm duy nhất. 2. Nếu hàm f thỏa mãn các giả thiết (A1),(A2) và giả đơn điệu trên C thì nghiệm của EP(C, f ) là một tập lồi, đóng yếu. 3. Nếu hàm f thỏa mãn các giả thiết (A1),(A2) và (A3) thì tập nghiệm của EP(C, f ) là khác rỗng. Mệnh đề 2.3.2. Giả sử f thỏa mãn các giả thiết (A1) và (A2). Xét các mệnh đề sau 1. Tồn tại một véctơ y0 ∈C sao cho L(y0, f ) := {x ∈C : f (x,y0)≥ 0} là một tập bị chặn. 2. Tồn tại một hình cầu đóng B⊆H và một vectơ y0 ∈C∩B sao cho f (x,y0)< 0,∀x ∈C \B. 3. Tập nghiệm S(C, f ) của bài toán EP(C, f ) là khác rỗng và compact yếu. Khi đó 1)⇒ 2)⇒ 3). Hơn nữa nếu f là giả đơn điệu trênC thì S(C, f ) là lồi và tập L>(y0, f ) : {x ∈C : f (x,y0)> 0} là rỗng với mọi y0 ∈ S(C, f ). 13 Chương 3 Hiệu chỉnh dựa trên tối ưu hai cấp Trong chương này chúng ta sẽ nghiên cứu hai phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu đó là phương pháp Tikhonov và phương pháp điểm gần kề. Thuật toán và tính hội tụ của thuật toán hiệu chỉnh dựa trên bài toán tối ưu hai cấp. Các kết quả được lấy ra từ các tài liệu [3], [4], [5], [6], [7]. 3.1 Hiệu chỉnh bài toán cân bằng giả đơn điệu 3.1.1 Phương pháp hiệu chỉnh Tikhonov Xét bài toán cân bằng Tìm x∗ ∈C sao cho f (x∗,y)≥ 0, ∀y ∈C, trong đó C là một tập lồi đóng trongH , f :C×C→R là một song hàm giả đơn điệu trên C. Khi đó bài toán hiệu chỉnh được xây dựng như sau.{ Tìm x ∈C sao cho fε(x,y) := f (x,y)+ ε〈x− xg,y− x〉 ≥ −δ , ∀y ∈C (EPδ (C, fε)) trong đó g(x,y) là một song hàm đơn điệu mạnh được gọi là song hàm hiệu chỉnh, ε > 0 là tham số hiệu chỉnh. Kí hiệu Sδ (C, fε) là tập nghiệm của bài toán EPδ (C, fε). Ta xét bổ đề sau Bổ đề 3.1.1. Giả sử f là giả đơn điệu trên C. Khi đó với mọi ε > 0, δ ≥ 0, x ∈ S(C, f ), x(ε) ∈ Sδ (C, fε) và xg ∈C, ta có 1. ‖xg− x(ε)‖2+‖x(ε)− x‖2 ≤ ‖xg− x‖2+2δ ε , 2. Sδ (C, fε)⊂ B ( 0, ∥∥∥x+ xg 2 ∥∥∥+√∥∥∥x− xg 2 ∥∥∥+ δε ) ∩C, 14 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp 3. ‖x(ε)− xg‖ ≤ ∥∥∥x− xg 2 ∥∥∥+√∥∥∥x− xg 2 ∥∥∥2+ δε , trong đó kí hiệu B(x,r) là hình cầu đóng tâm x, bán kính r. Ví dụ 3.1.1. Ta xét song hàm giả đơn điệu được xác định như ở Ví dụ 2.1.3 Xét bài toán hiệu chỉnh{ Tìm xk ∈C sao cho fεk(x k,y) := f (xk,y)+ εk〈xk− xg,y− xk〉 ≥ −δk, ∀y ∈C, (EP(C, fεk)) trong đó xg=(xg1,x g 2, ...,x g i , ...)∈C là nghiệm dự đoán của bài toán EP(C, f );{εk},{δk} là hai dãy số dương đơn điệu giảm về 0 thỏa mãn δk εk → 0 khi k→ ∞, và fεk(x k,y) = (2−‖x̂k‖)〈x̂k, ŷ− x̂k〉+ εk(xk1− xg1)(y1− xk1)+ εk〈x̂k− x̂g, ŷ− x̂k〉 = εk(xk1− xg1)(y1− xk1)+ ε〈(2−‖x̂k‖+ εk)x̂k− εkx̂g, ŷ− x̂k〉. Ta nhận thấy, nếu xk1 = x g 1,(2−‖x̂k‖+ εk)x̂k− εkx̂g = 0 được thỏa mãn thì xk = (xk1, x̂ k) là một nghiệm của bài toán EP(C, fεk). Từ đẳng thức (2−‖x̂k‖+ εk)x̂k− εkx̂g = 0 ta suy ra 0≤ ‖x̂k‖= ∥∥∥ εkx̂g 2−‖x̂k‖+ εk ∥∥∥≤ ε√2 2−√2+ εk . Do khi k→ ∞ thì εk→ 0 nên 0≤ limk→+∞‖x̂k− 0̂‖= limk→+∞‖x̂k‖ ≤ lim k→+∞ εk √ 2 2−√2+ εk ⇒ limk→+∞‖x̂k− 0̂‖= 0. Điều này chứng tỏ x̂k hội tụ mạnh về 0̂. Do đó, xk hội tụ mạnh về x∗ := (xg1, 0̂) = (x g 1,0, ...,0, ...) ∈ C˜. Hơn nữa, x∗ là nghiệm duy nhất của bài toán cân bằng đơn điệu mạnh EP(C˜,g) với g(x,y) := (x1− xg1)(y1− x1)+ 〈x̂− x̂g, ŷ− x̂〉 ≥ 0. 3.1.2 Phương pháp điểm gần kề Trong phần này chúng ta sẽ nghiên cứu phương pháp điểm gần kề cho bài toán cân bằng giả đơn điệu. Kết quả hội tụ của phương pháp này cho thấy phương pháp điểm 15 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp gần kề cũng có thể sử dụng cho bài toán cân bằng giả đơn điệu. Tuy nhiên, khác với phương pháp hiệu chỉnh Tikhonov, ở phương pháp này, tại mỗi bước lặp, bài toán hiệu chỉnh phụ thuộc vào điểm lặp ở bước trước và tham số hiệu chỉnh ck > 0 không cần dần đến 0. Xuất phát từ một điểm x0 ∈C cho trước, tại mỗi bước lặp k = 1,2, ... xét bài toán hiệu chỉnh{ Tìm xk ∈C sao cho fk(xk,y) := f (xk,y)+ ck〈xk− xk−1,y− xk〉 ≥ −δk, ∀y ∈C trong đó tham số ck > 0 và sai số δk ≥ 0 cho trước. Ta gọi nghiệm của bài toán hiệu chỉnh trên là δk−nghiệm và kí hiệu tập tất cả các δk−nghiệm là Sδk(C, fk). Gọi dãy {xk} với xk ∈ Sδk(C, fk) là một quỹ đạo xấp xỉ gần kề. Định lý sau đây sẽ chỉ ra rằng, đối với bài toán cân bằng giả đơn điệu, mặc dù bài toán hiệu chỉnh không có duy nhất nghiệm nhưng mọi quỹ đạo xấp xỉ đều có cùng một giới hạn. Định lý 3.1.1. Giả sử f là giả đơn điệu trên C thỏa mãn các giả thiết (A1), (A2) và bài toán EP(C, f ) là có lời giải. Lấy {ck} và {δk} là hai dãy số dương sao cho ck ≤ c<+∞,∀k, và ∑∞k=1 δkck <+∞. Khi đó 1. Đối với mỗi k ∈N tập nghiệm Sδk(C, fk) khác rỗng, đóng và bị chặn đều. Khi đó ta có ‖xk−1− xk‖2+‖xk− x‖2 ≤ ‖xk−1− x‖2+2δk ck , (3.3) trong đó x ∈ S(C, f ), xk ∈ Sδk(C, fk). 2. Xét dãy {xk} bất kỳ, trong đó xk chọn tùy ý trong tập Sδk(C, fεk), hội tụ yếu đến một nghiệm của bài toán EP(C, f ). Hơn nữa, nếu {xk} có một điểm hội tụ mạnh, khi đó toàn bộ dãy sẽ hội tụ mạnh đến một nghiệm của bài toán EP(C, f ) ban đầu. Định lý 3.1.2. Giả sử C ⊆ Rn là một tập lồi, đóng, khác rỗng, f là giả đơn điệu trên C, f (.,y) là nửa liên tục trên với mỗi y ∈C, f (x, .) là nửa lên tục dưới và lồi với mỗi x ∈C, bài toán cân bằng EP(C, f ) có nghiệm. Lấy {ck},{δk} là hai dãy số dương sao cho ck < c<+∞ và ∑∞k=1 δk ck <+∞. Khi đó 1. Với mọi k, tập δk-nghiệm của bài toán EP(C, fk) là khác rỗng và compact. 2. Mọi dãy {xk}, với xk là một δk-nghiệm của bài toán EP(C, fk) đều hội tụ mạnh tới các nghiệm của bài toán EP(C, f ). 16 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp Nhận xét. Các kết quả trên đã chỉ ra rằng, mọi quỹ đạo của thuật toán điểm gần kề đều có chung một điểm giới hạn yếu. Tuy nhiên việc tìm điểm giới hạn này là một việc khó do sự hội tụ là không mạnh và các kết quả trên không chỉ ra được điểm giới hạn này. Để làm rõ điều này ta xét ví dụ sau. Ví dụ 3.1.2. Xét song hàm cân bằng giả đơn điệu trong Ví dụ 2.1.3. Ta xét bài toán hiệu chỉnh{ Tìm xk ∈C sao cho fk(xk,y) := f (xk,y)+ ck〈xk− xk−1,y− xk〉 ≥ −δk, ∀y ∈C, (3.1.1) trong đó x0 = xg = (xg1,x g 2, ...,x g i , ...) là điểm xuất phát của dãy lặp, đóng vai trò là nghiệm dự đoán của bài toán EP(C, f );{ck},{δk} là hai dãy số không âm sao cho ck ≤ c<+∞ với mọi k ∈ N và ∑∞k=1 δk ck <+∞. Khi đó fk(xk,y) = (2−‖x̂k‖)〈x̂k, ŷ− x̂k〉+ ck(xk1− xk−11 )(y1− xk1)+ ck〈x̂k− x̂k−1, ŷ− x̂k〉, = ck(xk1− xk−11 )(y1− xk1)+ ck〈(2−‖x̂k‖+ ck)x̂k− ckx̂k−1, ŷ− x̂k〉. Nhận thấy, nếu xk1 = x k−1 1 ,(2−‖x̂k‖+ ck)x̂k− ckx̂k−1 = 0 được thỏa mãn thì xk = (xk1, x̂ k) là một nghiệm của bài toán EP(C, fk) và ta có 0≤ ‖x̂k‖= ∥∥∥ ckx̂k−1 2−‖x̂k‖+ ck ∥∥∥≤ ck√2 2−√2+ ck . Tuy nhiên, khác với phương pháp hiệu chỉnh Tikhonov, khi cho k→ ∞ thì ck 6→ 0 do đó, từ ước lượng trên ta không suy ra được dãy {xk} hội tụ mạnh đến một nghiệm cụ thể nào của bài toán EP(C, f ) mà chỉ có thể kết luận được rằng dãy này bị chặn, hội tụ yếu về một nghiệm nào đó của bài toán ban đầu. 3.2 Thuật toán giải Như chúng ta đã biết, đối với bài toán cân bằng đơn điệu, nhờ tính đơn điệu mạnh của các bài toán hiệu chỉnh, các thuật toán hiệu chỉnh Tikhonov và điềm gần kề có thể dẫn đến những phương pháp giải chấp nhận được. Còn đối với bài toán cân bằng giả đơn điệu, các bài toán hiệu chỉnh nói chung là không đơn điệu mạnh, thậm chí không giả đơn điệu, vì vậy các phương pháp giải đòi hỏi tính đơn điệu không thể áp dụng 17 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp được. Trong trường hợp này, các điểm giới hạn là điểm chiếu của các nghiệm dự đoán xg trên tập nghiệm của bài toán EP(C, f ). Các điểm giới hạn này có thể thu được dựa vào bài toán tối ưu hai cấp min{‖x− xg‖2 với x ∈ S(C, f )}. (BO) 3.2.1 Mô tả thuật toán Như ta đã biết, khi f là giả đơn điệu trên C, tập nghiệm S(C, f ) của bài toán EP(C, f ) là một tập lồi. Do đó (BO)là bài toán tìm cực tiểu của một hàm chuẩn trên một tập lồi. Giả sử tập nghiệm S(C, f ) của bài toán EP(C, f ) là khác rỗng và f là liên tục yếu, giả đơn điệu trênC. Xét một song hàm L :H ×H → R thỏa mãn các điều kiện sau (B1)L(x,x) = 0,∃β > 0 : L(x,y)≥ β2 ‖x− y‖2, ∀x,y ∈C; (B2)L là liên tục yếu, L(x, .) là khả vi, lồi mạnh trênH với mọi x∈C và∇2L(x,x) = 0 với mọi x ∈H . Ta xét bổ đề sau Bổ đề 3.2.1. Giả sử f thỏa mãn các giả thiết (A1),(A2) và L thỏa mãn giả thiết (B1),(B2). Khi đó, với mọi ρ > 0, các mệnh đề sau đây là tương đương 1. x∗ là nghiệm của bài toán cân bằng; 2. x∗ ∈C : f (x∗,y)+ 1 ρ L(x∗,y)≥ 0, ∀y ∈C; 3. x∗ = argmin{ f (x∗,y)+ 1 ρ L(x∗,y) : y ∈C}. Thuật toán. Chọn ρ > 0 và η ∈ (0,1). Khởi đầu với x1 := xg ∈C (xg có vai trò như là một nghiệm dự đoán). Nếu x1 ∈ S(C, f ), thì x1 là một nghiệm của bài toán tối ưu (BO), ngược lại ta thực hiện phép lặp đối với k theo các bước sau. Bước 1. Giải các bài toán quy hoạch lồi mạnh min{ f (xk,y)+ 1 ρ L(xk,y) : y ∈C} (CP(xk)) để tìm nghiệm duy nhất yk. Nếu yk = xk, chọn uk := xk và chuyển đến Bước 3. Ngược lại chuyển sang Bước 2 18 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp Bước 2.(Qui tắc tìm kiếm theo tia Amijio) Tìm một số nguyên, không âm nhỏ nhất mk , m là một số nguyên, thỏa mãn zk,m := (1−ηm)xk+ηmyk, (3.11) f (zk,m,yk)+ 1 ρ L(xk,yk)≤ 0. (3.12) Đặt ηk := ηmk ,zk := zk,mk , tính σk = −ηk f (zk,yk) (1−ηk)‖gk‖2 , u k := PC(xk−σkgk), (3.13) trong đó gk ∈ ∂2 f (zk,zk), dưới đạo hàm của hàm lồi f (zk, .) tại zk. Bước 3. Xây dựng các nửa không gian Ck := {y ∈H : ‖uk− y‖2 ≤ ‖xk− y‖2}; Dk := {y ∈H : 〈xg− xk,y− xk〉 ≤ 0}. Bước 4. Đặt Bk =Ck∩Dk∩C và tính xk+1 := PBk(xg). Nếu xk+1 ∈ S(C, f ), kết luận xk+1 là nghiệm của bài toán (BO). Ngược lại, tăng k lên 1 và lặp lại quá trình. 3.2.2 Tính hội tụ của thuật toán Bổ đề và định lý sau cho thấy tính hội tụ mạnh của các dãy {xk},{uk} trong thuật toán trên. Bổ đề 3.2.2. Từ các giả thiết của Bổ đề 3.2.1 ta có Giả sử f thỏa mãn các giả thiết (A1),(A2) và L thỏa mãn giả thiết (B1),(B2) ‖uk− x∗‖2 ≤ ‖xk− x∗‖2−σ2k ‖gk‖2, ∀x∗ ∈ S(C, f ), ∀k. (3.15) Định lý 3.2.1. Giả sử f là song hàm liên tục yếu, f(x,.) là lồi, khả dưới vi phân trên C với mọi x ∈C và bài toán EP(C, f ) có nghiệm. Khi đó cả hai dãy {xk},{uk} đều hội tụ tới nghiệm duy nhất của bài toán tối ưu hai cấp (BO). Chứng minh. Ta có S(C, f )⊆ Bk với mọi k. Thật vậy, từ Định lý 3.1.2 ta có ‖un− x∗‖2 ≤ ‖xn− x∗‖2, ∀x∗ ∈ S(C, f ), 19 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp do đó S(C, f )⊆Ck. Ta chứng minh S(C, f )⊆ Dk bằng phương pháp qui nạp. Với k = 1 thì D1 =H nên S(C, f )⊆ D1. Giả sử S(C, f )⊆ Dk, tức là 〈xg− xk,x∗− xk〉 ≤ 0 với mọi x∗ ∈ S(C, f ). Khi đó S(C, f )⊆ Bk =Ck∩Dk.Mặt khác theo định nghĩa xk+1 = PBk(xg) nên ta có 〈x∗− xk+1,xk+1− xg〉 ≤ 0, ∀x∗ ∈ S(C, f ), hay 〈xk+1− x∗,xg− xk+1〉 ≤ 0, ∀x∗ ∈ S(C, f ). Vậy S(C, f )⊆ Dk+1, suy ra S(C, f )⊆ Bk. Từ định nghĩa của Dk, ta có xk = PDk(x g). Do xk+1 ∈ Dk nên ‖xk− xg‖ ≤ ‖xk+1− xg‖, ∀k ∈C. Hơn nữa, xk = PDk(x g) và S(C, f )⊂ Dk với mọi k nên ta có ‖xk− xg‖ ≤ ‖x∗− xg‖, ∀x∗ ∈ S(C, f ), ∀k. (3.20) Do đó {xk} bị chặn. Do tính bị chặn của {xk} và ‖xk−xg‖ ≤ ‖xk+1−xg‖ với mọi k nên limk ‖xk− xg‖ tồn tại. Ta chứng minh ‖xk+1− xk‖→ 0 khi k→ ∞.. Thật vậy, do xk ∈ Dk và xk+1 ∈ Dk, Dk là một tập lồi nên ta có kk+1+ xk 2 ∈ Dk. Mặt khác, xk = PDk(x g) nên theo tính chất lồi mạnh của hàm ‖xg− .‖2 ta có ‖xg− xk‖2 ≤ ∥∥xg− xk+1+ xk 2 ∥∥2; = ∥∥xk− xg 2 + xk+1− xg 2 ∥∥2; = 1 2 ‖xg− xk+1‖2+ 1 2 ‖xg− xk‖2− 1 4 ‖xk+1− xk‖2. Suy ra 1 2 ‖xk+1− xk‖2 ≤ ‖xg− xk+1‖2−‖xg− xk‖2. Do lim‖xk− xg‖ tồn tại nên ta suy ra ‖xk+1− xk‖→ 0 khi k→ ∞. Mặt khác, xk+1 ∈ Bk ⊆Ck, từ định nghĩa củaCk ta có ‖uk− xk+1‖ ≤ ‖xk+1− xk‖. 20 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp Do đó, ‖uk− xk‖ ≤ ‖uk− xk+1‖+‖xk+1− xk‖ ≤ 2‖xk+1− xk‖, và ‖xk+1− xk‖→ 0, tức là ‖uk− xk‖→ 0 khi k→ ∞. Sau đây ta sẽ chỉ ra rằng một điểm tụ yếu bất kỳ của dãy {xk} đều là một nghiệm của bài toán EP(C, f ). Thật vậy, lấy x là một điểm tụ yếu bất kỳ của dãy {xk}. Không mất tính chất tổng quát, ta giả sử xk ⇀ x. Ta xét hai trường hợp Trường hợp 1. Việc tìm kiếm theo tia chỉ xảy ra ở hữu hạn điểm. Trong trường hợp này, theo thuật toán, uk = xk với mọi k vô hạn, do đó yk = xk là một nghiệm của bài toán EP(C, f ) với mọi k. Do vậy, trường hợp này luôn đúng. Trường hợp 2. Việc tìm kiếm theo tia xảy ra tại vô hạn điểm. Khi đó ta trích ra một dãy con và giả thiết rằng việc tìm kiếm theo tia là thực hiện được với mọi k. Ta xét hai khả năng (a) limkηk > 0. Do xk ⇀ x và ‖uk− xk‖→ 0 nên uk ⇀ x. Áp dụng công thức (3.15) với x∗ ∈ S(C, f ) ta thấy σk‖gk‖2→ 0. Do định nghĩa của σk nên ta có − ηk 1−ηk 〈g k,yk− zk〉 → 0. Từ điều kiện limkηk > 0, giả sử 〈gk,yk− zk〉 → 0. Mặt khác từ giả thiết (B1) và qui tắc tìm kiếm Armijo ta có 0≤ β 2ρ ‖xk− yk‖2 ≤ 1 2ρ L(xk,yk)≤−〈gk,yk− zk〉 → 0. Do đó, ‖xk− yk‖→ 0. Do xk ⇀ x nên yk ⇀ x, trong đó yk là nghiệm của bài toán min { f (xk,y)+ 1 ρ L(xk,y) : y ∈C } . (CP(Ck)) Khi đó ta có thể viết lại như sau f (xk,y)+ 1 ρ L(xk,y)≥ f (xk,yk)+ 1 ρ L(xk,yk) ∀y ∈C. Cho k tiến ra vô cùng, do tính liên tục yếu của f và L nên f (x,y)+ 1 ρ L(x,y)≥ f (x,y)+ 1 ρ L(x,y) ∀y ∈C, điều này cho thấy y là nghiệm của bài toánCP(x). Do ‖xk− yk‖→ 0 và xk ⇀ x,yk ⇀ y nên suy ra x= y. Vậy theo Bổ đề 3.2.1 x là một nghiệm của bài toán EP(C, f ). 21 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp (b) limkηk = 0. Trong trường hợp này dãy {yk} cũng bị chặn. Thật vậy, do yk là nghiệm của bài toán CP(xk), hàm mục tiêu là liên tục yếu, lồi mạnh và lời giải là không đổi. Theo Định lý Berge, ánh xạ xk→ s(xk) := yk là liên tục yếu. Từ tính chất bị chặn của {xk} ta suy ra {yk} bị chặn, suy ra yk ⇀ y. Lập luận tương tự như trước ta được f (x,y)+ 1 ρ L(x,y)≤ f (x,y)+ 1 ρ L(x,y), ∀y ∈C (3.21) Mặt khác, do mk là số tự nhiên nhỏ nhất thỏa mãn quy tắc tìm kiếm theo tia Armijo nên f (zk,mk−1,yk)+ 1 ρ L(xk,yk)> 0. (3.22) Trong đó zk,mk−1 ⇀ x khi k→ ∞. Từ bất đẳng thức (3.22), do tính liên tục yếu của f và L ta thu được giới hạn f (x,y)+ 1 ρ L(x,y)≥ 0. (3.23) Thay y= x vào (3.21) ta được f (x,y)+ 1 ρ L(x,y)≤ 0, kết hợp với (3.23) ta được f (x,y)+ 1 ρ L(x,y) = 0. (3.24) Từ (3.24) và f (x,x)+ 1 ρ L(x,x) = 0, suy ra cả x,y đều là nghiệm của bài toán min { f (x,y)+ 1 ρ L(x,y) : y ∈C } . Do đó x= y, theo Bổ đề 3.2.1 x là nghiệ