Luận văn Phương pháp giải bất đẳng thức biến phân đa trị thông qua tìm điểm bất động của ánh xạ nghiệm

T, T′ : Rn → 2Rn và λ, λ′ ∈ R thỏa mãn |λ|+ |λ′| ≤ 1 thì λT + λ′T′ cũng là ánh xạ không giãn. Chứng minh. Với mọi z, z′ ∈ Rn và v = λa + λ′b ∈ (λT + λ′T′)(z), a ∈ T(z), b ∈ T′(z), v′ = λa′ + λ′b′ ∈ (λT + λ′T′)(z′), a′ ∈ T(z′), b′ ∈ T′(z′). Ta có ||v − v′|| = ||λ(a − a′) + λ′(b − b′)|| ≤ |λ|.||a − a′||+ |λ′|.||b − b′|| ≤ |λ|.||z − z′||+ |λ′|.||z − z′|| (do T, T′ không giãn) = (|λ| + |λ′|)||z − z′|| ≤ ||z − z′|| (do |λ| + |λ′| ≤ 1). Vậy λT + λ′T′ là ánh xạ không giãn.  17 Bổ đề 1.2.14 Song ánh J : Rn × Rn → Rn × Rn với J(x, v) = (v + x, v − x) cảm sinh tương ứng 1-1 giữa ánh xạ T : Rn → 2Rn và ánh xạ S : Rn → 2Rn với gph S = J(gph T), gph T = J−1(gph S). Khi đó, S là ánh xạ không giãn khi và chỉ khi T đơn điệu; S là ánh xạ co khi và chỉ khi T đơn điệu ngặt và đơn trị trên dom T và ta có: S = I − 2I◦(I + T)−1, T = (I − S)−1◦2I − I. (1.2) Chứng minh. Với (z, w) = J(x, v) và (z′, w′) = J(x′, v′) ta có: ||z − z′||2 − ||w − w′||2 = 〈(z − z′) + w − w′, (z − z′)− (w − w′)〉 = 〈(z + w)− (z′ + w′), (z − w)− (z′ − w′)〉 = 〈2v − 2v′, 2x − 2x′〉 = 4〈v − v′, x − x′〉 và do đó ||w − w′|| ≤ ||z − z′|| ⇔ 〈v − v′, x − x′〉 ≥ 0. (1.3) Vì điều này đúng với mọi cặp tương ứng (z, w), (z′ , w′) ∈ gph S và (x, v), (x′, v′) ∈ gph T, nên S không giãn khi và chỉ khi T đơn điệu. Ta có S là ánh xạ co khi và chỉ khi bất đẳng thức bên trái của (1.3) là ngặt khi (z, w) 6= (z′, w′). Mặt khác T đơn điệu ngặt và đơn trị trên dom T khi và chỉ khi bất đẳng thức bên phải của (1.3) là ngặt khi (x, v) 6= (x′, v′). Với (z, w) ∈ J(gph T), x, v ∈ T(x) ta có: z = v + x và w = v − x. Điều này tương đương với tồn tại x sao cho z ∈ (I + T)(x) và w = (z − x) − x = z − 2x. Vì vậy w ∈ S(z) khi và chỉ khi w = z − 2x với x ∈ (I + T)−1(z). Vậy S = I − 2I◦(I + T)−1, suy ra (I + T) = (I − S)−1◦2I.  Định lý 1.2.15 Nếu T : Rn → 2Rn là ánh xạ đơn điệu và λ > 0 thì (I + λT)−1 đơn điệu và không giãn. Hơn nữa, T là đơn điệu cực đại khi và chỉ khi dom(I + λT)−1 = Rn. Trong trường hợp đó (I + λT)−1 cũng đơn điệu cực đại và đơn trị trên Rn. 18 Chứng minh. Theo tính chất 1.2.7(b), ánh xạ T đơn điệu khi và chỉ khi λT(λ > 0) đơn điệu, và dễ thấy λT đơn điệu cực đại khi và chỉ khi T đơn điệu cực đại. Do đó, không mất tính tổng quát ta có thể thay λT bởi T. Giả sử T đơn điệu, do I cũng đơn điệu nên I + T đơn điệu (theo 1.2.7(c)), do vậy (I + T)−1 đơn điệu (theo 1.2.7(a)). Theo Bổ đề 1.2.14 ta có (I + T)−1 = 12(I − S) với ánh xạ không giãn S nào đó. Vì I là ánh xạ không giãn nên 12 I − 12S cũng không giãn (theo 1.2.13). Do đó (I + T)−1 không giãn trên D = dom(I + T)−1. Vậy (I + T)−1 đơn điệu và không giãn. Từ Bổ đề 1.2.14, T là ánh xạ đơn điệu cực đại khi và chỉ khi S là ánh xạ không giãn cực đại. Mặt khác, ánh xạ không giãn S có thể được mở rộng lên toàn Rn (xem [8], Định lý 9.58). Do đó, S là ánh xạ không giãn cực đại khi và chỉ khi dom S = Rn. Vậy đối với ánh xạ (I + T)−1, khi T đơn điệu cực đại, ta có dom(I + T)−1 = Rn. Do (I + T)−1 là đơn trị, liên tục trên dom(I + T)−1 và đơn điệu dẫn đến (I + T)−1 là đơn điệu cực đại (theo 1.2.11).  Bổ đề 1.2.16 Mọi ánh xạ đa trị T : Rn → 2Rn ta có đồng nhất thức: (λI + T−1)−1 = λ−1[I − (I + λT)−1] với λ > 0. Chứng minh. Ta có: z ∈ λ−1[I−(I + λT)−1](w) ⇔ λz ∈ w − (I + λT)−1(w) ⇔ w − λz ∈ (I + λT)−1(w) ⇔ w ∈ (w − λz) + λT(w − λz) ⇔ z ∈ T(w − λz) ⇔ w − λz ∈ T−1(z) ⇔ w ∈ (λI + T−1)(z) ⇔ z ∈ (λI + T−1)−1(w)  Tính chất 1.2.17 (Tham số hóa Minty). Cho T : Rn → 2Rn là đơn điệu cực đại. Khi đó các ánh xạ P = (I + T)−1, Q = (I + T−1)−1 là đơn trị, đơn điệu cực đại và không giãn, ánh xạ z 7→ (P(z), Q(z)) là ánh xạ 1-1 từ Rn vào gph T. Do vậy, ta có một cách tham số hóa của T mà Lipschitz theo cả 19 hai phương: (P(z), Q(z)) = (x, v) ⇔ z = x + v, (x, v) ∈ gph T. Chứng minh. Theo tính chất 1.2.7(a), T−1 đơn điệu cực đại khi và chỉ khi T đơn điệu cực đại, và từ Định lý 1.2.15 suy ra P và Q đơn trị, đơn điệu cực đại và không giãn, do đó liên tục Lipschitz. Mặt khác, P + Q = I (theo Bổ đề 1.2.16) nên khi (P(z), Q(z)) = (x, v) ta có x + v = z và z ∈ (I + T)(x), vì thế v = z − x ∈ T(x), tức là (x, v) ∈ gph T. Ngược lại, nếu (x, v) ∈ gph T và x + v = z thì z − x = v ∈ T(x), hay z ∈ (I + T)(x), vì thế x = P(z), do tính đối xứng nên ta cũng có v = Q(z). Ánh xạ z 7→ (P (z) , Q (z)) liên tục Lipschitz vì P và Q liên tục Lipschitz. Thật vậy, giả sử P, Q liên tục Lipschitz với hệ số LP, LQ. Với mọi z1, z2 thì : ||((P(z1)), Q(z1))− (P(z2), Q(z2))|| = ||(P(z1)− P(z2), Q(z1)− Q(z2))|| = √ (P(z1)− P(z2))2 + (Q(z1) + Q(z2))2 ≤ √ 2 √ (LP||z1 − z2||)2 + (LQ||z1 − z2||)2 = √ 2(L2P + L 2 Q)||z1 − z2|| Ánh xạ (x, v) 7→ x + v là liên tục Lipschitz vì đây là phép biến đổi tuyến tính.  Ví dụ 1.2.18 Cho ánh xạ không giãn F : Rn → Rn, khi đó ánh xạ I − F là đơn điệu cực đại. Chứng minh. Vì F là ánh xạ không giãn, xác định trên Rn nên F là ánh xạ không giãn cực đại. Theo Bổ đề 1.2.14 ta có T0 = (I − F)−1◦2I − I là ánh xạ đơn điệu cực đại. Do đó, I − F = 12 I◦(I + T0)−1 đơn điệu cực đại (theo 1.2.17).  1.2.4. Tính đơn điệu của hàm lồi Trước khi đưa ra tính đơn điệu của hàm lồi, ta nhắc lại một số kết quả của Rockafellar dưới dạng bổ đề như sau: 20 Bổ đề 1.2.19 Cho hàm lồi, chính thường f : Rn → R và λ > 0. Khi đó Pλ f (x) = (I + λ∂ f ) −1(x), với ∀x ∈ Rn, trong đó, Pλ f (x) = argmin w { f (w) + 1 2λ ||w − x||2}. Chứng minh. Theo Tính chất 1.1.8 ta có: y ∈ Pλ f (x) ⇔ y ∈ argmin w { f (w) + 1 2λ ||w − x||2} ⇔ 0 ∈ ∂ f (y) + 1 λ (y − x) ⇔ 0 ∈ λ∂ f (y) + y − x ⇔ x ∈ y + λ∂ f (y) = (I + λ∂ f )(y) ⇔ y ∈ (I + λ∂ f )−1(x). Vậy ta có điều phải chứng minh.  Bổ đề 1.2.20 Với hàm lồi, chính thường, nửa liên tục dưới f : Rn → R ta có ∂ f ∗ = (∂ f )−1, với f ∗(x∗) := sup{〈x∗, x〉 − f (x) | x ∈ Rn} là hàm liên hợp của f . Chứng minh. Theo định nghĩa hàm liên hợp, ta có f ∗(x∗) = sup x {〈x∗, x〉 − f (x)}. Điều này tương đương với f ∗(x∗) ≥ 〈x∗, y〉 − f (y) ∀y. Do đó f ∗(x∗) + f (x) = 〈x∗, x〉, khi và chỉ khi 〈x∗, y〉 − f (y) − f (x) ≤ 〈x∗, x〉 ∀y, tương đương với x∗ ∈ ∂ f (x). Do tính đối xứng nên ta cũng có f ∗(x∗) + f (x) = 〈x∗, x〉 21 khi và chỉ khi x ∈ ∂ f ∗(x∗). Vậy x∗ ∈ ∂ f (x) ⇔ x ∈ ∂ f ∗(x∗), hay ∂ f ∗ = (∂ f )−1.  Định lý 1.2.21 Nếu f : Rn → R là hàm lồi, chính thường thì ∂ f đơn điệu cực đại. Chứng minh. Giả sử f là hàm lồi, chính thường, ta có ∂ f đơn điệu (theo Ví dụ 1.2.5) và với λ > 0, Pλ f = (I + λ∂ f )−1 (theo Bổ đề 1.2.19). Mặt khác, từ định nghĩa của Pλ f ta dễ thấy dom Pλ f = Rn, suy ra dom(I + λ∂ f )−1 = Rn . Vậy ∂ f đơn điệu cực đại (theo Định lý 1.2.15).  Hệ quả 1.2.22 Với bất kì tập lồi, đóng, khác rỗng C trong Rn, ánh xạ NC : Rn → 2R n là đơn điệu cực đại. Chứng minh. Ta xét hàm f = δC, thì f là hàm chính thường, nửa liên tục dưới và lồi (do C là tập lồi) với ∂ f = NC. Áp dụng Định lý 1.2.21 ta có ∂ f = NC đơn điệu cực đại.  Ở đây, ta lưu ý rằng, khi xem NC như một ánh xạ đa trị từ Rn vào 2R n , ta đã quy ước NC(x) := ∅ với mọi x /∈ C. Mệnh đề 1.2.23 Cho f : Rn → R là hàm lồi, chính thường, nửa liên tục dưới, khi đó với bất kì λ > 0, ánh xạ xấp xỉ Pλ f : Rn → 2Rn là đơn điệu cực đại, không giãn và I − Pλ f = Pλ f ∗ khi λ = 1. Chứng minh. Do f là hàm lồi, chính thường, nửa liên tục dưới nên theo Định lý 1.2.21 ta có ∂ f đơn điệu cực đại, do đó với λ > 0 thì λ∂ f đơn điệu cực đại. Áp dụng tính chất 1.2.17 suy ra (I + λ∂ f )−1 đơn điệu cực đại và không giãn. Nhưng theo 1.2.19 thì Pλ f (x) = (I + λ∂ f )−1(x) với mọi x. Vậy ta có Pλ f đơn điệu cực đại 22 và không giãn. Với bất kì hàm f : Rn → R ta luôn có ∂ f ∗ = (∂ f )−1. Do đó: I − P1 f = I − (I + ∂ f )−1 = [I + (∂ f )−1]−1 (theo Bổ đề 1.2.16) = (I + ∂ f ∗) = P1 f ∗. Vậy khi λ = 1 ta có: I − Pλ f = Pλ f ∗.  Hàm f = δC là hàm chính thường, nửa liên tục dưới với ∂ f = NC, và hàm f lồi khi C là tập lồi. Ta có Pλ f = PC, nên theo mệnh đề 1.2.23 ta có kết quả dưới đây: Hệ quả 1.2.24 (Phép chiếu). Cho tập lồi, khác rỗng C ⊂ Rn, phép chiếu PC : R n → 2Rn xác định bởi PC(x) = argmin w∈Rn {||w − x||+ δC(w)} là đơn điệu cực đại. Ta đa biết một không gian con là một tập lồi nên áp dụng Hệ quả 1.2.22 và 1.2.24 ta có kết quả dưới đây: Hệ quả 1.2.25 (Phép chiếu trong không gian con). Với mọi không gian con tuyến tính M ⊂ Rn và phần bù trực giao M⊥, ánh xạ: NM(x) =  M ⊥ khi x ∈ M, ∅ khi x /∈ M và ánh xạ nghịch đảo N−1M (v) =  M khi v ∈ M ⊥, ∅ khi x /∈ M⊥. đơn điệu cực đại với . Phép chiếu tuyến tính lên M là PM = (I + NM)−1, lên M⊥ là PM⊥ = (I + N −1 M ) −1. Các phép chiếu này cũng đơn điệu cực đại. 1.2.5. Ánh xạ đơn điệu mạnh Định nghĩa 1.2.26 Ánh xạ đa trị T : Rn → 2Rn gọi là đơn điệu mạnh với hệ số σ > 0 trên C nếu với mọi x, x′ ∈ C, tồn tại σ > 0 sao cho T − σI đơn điệu, tức là 〈(v − σx)− (v′ − σx′), x − x′〉 ≥ 0 ∀v ∈ T(x), v′ ∈ T(x′). 23 Bất đẳng thức trong định nghĩa có thể viết dưới dạng: 〈v − v′, x − x′〉 ≥ σ||x − x′||2 ∀v ∈ T(x), v′ ∈ T(x′). Dễ dàng suy ra rằng nếu T đơn điệu mạnh thì T đơn điệu ngặt. Ví dụ 1.2.27 Cho C = {(x, 0) | x ≥ 0} và ánh xạ G : C → 2Rn được cho bởi G(x, 0) := {(2x, y) | 0 ≤ y ≤ x}. Khi đó, G đơn điệu mạnh trên C với hệ số σ = 1. x y O 2x G(x, 0) y = 12 x x Hình 1.6: Thật vậy, ta có (G − I)(x, 0) = {(x, y) | 0 ≤ y ≤ x} =: F(x, 0). Mà theo Ví dụ 1.2.2 thì F(x, 0) đơn điệu trên C. Vậy G(x, 0) đơn điệu mạnh trên C với hệ số σ = 1.  Mệnh đề 1.2.28 Nếu ánh xạ đơn điệu cực đại T : Rn → 2Rn đơn điệu mạnh với hệ số σ > 0 thì T−1 đơn trị và liên tục Lipschitz với hệ số κ = 1σ . Chứng minh. Do T đơn điệu mạnh với hệ số σ > 0 nên ánh xạ T0 = T − σI đơn điệu, do đó T−1 = (σI + T0)−1 cũng đơn điệu; mặt khác, T đơn điệu cực đại nên T0 phải đơn điệu cực đại. Mở rộng đơn điệu chính tắc T0 của T0 tương ứng cho ta mở rộng đơn điệu chính tắc T0 + σI của T. Theo Định lý 1.2.15, ánh xạ (I + 1σ T0) −1 đơn trị và không giãn. Vậy (σI + T0)−1 đơn trị và liên tục Lipschitz với hệ số 1σ .  Áp dụng mệnh đề 1.2.28 cho ánh xạ T−1 ta có hệ quả sau: 24 Hệ quả 1.2.29 Nếu T : Rn → 2Rn là đơn điệu cực đại và T−1 đơn điệu mạnh với hệ số σ > 0, tức là 〈v − v′, x − x′〉 ≥ σ||v − v′||2 ∀v ∈ T(x), v′ ∈ T(x′). Tính chất 1.2.30 Cho hàm f : Rn → R và σ > 0, nếu f lồi mạnh với hệ số σ thì ∂ f đơn điệu mạnh với hệ số σ. Chứng minh. Trước hết ta chứng minh rằng: f lồi mạnh với hệ số σ khi và chỉ khi f − 12 σ|| · ||2 là lồi. Thật vậy, giả sử f − 12σ || · ||2 lồi, với mọi x, x′ ∈ Rn, λ ∈ (0, 1) ta có: f ((1 − λ)x + λx′)−1 2 σ||(1 − λ)x + λx′||2 ≤(1 − λ)( f (x) − 1 2 σ||x||2) + λ( f (x′)− 1 2 σ||x′||2) ⇔ f ((1 − λ)x + λx′) ≤(1 − λ) f (x) + λ f (x′)− 1 2 (1 − λ)σ||x||2 − 1 2 λσ||x′||2 + 1 2 σ||(1 − λ)x + λx′||2. (1.4) Thực hiện biến đổi 1 2 σ||(1 − λ)x + λx′||2 − 1 2 (1 − λ)σ||x||2 − 1 2 λσ||x′||2 = 1 2 σ||x||2 + 1 2 σλ2||x − x′||2 − σ〈x, λ(x − x′)〉 − 1 2 σ(1 − λ)||x||2 − 1 2 σλ||x′||2 = 1 2 σλ2||x − x′||2 − σλ||x||2 + σλ〈x, x′〉+ 1 2 σλ||x||2 − 1 2 σλ||x′||2 = 1 2 σλ2||x − x′||2 − 1 2 σλ||x||2 + σλ〈x, x′〉 − 1 2 σλ||x′||2 = 1 2 σλ2||x − x′||2 − 1 2 σλ||x − x′||2 = 1 2 σλ(λ − 1)||x − x′||2. Do vậy, bất đẳng thức (1.4) tương đương với f ((1 − λ)x + λx′) ≤ (1− λ) f (x) + λ f (x′)− 1 2 σλ(1 − λ)||x − x′||2. Theo Ví dụ 1.2.5, ∂ f − σI đơn điệu. Vậy ∂ f đơn điệu mạnh với hệ số σ.  Từ Tính chất trên với chú ý đến Bổ đề 1.2.20 và Hệ quả 1.2.29 ta có hệ quả sau: 25 Hệ quả 1.2.31 Với f : Rn → R là hàm lồi, chính thường, nửa liên tục dưới và số thực σ > 0. Nếu hàm liên hợp f ∗ của f lồi mạnh với hệ số σ thì 〈v − v′, x − x′〉 ≥ σ||v − v′||2 ∀x, x′, v ∈ ∂ f (x), v′ ∈ ∂ f (x′). 1.2.6. Ánh xạ đồng bức Định nghĩa 1.2.32 Cho ánh xạ đa trị T : Rn → 2Rn , T được gọi là đồng bức với hệ số δ > 0 trên C nếu 〈v − v′, x − x′〉 ≥ δρ2(T(x), T(x′)) ∀x, x′ ∈ C, v ∈ T(x), v′ ∈ T(x′). Ví dụ 1.2.33 Xét ánh xạ F : C → 2Rn , với C = {(x, 0) | x ≥ 0} ⊂ R2 xác định bởi F(x, 0) := {(x, y) | 0 ≤ y ≤ x}. Khi đó, F đồng bức trên C với hế số δ = 12 . Chứng minh. Theo Ví dụ 1.1.12, ta đã biết ánh xạ này Lipschitz trên C với hệ số L = √ 2. Bây giờ, lấy tùy ý (x, 0), (x′, 0) ∈ C, (x, y) ∈ T(x), (x′, y′) ∈ T(x′) ta có 〈(x, y) − (x′, y′), (x, 0)− (x′, 0)〉 = |x − x′|2 = ||(x, 0)− (x′, 0)||2. Từ hai điều trên ta suy ra ρ2(F(x, 0), F(x′ , 0)) ≤ 2||(x, 0)− (x′, 0)||2 = 2〈(x, y)− (x′, y′), (x, 0)− (x′, 0)〉, với mọi (x, 0), (x′, 0) ∈ C, (x, y) ∈ T(x), (x′, y′) ∈ T(x′). Vậy F(x, 0) đồng bức trên C với hệ số δ = 12 .  Mệnh đề 1.2.34 Nếu T : Rn → 2Rn là ánh xạ đồng bức thì T là ánh xạ Lipschitz. Chứng minh. Giả sử ánh xạ T đồng bức với hệ số δ > 0 trên C, khi đó với mọi x, x′ ∈ C, v ∈ T(x), v′ ∈ T(x′) ta có δρ2(T(x), T(x′)) ≤ 〈v − v′, x − x′〉 ≤ ||v − v′||.||x − x′||. Suy ra δρ2(T(x), T(x′)) ≤ ||x − x′|| inf v′∈T(x′) ||v − v′|| với v ∈ T(x) cố định tùy ý, 26 do đó δρ2(T(x), T(x′)) ≤ ||x − x′|| sup v∈T(x) inf v′∈T(x′) ||v − v′|| = ||x − x′|| d(T(x), T(x′)). Tương tự ta có δρ2(T(x), T(x′)) ≤ ||x − x′|| sup v′∈T(x′) inf v∈T(x) ||v − v′|| = ||x − x′|| d(T(x′), T(x)). Vậy δρ2(T(x), T(x′)) ≤ ||x − x′||ρ(T(x), T(x′))||x − x′||. Hay ρ(T(x), T(x′)) ≤ 1 δ ||x − x′||.  Ngược lại ta có mệnh đề sau: Mệnh đề 1.2.35 Nếu T : Rn → 2Rn là ánh xạ Lipschitz và đơn điệu mạnh thì T là ánh xạ đồng bức. Chứng minh. Giả sử T là ánh xạ Lipschitz với hệ số L > 0 và đơn điệu mạnh với hệ số σ > 0 trên C. Áp dụng trực tiếp định nghĩa, với mọi x, x′ ∈ C và v ∈ T(x), v′ ∈ T(x′), ta có 〈v − v′, x − x′〉 ≥ σ||x − x′||2 ≥ σ L2 ρ2(T(x), T(x′)).  27 CHƯƠNG2 Bất đẳng thức biến phân đa trị Chương này gồm hai phần, phần đầu định nghĩa bài toán bất đẳng thức biến phân đa trị (MVIP) và hai trường hợp đặc biệt là bài toán quy hoạch lồi và bài toán bù. Bên cạnh đó, ta xét một vài ví dụ thực tế của bài toán MVIP. Trong phần tiếp theo phát biểu một số kết quả về điều kiện có nghiệm của bài toán MVIP và tính chất nghiệm của bài toán đó. Tài liệu tham khảo chính của chương này là [2], [5] và [6]. 2.1. Phát biểu bài toán và các ví dụ minh hoạ Cho C là một tập lồi, đóng, khác rỗng trong Rn, cho F : C → 2Rn là một ánh xạ đa trị, ta luôn giả sử C ⊆ domF, trong đó theo định nghĩa domF := {x ∈ Rn | F(x) 6= ∅}. Ta cũng luôn giả sử rằng F(x) lồi, đóng với mọi x ∈ domF. Khi đó, bài toán bất đẳng thức biến phân đa trị (được viết tắt là MVIP) có thể được phát biểu như sau: (MVIP) { Tìm x∗ ∈ C và v∗ ∈ F(x∗) sao cho 〈v∗, x − x∗〉 ≥ 0 ∀x ∈ C. (2.1) F được gọi là ánh xạ giá của bài toán bất đẳng thức biến phân đa trị (MVIP). Một trường hợp riêng điển hình của bài toán MVIP là bài toán quy hoạch lồi. Ta có cách tiếp cận bài toán dựa trên mệnh đề sau: 28 Mệnh đề 2.1.1 Cho C là một tập lồi, đóng, khác rỗng của không gian Rn. Hàm f : C → R là lồi, khả dưới vi phân trên C. Khi đó, x∗ là nghiệm của bài toán min{ f (x) | x ∈ C} (2.2) khi và chỉ khi x∗ là nghiệm của bài toán bất đẳng thức biến phân:{ Tìm x∗ ∈ C và v∗ ∈ ∂ f (x∗) sao cho 〈v∗, x − x∗〉 ≥ 0 ∀x ∈ C. Chứng minh. Giả sử x∗ là nghiệm của bài toán (2.2) và v∗ ∈ ∂ f (x∗). Khi đó x∗ ∈ C, f (x∗) ≤ f (x), ∀x ∈ C và 〈v∗, x − x∗〉 ≥ f (x) − f (x∗). Suy ra 〈v∗, x − x∗〉 ≥ 0, ∀x ∈ C Ngược lại, giả sử x∗ ∈ C và v∗ ∈ ∂ f (x∗) sao cho 〈v∗, x − x∗〉 ≥ 0, ∀x ∈ C. Điều này có nghĩa là 〈v∗, x − x∗〉 ≥ f (x) − f (x∗), và 〈v∗, x − x∗〉 ≥ 0 với ∀x ∈ C. Do đó, f (x) − f (x∗) ≥ 0 ∀x ∈ C, hay x∗ là nghiệm của bài toán (2.2).  Từ Mệnh đề 2.1.1, khi f là hàm khả vi trên C, suy ra ngay rằng bài toán (2.2) tương đương với bài toán:{ Tìm x∗ ∈ C sao cho 〈5 f (x∗), x − x∗〉 ≥ 0 ∀x ∈ C. Chú ý rằng khi C là một nón lồi, đóng trong Rn, thì bài toán MVIP trở thành bài toán bù. Cụ thể ta có mệnh đề sau: Mệnh đề 2.1.2 Nếu C là một nón lồi, đóng trong Rn, F là ánh xạ đơn trị, thì bài toán MVIP tương đương với bài toán bù sau:{ Tìm x ∈ C sao cho F(x) ∈ C+ và 〈F(x), x〉 = 0, trong đó C+ := {y ∈ Rn | 〈y, x〉 ≥ 0 ∀x ∈ C} là nón đối ngẫu của C. 29 Chứng minh. Nếu x là nghiệm của bất đẳng thức biến phân thì 〈F(x), y − x〉 ≥ 0 ∀y ∈ C. Do C là nón lồi, x ∈ C nên x + y ∈ C với mọi y ∈ C. Trong bất đẳng thức trên thay y bởi x + y ta có 〈F(x), x + y− x〉 = 〈F(x), y〉 ≥ 0, ∀y ∈ C. Ngoài ra nếu chọn y = 0 ta có 0 ≤ −〈F(x), x〉 ≤ 0. Suy ra 〈F(x), x〉 = 0. Điều ngược lại mọi nghiệm của bài toán bù đều là nghiệm của bất đẳng thức biến phân là hiển nhiên.  Như vậy, bài toán bù cũng là một trường hợp đặc biệt của bài toán bất đẳng thức biến phân. Dưới đây ta xét hai ví dụ thực tế của bài toán MVIP. Ví dụ 2.1.3 (Bài toán cân bằng mạng giao thông). Xét một mạng giao thông được cho bởi một mạng luồng hữu hạn. Gọi • N : tập hợp các nút của mạng. • A: là tập hợp các cạnh (mỗi cạnh được gọi là một đoạn đường). Giả sử O ⊆ N , D ⊆ N sao cho O ∩D = ∅. Mỗi phần tử của O được gọi là điểm nguồn, còn mỗi phần tử của D được gọi là đ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 (được gọi là một tuyến đường). Ký hiệu: • f ia là mật độ giao thông của phương tiện i trên đoạn đường a ∈ A. Đặt f là vec-tơ có các thành phần là f ia với i ∈ I và a ∈ A (I là tập hợp các phương tiện giao thông. • cia là chi phí khi sử dụng phương tiện giao thông i trên đoạn đường a ∈ A. Đặt c là vec-tơ có các thành phần là cia với i ∈ I, a ∈ A. • diw là nhu cầu sử dụng loại phương tiện i ∈ I trên tuyến đường w = (O, D) với O ∈ O, D ∈ D. Giả sử rằng 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 . • λiw là mức độ chi phí trên tuyến đường w của phương tiện giao thông i. • xiw là mật độ giao thông của phương tiện i ∈ I trên tuyến w ∈ O ×D. 30 Giả sử trong mạng trên, phương trình cân bằng sau được thoả mãn diw = ∑ p∈Pw xip ∀i ∈ I, w ∈ O ×D, (2.3) trong đó, Pw ký hiệu tập hợp các tuyến đường của w = (O, D) (nối điểm nguồn O và điểm đích D). Theo phương trình (2.3), thì nhu cầu sử dụng loại phương tiện i trên tuyến đường w bằng đúng tổng mật độ giao thông của phương tiện đó trên mọi tuyến đường nối điểm nguồn và điểm đích của tuyến đường đó. Khi đó ta có f ia = ∑ p∈Pw xipδap ∀i ∈ I, w ∈ O ×D, (2.4) trong đó δap :=  1 nếu a ∈ p0 nếu a /∈ 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 = ∑ a∈A ciaδap. (2.5) Như vậy, cip là một chi phí khi sử dụng phương tiện i trên tuyến đường p. Đặt d là vec-tơ có các thành phần là diw (i ∈ I, w ∈ O ×D) và đặt f là vec-tơ có các thành phần là dia (i ∈ I, a ∈ O × D). Một cặp (d∗, f ∗) thoả mãn các điều kiện (2.3) và (2.4) được gọi là điểm cân bằng của mạng giao thông nếu cip( f ∗)  = λ i w(d ∗) khi xip > 0, > λiw(d ∗) khi xip = 0, (2.6) 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ọi 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 đó. Trái lại, chi phí sẽ không phải thấp nhất. Đặt K = {( f , d) | ∃ x ≥ 0 sao cho (2.3) và (2.4) đúng}. Khi đó, theo [6], ta có định lý sau: Định lý 2.1.4 Một cặp vec-tơ ( 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ất đẳng thức biến phân sau: Tìm ( f ∗, d∗) ∈ K sao cho 〈(c( f ∗), λ(d∗)), ( f , d)− ( f ∗, d∗)〉 ≥ 0 ∀( f , d) ∈ K. 31 Ví dụ 2.1.5 (Bài toán kinh tế bán độc quyền). Giả sử có n công ty cùng sản xuất một loại sản phẩm và lợi nhuận pi của mỗi công ty i phụ thuộc vào tổng số lượng sản phẩm của tất cả các công ty σ := ∑nj=1 xj. Ký hiệu hi(xi) là chi phí của công ty i khi sản xuất ra lượng hàng hoá xi. Giả sử rằng lợi nhuận của công ty i được cho bởi fi(x1, ..., xn) = xi pi ( n ∑ j=1 xj ) − hi(xi) (i = 1, ..., n), (2.7) trong đó p(∑nj=1 xj) là giá của một đơn vị sản phẩm, phụ thuộc vào tổng sản phẩm, còn hàm chi phí của mỗi công ty i chỉ phụ thuộc vào mức độ sản xuất của công ty đó. Đặt Ui ⊂ R, (i = 1, ..., n) là tập chiến lược của công ty i. Lẽ dĩ nhiên, mỗi công ty cần xác định cho mình một mức độ sản xuất để đạt được lợi nhuận cao nhất. Tuy nhiên, trong trường hợp tổng quát, việc tất cả các công ty đều có lợi nhuận cực đại là khó có thể được. Vì vậy người ta dùng đến khái niệm cân bằng: Một điểm x∗ = (x∗1 , ..., x ∗ n) ∈ U := U1 × ...×Un được gọi là điểm cân bằng Nash nếu fi(x ∗ 1 , ..., x ∗ i−1, yi, x ∗ i+1, ..., x ∗ n) 6 fi(x ∗ 1 , ..., x ∗ n) ∀yi ∈ Ui, ∀i = 1, ..., n. Trong mô hình cân bằng Cournot cổ điển, hàm chi phí và hàm lợi nhuận của mỗi công ty là affine có dạng pi(σ) ≡ p(σ) = α0 − βσ, α0 ≥ 0, β > 0, với σ = ∑ni=1 xi, hi(xi) = µixi + ξi, µi ≥ 0, ξi ≥ 0 (i = 1, ..., n). Ta đặt A =   β 0 0 ... 0 0 β 0 ... 0 ... ... ... ... ... 0 0 0 ... β   , A˜ =   0 β β ... β β 0 β ... β ... ... ... ... ... β β β ... 0   và αT = (α0, ..., α0), µ T = (µ1, ..., µn). Theo [6], điểm x∗ là điểm cân bằng Nash khi và chỉ khi x∗ là nghiệm của bài toán bất đẳng thức biến phân: Tìm điểm x ∈ U sao cho〈A˜x + µ − α, y − x〉+ yT Ay − xT Ax ≥ 0 ∀y ∈ U. 32 2.2. Sự tồn tại nghiệm và tính chất của tập nghiệm Định lý 2.2.1 Cho ánh xạ F : Rn → 2Rn, f : gph F → R, và g : Rn → R ∪ {+∞} được xác định bởi công thức g(x) = sup y∈F(x) f (x, y). Khi đó, (i) Nếu f và F nửa liên tục dưới, thì g cũng là nửa liên tục dưới. (ii) Nếu f và F nửa liên tục trên và F(x) compact với mọi x ∈ Rn, thì g cũng là nửa liên tục trên. Định lý dưới đây được đưa ra bởi Ky Fan (thường được gọi là bất đẳng thức Ky Fan), và sau đó được mở rộng bởi H. Brézis, L Nirenberg và G. Stampacchia. Định lý 2.2.2 Cho C là một tập lồi, đóng của không gian Rn, và song hàm φ : C × C → R thoả mãn φ(x, x) = 0 ∀x ∈ C, φ(., v) là nửa liên tục trên với mỗi v ∈ C và φ(u, .) là hàm lồi trên C với mỗi u ∈ C. Giả sử rằng một trong các giả thiết sau đây đúng: (i) C là tập bị chặn. (ii) Tồn tại một tập con U khác rỗng và bị chặn của C sao cho với mọi u ∈ C \ U tồn tại v ∈ U thoả mãn φ(u, v) < 0. Khi đó, tồn tại u∗ ∈ C sao cho φ(u∗, v) ≥ 0 ∀v ∈ C. Để áp dụng cho bài toán MVIP, với mỗi x ∈ C và w ∈ F(x), ta đặt φ(x, y) := max w∈F(x) {〈w, y − x〉}. (2.8) Giả thiết thêm rằng với mỗi x ∈ C, F(x) là một tập compact. Khi đó, theo Định lý 2.2.1, hàm φ(., y) là nửa liên tục trên theo biến x với mỗi y ∈ C. φ(x, .) là hàm lồi theo biến y với mỗi x ∈ C cố định. Như vậy, hàm φ thoả mãn các giả thiết của Định lý 2.2.2. Khi đó, ta có định lý về sự tồn tại nghiệm của bài toán MVIP như sau. 33 Định lý 2.2.3 Cho C là một tập lồi, đóng của không gian Rn; Cho F : C → 2Rn thoả mãn F là nửa liên tục trên, F(x) lồi compact với mỗi x ∈ C. Giả sử rằng một trong các điều kiện sau đây đúng: (i) C là tập bị chặn. (ii) Tồn tại một tập con U khác rỗng và bị chặn của C sao cho với mọi x ∈ C \ U tồn tại y ∈ U thoả mãn 〈w, x − y〉 > 0 ∀w ∈ F(x). Khi đó, bài toán MVIP có nghiệm. Định lý 2.2.4 Cho một tập lồi compact C ⊂ Rn, và một ánh xạ đa trị đóng F : C → 2D từ C vào một tập compact D ⊂ Rn, sao cho với mọi x ∈ C, F(x) là tập lồi compact không rỗng. Khi ấy bài toán MVIP có nghiệm. Chứng minh. Xem [2], Định lý 21, trang 305 . Tính chất về nghiệm của bài toán MVIP được phát biểu qua mệnh đề sau. Mệnh đề 2.2.5 Cho C là một tập lồi, đóng, khác rỗng trong Rn, F như trong bài toán MVIP. Khi đó, (i) Nếu F đơn điệu ngặt trên C, thì bài toán MVIP có nhiều nhất một nghiệm. (ii) Nếu F đơn điệu mạnh, nửa liên tục trên và F(x) lồi, đóng, khác rỗng với mọi x ∈ C, thì bài toán MVIP có duy nhất một nghiệm. 34 CHƯƠNG3 Phương pháp lặp Banach giải bài toán (MVIP) đơn điệu mạnh Như ta đã biết, phương pháp lặp theo nguyên lý ánh xạ co Banach là một kết quả nổi tiếng và là phương pháp cơ bản, rất hiệu quả để tính điểm bất động của một ánh xạ co. Nguyên lý này sau đó được Nadler mở rộng cho ánh xạ đa trị (xem [2], Định lý 14). Trong chương này, chúng ta sẽ dùng cách tiếp cận điểm bất động theo phương pháp lặp của nguyên lý ánh xạ co Banach để giải bài toán bất đẳng thức biến phân đa trị (2.1) được định nghĩa ở Chương 2. Ta sẽ xét trường hợp khi F là ánh xạ đơn điệu mạnh. Chương này sẽ xét đến tính chất co của ánh xạ nghiệm được xây dựng từ bài toán (2.1), trên cơ sở đó trình bày thuật toán lặp Banach và chứng minh tính chất hội tụ của thuật toán. 3.1. Tính chất co của ánh xạ nghiệm Bổ đề 3.1.1 Giả sử C ⊆ Rn là một tập lồi đóng khác rỗng và ánh xạ F : Rn → 2Rn là L-Lipschitz trên C sao cho F(x) là lồi đóng khác rỗng với mọi x ∈ C. Khi đó với mọi x, x′ ∈ C và w ∈ F(x), đều tồn tại w′ ∈ F(x′) (nói riêng w′ = PF(x′)(w)), sao cho ||w − w′|| 6 L||x − x′||, 35 trong đó, PF(x′)(w) là hình chiếu vuông góc của w trên F(x ′). Ngược lại, nếu ánh xạ F thoả mãn điều kiện trên thì F là ánh xạ L-Lipschitz. Chứng minh. Dùng định nghĩa của hình chiếu w′ = PF(x′)(w), ta có ||w − w′|| = min v′∈F(x′) ||w − v′||. (3.1) Theo định nghĩa của khoảng cách Hausdorff, ta được ρ ( F(x), F(x′) ) = max{d(F(x), F(x′)), d(F(x′), F(x))} ≥ d(F(x), F(x′)) = max v∈F(x) min v′∈F(x′) ||v − v′|| ≥ min v′∈F(x′) ||w − v′||. (3.2) Kết hợp (3.1), (3.2) và giả thiết F là L-Lipschitz trên C, ta nhận được ||w − w′|| 6 L||x − x′||. Ngược lại, nếu với mọi x, x′ ∈ C, w ∈ F(x), đều tồn tại w′ ∈ F(x′) sao cho ||w − w′|| 6 L||x − x′||. Do vậy, với w ∈ F(x) cố định tùy ý thì inf w′∈F(x′) ||w − w′|| 6 L||x − x′||, suy ra sup w∈F(x) inf w′∈F(x′) ||w − w′|| 6 L||x − x′|| ∀x, x′ ∈ C. Do đó, d(F(x), F(x′)) 6 L||x − x′|| ∀x, x′ ∈ C. Tương tự d(F(x′), F(x)) 6 L||x − x′|| ∀x, x′ ∈ C. Vậy ta có ρ(F(x), F(x′)) 6 L||x − x′|| ∀x, x′ ∈ C.  36 Trong trường hợp ánh xạ F là đơn trị, bài toán MVIP được viết lại dưới dạng như sau (viết tắt là VI): (VI)  Tìm x ∗ ∈ C sao cho 〈F(x∗), x − x∗〉 ≥ 0 ∀x ∈ C. Khi xét bài toán VI, Auslender đã đưa ra hàm chắn (gap, merit) bằng cách với mỗi x ∈ C, đặt g1(x) = sup{〈F(x), x − y〉 | y ∈ C}. Ta dễ nhận thấy rằng g(x) ≥ 0 với mọi x ∈ C. Theo [7], bài toán VI có thể được viết dưới dạng bài toán tối ưu inf{g1(x) | x ∈ C}. (3.3) Tuy nhiên, một khó khăn của bài toán này là trong trường hợp tổng quát, hàm g1 có thể không khả vi. Để giải quyết khó khăn này, Fukushima (xem [9]) đã đề xuất hàm chắn mới có dạng g2(x) = max{−1 2 〈y − x, G(y − x)〉 − 〈F(x), y − x〉 | y ∈ C}, (3.4) trong đó, G là một ma trận đối xứng, xác định dương. Cũng như đối với hàm chắn g1, ta có g2(x) ≥ 0 với mọi x ∈ C và bài toán VI có thể được viết dưới dạng bài toán tối ưu inf{g2(x) | x ∈ C}. (3.5) Theo [9], hàm g2 được xác định bởi công thức (3.4) là khả vi trên C với F là hàm khả vi. Khi đó, có thể dùng phương pháp tối ưu để giải bài toán VI thông qua việc giải bài toán trơn (3.4). Dựa vào cách xây dựng các hàm chắn ở trên, ta xét trở lại bài toán bất đẳng thức biến phân đa trị (2.1). Với mỗi x ∈ C và w ∈ F(x), đặt y = h(x, w) là nghiệm duy nhất của bài toán qui hoạch min{1 2 〈y − x, G(y − x)〉+ 〈w, y − x〉 | y ∈ C}, (3.6) trong đó G là một ma trận đối xứng, xác định dương. Do C khác rỗng, lồi, đóng và hàm mục tiêu của bài toán (3.6) lồi mạnh (do đó, theo Tính chất 1.1.30, hàm 37 G(y − x) + w đơn điệu mạnh), nửa liên tục trên trên C, nên h(x, w) được xác định và duy nhất (theo Mệnh đề 2.2.5). Theo Mệnh đề 2.1.1, h(x, w) là nghiệm của bài toán (3.6) khi và chỉ khi h(x, w) là nghiệm của bài toán bất đẳng thức biến phân 〈w + G(h(x, w) − x), y − h(x, w)〉 ≥ 0 ∀y ∈ C. (3.7) Với mỗi x ∈ C, ta định nghĩa ánh xạ sau: H(x) := {h(x, w) | w ∈ F(x)}. Nói chung, H là một ánh xạ đa trị và domH ⊆ C. Để tiện cho việc trình bày, ta sẽ gọi H là ánh xạ nghiệm của bài toán MVIP. Kết quả sau đây chỉ ra rằng điểm x∗ là nghiệm của bài toán MVIP khi và chỉ khi x∗ là điểm bất động của ánh xạ H. Định lý 3.1.2 x∗ là nghiệm của bài toán MVIP khi và chỉ khi x∗ ∈ H(x∗). Chứng minh. Giả sử x∗ là nghiệm của bài toán MVIP. Điều đó có nghĩa rằng tồn tại w∗ ∈ F(x∗) sao cho (x∗, w∗) thoả mãn bất đẳng thức 〈w∗, x − x∗〉 ≥ 0 ∀x ∈ C. (3.8) Với mỗi (x∗, w∗) cho trước, do h(x∗, w∗) là nghiệm duy nhất của bài toán (3.6), nên h(x∗, w∗) ∈ C. Thay thế x bởi h(x∗, w∗) trong bất đẳng thức (3.8), ta được 〈w∗, h(x∗, w∗)− x∗〉 ≥ 0. (3.9) Bất đẳng thức (3.7) chỉ ra rằng 〈w∗ + G(h(x∗, w∗)− x∗), y − h(x∗, w∗)〉 ≥ 0 ∀y ∈ C. (3.10) Thay thế y bởi x∗ ∈ C trong bất đẳng thức (3.10), ta có 〈w∗ + G(h(x∗, w∗)− x∗), x∗ − h(x∗, w∗)〉 ≥ 0. (3.11) Từ bất đẳng thức (3.9) và (3.11) suy ra 〈G(h(x∗ , w∗)− x∗), x∗ − h(x∗, w∗)〉 ≥ 0, (3.12) Do ma trận G là đối xứng, xác định dương, ta có h(x∗, w∗) = x∗. Suy ra x∗ ∈ H(x∗). 38 Bây giờ, ta xét chiều ngược lại. Giả sử rằng x∗ ∈ H(x∗). Khi đó, tồn tại w∗ thuộc F(x∗) sao cho x∗ = h(x∗, w∗). Nhưng với mọi x ∈ C, w ∈ F(x), chúng ta luôn có 〈w + G(h(x, w) − x), y − h(x, w)〉 ≥ 0 ∀y ∈ C. (3.13) Thay thế x, w bởi các điểm tương ứng x∗ = h(x∗, w∗), w∗ trong bất đẳng thức (3.13) ta được 〈w∗ + z∗, y − x∗〉 ≥ 0 ∀y ∈ C, (3.14) Điều này có nghĩa rằng x∗ là nghiệm của bài toán MVIP.  Hãy trở lại bài toán (3.4) với C lồi, đóng. Để tiện cho việc trình bày, ta viết bài toán này dưới dạng tương đương là: g2(x) = −min{1 2 〈y − x, G(y − x)〉+ 〈F(x), y − x〉 | y ∈ C}. (3.15) Vì G là ma trận đối xứng và xác định dương, nên (3.15) là một bài toán quy hoạch lồi mạnh và do đó nó có duy nhất nghiệm. Khi F là ánh xạ đơn trị thì ánh xạ nghiệm H của bài toán MVIP là đơn trị và H(x) chính là nghiệm của bài toán (3.15) với mỗi x ∈ C. Khi đó, kết quả nhận được của Định lý 3.1.2 trùng với kết quả được chỉ ra bởi Fukushima (xem [9]) cho bài toán VI. Cụ thể, ta thu được hệ quả sau. Hệ quả 3.1.3 x∗ là nghiệm của bài toán VI khi và chỉ khi x∗ = H(x∗). Dưới đây để đơn giản, ta giả sử G = αI, trong đó α > 0 và I là ma trận đồng nhất. Khi đó, chúng ta sẽ đưa ra cách điều chỉnh tham số α phù hợp, sao cho ánh xạ nghiệm H có tính chất co trên C. Tham số α được gọi là tham số chính quy hoá. Định lý dưới đây sẽ khẳng định tính chất co của ánh xạ nghiệm H trong trường hợp F là ánh xạ đơn điệu mạnh trên C. Định lý 3.1.4 Giả sử rằng F(x) là lồi, đóng, khác rỗng với mỗi x ∈ C, F là một ánh xạ đơn điệu mạnh với hệ số β > 0 và Lipschitz với hệ số L > 0 trên C. Khi đó, với α > L 2 2β , ánh xạ H là co trên C với hệ số δ := √ 1− 2βα + L 2 α2 . Cụ thể, ta có ρ(H(x), H(x′)) 6 δ||x − x′|| ∀x, x′ ∈ C. Chứng minh. Bài toán (3.6) có thể được viết dưới dạng min y {1 2 α||y − x||2 + 〈w, y − x〉+ δC(y)}, 39 ở đây δC là hàm chỉ của C. Đây là một quy hoạch toàn phương lồi mạnh, do đó nó có duy nhất nghiệm và nghiệm này được ký hiệu bởi h(x, w). Theo Tính chất 1.1.8, ta có 0 ∈ α(h(x, w) − x) + w + NC(h(x, w)), NC(h(x, w)) là nón pháp tuyến của C tại h(x, w). Điều này có nghĩa rằng tồn tại z1 ∈ NC(h(x, w)) sao cho α(h(x, w) − x) + w + z1 = 0. Do vậy h(x, w) = x − 1 α w − 1 α z1. (3.16) Tương tự với x′ ∈ C, w′ ∈ F(x′), ta có h(x′, w′) = x′ − 1 α w′ − 1 α z′1 − 1 α z′2, (3.17) ở đây z′1 ∈ NC(h(x′ , w′)). Do ánh xạ đa trị NC là đơn điệu, ta có 〈z1 − z′1, h(x, w)− h(x′, w′)〉 ≥ 0. (3.18) Thay thế z1 của công thức (3.16) và z′1 của công thức (3.17) vào công thức (3.18), ta nhận được 〈x − x′ − 1 α (w − w′)− (h(x, w) − h(x′, w′)), h(x, w) − h(x′, w′)〉 ≥ 0, điều này tương đương với ||h(x, w) − h(x′, w′)||2 6〈x − x′ − 1 α (w − w′), h(x, w) − h(x′, w′)〉. (3.19) Bất đẳng thức này chỉ ra rằng ||h(x, w) − h(x′, w′)||2 6 ||x − x′ − 1 α (w − w′)||.||h(x, w) − h(x′, w′)||. Như vậy là ||h(x, w) − h(x′, w′)||2 6 ||x − x′ − 1 α (w − w′)||2 = ||x − x′||2 − 2 α 〈x − x′, w − w′〉+ 1 α2 ||w − w′||2. (3.20) 40 Từ giả thiết ánh xạ F là L-Lipschitz trên C, F(x′) đóng với mỗi x′ ∈ C và w ∈ F(x), nên theo Bổ đề 3.1.1, tồn tại w′ ∈ F(x′) sao cho ||w(x) − w(x′)|| 6 L||x − x′||. Mặt khác, do giả thiết F đơn điệu mạnh với hệ số β nên 〈w − w′, x − x′〉 ≥ β||x − x′||2, Do vậy, từ bất đẳng thức (3.20), ta có ||(h(x, w) − h(x′, w′)||2 6 (1 − 2β α + L2 α2 )||x − x′||2. (3.21) Nếu chọn hệ số α > L 2 2β , thì 1− 2βα + L 2 α2 > 0. Cuối cùng, từ bất đẳng thức (3.21) ta được ||h(x, w) − h(x′, w′)|| 6 √ 1− 2β α + L2 α2 ||x − x′||. Đặt δ := √ 1− 2βα + L 2 α2 , khi đó ||h(x, w) − h(x′, w′)|| 6 δ||x − x′|| ∀x, x′ ∈ C, w ∈ F(x). Do đó ρ(H(x), H(x′)) 6 δ||x − x′|| ∀x, x′ ∈ C. Chú ý rằng nếu α > L 2 2β thì δ ∈ (0, 1). Như vậy, ánh xạ đa trị H là co trên C với hệ số δ.  Chú ý 3.1.5 Kết hợp định nghĩa của ánh xạ H và Định lý 3.1.4, ta nhận thấy nếu F là ánh xạ đơn trị thì ánh xạ nghiệm H là co trên C. Bây giờ, thay giả thiết đơn điệu mạnh của ánh xạ F bởi giả thiết yếu hơn là F đơn điệu. Khi đó, ta có hệ quả trực tiếp sau: Hệ quả 3.1.6 Giả sử F là ánh xạ đơn điệu và Lipschitz với hệ số L > 0, F(x) là một tập lồi, đóng với mỗi x ∈ C. Khi đó, nếu α > 0, thì ánh xạ H có tính chất Lipschitz trên C với hệ số δ := √ L2 + α2 α . 41 3.2. Thuật toán lặp Banach cho bài toán (MVIP) đơn điệu mạnh. Theo Định lý 3.1.4, với giả thiết ánh xạ F là đơn điệu mạnh, ta có thể chọn tham số chính quy α phù hợp sao cho ánh xạ nghiệm H là co trên C. Trong trường hợp này, theo nguyên lý ánh xạ co Banach, được mở rộng bởi Nadler, nghiệm của bài toán MVIP có thể được xấp xỉ bởi quá trình lặp xk+1 ∈ H(xk), k = 0, 1, ... với x0 là một điểm tuỳ ý của C. Theo định nghĩa của ánh xạ H, điểm xk+1 chính là nghiệm duy nhất của quy hoạch toàn phương lồi mạnh. Hiển nhiên, khi F đơn trị, ánh xạ nghiệm H cũng đơn trị và khi đó quá trình lặp được viết dưới dạng đơn giản như sau: x0 ∈ C, xk+1 := H(xk) ∀k = 0, 1, .... Mô tả thuật toán và sự hội tụ Khi thực hiện các thuật toán vô hạn, việc tìm ra một nghiệm tối ưu chính xác là khó thực hiện được. Vì vậy, người ta thường phải lấy nghiệm xấp xỉ với độ chính xác nào đó. Giả sử x∗ là nghiệm chính xác của bài toán MVIP, khi đó x ∈ C được gọi là e- nghiệm của bài toán MVIP nếu ||x − x∗|| 6 e. Thuật toán lặp Banach cho ánh xạ F đơn điệu mạnh trên C được miêu tả chi tiết như sau: Thuật toán 3.2.1 Bước đầu. Chọn sai số e ≥ 0. Chọn tham số chính quy α > L 2 β , khi F là β-đơn điệu mạnh, ở đây L là hệ số Lipschitz của F. Chọn x0 ∈ C, w0 ∈ F(x0). Bước lặp k(k = 0, 1, 2, ...). Giải bài toán quy hoạch lồi mạnh P(xk) : min{1 2 α||x − xk||2 + 〈wk, x − xk〉 | x ∈ C}, thu được nghiệm duy nhất xk+1. Tìm wk+1 ∈ F(xk+1) sao cho ||wk+1 − wk|| 6 L||xk+1 − xk||, 42 chẳng hạn có thể chọn wk+1 := PF(xk+1)(w k) (hình chiếu của wk trên F(xk+1)). Xét hai trường hợp: -Trường hợp 1: Nếu ||xk+1 − xk|| 6 e(1−δ) δk , thì thuật toán dừng: xk là một e- nghiệm của bài toán MVIP. -Trường hợp 2: Nếu ||xk+1 − xk|| > e(1−δ) δk , thì ta thay thế k := k + 1 và chuyển sang Bước lặp k. Theo Định lý 3.1.4, và nguyên lý lặp Banach, ta có mối quan hệ giữa điểm xk và nghiệm chính xác x∗ của bài toán MVIP được xác định bởi công thức sau: ||xk+1 − x∗|| 6 δ k+1 1− δ ||x 0 − x1|| ∀k, ở đây 0 < δ < 1 là hệ số co của ánh xạ nghiệm H. Theo Định lý 3.1.4 δ = √ 1− 2β α + L2 α2 , khi F là β-đơn điệu mạnh. Định lý 3.2.2 Dưới giả thiết của Định lý 3.1.4, dãy {xk} được xây dựng bởi Thuật toán 3.2.1 thoả mãn ||xk+1 − x∗|| 6 δ k+1 1 − δ ||x 0 − x1|| ∀k, (3.22) ở đây x∗ là nghiệm chính xác của bài toán MVIP. Nếu ta thêm giả thiết ánh xạ F là đóng trên C, thì dãy {wk} hội tụ tới w∗ ∈ F(x∗) với tốc độ hội tụ ||wk − w∗|| 6 Lδ k 1− δ ||x 0 − x1|| ∀k. Chứng minh. Trước hết, ta giả sử các giả thiết của Định lý 3.1.4 được thoả mãn. Theo Bổ đề 3.1.1, ta có x∗ ∈ H(x∗) := {h(x∗, w) | w ∈ F(x∗)}. Lấy w∗ ∈ F(x∗) sao cho x∗ = h(x∗, w∗) ∈ H(x∗). Theo cách xây dựng wk+1 của Thuật toán 3.2.1, ta được ||wk+1 − wk|| 6 L||xk+1 − xk|| ∀k = 0, 1, ... 43 Khi đó theo Định lý 3.1.4 ta nhận được ||h(xk+1, wk+1)− h(xk, wk)|| 6 δ||xk+1 − xk|| ∀k = 0, 1, ... Từ h(xk+1, wk+1) = xk+2 suy ra ||xk+2 − xk+1|| 6 δ||xk+1 − xk|| ∀k = 0, 1, ... Theo nguyên lý ánh xạ co Banach, ta có ||xk − x∗|| 6 δ k+1 1− δ ||x 0 − x1|| ∀k = 0, 1, ... Như vậy, xk → x∗ khi k → +∞. Hơn nữa, sử dụng tính chất co của ánh xạ nghiệm H, ta đạt được ||xp+k − xk|| 6 δ k(1 − δp) 1− δ ||x k+1 − xk|| ∀k, p. Cho p → +∞, ta được ||xk − x∗|| 6 δ k 1− δ ||x k+1 − xk|| ∀k = 0, 1, ... Nếu Trường hợp 1 của Thuật toán 3.2.1 xảy ra ||xk+1 − xk|| 6 e(1 − δ) δk và do đó ||xk − x∗|| 6 e. Điều đó có nghĩa là xk là một e-nghiệm của bài toán MVIP. Mặt khác, từ ||wk+1 − wk|| 6 L||xk+1 − xk|| suy ra ||wk+p − wj|| 6 ||wk+1 − wk||+ ||wk+2 − wk+1||+ ... + ||wk+p − wk+p−1|| 6 L (||xk+1 − xk||+ ||xk+2 − xk+1||+ ... + ||xk+p − xk+p−1||) 6 L ( δk + δk+1 + ... + δk+p−1 )||x1 − x0||. Do vậy ||wk+p − wk|| 6 Lδ k(δp − 1) δ − 1 ||x 1 − x0||. (3.23) 44 Điều này chỉ ra rằng {wk} là dãy Cauchy trong không gian Rn. Do đó, dãy {wk} hội tụ tới w∗ ∈ C. Do F là ánh xạ đóng trên C nên w∗ ∈ F(x∗). Trong đẳng thức (3.23), ta cho p → +∞ và nhận được ||wk − w∗|| 6 Lδ k 1− δ ||x 1 − x0|| ∀j.  Chú ý 3.2.3 • Theo Định lý 3.1.4, δ := √ 1 − 2βα + L 2 α2 ta thấy rằng hệ số co δ là một hàm theo tham số chính quy hoá α. Tính toán thông thường đã chỉ ra rằng δ nhỏ nhất khi chọn tham số α = L 2 β . Do vậy, Thuật toán 3.2.1 hội tụ tốt nhất khi ta chọn tham số α = L 2 β . • Trong Thuật toán 3.2.1, tại Bước lặp k, thuật toán này đòi hỏi phải tìm wk+1 ∈ F(xk+1) sao cho ||wk+1 − wk|| 6 L||xk+1 − xk||. Việc tính toán này là dễ dàng khi với mỗi x ∈ C, F(x) có một cấu trúc đặc biệt như không gian con, hình hộp, hình cầu, đơn hình. • Ta áp dụng Thuật toán 3.2.1 cho bài toán VI, ở đây F là ánh xạ đơn trị. Khi đó, bài toán phụ của thuật toán này là tìm hình chiếu của một điểm trên tập C. Trong trường hợp này, ta thu lại được các thuật toán đã có. Cụ thể, thuật toán được trình bày như sau. Thuật toán 3.2.4 Bước đầu. Chọn sai số e ≥ 0. Chọn tham số chính quy α > L 2 2β , khi F là β-đơn điệu mạnh, ở đây L là hệ số Lipschitz của ánh xạ đơn trị F. Chọn x0 ∈ C, w0 ∈ F(x0). Bước lặp k(k = 0, 1, 2, ...) Giải bài toán quy hoạch toàn phương lồi mạnh P(xk) : min{1 2 α||x − xk||2 + 〈F(xk), x − xk〉 | x ∈ C}, thu được nghiệm duy nhất xk+1. Xét hai trường hợp: -Trường hợp 1: Nếu ||xk+1 − xk|| 6 e(1−δ) δk , thì thuật toán dừng: xk là một e- nghiệm của bài toán VI. -Trường hợp 2: Nếu ||xk+1 − xk|| > e(1−δ) δk , thì ta thay thế k := k + 1 và chuyển sang Bước lặp k. 45 Như vậy, trong chương này ta đã dùng cách tiếp cận điểm bất động cho bài toán bất đẳng thức biến phân đa trị với ánh xạ giá là đơn điệu mạnh. Ta đã chứng tỏ rằng việc tìm nghiệm của bài toán MVIP được qui về tìm điểm bất động của một ánh xạ đa trị H. Bằng cách sử dụng kỹ thuật điều chỉnh, ta đã chứng tỏ rằng ánh xạ nghiệm H có tính chất co (theo khoảng cách Hausdorff). Cụ thể, khi ánh xạ giá là đơn điệu mạnh, tính chất co này cho phép ta xây dựng một thuật toán lặp theo kiểu nguyên lý ánh xạ co Banach để giải bài toán MVIP. Cách tiếp cận này cho phép thiết lập dễ dàng tốc độ hội tụ của phương pháp lặp. 46 CHƯƠNG4 Phương pháp lặp Banach giải bài toán (MVIP) đồng bức Trong chương này, ta xét bài toán MVIP với giả thiết F là ánh xạ đồng bức trên C. Trong trường hợp này, bài toán MVIP có thể không duy nhất nghiệm. Chúng ta sẽ chỉ ra cách chọn tham số chính quy hoá α sao cho ánh xạ nghiệm H là không giãn trên C. Trên cơ sở đó xây dựng thuật toán giải bài toán MVIP với F là ánh xạ đồng bức. 4.1. Tính không giãn của ánh xạ nghiệm Định lý 4.1.1 Giả sử rằng ánh xạ F là đồng bức với hệ số γ > 0 trên C, tập F(x) là lồi, đóng với mỗi x ∈ C. Khi đó, nếu α ≥ 12γ thì ánh xạ nghiệm H là không giãn trên C. Chứng minh. Bằng cách suy luận tương tự như trong chứng minh của Định lý 3.1.4, ta có ||h(x, w) − h(x′, w′)||2 6 ||x − x′ − 1 α (w − w′)||2 ∀x, (4.1) ∀x′ ∈ C, w ∈ F(x), w′ ∈ F(x′). Từ tính đồng bức của F trên C với hệ số γ suy ra γρ2(F(x), F(x′)) 6 〈x − x′, w − w′〉 ∀x, x′ ∈ C, w ∈ F(x), w′ ∈ F(x′). 47 Vậy, ||x − x′ − 1 α (w − w′)||2 =||x − x′||2 − 2 α 〈x − x′, w − w′〉+ 1 α2 ||w − w′||2 6||x − x′||2 − 2γ α ρ2(F(x), F(x′)) + 1 α2 ||w − w′||2 ∀x, x′ ∈ C, w ∈ F(x), w′ ∈ F(x′). Mặt khác, với mọi x, x′ ∈ C, w(x) ∈ F(x), tồn tại w(x′) = PF(x′)(w(x)) sao cho ρ(F(x), F(x′)) ≥ ||w(x) − w(x′)||. Do vậy, ||x − x′ − 1 α (w(x) − w(x′))||2 6||x − x′||2 − 2γ α ||w(x) − w(x′)||2 + 1 α2 ||w(x)− w(x′)||2 6||x − x′||2 − (2γ α − 1 α2 )||w(x) − w(x′)||2. Từ α ≥ 12γ suy ra ||x − x′ − 1 α (w(x) − w(x′))||2 6 ||x − x′||2 ∀x, x′ ∈ C, w(x) ∈ F(x). (4.2) Kết hợp (4.1) và (4.2), ta nhận được ||h(x, w(x)) − h(x′, w(x′))|| 6 ||x − x′|| ∀x, x′ ∈ C, w(x) ∈ F(x). Do đó, ρ(H(x), H(x′)) 6 ||x − x′|| ∀x, x′ ∈ C.  Như vậy, tuy rằng bài toán MVIP có thể không duy nhất nghiệm trong trường hợp ánh xạ F là đồng bức, nhưng Định lý 4.1.1 chỉ ra rằng ta có thể tìm được một nghiệm của bài toán này thông qua việc tìm điểm bất động của ánh xạ không giãn H. Để tìm điểm bất động của ánh xạ H, ta sẽ sử dụng định lý sau. Định lý 4.1.2 Cho C ⊂ Rn là một tập lồi, compact, khác rỗng và S : Rn → 2Rn. Giả sử rằng S là ánh xạ đóng, dom S ⊇ C và không giãn trên C. Với mỗi λ ∈ (0, 1), ta đặt Sλ := (1 − λ)I + λS. 48 Khi đó, các dãy {xk}, {yk} được xác định bởi xk+1 := (1 − λ)xk + λyk, yk ∈ S(xk), ||yk+1 − yk|| 6 ||xk+1 − xk|| ∀k = 0, 1, 2, ... sẽ thoả mãn ||xk − yk|| → 0 khi k → +∞. Hơn nữa, bất kỳ một điểm tụ nào của dãy {xk} đều là điểm bất động của ánh xạ S. Để chứng minh định lý này, ta cần tới bổ đề sau: Bổ đề 4.1.3 Dưới giả thiết của Định lý 4.1.2, với mọi i, m = 0, 1, ..., ta có ||yi+m − xi|| ≥ (1 − λ)−m[||yi+m − xi+m|| − ||yi − xi||] + (1 + λm)||yi − xi||. (4.3) Chứng minh của Bổ đề 4.1.3. Ta sẽ chứng minh bằng quy nạp toán học theo m. Với m = 0, thì (4.3) hiển nhiên đúng với mọi i. Giả sử (4.3) đúng với m và với mọi i. Thay thế i bởi i + 1 trong (4.3), suy ra ||yi+m+1 − xi+1|| ≥(1 − λ)−m[||yi+m+1 − xi+m+1|| − ||yi+1 − xi+1||] + (1 + λm)||yi+1 − xi+1||. (4.4) Từ xk+1 := (1 − λ)xk + λyk với yk ∈ S(xk) với mọi k = 0, 1, ... suy ra ||yi+m+1 − xi+1|| = ||yi+m+1 − [(1 − λ)xi + λyi]|| 6 λ||yi+m+1 − yi||+ (1 − λ)||yi+m+1 − xi|| 6 (1 − λ)||yi+m+1 − xi||+ λ m ∑ k=0 ||xi+k+1 − xi+k||. (4.5) Kết hợp (4.4) và (4.5), ta nhận được ||yi+m+1 − xi|| ≥(1 − λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi+1 − xi+1||] + (1 − λ)−1(1 + λm)||yi+1 − xi+1|| − λ(1 − λ)−1 m ∑ k=0 ||xi+k+1 − xi+k||. 49 Do ||xi+k+1 − xi+k|| = λ||yk+i − xk+i||, nên dãy {||ym − xm||} là giảm vì λ||ym − xm|| = ||xm+1 − xm|| = ||(1 − λ)xm + λym − [(1 − λ)xm−1 − λym−1]|| 6 (1 − λ)||xm − xm−1||+ λ||ym − ym−1|| 6 ||xm − xm−1|| = λ||ym−1 − xm−1||. Suy ra ||yi+m+1 − xi|| ≥(1 − λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi+1 − xi+1||] + (1 − λ)−1(1 + λm)||yi+1 − xi+1|| − λ2(1 − λ)−1(m + 1)||yi − xi|| =(1 − λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi − xi||] + [(1 − λ)−1(1 + λm)− (1 − λ)−(m+1)]||yi+1 − xi+1|| + [(1 − λ)−(m+1) − λ2(1 − λ)−1(m + 1)]||yi − xi|| ≥(1 − λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi − xi||] + [(1 − λ)−1(1 + λm)− (1 − λ)−(m+1)]||yi − xi|| + [(1 − λ)−(m+1) − λ2(1 − λ)−1(m + 1)]||yi − xi|| =(1 − λ)−(m+1)[||yi+m+1 − xi+m+1|| − ||yi − xi||] + [1 + λ(m + 1)]||yi − xi||. Như vậy, bất đẳng thức (4.3) đúng với m + 1. Theo quy nạp toán học, Bổ đề 4.1.3 được chứng minh.  Chứng minh của Định lý 4.1.2. Đặt d := sup{diam S(x) | x ∈ C}. Từ tính bị chặn của C và S : C → 2C là ánh xạ không giãn, suy ra d < +∞. Ta chứng minh bằng phản chứng. Giả sử rằng lim m→∞ ||y m − xm|| = r > 0. Chọn m ≥ drλ và e là một số dương đủ nhỏ sao cho e(1 − λ)−m < r. 50 Từ dãy {||ym − xm||} giảm, suy ra tồn tại một số tự nhiên i sao cho 0 6 ||yi − xi|| − ||ym+i − xm+i|| 6 e. Bổ đề 4.1.3 và bất đẳng thức 1 + mλ(1 − λ)−mdẫn đến sự mâu thuẫn sau d + r 6 (1 + mλ)r 6 (1 + mλ)||yi − xi|| 6 ||ym+i − xi||+ (1− λ)−m[||yi − xi|| − ||ym+i − xm+i||] 6 ||ym+i − xi||+ (1− λ)−me < d + r. Do vậy, r = 0, cụ thể hơn là lim m→∞ ||x m − ym|| = 0. (4.6) Do xk ∈ C với mọi k và C compact, nên tồn tại một dãy con xkj hội tụ tới x∗. Khi đó, do (4.6) nên ykj ∈ S(xkj) cũng hội tụ tới x∗. Từ S là ánh xạ đóng, suy ra x∗ ∈ S(x∗). Như vậy, mọi điểm tụ của dãy {xk} đều là điểm bất động của ánh xạ S.  4.2. Mô tả thuật toán và sự hội tụ Bây giờ, áp dụng Định lý 4.1.1 cho ánh xạ không giãn H, ta có thể tìm một nghiệm của bài toán MVIP với F là ánh xạ đồng bức với hệ số γ trên C bằng cách tìm điểm bất động của ánh xạ H. Như trên đã thấy, nếu xk lại chính là nghiệm của bài toán P(xk), thì xk là nghiệm của bài toán MVIP. Do đó, trong thuật toán dưới đây, nếu yk là nghiệm của bài toán P(xk) và ||xk − yk|| 6 e thì ta có thể coi yk là một e-nghiệm của bài toán MVIP và dừng thuật toán. Thuật toán cụ thể được trình bày như sau. Thuật toán 4.2.1 Bước 0. Chọn sai số e ≥ 0 và λ ∈ (0, 1), α ≥ 12γ và tìm x0 ∈ C, w0 ∈ F(x0). Đặt k = 0. Bước 1. Giải bài toán quy hoạch lồi mạnh P(xk) : min{1 2 α||y − xk||2 + 〈wk, y − xk〉 | y ∈ C} 51 để được nghiệm duy nhất yk. Nếu ||yk − xk|| 6 e, thì dừng thuật toán. Ngược lại chuyển sang Bước 2. Bước 2. Lấy xk+1 := (1 − λ)xk + λyk. Tìm wk+1 := PF(xk+1)(w k). Gán k := k + 1 và trở lại Bước 1. Định lý 4.2.2 Ngoài các giả thiết của Định lý 4.1.1, ta giả sử thêm rằng C là tập compact. Khi đó, nếu Thuật toán 4.2.1 không dừng, thì dãy {xk} bị chặn và mọi điểm tụ của nó đều là nghiệm của bài toán MVIP. Hơn nữa, d(xk, H(xk)) → 0 khi k → ∞. Chứng minh. Trong Thuật toán 4.2.1, ta có wk+1 := PF(xk+1)(w k) với wk ∈ F(xk). Từ Bổ đề 3.1.1 và định nghĩa của ρ(F(xk), F(xk+1)) suy ra ||wk+1 − wk|| 6 ρ(F(xk), F(xk+1)). Theo tính chất đồng bức của F trên C với hệ số γ, ta có γρ2(F(xk), F(xk+1)) 6 〈xk − xk+1, wk − wk+1〉. Do đó, ||xk − xk+1 − 1 α (wk − wk+1)||2 =||xk − xk+1||2 − 2 α 〈xk − xk+1, wk − wk+1〉 + 1 α2 ||wk − wk+1||2 6||xk − xk+1||2 − 2γ α ||wk − wk+1||2 + 1 α2 ||wk − wk+1||2 =||xk − xk+1||2 − (2γ α − 1 α2 )||wk − wk+1||2. Vì α > 12γ , ta có ||xk − xk+1 − 1 α (wk − wk+1)||2 6 ||xk − xk+1||2. Kết hợp điều này với tính chất không giãn của ánh xạ nghiệm H, ta được ||yk+1 − yk|| 6 ||xk+1 − xk||, 52 trong đó yk = h(xk, wk) ∈ H(xk), yk+1 = h(xk+1, wk+1) ∈ H(xk+1). Từ điều kiện bức của F với hệ số β > 0 hay với mọi x, x′ ∈ C, w ∈ F(x), tồn tại w′ ∈ F(x′) sao cho 〈w − w′, x − x′〉 ≥ β||w − w′||2, suy ra ||w − w′|| 6 1 β ||x − x′||. Do đó, F là đóng trên C. Từ các giả thiết C là tập compact, F là đóng, suy ra ánh xạ nghiệm H(x) := {h(x, w) | w ∈ F(x)}, với h(x, w) là nghiệm của bài toán quy hoạch lồi mạnh min{1 2 α||z − x||2 + 〈w, z − x〉 |z ∈ C} là đóng trên C. Theo Định lý 4.1.2, mọi điểm tụ x∗ của dãy {xk} là điểm bất động của ánh xạ nghiệm H và cũng là nghiệm của bài toán MVIP. Hơn nữa, kết hợp các giả thiết C là tập compact, F là nửa liên tục trên trên C và wk ∈ F(xk) với mọi k, ta có F(C) là compact. Như vậy, không mất tính tổng quát, ta có thể coi wk hội tụ tới w∗. Do F đóng tại x∗, nên w∗ ∈ F(x∗). Trong Thuật toán 4.2.1, ta luôn có yk ∈ H(xk), do vậy d(xk, H(xk)) 6 ||xk − yk|| ∀k = 0, 1, ... Theo Định lý 4.1.2, ||xk − yk|| → 0 khi k → ∞, nên d(xk, H(xk)) → 0 khi k → ∞.  Như vậy, cũng bằng cách sử dụng phương pháp lặp Banach, nhưng khi giảm nhẹ điều kiện đơn điệu mạnh bằng điều kiện đồng bức, ta đã chỉ ra rằng ánh xạ nghiệm H có tính chất không giãn. Tính chất này cho phép ta bổ sung phương pháp lặp theo nguyên lý ánh xạ co Banach để thu được một phương pháp giải cho bài toán MVIP. 53 Kết luận Các kết quả chính của luận văn: Trình bày về ánh xạ đa trị đơn điệu, đặc biệt là tính chất đơn điệu liên quan đến dưới vi phân của một hàm lồi. Phát biểu bài toán bất đẳng thức biến phân đa trị (MVIP), đề cập đến hai trường hợp riêng điển hình là bài toán quy hoạch lồi và bài toán bù. Đưa ra ví dụ thực tế liên quan đến bài toán MVIP là bài toán cân bằng mạng giao thông và bài toán kinh tế bán độc quyền. Đặc biệt, luận văn đã nêu lên được điều kiện để bài toán MVIP có nghiệm cũng như tính chất của tập nghiệm (có duy nhất nghiệm hay có nhiều nhất một nghiệm). Phần trọng tâm của luận văn này là trình bày phương pháp lặp Banach để giải bài toán MVIP. Ta đã chứng tỏ rằng việc tìm nghiệm của bài toán MVIP được qui về tìm điểm bất động của một ánh xạ nghiệm đa trị H. Bằng cách sử dụng kỹ thuật hiệu chỉnh, ta đã chỉ ra rằng ánh xạ nghiệm H có tính chất co (theo khoảng cách Hausdorff). Cụ thể, khi ánh xạ giá là đơn điệu mạnh, tính chất co này cho phép ta xây dựng một thuật toán lặp theo kiểu nguyên lý ánh xạ co Banach để giải bài toán MVIP. Khi ánh xạ giá là đồng bức, ánh xạ đa trị H có tính chất không giãn. Tính chất này cũng giúp ta xây dựng được một thuật toán tìm nghiệm cho bài toán MVIP, hơn nữa, ta còn đánh giá được sự hội tụ của thuật toán này. Do vấn đề được đề cập trong luận văn là tương đối mới và phức tạp và thời gian cũng như khả năng còn hạn chế nên luận văn không tránh khỏi những thiếu xót. Tác giả mong muốn nhận được những ý kiến đóng góp quý báu của các thầy cô giáo, các bạn đồng nghiệp và những người quan tâm để đề tài được hoàn thiện hơn. 54 Tài liệu tham khảo [1] Nguyễn Văn Hiền, Lê Dũng Mưu (2003), Nhập môn Giải tích lồi và ứng dụng, Viện Toán học, Hà Nội. [2] Hoàng Tụy (2003), Hàm thực và giải tích hàm, Viện Toán học, Hà Nội. [3] P. N. Anh, L. D. Muu, V. H. Nguyen and J. J. Strodiot (2005), "Using the Banach contraction principle to implement the proximal point method for multivalued monotone variational inequalities", J. Optim. Theory Appl, 124 , pp. 285- 306. [4] P. N. Anh (2009), "An interior proximal method for solving pseudomonotone nonlipschitzian multivalued variational inequalities", Nonlinear Analysis Forum, 4, pp. 1-16. [5] F. Facchinei and J. S. Pang (2003), Finite-Dimensional Variational Inequal- ities and Complementary Problems, Springer-Verlag, New York. [6] I. V. Konnov (2001), Combined Relaxation Methods for Variational Inequali- ties, Lecture Notes in Economics and Mathematical Systems, 495, Springer, Berlin. [7] M. Patriksson (1997), "Merit function and descent algorithms for a class of variational inequality problems", Optimization, 41, pp. 37-55. [8] R. T. Rockafellar (1999), Variational Analysis, Springer, Berlin. [9] K. Taji and M. Fukushima (1996), "A new merit funtion and a succes- sive quadratic programming algorithm for variational inequality problem", SIAM Jounal on Optimization, 6, pp. 704-713. 55