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

2. đơn điệu trên C nếu 〈F(x)−F(y),x− y〉 ≥ 0, ∀x,y ∈C; 3. giả đơn điệu trên C nếu 〈F(x),x− y〉 ≤ 0⇒ 〈F(y),y− x〉 ≥ 0. Ta đặt f (x,y) = 〈F(x),y− x〉. Khi đó toán tử cân bằng trở thành song hàm cân bằng. 16 Chương 2. Bài toán cân bằng Nhận xét Nếu F là toán tử đơn điệu mạnh, đơn điệu hoặc giả đơn điệu trên C thì f cũng là song hàm đơn điệu mạnh, đơn điệu hoặc giả đơn điệu trênC. Thật vậy Nếu toán tử F là đơn điệu mạnh trênC với hệ số γ > 0, khi đó 〈F(x)−F(y),x− y〉 ≥ γ‖x− y‖2, ∀x,y ∈C; ⇔ 〈F(x),x− y〉−〈F(y),x− y〉 ≥ γ‖x− y‖2, ∀x,y ∈C; ⇔−〈F(x),y− x〉−〈F(y),x− y〉 ≥ γ‖x− y‖2, ∀x,y ∈C; ⇔− f (x,y)− f (y,x)≥ γ‖x− y‖2, ∀x,y ∈C; ⇔ f (x,y)+ f (y,x)≤−γ‖x− y‖2,∀x,y ∈C; Vậy f là song hàm đơn điệu mạnh trênC với hệ số γ > 0. Nếu toán tử F là đơn điệu trênC, khi đó 〈F(x)−F(y),x− y〉 ≥ 0, ∀x,y ∈C; ⇔ 〈F(x),x− y〉−〈F(y),x− y〉 ≥ 0, ∀x,y ∈C; ⇔−〈F(x),y− x〉−〈F(y),x− y〉 ≥ 0, ∀x,y ∈C; ⇔− f (x,y)− f (y,x)≥ 0, ∀x,y ∈C; ⇔ f (x,y)+ f (y,x)≤ 0,∀x,y ∈C; Vậy f là song hàm đơn điệu trênC. Nếu toán tử F là giả đơn điệu trênC, khi đó nếu 〈F(x),x− y〉 ≤ 0 thì 〈F(y),y− x〉 ≥ 0, ∀x,y ∈C; ⇔−〈F(x),y− x〉 ≤ 0 thì 〈F(y),y− x〉 ≥ 0, ∀x,y ∈C; ⇔−〈F(x),y− x〉 ≤ 0 thì −〈F(y),x− y〉 ≥ 0, ∀x,y ∈C; suy ra − f (x,y)≤ 0 thì − f (y,x)≥ 0, ∀x,y ∈C; ⇔ f (x,y)≥ 0 thì f (y,x)≤ 0 ∀x,y ∈C. Vậy f là song hàm giả đơn điệu trênC. Sau đây ta xét một vài trường hợp riêng có thể đưa về bài toán cân bằng. 17 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. Nhận thấy, tập nghiệm của bài toán tối ưu (OP) chính là S(C, f ). Thật vậy, giả sử x∗ ∈C là nghiệm của bài toán (OP), theo định nghĩa ta có ϕ(x∗)≤ ϕ(y), ∀y ∈C. Suy ra ϕ(y)−ϕ(x∗)≥ 0, ∀y ∈C. Mặt khác f (x,y) := ϕ(y)−ϕ(x), ∀x,y ∈C, nên f (x∗,y) := ϕ(y)−ϕ(x∗)≥ 0, ∀y ∈C. Vậy x∗ là nghiệm cuả bài toán EP(C, f ). Ngược lại, lấy x∗ ∈C là nghiệm của bài toán EP(C, f ). Khi đó f (x∗,y) ≥ 0 với mọi y ∈C. Theo cách đặt ta có f (x∗,y) := ϕ(y)−ϕ(x∗)≥ 0, ∀y ∈C. Suy ra ϕ(y)≥ ϕ(x∗), ∀y ∈C. Vậy x∗ là nghiệm của bài toán (OP). 18 Chương 2. Bài toán cân bằng 2.2.2 Bài toán điểm bất động Cho F :C→C là một ánh xạ đơn trị. Xét bài toán điểm bất động sau Tìm x∗ sao cho F(x∗) = x∗. (F(C,F)) Đặt f (x,y) = 〈x−F(x),y− x〉, thì f là một song hàm cân bằng với mọi y ∈C. Khi đó bài toán điểm bất động F(C,F) trở thành bài toán EP(C, f ), tập nghiệm của F(C,F) chính là S(C, f ). Thật vậy, giả sử x∗ là nghiệm của bài toán F(C,F). Tức là F(x∗) = x∗. Khi đó f (x∗,y) = 〈x∗−F(x∗),y− x∗〉; = 〈0,y− x∗〉; = 0≥ 0, ∀y ∈C. Vậy x∗ là nghiệm của bài toán cân bằng EP(C, f ). Ngược lại, giả sử x∗ là điểm sao cho f (x∗,y)≥ 0, ∀y ∈C. Khi đó: 〈x∗−F(x∗),y− x∗〉 ≥ 0, ∀y ∈C. Chọn y= F(x∗) 〈x∗−F(x∗),F(x∗)− x∗〉 ≥ 0, ∀y ∈C; ⇔−||x∗−F(x∗)||2 ≥ 0, ∀y ∈C. ⇒ x∗ = F(x∗) ∀y ∈C. Vậy x∗ là điểm bất động củaC. 2.2.3 Bài toán cân bằng Nash trong trò chơi không hợp tác Xét một trò chơi không hợp tác gồm có p đấu thủ, đấu thủ thứ i có tập chiến lược là Ci ∈ Rpi và có hàm chi phí là fi := C → R với C := C1 ×C2 × ...×Cp tương ứng, tức là, nếu đối thủ thứ nhất, thứ hai, ..., thứ p, lần lượt chọn chiến lược chơi là x1 ∈ C1,x2 ∈ C2, ...,xp ∈ Cp , thì chi phí của mỗi đối thủ tương ứng sẽ là f1(x1,x2, ...,xp), f2(x1,x2, ...,xp), ..., fp(x1,x2, ...,xp). Mục tiêu của mỗi đối thủ là tìm kiếm một chiến lược chơi trong tập chiến lược chơi tương ứng để làm cực tiểu chi phí của mình. Ký hiệu x = (x1,x2, ...,xp), một điểm x∗ ∈ C được gọi là điểm cân bằng Nash nếu fi(x∗1, ...,x ∗ i−1,x ∗ i ,x ∗ i+1, ...,x ∗ p)≤ fi(x∗1, ...,x∗i−1,y∗i ,x∗i+1, ...,x∗p) 19 Chương 2. Bài toán cân bằng với mọi y∗i ∈ Ci và với mọi i = 1,2, ..., p. Khi đó bài toán cân bằng Nash được phát biểu như sau{ Tìm x∗ ∈C sao cho fi(x∗)≤ fi(x∗1, ...,x∗i−1,y∗i ,x∗i+1, ...,x∗p) ∀yi ∈Ci,∀i= 1,2, ..., p. (N(C, f )) Đặt f (x,y) := p ∑ j=1 [ f j(x)− f j(x1, ...,x j−1,y j,x j+1, ...,xp) ] . Nhận thấy, nếu x∗ là một điểm cân bằng Nash thì f (x∗,y)≥ 0 với mọi y ∈C. Khi đó bài toán cân bằng Nash N(C, f ) trở thành bài toán cân bằng EP(C, f ). Ngược lại, giả sử x∗ ∈C là nghiệm của EP(C, f ) tức là f (x∗,y)≥ 0 với mọi y ∈C. Ta sẽ chứng tỏ x∗ = (x∗1, ...,x ∗ p) với x ∗ j ∈C j là một điểm cân bằng Nash. Thật vậy, giả sử x∗ không là một điểm cân bằng Nash, khi đó sẽ tồn tại j và một y j ∈C j sao cho f j(x∗1, ...,x ∗ j−1,x ∗ j ,x ∗ j+1, ...,x ∗ p)< f j(x ∗ 1, ...,x ∗ j−1,y j,x ∗ j+1, ...,x ∗ p). Khi đó với phương án y = (x∗1, ...,x ∗ j−1,y j,x ∗ j+1, ...,x ∗ p), theo định nghĩa của hàm f ta có f (x∗,y) = f j(x∗1, ...,x ∗ j−1,y j,x ∗ j+1, ...,x ∗ p)− f j(x∗)< 0. Điều này mâu thuẫn với giả thiết x∗ là nghiệm của EP(C, f ), hay x∗ là một điểm cân bằng Nash. 2.2.4 Bài toán điểm yên ngựa Trong nhiều vấn đề, ta thường phải làm việc việc với một hàm số thực của hai nhóm biến có tính chất là tựa lồi theo nhóm biến thứ nhất khi nhóm biến thứ hai cố định và tựa lõm theo nhóm biến thứ hai, khi nhóm biến thứ nhất cố định. Các song hàm này được gọi là hàm yên ngựa. Định nghĩa 2.2.1. Cho C ⊆H ,D ⊆H là các tập lồi khác rỗng và ϕ :C×D→ R. Hàm ϕ được gọi là hàm yên ngựa trênC×D, nếu với mọi y ∈ D cố định, hàm ϕ(.,y) tựa lồi trên C và với mọi x ∈C cố định, hàm ϕ(x, .) tựa lõm trên D. Hột hàm yên ngựa cũng được gọi là hàm tựa - lồi tựa - lõm. Do mọi hàm lồi đều là tựa lồi và mọi hàm lõm đều là tựa lõm, nên hàm lồi - lõm (nói riêng hàm song tuyến) là hàm yên ngựa. Định nghĩa 2.2.2. Một điểm (x∗,y∗) ∈C×D được gọi là điểm yên ngựa của hàm ϕ trênC×D nếu ϕ(x∗,y)≤ ϕ(x∗,y∗)≤ ϕ(x,y∗), ∀x ∈C, ∀y ∈ D. 20 Chương 2. Bài toán cân bằng Xét bài toán tìm điểm yên ngựa sau{ Tìm điểm (x∗,y∗) ∈C×D sao cho ϕ(x∗,y)≤ ϕ(x∗,y∗)≤ ϕ(x,y∗), ∀x,y ∈C×D. (2.2.1) Ta sẽ chỉ ra rằng, bài toán tìm điểm yên ngựa có thể mô tả dưới dạng bài toán cân bằng như sau. Với mỗi u= (x′,y′),v= (x,y) ∈ K :=C×D, đặt f (u,v) := ϕ(x,y′)−ϕ(x′,y). Khi đó, nếu u∗ = (x∗,y∗) ∈ K là nghiệm của EP(K, f ), tức là f (u∗,v)≥ 0, ∀v ∈ K, thì ϕ(x∗,y)≤ ϕ(x,y∗), ∀(x,y) ∈ K. Lần lượt thay x= x∗,y= y∗ vào bất đẳng thức này ta được ϕ(x∗,y)≤ ϕ(x∗,y∗)≤ ϕ(x,y∗), ∀(x,y) ∈ K. Vậy (x∗,y∗) là điểm yên ngựa của ϕ trên K. Ngược lại, giả sử (x∗,y∗) là điểm yên ngựa của ϕ trên K. Theo định nghĩa ta có ϕ(x∗,y)≤ ϕ(x∗,y∗)≤ ϕ(x,y∗), ∀x ∈C, ∀y ∈ D. Suy ra ϕ(x,y∗)−ϕ(x∗,y)≥ 0 ∀x,y ∈ K, hay f (u∗,v)≥ 0 ∀v ∈ K. Vậy u∗ = (x∗,y∗) là nghiệm của EP(K, f ). 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. Trước hết chúng ta nhắc lại định lý cực đại Berge sau Định lý 2.3.1. Cho X, Y là các không gian Tô pô, F : X ×Y → 2Y là ánh xạ nửa liên tục trên trên X sao cho F(x) compact, hơn nữa F(X) compact. Giả sử f : X ×Y → R là một hàm số nửa liên tục trên trên X. Khi đó, hàm giá trị tối ưu g(x) :=max{ f (x,y) : y ∈ F(x)} 21 Chương 2. Bài toán cân bằng nửa liên tục trên và ánh xạ tập nghiệm tối ưu S(x) := {y ∈ F(x) : f (x,y) = g(x)} nửa liên tục trên. 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.2. (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. 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. 22 Chương 2. Bài toán cân bằng 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 ). Chứng minh. 1)⇒ 2): Từ giả thiết 1), ta chọn B là hình cầu đóng chứa L(y0, f ). Khi đó {x ∈C \B : f (x,y0)≥ 0}= /0. Vậy f (x,y0)< 0, ∀x ∈C \B. 2)⇒ 3): Từ Mệnh đề 2.3.1 ta có S(C, f ) 6= /0 . DoC là tập đóng yếu, f (.,y) là hàm nửa liên tục trên yếu trên C và tập nghiệm S(C, f ) là đóng yếu. Hơn nữa, từ 2) và từ định nghĩa của L(y0, f ), ta có S(C, f )⊆ L(y0, f )⊆C∩B. Do đó, S(C, f ) là tập compact yếu. Lấy y0 ∈ S(C, f ). Khi đó f (y0,x) ≥ 0 với mọi x ∈ C. Do tính chất giả đơn điệu của song hàm nên f (x,y0)≤ 0 với mọi x ∈C. Do đó, L> = /0.  Mệnh đề 2.3.3. (Trường hợp compact) Cho C là một tập lồi, compact, khác rỗng và song hàm cân bằng f :C×C→ R∪+{∞} thỏa mãn các tính chất sau 1. f(.,y) nửa liên tục trên yếu trênH với mọi y ∈C. 2. f(x,.) lồi, nửa liên tục dưới và khả dưới vi phân trênH với mọi x ∈C. Khi đó bài toán EP(C, f ) có nghiệm. Chứng minh. Với mỗi x ∈C ta gọi S(x) là tập nghiệm của bài toán min{ f (x,y) : y ∈C}. Do C là compact và f (, .) nửa liên tục dưới trênH nên bài toán này có nghiệm. Hơn nữa doC lồi, compact, f (x, .) lồi nên S(x) lồi, compact. Theo Định lý Berger thì ánh xạ S(.) nửa liên tục trên. Vậy, theo định lý về điểm bất động, tồn tại x∗ ∈C thỏa mãn x∗ ∈ S(x∗). Ta sẽ chỉ ra x∗ là nghiệm của bài toán cân bằng EP(C, f ). 23 Chương 2. Bài toán cân bằng Thật vậy, do f (x, .) lồi, khả dưới vi phân nên theo điều kiện cần và đủ tối ưu của qui hoạch lồi ta có 0 ∈ ∂2 f (x∗,x∗)+NC(x∗), theo định nghĩa của dưới vi phân và nón pháp tuyến ta có ∃v∗ ∈ ∂2 f (x∗,x∗) thỏa mãn 〈v∗,y− x∗〉 ≥ 0, ∀y ∈C. Do v∗ ∈ ∂2 f (x∗,x∗) nên 〈v∗,y− x∗〉 ≤ f (x∗,y)− f (x∗,x∗) = f (x∗,y), ∀y ∈C. Vậy f (x∗,y)≥ 0, ∀y ∈C, hay x∗ là nghiệm của bài toán EP(C, f ).  Hệ quả 2.3.1. (Trường hợp có điều kiện bức).Cho C là một tập lồi, đóng (không cần compact) và song hàm cân bằng f thỏa mãn các điều kiện của Mệnh đề 2.3.3. Giả sử điều kiện bức (K1) sau đây được thỏa mãn. Tồn tại tập compact B sao cho C∩B 6=∅, ∀x ∈C \B, ∀y ∈C : f (x,y)< 0. Khi đó bài toán EP(C, f ) có nghiệm. Chứng minh. Theo Mệnh đề 2.3.3, bài toán EP(C, f ) trên tậpC∩B với hàm cân bằng f có nghiệm, tức là tồn tại x∗ ∈C∩B. Từ điều kiện bức (K1) và tính lồi của tậpC ta có thể suy ra x∗ cũng là nghiệm của bài toán EP(C, f ).  Ngoài ra để chứng minh sự tồn tại nghiệm của bài toán cân bằng ta có thể dựa vào Định lý minimax sau. Cho một song hàm f :=C×D→ R. Ta xét định lý sau (Định lý minimax). Định lý 2.3.3. ChoC⊆H ,D⊆H là các tập lồi, đóng khác rỗng và f :C×D→R. Giả sử với mọi y ∈ D, hàm f (.,y) là hàm tựa lồi, nửa liên tục dưới trên C và với mọi x ∈C, hàm f (x, .) là hàm tựa lõm, nửa liên tục trên trên D. Khi đó nếu có một trong hai điều kiện sau (A) Có một tập hữu hạn N∗ ⊂ D và một số η∗ > γ sao cho tập C(N∗) := {x ∈C|max y∈N∗ f (x,y)≤ η∗} compact. 24 Chương 2. Bài toán cân bằng (B) Có một tập hữu hạn M∗ ⊂C và một số γ∗ < η sao cho tập D(M∗) := {y ∈ D|min x∈M∗ f (x,y)≥ γ∗} compact. Khi đó sup y∈D inf x∈C f (x,y) = inf x∈C sup y∈D f (x,y). Cụ thể hơn, ta có sup y∈D min x∈C(N∗) f (x,y) = inf x∈C sup y∈D f (x,y) nếu có (A) và inf x∈C sup y∈D f (x,y) = max y∈D(M∗)) inf x∈C f (x,y) nếu có (B). Để chứng minh Định lý minimax, ta xét bổ đề sau Bổ đề 2.3.1. Cho C ⊆H ,D⊆H là các tập lồi, đóng khác rỗng và f :C×D→ R. Giả sử với mọi y ∈ D, hàm f (.,y) tựa lồi, nửa liên tục dưới trên C và với mọi x ∈C, hàm f (x, .) tựa lõm, nửa liên tục trên trên D. Khi đó ta có 1. Với mọi γ ′ > γ := supy∈D infx∈C f (x,y) và mọi tập hữu hạn N ⊂ D, tập C(N) := {x ∈C|max y∈N f (x,y)≤ γ ′} 6=∅. 2. Với mọi η ′ < η = infx∈C supy∈D f (x,y) và mọi tập hữu hạn M ⊂C, tập D(M) := {y ∈ D|min x∈M f (x,y)≥ η ′} 6=∅. Chứng minh. 1. Đặt C′γ(y) := {x ∈C| f (x,y)≤ γ ′}. Do C lồi, f (.,y) tựa lồi và nửa liên tục dưới, nên C′γ(y) lồi đóng. Ta chứng minh 1) bằng qui nạp theo số phần tử của N (khẳng định 1) có nghĩa là ⋂ y∈N C′γ(y) 6=∅). Khi N chỉ có duy nhất một phần tử y, tập C′γ(N) =C ′ γ(y) = {x ∈C| f (x,y)≤ γ ′}. Do γ ′ > γ ≥ inf x∈C f (x,y), 25 Chương 2. Bài toán cân bằng suy ra ∃ x ∈C sao cho f (x,y)≤ γ ′. Suy raC′γ(N) 6=∅. Vậy 1) đúng khi N có một phần tử. Giả sử 1) đúng với N có k phần tử. Tức là k⋂ i=1 C′γ ′(y i) 6=∅, ta chứng minh (i) đúng khi N có k+1 phần tử. tức là chứng minh k+1⋂ i=1 C′γ ′(y i) 6=∅, trong đó N := {y1, ...,yk,yk+1}. Thật vậy, Đặt C′γ ′(y i) :=Cγ ′(y i)∩Cγ ′(yk+1) (i= 1, ...,k). Khi đó k+1⋂ i=1 Cγ ′(y i) = k⋂ i=1 C′γ ′(y i). Theo giả thiết qui nạp k⋂ i=1 C′γ ′(y i) 6=∅, nếu như các tập C′γ ′(y i) =Cγ ′(y i)∩Cγ ′(yk+1) 6=∅. Ta chứng minh với hai điểm bất kỳ a,b ∈ D, thìCγ ′(a)∩Cγ ′(b) 6=∅. Giả sử ngược lại, tồn tại hai điểm a,b ∈ D sao choCγ ′(a)∩Cγ ′(b) =∅. Lấy α ∈ (γ,γ ′) bất kỳ. Khi đó γ sup y∈D inf x∈C f (x,y), nênCα(y) 6=∅, ∀y ∈ D. Lấy yt := ta+(1− t)b với 0≤ t ≤ 1. Do D lồi, nên yt ∈ D. Với mọi x ∈Cα(yt) ta có f (x,yt)≤ α . Do f là tựa lõm theo biến thứ hai, nên f (x,yt)≥ min{ f (x,a), f (x,b)}. Vậy min{ f (x,a), f (x,b)} ≤ α . Do đó f (x,a)≤ α hoặc f (x,b)≤ α ∀x ∈Cα(yt), 26 Chương 2. Bài toán cân bằng suy ra Cα(yt)⊂Cα(a)∪Cα(b). DoCα(a),Cα(b),Cα(yt) lồi vàCα(a)∩Cα(b) =∅ nên Cα(yt)⊂Cα(a) hoặcCα(yt)⊂Cα(b). Đặt Ma := {t|0≤ t ≤ 1 :Cα(yt)⊂Cα(a)}; Mb := {t|0≤ t ≤ 1 :Cα(yt)⊂Cα(b)}. Khi đó 0 ∈Ma,1 ∈Mb và Ma∪Mb = [0,1]. Tương tự, ta có Cα(yt)⊂Cα(yt1)∪Cα(yt2), ∀t ∈ [t1, t2]⊂ [0,1]. Nhận thấy t ∈Ma⇒ [0, t] ∈Ma và t ∈Mb⇒ [t,1] ∈Mb. Đặt s := supMa. Giả sử s ∈Ma. Do α > γ ≥ inf f (x,ys), nên tồn tại x ∈C sao cho f (x,ys) < α . Do tính nửa liên tục trên của f (x, .) nên f (x,ys) s và đủ gần s. Hay x ∈Cα(yt) với mọi t đủ gần s. Khi đóCα(yt)⊂Cα(a). Theo định nghĩa của Ma, ta có t ∈Ma. Tuy nhiên, t > s= supMa, điều này mâu thuẫn, VậyCα(a)∩Cα(b) 6=∅. Hay C(N) := {x ∈C|max y∈N f (x,y)≤ γ ′} 6=∅. 2. Do hàm f là tựa lõm và nửa liên tục trên theo biến thứ hai nên − f là tựa lồi và nửa liên tục dưới theo biến thứ hai và −min x∈M ( sup y∈D f (x,y) ) =max x∈M ( inf y∈D (− f (x,y)). Vậy D(M) := {y ∈ D|min x∈M f (x,y)≥ η ′} 6=∅.  Chứng minh định lý Minimax Giả sử giả thiết (A) được thỏa mãn. Khi đó γ <+∞. 27 Chương 2. Bài toán cân bằng Do sup y∈D inf x∈C f (x,y)≤ inf x∈C sup y∈D f (x,y), ta chỉ cần chứng minh γ ≥ inf x∈C sup y∈D f (x,y). Lấy α ∈ (γ,η) bất kỳ và xét tập C′(y) :=C(N∗)∩C(y). Áp dụng bổ đề trên với tập N =N∗∪{y} và γ ′ = α , ta cóC′ 6=∅ và họ tập {C′|y∈D} có tính chất tương giao hữu hạn. Hơn nữa, tất cả các tập này đều nằm trong tập compact C(N∗). Do đó theo định lý tương giao hữu hạn của các tập lồi đóng, ta có⋂ y∈D C′ 6=∅. Mặt khác, theo định nghĩa củaC′(y) thì ⋂ y∈D C′(y) = ⋂ y∈D C(y). Lấy x∗ ∈ ⋂ y∈D C(y). Ta có x∗ ∈C(N∗), f (x∗,y)≤ α, ∀y ∈ D. Suy ra min x∈C(N∗) sup y∈D f (x,y)≤ sup y∈D f (x∗,y)≤ α. Do α là số bất kỳ thỏa mãn α ≥ γ , nên ta có điều phải chứng minh là γ ≥ min x∈C(N∗) sup y∈D f (x,y). Nhận xét 1. Điều kiện (A) sẽ thỏa mãn nếu có điều kiện bức sau (AC) Có một tập hữu hạn N∗ ⊂ D sao cho max y∈N∗ f (x,y)→+∞ khi x ∈C,‖x‖→+∞. Điều kiện (B) sẽ thỏa mãn nếu có điều kiện bức sau: (BC) Có một tập hữu hạn M∗ ⊂C sao cho min y∈M∗ f (x,y)→+∞ khi y ∈ D,‖y‖→+∞. Thật vậy, giả sử có (AC). Ta có thể giả thiết γ := sup y∈D inf x∈C f (x,y)<+∞. Lấy η > γ, khi đó tập C(N∗) := {x ∈ D| sup y∈N∗ f (x,y)≤ η} 28 Chương 2. Bài toán cân bằng bị chặn (và do đó compact). Vậy (AC) kéo theo (A). Nhận xét 2. Nếu (C) là tập compact thì (A) thỏa mãn và nếu (D) là tập compact thì (B) thỏa mãn. Sau đây ta sẽ chứng minh một kết quả về sự tồn tại nghiệm của bài toán cân bằng EP(C, f ) dựa trên định lý Minimax. Mệnh đề 2.3.4. Cho C là một tập lồi đóng, khác rỗng và hàm φ có các tính chất: φ(x, .) là hàm tựa lồi, nửa liên tục dưới trên C , φ(.,y) là hàm tựa lõm, nửa liên tục trên trên C. Ngoài ra φ(y,y) = 0 với mọi y ∈C. Giả sử (A1) Có một tập hữu hạn N∗ ⊂C sao cho tập C(N∗) := {x ∈C|min y∈N∗ φ(x,y)≥ 0} compact, hoặc (B1) Có một tập hữu hạn M∗ ⊂C sao cho tập D(M∗) := {y ∈C|min x∈M∗ φ(x,y)≤ 0} compact. Khi đó bài toán (EP) có nghiệm. Chứng minh. Đặt f (x,y) :=−φ(x,y) và D≡C. Khi đó hàm f thỏa mãn điều kiện của định lý Minimax, khi đó ta có sup y∈C inf x∈C f (x,y) = inf x∈C sup y∈C f (x,y). (2.1) Ta sẽ chứng minh inf x∈C sup y∈C f (x,y) = 0. (2.2) Thật vậy, ta có inf x∈C sup y∈C f (x,y)≥ inf x∈C f (x,x) = 0; có được đẳng thức cuối là do f (x,x) = 0. Mặt khác, sup y∈C inf x∈C f (x,y)≤ sup y∈C f (y,y). (2.3) Từ (2.1), (2.2) và (2.3) ta có sup y∈C inf x∈C f (x,y) = inf x∈C sup y∈C f (x,y) = 0. 29 Chương 2. Bài toán cân bằng Giả sử điều kiện (A1) thỏa mãn, theo Định lý minimax tồn tại x ∈C(N∗)⊂C sao cho min x∈C(N∗) sup y∈C f (x,y) = 0. Đặt s(x) := sup y∈C f (x,y). Do f (.,y) nửa liên tục dưới trên C, nên s cũng nửa liên tục dưới trên C. Mặt khác, doC(N∗) là tập compact nên tồn tại x∗ ∈C(N∗), sao cho s(x∗) = min x∈C(N∗) s(x) = 0. Hay s(x∗) = sup y∈C f (x∗,y) = 0. Suy ra f (x∗,y)≤ 0, ∀y ∈C. Vậy φ(x∗,y) =− f (x∗,y)≥ 0 với mọi y ∈C. Chứng tỏ x∗ là nghiệm của bài toán cân bằng EP(C, f )  Nhận xét. Điều kiện (A1) sẽ thỏa mãn nếu có điều kiện bức sau: Tồn tại tập hữu hạn N∗ ⊂C sao cho min y∈N∗ φ(x,y)→−∞ khi x ∈C,‖x‖→+∞. Điều kiện (B1) sẽ thỏa mãn nếu có điều kiện bức sau: Tồn tại tập hữu hạnM∗ ⊂C sao cho max x∈M∗ φ(x,y)→+∞ khi y ∈C,‖y‖→−∞. 2.4 Kết luận Chương 2 đã trình bày được các khái niệm về song hàm cân bằng, toán tử cân bằng và bài toán cân bằng; các khái niệm về song hàm đơn điệu mạnh, đơn điệu, giả đơn điệu. Một số bài toán có thể đưa về dạng bài toán cân bằng. Phát biểu và chứng minh sự tồn tại nghiệm của bài toán cân bằng. 30 Chương 3 Hiệu chỉnh dựa trên tối ưu hai cấp Bài toán cân bằng hai cấp là bài toán có dạng Tìm x∗ ∈ S f sao cho g(x∗,y)≥ 0,∀y ∈ S f trong đó S f là tập nghiệm của bài toán cân bằng Tìm u ∈C sao cho f (u,y)≥ 0,∀y ∈C với C là một tập lồi, đóng, khác rỗng trong không gian HilbertH và f ,g :C×C→ R∪{+∞} là các song hàm cân bằng xác định trên C. Bài toán cân bằng chứa nhiều lớp bài toán quan trọng khác như là các trường hợp riêng của nó như bài toán bất đẳng thức biến phân hai cấp, bài toán bất đẳng thức biến phân trên tập nghiệm của bài toán cân bằng. Bài toán tối ưu hai cấp là bài toán tìm cực tiểu của một hàm chuẩn trên tập nghiệm của bài toán cân bằng ban đầu. 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 Phương pháp hiệu chỉnh Tikhonov là một trong những phương pháp cơ bản thường được sử dụng để giải các bài toán đặt không chỉnh. Ý tưởng của phương pháp hiệu chỉnh Tikhonov cho bài toán cân bằng là thay song hàm f bằng một song hàm fε := f + εg, trong đó ε > 0 là tham số hiệu chỉnh và g là song hàm đơn điệu mạnh được gọi là song hàm hiệu chỉnh, sau đó xét bài toán cân bằng với song hàm fε . Xét bài toán cân bằng Tìm x∗ ∈C sao cho f (x∗,y)≥ 0, ∀y ∈C, 31 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp 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)+ εg(x,y)≥ 0, ∀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. Định lý sau đây cho thấy, khi song hàm cân bằng f là giả đơn điệu, bài toán hiệu chỉnh EP(C, fε) có nghiệm khi và chỉ khi bài toán ban đầu EP(C, f ) có nghiệm và mặc dù không có nghiệm duy nhất nhưng mọi quỹ đạo nghiệm của nó đều hội tụ đến nghiệm của bài toán EP(C, f ) gần với nghiệm dự đoán xg nhất. Định lý 3.1.1. Giả sử f là giả đơn điệu trên C và thỏa mãn các giả thiết (A1),(A2). Khi đó các khẳng định sau là tương đương 1. S(C, fε) khác rỗng với mọi ε > 0 và limε→0+ x(ε) tồn tại, với x(ε) chọn tùy ý trong S(C, fε). 2. S(C, fε) khác rỗng với mọi ε > 0 và limε→0+ sup‖x(ε)‖ < ∞, với x(ε) chọn tùy ý trong S(C, fε). 3. S(C, f ) 6= 0. Hơn nữa, nếu một trong các khẳng định trên được thỏa mãn thì lim ε→0+ x(ε) = x∗, trong đó x∗ là nghiệm duy nhất của bài toán cân bằng EP(C˜,g) với C˜ := S(C, f ), g là một song hàm đơn điệu mạnh thỏa mãn ∃δ > 0 : |g(x,y)| ≤ δ‖x− xg‖.‖y− x‖, ∀x,y ∈C. Ngoài ra nếu g là song hàm khoảng cách thì x∗ là hình chiếu của xg trên tập nghiệm của bài toán EP(C, f ). Tuy nhiên, nhiều khi bài toán hiệu chỉnh còn khó giải hơn bài toán ban đầu, vì vậy để hạn chế phần nào nhược điểm nói trên ta thay thế bất đẳng thức fε(x,y)≥ 0 trong bài toán EP(C, fε) bởi bất đẳng thức fε(x,y)≥−δ trong đó δ ≥ 0 là một hằng số cho trước. Khi đó bài toán EP(C, fε) với song hàm hiệu chỉnh là song hàm khoảng cách g(x,y) = 〈x− xg,y− x〉 trở thành bài toán hiệu chỉnh{ Tìm x ∈C sao cho fε(x,y) := f (x,y)+ ε〈x− xg,y− x〉 ≥ −δ , ∀y ∈C (EPδ (C, fε)) 32 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp Kí hiệu Sδ (C, fε) là tập nghiệm của bài toán EPδ (C, fε). Nhận xét. Nếu x thỏa mãn fε(x,y) ≥ 0 với mọi y ∈C thì cũng thỏa mãn fε(x,y) ≥ −δ với mọi y ∈C, do đó S(C, fε)⊆ Sδ (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, 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. Chứng minh. Giả thiết x ∈ S(C, f ), do f là giả đơn điệu nên ta có f (x,y)≥ 0⇒ f (y,x)≤ 0, ∀y ∈C. (3.1) Do x(ε) ∈ Sδ (C, fε) nên f (x(ε),y)+ ε 〈 x(ε)− xg,y− x(ε)〉≥−δ , ∀y ∈C. (3.2) Thay y= x(ε) vào bất đẳng thức thứ hai trong công thức (3.1), và y= x vào công thức (3.2) ta được f (x(ε),x)≤ 0 và f (x(ε),x)+ ε〈x(ε)− xg,x− x(ε)〉≥−δ . Từ đó ta có 1 2 [∥∥xg− x∥∥2−∥∥xg− x(ε)∥∥2−∥∥x(ε)− x∥∥2]= 〈x(ε)− xg,x− x(ε)〉≥−δ ε . Do đó ‖xg− x(ε)‖2+‖x(ε)− x‖2 ≤ ‖xg− x‖2+2δ ε . Vậy 1) được chứng minh. Mặt khác, ta có∥∥x(ε)− xg∥∥2+∥∥[x(ε)− xg]− [x− xg]∥∥2 ≤ ∥∥x− xg∥∥2+2δ ε , 33 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp trong đó ∥∥x(ε)− xg∥∥2−〈x(ε)− xg,x− xg〉≤ δ ε . Do đó ∥∥∥x(ε)− x+ xg 2 ∥∥∥2 = ∥∥∥x(ε)− xg− x− xg 2 ∥∥∥2; = ∥∥x(ε)− xg∥∥2−〈x(ε)− xg,x− xg〉+∥∥∥x− xg 2 ∥∥∥2; ≤ ∥∥∥x− xg 2 ∥∥∥2+ δε . Khi đó 2), 3) được chứng minh.  Bổ đề 3.1.2. Giả sử f là giả đơn điệu trên C và thỏa mãn các giả thiết (A1), (A2). Khi đó, nếu tập nghiệm S(C, f ) là khác rỗng thì với mọi ε > 0,δ ≥ 0 tập δ − nghiệm Sδ (C, fε) là khác rỗng và compact yếu. Chứng minh. Theo Mệnh đề 2.3.2, ta luôn tìm được một vectơ y0 ∈C sao cho tập Lδ (y 0, fε) := { x ∈C : fε(x,y0) := f (x,y0)+ ε 〈 x− xg,y0− x〉≥−δ} là bị chặn. Lấy y0 ∈ S(C, f ) và x ∈ Lδ (y0, fε). Từ định nghĩa của Lδ (y0, fε) ta có fε(x,y0) = f (x,y0)+ ε 〈 x− xg,y0− x〉≥−δ . Từ điều kiện f (y0,x)≥ 0, do f là giả đơn điệu nên ta có f (x,y0)≤ 0. Do đó 〈 x− xg,y0− x〉≥−δ ε . Khi đó 1 2 [‖xg− y0‖2−‖xg− x‖2−‖x− y0‖2]= 〈x− xg,y0− x〉≥−δ ε . Từ đó ‖xg− x‖2+‖x− y0‖2 ≤ ‖xg− y0‖2+2δ ε , trong đó ‖xg− x‖ ≤ √ ‖xg− y0‖2+2δ ε , suy ra ‖x‖ ≤ ‖xg‖+ √ ‖y0− xg‖2+2δ ε , ∀x ∈ Lδ (y0, fε). Vậy tập Lδ (y0, fε) là bị chặn. 34 Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp 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, ŷ