Luận văn Bài toán cân bằng với song hàm giả đơn điệu mạnh

hợp tác v.v... 1.1.1 Bài toán tối ưu Xét bài toánmin {ϕ (x) : x ∈ C}. Đặt f (x, y) = ϕ (y)− ϕ (x). Khi đó ϕ (x) ≤ ϕ(y), ∀y ∈ C⇔ f(x, y) ≥ 0, ∀y ∈ C Vậy bài toán tối ưu trên là một trường hợp riêng của bài toán (EP ). 1.1.2 Bài toán điểm bất động Brouwer Giả sử C ⊂ H là một tập lồi compact khác rỗng và ánh xạ đơn trị F : C → C. Khi đó bài toán điểm bất động có dạng sau: Tìm x∗ ∈ C sao cho x∗ = F (x∗). (FP) Đặt f (x, y) = 〈x− F (x), y − x〉 , ∀x, y ∈ C. Khi đó bài toán (FP ) trở thành bài toán cân bằng (EP ). 4Tổng quát hơn, bài toán điểm bất động của ánh xạ đa trị (MFP ) là bài toán: Tìm x∗ ∈ C sao cho x∗ ∈ F (x∗), với F : C → 2C là ánh xạ đa trị có giá trị lồi compact khác rỗng. Khi đó, x∗ ∈ C là nghiệm của bài toán (MFP ) khi và chỉ khi x∗ là nghiệm của bài toán cân bằng (EP ). 1.1.3 Bài toán bất đẳng thức biến phân tổng quát Cho T : C → 2Rn là ánh xạ nửa liên tục sao cho T (x) là tập compact, lồi ∀x ∈ C. Khi đó, bài toán bất đẳng thức biến phân tổng quát được phát biểu như sau: Tìm x∗ ∈ C, ξ∗ ∈ T (x) sao cho 〈ξ∗, y − x〉 ≥ 0, ∀y ∈ C. (1.1) Nếu ta đặt f (x, y) := max ξ∈T (x) 〈ξ, y − x〉 , ∀x, y ∈ C thì bài toán cân bằng (EP ) tương đương với bài toán bất đẳng thức biến phân tổng quát. Thật vậy, vì x∗ ∈ C là nghiệm của bài toán (1.1) nên ta có: 〈ξ∗, y − x∗〉 ≥ 0, ∀y ∈ C, ξ∗ ∈ T (x∗). Mặt khác theo cách đặt ta được: f (x∗, y) = max ξ∗∈T (x∗) 〈ξ∗, y − x∗〉 ≥ 0, ∀y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (EP ). Ngược lại, cho x∗ ∈ C là nghiệm của bài toán (EP ), nghĩa là 5f (x∗, y) ≥ 0, ∀y ∈ C. Theo cách đặt ta có: f (x∗, y) = max ξ∗∈T (x∗) 〈ξ∗, y − x∗〉 ≥ 0, ∀y ∈ C. Vậy x∗ ∈ C là nghiệm của bài toán (1.1). Nếu T là ánh xạ đơn trị thì bài toán bất đẳng thức biến phân tổng quát là bài toán bất đẳng thức biến phân sau: Tìm x∗ ∈ C sao cho 〈T (x∗) , y − x∗〉 ≥ 0, ∀y ∈ C. (1.2) Nếu ta đặt f(x, y) := 〈T (x), y − x〉 , ∀x, y ∈ C thì với cách lập luận tương như trên bài toán (1.2) tương đương với bài toán cân bằng (EP ). 1.1.4 Bài toán cân bằng Nash (i) Cho I = {1, 2, ..., p} là tập chỉ số hữu hạn (tập p-người chơi); (ii)Ki là tập lồi khác rỗng của Rni (tập chiến lược của người chơi thứ i); (iii) Hàm fi : K1 × ....×Kp → R cho trước (hàm tổn thất của người chơi thứ i khi vi phạm, chiến lược của người chơi ∀i ∈ I). Cho x = (x1, x2, ..., xp) ∈ K1 × .... ×Kp và y = (y1, y2, ..., yp) ∈ K1 × ....×Kp. Ta định nghĩa vectơ x [yi] ∈ K1 × ....×Kp như sau: x [yi]j = xj ∀j 6= iyj ∀j = i đặtK = K1 × ....×Kp. Khi đó, bài toán cân bằng Nash được phát biểu như sau: Tìm x∗ ∈ K sao cho fi (x∗) ≤ fi (x∗ [yj]) , ∀i ∈ I, ∀y ∈ K (1.3) 6Điểm thỏa mãn (1.3) gọi là điểm cân bằng Nash. Về ý nghĩa kinh tế, điểm cân bằng Nash nói lên rằng bất kỳ đối thủ nào chọn phương án ra khỏi điểm cân bằng trong khi các đối thủ còn lại vẫn giữ phương án điểm cân bằng thì đối thủ ra khỏi điểm cân bằng sẽ bị thua thiệt. Nếu ta đặt f : K ×K → R là hàm số xác định bởi f (x, y) := p∑ i=1 (fi (x [yi])− fi (x)) với mọi ∀x, y ∈ K, thì bài toán cân bằng Nash (1.3) tương đương với bài toán cân bằng (EP). Thật vậy, giả sử x∗ ∈ K là nghiệm của bài toán cân bằng (1.3), khi đó fi (x ∗) ≤ fi (x∗ [yi]) , ∀i ∈ I, ∀yi ∈ Ki ⇔ fi (x∗ [yi])−fi (x∗) ≥ 0, ∀i ∈ I, ∀yi ∈ Ki ⇔ p∑ i=1 (fi (x ∗ [yi])−fi (x∗)) ≥ 0, ∀y ∈ K. Theo định nghĩa của f , ta có f (x∗, y) ≥ 0, ∀y ∈ K. Vậy x∗ ∈ K là nghiệm của (EP) Ngược lại, giả sử x∗ ∈ K là nghiệm của (EP) nhưng không là nghiệm của (1.3). Khi đó, ta có: f (x∗, y) ≥ 0, ∀y ∈ K. Theo định nghĩa của f , ta có: n∑ i=1 (fi (x ∗ [yi])−fi (x∗)) ≥ 0, ∀y ∈ K. Vì x∗ ∈ K không là nghiệm của (1.3), nên tồn tại i0 ∈ I sao cho 7fi0 (x ∗) > fi0 (x ∗ [yi]) , ∀yi ∈ Ki. Lấy x∗ [yi] = x∗, ∀j 6= i0, ta có fi0 (x ∗) = fi0 (x ∗ [yi]) , ∀j 6= i0. Kết hợp với hai điều kiện trên ta suy ra rằng n∑ i=1 (fi (x ∗ [yi])−fi (x∗)) < 0, ∀y ∈ K. Điều này mâu thuẫn với giả thiết. Vậy x∗ ∈ K là nghiệm của bài toán (1.3). 1.2 Định nghĩa về tính đơn điệu, giả đơn điệu mạnh của song hàm Ta ký hiệu PC - toán tử chiếu theo chuẩn lên tập C lồi đóng, tức là: PC (x) ∈ C : ‖x− PC(x)‖ ≤ ‖x− y‖ , ∀y ∈ C. Bổ đề 1.1. Giả sử C là một tập lồi đóng khác rỗng trongH. (i) PC (x) là duy nhất và được xác định với mọi x; (ii) pi=PC (x) khi và chỉ khi 〈x− pi, y − pi〉 ≤ 0, ∀y ∈ C; (iii) ‖PC (x)− PC (y)‖2 ≤ ‖x− y‖2 − ‖PC(x)− x+ y − PC(y)‖2 , ∀x, y ∈ C. Định nghĩa 1.1. Một song hàm f : C × C → R được gọi là (i) Đơn điệu mạnh trên C với hệ số β > 0 nếu f (x, y) + f (y, x) ≤ −β‖y − x‖2, ∀x, y ∈ C; (ii) Đơn điệu trên C nếu 8f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; (iii) Giả đơn điệu mạnh trên C với hệ số β > 0 nếu f (x, y) ≥ 0⇒ f (y, x) ≤ −β‖y − x‖2, ∀x, y ∈ C; (iv) Giả đơn điệu trên C nếu f(x, y) ≥ 0⇒ f(y, x) ≤ 0, ∀x, y ∈ C. Chú ý rằng một song hàm giả đơn điệu mạnh có thể không đơn điệu Từ định nghĩa cho thấy (i) ⇒ (ii) ⇒ (iv) và (i) ⇒ (iii) ⇒ (iv) nhưng không có sự liên hệ giữa (ii) và (iii). Ngoài ra, nếu f là đơn điệu mạnh (tương ứng giả đơn điệu) với hệ số β > 0, thì nó là đơn điệu mạnh (tương ứng giả đơn điệu) với hệ số β′ cho mọi 0 < β′ ≤ β Sau đây là một ví dụ cho song hàm giả đơn điệu mạnh. Giả sử f (x, y) := (R− ‖x‖) g (x, y) ,Br := {x ∈ H : ‖x‖ ≤ r} , khi g là một đơn điệu mạnh trên Br với hệ số β > 0, ví dụ g (x, y) = 〈x, y − x〉 , và R > r > 0. Ta thấy rằng f là giả đơn điệu mạnh trên Br. Thực vậy, giả sử rằng f (x, y) ≥ 0, từ x ∈ Br ta có g (x, y) ≥ 0. Với hàm g, β - đơn điệu mạnh trên Br, g (x, y) ≤ −β‖x− y‖2, ∀x, y ∈ Cr. Từ định nghĩa của f và y ∈ Br kéo theo f (y, x) = (R− ‖y‖) g (y, x) ≤ −β (R− ‖y‖) ‖x− y‖2 ≤ −β (R− r) ‖x− y‖2. Vì vậy f là đơn điệu mạnh trên Br với hệ số β (R− r) . Giả thiết sau đây sẽ được sử dụng cho song hàm f : C × C → R (A1) f(., y) là nửa liên tục trên C cho mỗi y ∈ C; 9(A2) f(x, .) là đóng, lồi và dưới khả vi trên C cho mỗi x ∈ C; (A2a) f(x, .) là đóng, lồi trên C cho mỗi x ∈ C. Điều kiện kiểu Lipschitz sau đây sẽ được sử dụng ở phần tiếp theo. ∃L1, L2 : f(x, y) + f(y, z) ≥ f(x, z)− L1‖x− y‖2− − L2‖y − z‖2, ∀x, y, z ∈ C. (1.4) Rõ ràng với bài toán cực tiểu minx∈cϕ(x), song hàm f (x, y) := ϕ (y) − ϕ (x) có tính chất (1.4) với hàm ϕ bất kỳ được định nghĩa trên C. Với F : C → H, cho bất đẳng thức biến phân f (x, y) := 〈F (x) , y − x〉 nếu F là Lipschitz trên C với hằng số L > 0, thì cho một số bất kỳ µ > 0 ta có f (x, y) + f (y, z) ≥ f (x, z)− Lµ2 ‖x− y‖2− L2µ‖y − z‖2, ∀x, y, z ∈ C, f thỏa mãn điều kiện Lipschitz với L1 = Lµ 2 và L2 = L 2µ . 1.3 Sự tồn tại nghiệm của bài toán cân bằng Bổ đề 1.2. Giả sử f : C × C → R ∪ {∞} là một song hàm cân bằng sao cho f (., y) là bán liên tục trên với mỗi y ∈ C và f (x, .) là lồi với mọi x ∈ C. Nếu ít nhất một trong những giả thiết dưới đây thỏa mãn: (i) C là compact; (ii) Tồn tại một tập hợpW compact khác rỗng sao cho mỗi x ∈ C\W có một y ∈ C ∩W với f (x, y) < 0; thì bài toán cân bằng (EP) có một nghiệm. 10 Trong những kết quả dưới đây, chúng ta cần các điều kiện về song hàm f : (A1) với mỗi x ∈ C, y ∈ C, hàm f (x, .) lồi chính thường (không nhất thiết khả dưới vi phân) và hàm f (., y) là nửa liên tục trên C. (A2) f là β - giả đơn điệu mạnh trên C. Kết quả sau đây nói về sự tồn tại nghiệm của bài toán cân bằng giả đơn điệu mạnh. Định lí 1.1. Giả sử rằng f là giả đơn điệu mạnh trên C, khi đó dưới giả thiết (A1), (A2) bài toán (EP ) có một nghiệm duy nhất. Chứng minh. Theo Bổ đề 1.2 ta chỉ cần chứng minh điều kiện bức sau đây: Tồn tại hình cầu đóng B sao cho: (∀x ∈ C\B, ∃y ∈ C ∩B : f(x, y) < 0). (C0) Thực vậy, nếu trái lại, với mọi hình cầu đóng Br bao O với bán kính r, có xr ∈ C\Br sao cho f (x, y) ≥ 0, ∀y ∈ C ∩Br. Cố định r0 > 0, thì với mọi r > r0, có tồn tại xr ∈ C\Br sao cho f ( xr, y0 ) ≥ 0 với y0 ∈ C ∩Br. Do đó, từ f là β - giả đơn điệu mạnh, chúng ta có: f ( y0, xr ) + β ∥∥xr − y0∥∥2 ≤ 0, ∀r (1.5) Mặt khác, do f ( y0, . ) là lồi chính thường, tồn tại x0 ∈ C sao cho ∂2f ( y0, x0 ) 6= φ, tại x0. Lấy w∗ ∈ ∂2f ( y0, x0 ) , theo định nghĩa của dưới vi phân ta có:〈 w∗, x− x0〉+ f (y0, x0) ≤ f (y0, x) , ∀x. 11 Với x = xr ta được: f(y0, xr) + β‖xr − y0‖2 ≥ f(y0, x0) + 〈w∗, xr − x0〉+ β‖xr − y0‖2 ≥ f(y0, x0)− ‖w∗‖‖xr − x0|+ β‖xr − y0‖2. Do r → ∞, từ ‖xr‖ → ∞, ta thu được f (y0, xr) + β∥∥xr − y0∥∥2 → ∞, mâu thuẫn với (1.5). Vì vậy điều kiện bức (C0) phải đúng. Theo Bổ đề 1.2, bài toán (EP ) có nghiệm. Toán tử F : C → H là được gọi là giả đơn điệu mạnh trên C với hệ số β > 0, nếu: 〈F (x) , y − x〉 ≥ 0⇒ 〈F (y) , y − x〉 ≥ β‖y − x‖2, ∀x, y ∈ C. Ta áp dụng định lý trên với bất đẳng thức biến phân Tìm x∗ ∈ C : 〈F (x∗) , y − x∗〉 ≥ 0 , ∀y ∈ C, (VI) Định nghĩa song hàm f theo công thức f(x, y) := 〈F (x), y − x〉 (1.6) Rõ ràng x∗ là một nghiệm của (1.6) khi và chỉ khi nó là một nghiệm của bài toán (EP) với f xác định bởi (1.6). Khi đó f là giả đơn điệu mạnh nếu F là giả đơn điệu mạnh. Thật vậy, giả sử f (x, y) ≥ 0 theo (1.6), ta có 〈F (x) , y − x〉 ≥ 0 nhưng do F là β− đơn điệu mạnh nên 〈F (y) , x− y〉 ≤ −β‖y − x‖2 Theo (1.6) thì f (x, y) = 〈F (y) , x− y〉 . 12 Hệ quả 1.1. Giả sử rằng F là liên tục và giả đơn điệu mạnh trên C. Khi đó bài toán bất đẳng thức biến phân (VI) có một nghiệm duy nhất. 13 Chương 2 Thuật toán chiếu giải bài toán cân bằng giả đơn điệu mạnh Trong chương này chúng ta trình bày thuật toán chiếu cho bài toán cân bằng giả đơn điệu mạnh, đặc biệt là ba thuật toán và tốc độ hội tụ của chúng: Thuật toán 1: Thuật toán tuyến tính hội tụ yêu cầu biết được hệ số Lipschitz của song hàm. Thuật toán 2: Thuật toán không cần biết hằng số Lipschitz. Thuật toán 3: Thuật toán không có điều kiện Lipschitz. Các kiến thức trong chương này chủ yếu được tham khảo ở trong các tài liệu [3], [4], [6], [7]. 2.1 Thuật toán chiếu cho bài toán cân bằng giả đơn điệu mạnh Cho ε ≥ 0, chúng ta gọi một điểm xε ∈ C một ε - nghiệm tới bài toán (EP). Nếu f (xε, y) ≥ −ε cho mọi y ∈ C. Bổ đề sau sẽ được sử dụng trong phần chứng minh của định lý hội tụ dưới đây. Bổ đề 2.1. Giả sử rằng {ak}∞k=0 là một dãy vô hạn các số dương thỏa mãn: ak+1 ≤ ak + ξk ∀k, 14 với ∑∞ k=0 ξk <∞. Khi đó dãy {ak} là hội tụ. Thuật toán Bước 1. (Chọn một điểm xuất phát và độ dài bước). Lấy x1 ∈ C, chọn sai số ε > 0 và một dãy các số dương {σk} sao cho ∞∑ k=1 σk =∞, ∞∑ k=1 σ2k < +∞. (2.1) Bước 2. (Tìm một hướng chuyển động) Tìm gk ∈ H sao cho f ( xk, y ) + 〈 gk, xk − y〉 ≥ −σk, ∀y ∈ C. (2.2) a) Nếu gk = 0 và σk ≤ ε, kết thúc: xk là 1 ε - nghiệm; b) Chuyển qua bước 3. Bước 3. (Phép chiếu) Lấy xk+1 := PC ( xk − σkgk ) và quay trở lại Bước 2 với k được thay bởi k + 1. Định lí 2.1. Giả sử rằng giả thiết (A1) và (A2) là thỏa mãn. Khi đó ta có: (i) Nếu thuật toán kết thúc ở Bước 2, thì xk là một ε - nghiệm và ∥∥xk+1 − x∗∥∥2 ≤ (1− 2βσk) ∥∥xk − x∗∥∥2 + 2σ2k + σ2k∥∥gk∥∥2, ∀k; (2.3) (ii) Nếu thuật toán không kết thúc và { gk } giới nội thì dãy { xk } hội tụ mạnh tới nghiệm duy nhất x∗ của (EP ). Chứng minh. (i) Nếu thuật toán kết thúc ở Bước 2, thì gk = 0 và σk ≤ ε. Khi đó, từ (2.2), f ( xk, y ) ≥ −σk ≥ −ε với ∀y ∈ C. Như vậy, xk là một ε - nghiệm. Từ xk+1 = PC ( xk − σkgk ) , ta có ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − σkgk − x∗∥∥2 15 = ∥∥xk − x∗∥∥2 − 2σk 〈gk, xk − x∗〉+ σ2k∥∥gk∥∥2. (2.4) Áp dụng (2.2) với y = x∗ ta thu được: f ( xk, x∗ ) + 〈 gk, xk − x∗〉 ≥ −σk; điều này kéo theo: − 〈gk, xk − x∗〉 ≤ f (xk, x∗)+ σk. (2.5) Khi đó từ (2.4) ta được:∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 + 2σk (f (xk, x∗)+ σk)+ σ2k∥∥gk∥∥2. (2.6) Do x∗ là nghiệm, f ( xk, x∗ ) ≥ 0, nên theo tính chất β− giả đơn điệu mạnh của f ta có: f ( xk, x∗ ) ≤ −β∥∥xk − x∗∥∥2. Kết hợp bất đẳng thức cuối cùng với (2.6) chúng ta thu được:∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 − 2βσk‖xk − x∗‖2 + 2σ2k + σ2k∥∥gk∥∥2 =(1− 2βσk) ‖xk − x∗‖2+2σ2k + σ2k ∥∥gk∥∥2. (2.7) (ii) Giả sử rằng bây giờ thuật toán không kết thúc và dãy { gk } là bị chặn. Vậy có một số thực c sao cho ∥∥gk∥∥ ≤ c <∞,∀k. Thì (2.7) có thể viết như sau:∥∥xk+1 − x∗∥∥2 ≤ (1− 2βσk) ‖xk − x∗‖2+c0σ2k =‖xk − x∗‖2 − λk‖xk − x∗‖2 + c0σ2k, (2.8) đặt λk := 2βσk, c0 := 2 + c. Từ ∑∞ k=1 σ 2 k < ∞, nên theo Bổ đề 2.1.1, dãy{∥∥xk − x∗∥∥2} hội tụ. Lấy tổng theo bất đẳng thức (2.8) từ 1 tới k + 1 ta được: ∥∥xk+1 − x∗∥∥2 ≤ ∥∥x1 − x∗∥∥2 − k∑ j=2 λj ∥∥xj − x∗∥∥2 + c0 k∑ j=2 σ2j , 16 vậy ∥∥xk+1 − x∗∥∥2 + k∑ j=2 λj ∥∥xj − x∗∥∥2 ≤ ∥∥x1 − x∗∥∥2 + c0 k∑ j=2 σ2j . (2.9) Chú ý rằng dãy {∥∥xj − x∗∥∥2} là hội tụ,∑∞j=1 λj = 2β∑∞j=1 σj =∞ và dãy∑∞ k=0 σ 2 k < ∞ chúng ta có thể suy ra từ (2.9) rằng ∥∥xk − x∗∥∥2 → 0 khi k→∞. Nhận xét (i) Một bài toán phụ trong thuật toán này là tìm một phương chuyển động gk 6= 0 thỏa mãn (2.2). Nếu gk là một σk - dưới đạo hàm của hàm lồi f ( xk, . ) tại xk, thì gk thỏa mãn (3.2). Thực vậy, bằng định nghĩa của σk - dưới đạo hàm ta có: f ( xk, y ) + 〈 gk, xk − y〉 ≥ f (xk, xk)− σk = −σk, ∀y ∈ C. Như vậy (2.2) thỏa mãn, thêm vào đó, nếu f là hữu hạn và liên tục trên C ×C, thì { gk } là bị chặn, khi σk → 0. Chú ý rằng vì f ( xk, . ) lồi với mọi σk > 0, một σk - dưới đạo hàm của hàm f ( xk, . ) , nhưng nó có thể không tồn tại nếu σk = 0 (ii) Cho bất đẳng thức biến phân (VI) với f (x, y) được xác định bởi (2.2). Công thức (2.2) có dạng 〈 F ( xk ) , y − xk〉+ 〈gk, xk − y〉 ≥ −σk, ∀y ∈ C, (2.10) nghĩa là gk − F (xk) ∈ NσkC (xk), khi NσkC (xk) biểu thị (bên ngoài) σk - nón pháp tuyến của C tại xk, đó là: 17 NσkC ( xk ) := { wk : 〈 wk, y − xk〉 ≤ σk, ∀y ∈ C} . Trong một trường hợp thông thường khi C đã cho bởi C := {x ∈ H : g(x) ≤ 0} với g là hàm số lồi khả vi, liên tục, lấy gk = F ( xk ) khi g ( xk ) < 0, và gk có thể vectơ bất kỳ sao cho gk−F (xk) ∈ ∂g (xk) khi g (xk) = 0. TừNC (xk) = {0} nếu g ( xk ) < 0 và NC ( xk ) = ∂g ( xk ) nếu g ( xk ) = 0, trong cả hai trường hợp gk − F (xk) ∈ NC (xk) ⊂ NσkC (xk) cho bất kỳ σk > 0. (iii) Phương gk được định nghĩa theo phương pháp sao cho gk − F (xk) ∈ NσkC ( xk ) không chỉ lấy giá trị toán tử F vào phép tính, nhưng cũng ép buộc tập C. Việc này hữu dụng trong một vài trường hợp nhất định, ví dụ để tránh phép chiếu trênC. Thực vậy, có thể xảy ra rằng f ( xk ) /∈ C. Nhưng gk−F (xk) ∈ C. (iv) Cho thuật toán thực hiện, ta lấy σk := εσ1k, khi σ 1 k thỏa mãn (3.1). 2.2 Các thuật toán và tốc độ hội tụ của chúng 2.2.1 Thuật toán hội tụ tuyến tính Một dãy { zk } hội tụ tuyến tính đến z∗ nếu nó tồn tại một số t ∈ (0, 1) và một chỉ số k0 sao cho ∥∥zk+1 − z∗∥∥ ≤ t ∥∥zk − z∗∥∥ cho mọi k ≥ k0. Mệnh đề 2.1. Giả sử rằng f là giả đơn điệu mạnh trên C với hệ số β. Khi đó dưới các giả thiết (A1), (A2) và điều kiện Lipschitz, với bất kỳ điểm x0 ∈ C, dãy { xk } k≥0 được xác định bởi xk+1 := argmin y∈C { ρf ( xk, y ) + 1 2 ∥∥y − xk∥∥2} (2.11) 18 thỏa mãn [1 + 2ρ (β − L2)] ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 (2.12) với điều kiện là 0 < ρ ≤ 12L1 , trong đó x∗ là nghiệm duy nhất của (EP). Chứng minh. Với mỗi k ≥ 0, để đơn giản ký hiệu, ta đặt fk (x) := ρf ( xk, x ) + 1 2 ∥∥x− xk∥∥2. (2.13) Theo giả thuyết (A2), hàm fk là lồi mạnh với hệ số 1 và khả dưới vi phân, vậy ta được fk ( xk+1 ) + 〈 gk, x− xk+1〉+ 1 2 ∥∥x− xk+1∥∥2 ≤ fk (x) , ∀x ∈ C. (2.14) Với bất kỳ gk ∈ ∂fk ( xk+1 ) . Do xk+1 được định nghĩa bởi (2.11), sử dụng điều kiện tối ưu cho bài toán quy hoạch lồi, sẽ tìm được gk ∈ ∂2fk ( xk, xk+1 ) chúng ta có xk+1, nghĩa là ở đó tồn tại −gk ∈ NC ( xk+1 ) sao cho 〈 gk, x− xk+1〉 ≥ 0, ∀x ∈ C. Do đó, từ (2.14), kéo theo fk ( xk+1 ) + 1 2 ∥∥x− xk+1∥∥2 ≤ fk (x) , ∀x ∈ C. (2.15) Thay thế x = x∗ trong (2.15) và sử dụng định nghĩa (2.13) của fk để có được ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 + 2ρ [f (xk, x∗)− f (xk, xk+1)]− − ∥∥xk+1 − xk∥∥2. (2.16) Áp dụng điều kiện Lipschitz với x = xk, y = xk+1, z = x∗ chúng ta đạt được 19 f ( xk, xk+1 ) +f ( xk+1, x∗ ) ≥ f (xk, x∗)−L1∥∥xk − xk+1∥∥2−L2∥∥xk+1 − x∗∥∥2 ⇒ f (xk, x∗)− f (xk, xk+1) ≤ f (xk+1, x∗)+ L1∥∥xk+1 − xk∥∥2+ + L2 ∥∥xk+1 − x∗∥∥2 (2.17) Vì x∗ là một nghiệm của (EP ), f ( x∗, xk+1 ) ≥ 0. Do f giả đơn điệu mạnh của f , nên f ( xk+1, x∗ ) ≤ −β∥∥xk+1 − x∗∥∥2. (2.18) Từ đây và (2.17), ta có f ( xk, x∗ )− f (xk, xk+1) ≤ −β∥∥xk+1 − x∗∥∥2 + L1∥∥xk − xk+1∥∥2+ + L2 ∥∥xk+1 − x∗∥∥2= − (β − L2) ∥∥xk+1 − x∗∥∥2+L1∥∥xk+1 − xk∥∥2 (2.19) Thay thế (2.19) vào (2.16), chúng ta có thể viết ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 + 2ρ [− (β − L2) ∥∥xk+1 − x∗∥∥2 +L1 ∥∥xk+1 − xk∥∥2]− ∥∥xk+1 − xk∥∥2 ⇔ [1 + 2ρ (β − L2)] ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 − 1− 2ρL1) ∥∥xk+1 − xk∥∥2 ≤ ∥∥xk − x∗∥∥2. Các mệnh đề như trên được chứng minh. Dựa trên Mệnh đề (2.1) chúng ta có thuật toán hội tụ tuyến tính sau đây cho bài toán giả đơn điệu mạnh thỏa mãn điều kiện Lipschitz. Như thường lệ, chúng ta gọi một điểm x ∈ C là một ε - nghiệm tới (EP ) nếu ∥∥xk − x∗∥∥ ≤ ε, trong đó x∗ là nghiệm chính xác của (EP ). 20 Thuật toán 1 Chọn sai số ε ≥ 0 và 0 < ρ < 12L1 . Lấy x0 ∈ C và k = 0. Bước 1: Giải bài toán lồi mạnh min { ρf ( xk, y ) + 12 ∥∥y − xk∥∥2 : x ∈ C} để có được nghiệm duy nhất xk+1 của nó; Bước 2: Nếu α1−α ∥∥xk+1 − xk∥∥ ≤ ε với α := 1√ 1+2ρ(β−L2) thì kết thúc: xk+1 là một ε− nghiệm của (EP ). Trái lại, cho k ← k + 1 và quay lại Bước 1. Với f (x, y) := 〈F (x) , y − x〉 , thì ta nhận được bất đẳng thức biến phân (V I), giải bài toán lồi mạnh ở Bước 1 trở thành chiếu vectơ xk− 1ρF ( xk ) lên C, tức là xk+1 = PC ( xk − 1ρF ( xk )) . Kết quả hội tụ sau đây được suy trực tiếp từ Mệnh đề (2.1) Bổ đề 2.2. Giả sử rằng L2 < β và 0 < ρ ≤ 12L1 . Khi đó dãy { xk } được xây dựng bởi Thuật toán 1 hội tụ tuyến tính tới nghiệm duy nhất x∗ của (EP) và chúng ta có ước lượng ∥∥xk+1 − x∗∥∥ ≤ αk+1 1− α ∥∥x1 − x0∥∥ , ∀k ≥ 0 (2.20) trong đó α := 1√ 1+2ρ(β−L2) ∈ (0, 1). Ví dụ: Xét hàm f (x, y) = 〈F (x) , y − x〉 với F(x)= 1 −1 1 1  x1 x2  và tập C thỏa mãn: C = { (x1, x2) : x 2 1 + x 2 2 ≤ 1 } . Ta nhận thấy f là song hàm đơn điệu mạnh. 21 Thật vậy, ta có: F (x) = 1 −1 1 1  x1 x2  = F1(x) + F2(x), trong đó F1(x) = 1 0 0 1  x1 x2  toán tử này đơn điệu mạnh Toán tử F2(x) = 0 −1 1 0  x1 x2  là đơn điệu, nên F (x) là đơn điệu mạnh, do đó: f(x, y) = 〈F (x), y − x)〉 cũng là đơn điệu mạnh Lấy ε = 110 và ρ = 1 2 . Tính L1. Bước 1: Giải bài toán Lấy x0 = (0, 1) ∈ C, ta có: F ( x0 ) =  1 −1 1 1   0 1  =  −1 1  Suy ra f ( x0, y ) = 〈 F ( x0 ) , y − x0〉 = (−1 1)  y1 y2 − 1  = −y1 + y2 − 1 Khi đó ta giải bài toán dạng: min { 1 2 f ( x0, y ) + 1 2 ∥∥y − x0∥∥2 : y ∈ C} hay min { 1 2 (−y1 + y2 − 1) + 1 2 [ y21 + (y2 − 1)2 ] : y ∈ C } 22 Ta có ∂f ∂y1 ( x0 ) = −1 2 + y1 = 0⇔ y1 = 1 2 ∂f ∂y2 ( x0 ) = 1 2 + y2 = 0⇔ y2 = −1 2 Ta thấy y21 + y 2 2 < 1 nên (y1, y2) là nghiệm của bài toán min { 1 2 (−y1 + y2 − 1) + 12 [ y21 + (y2 − 1)2 ] : y ∈ C } Vậy x1 = ( 1 2 ,−12 )T Trở về Bước 1 với x0 được thay bởi x1 và cứ tiếp tục. Ta sẽ dừng thuật toán ở Bước k nếu ∥∥xk+1 − xk∥∥ ≤ ε Khi đó xk là ε- nghiệm của bài toán. Tính L1: Với A =  1 −1 1 1 , ta có ‖F (x)− F (y)‖ ≤ L1 ‖x− y‖ ⇔ ‖A (x− y)‖ ≤ L1 ‖x− y‖ Do A = 1 0 0 1  0 −1 1 0  nên ta có F (x)− F (y) = x− y + x− y = 2(x− y) = 2 ‖x− y‖ ≤ L1 ‖x− y‖ Vậy L1 ≥ 2 23 2.2.2 Thuật toán không cần biết các hằng số Lipschitz Thuật toán 1 có một nhược điểm là, để xác định các quy tắc, nó yêu cầu phải biết trước hằng số Lipschitz. Thuật toán 2 dưới đây có thể tránh được nhược điểm này. Thuật toán 2 Khởi đầu: Chọn một dung sai ε ≥ 0 và một dãy {ρk}k≥0 ⊂ (0,∞) ccác số dương thỏa mãn ∞∑ k=0 ρk = +∞, lim x→∞ ρk = 0 Lấy x0 ∈ C và k = 0 Bước 1: Giải bài toán lồi mạnh min y∈C { ρkf ( xk, y ) + 1 2 ∥∥y − xk∥∥2} để có được nghiệm duy nhất xk+1. Nếu ∥∥xk+1 − xk∥∥ ≤ ε, thì kết thúc. Trái lại, tăng k bởi 1 đơn vị và quay trở lại Bước 1. Định lí 2.2. Giả sử rằng f giả đơn điệu mạnh trên C với hệ số β thỏa mãn điều kiện Lipschitz với L2 < β. Khi đó tồn tại một chỉ số k0 ∈ N sao cho mỗi k > k0, ta có ∥∥xk+1 − x∗∥∥ ≤ 1√∏k i=k0 [1 + 2ρk (β − L2)] ∥∥xk0 − x∗∥∥ , (2.21) và lim k→∞ 1√∏k i=k0 [1 + 2ρk (β − L2)] = 0, (2.22) do đó { xk } hội tụ mạnh tới x∗. 24 Chứng minh. Sử dụng các lập luận tương tự như chứng minh trên, cho mỗi k chúng ta có [1 + 2ρk (β − L2)] ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 − (1− 2ρkL1) ∥∥xk+1 − xk∥∥2. Vì limk→∞ρk = 0, nên tồn tại k0 ∈ N sao cho 1 − 2ρkL1 > 0, ∀k ≥ k0. Do vậy [1 + 2ρk (β − L2)] ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2, ∀k ≥ k0 hay ∥∥xk+1 − x∗∥∥ ≤ 1√ 1 + 2ρk (β − L2) ∥∥xk − x∗∥∥ , ∀k ≥ k0; vậy ∥∥xk+1 − x∗∥∥ ≤ 1√∏k i=k0 [1 + 2ρk (β − L2)] ∥∥xk − x∗∥∥ . Theo (2.2), chúng ta để αk := 2ρk (β − L2) > 0, thì ∞∑ k=k0 αk = 2 (β − L2) ∞∑ k=k0 ρk = +∞, Nghĩa là 1∏k i=k0 (1 + αi) ≤ 1 1 + ∑k i=k0 αi → 0, khi k →∞. Do đó từ (2.21) chúng ta thấy rằng xk → x∗ khi k → +∞. Ví dụ sau đây cho thấy rằng Thuật toán 2 không hội tụ tuyến tính. Xét C = H = R và f (x, y) = x (y − x) . Rõ ràng, f (x, y) là đơn điệu mạnh với hệ số 1 trên C và thỏa mãn loại điều kiện Lipschitz với L1 = L2 = 12 . Bài toán (EP ) có nghiệm duy nhất x∗ = 0. 25 Lấy {ρk}k≥0 ⊂ (0, 1) sao cho ρk → 0 khi k → +∞. Xuất phát từ 1 điểm bất kỳ x0 6= 0. Theo thuật toán xk+1 = argmin y∈C { ρkf ( xk, y ) + 1 2 ∥∥y − xk∥∥2} =argmin y∈C { ρkx k ( y − xk)+ 1 2 ∥∥y − xk∥∥2} = (1− ρk)xk. Kết hợp với limk→∞ ρk = 0 và xk 6= 0 cho mọi k ∈ N, suy ra rằng { xk } không hội tụ tuyến tính tới nghiệm duy nhất x∗ = 0. 2.2.3 Thuật toán không có điều kiện Lipschitz Thuật toán 2 ở trên mặc dù không có điều kiện Lipschitz, nhưng sự hội tụ của nó cần điều kiện Lipschitz. Trong tiểu mục này chúng tôi đề xuất một thuật toán hội tụ mạnh mà không yêu cầu f thỏa mãn điều kiện Lipschitz. Bổ đề đã biết sau sẽ được sử dụng để chứng minh kết quả hội tụ Bổ đề 2.3. Giả sử rằng {ak}∞k=0 là một dãy vô hạn các số dương thỏa mãn ak+1 ≤ ak + ξk, ∀k. Nếu ∑∞ k=0 ξk <∞ thì dãy {ak} hội tụ. Thuật toán 3 Chọn sai số ε > 0 và một dãy số {ρk} các số dương sao cho ∞∑ k=1 ρk =∞, ∞∑ k=1 ρ2k <∞. (2.23) Lấy x1 ∈ C và k := 1. Bước 1 (Tìm hướng đi) Tìm gk ∈ H sao cho f ( xk, y ) + 〈 gk, xk − y〉 ≥ −ρk, ∀y ∈ C; (2.24) 26 a) Nếu gk = 0 và ρk ≤ ε dừng: xk là một ε− nghiệm; b) Nếu gk = 0 và ρk > ε, quay lại Bước 1 với k được thay thế bởi k+1; c) Nếu không chuyển sang Bước 2. Bước 2 (Phép chiếu) Tính xk+1 := PC ( xk − ρkgk ) . a) Nếu xk+1 = xk và ρk ≤ ε, dừng: xk là một ε− nghiệm; b) Nếu không, quay lại Bước 1 với k được thay thế bởi k + 1. Định lí 2.3. Giả sử rằng giả thiết (A1) và (A2) được thỏa mãn. Khi đó (i) Nếu thuật toán dừng ở bước k, thì xk là một ε− nghiệm. (ii) Ta có ∥∥xk+1 − x∗∥∥2 ≤ (1− 2βρk) ∥∥xk − x∗∥∥2 + 2ρ2k + 2ρ2k∥∥gk∥∥2, ∀k. (2.25) trong đó x∗ là nghiệm duy nhất của (EP ). Hơn nữa, nếu thuật toán không dừng, thì dãy { xk } hội tụ mạnh tới nghiệm x∗ với điều kiện là { gk } bị chặn. Chứng minh. (i) Nếu thuật toán kết thúc ở Bước 1, thì gk = 0 và ρk ≤ ε. Sau đó, bằng biểu thức (2.24), f ( xk, y ) ≥ −ρk ≥ −ε với mọi y ∈ C. Vì thế, xk là một ε− nghiệm. Nếu thuật toán kết thúc ở Bước 2, với cùng một cách, ta có thể thấy rằng xk là một ε− nghiệm. (ii) Từ xk+1 = PC ( xk − ρkgk ) ta có ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − ρkgk − x∗∥∥2 = ∥∥xk − x∗∥∥2 − 2ρk 〈gk, xk − x∗〉+ ρ2k∥∥gk∥∥2. (2.26) Áp dụng (2.24) với y = x∗ chúng ta có được f ( xk, y ) + 〈 gk, xk − x∗〉 ≥ −ρk, 27 Nghĩa là − 〈gk, xk − x∗〉 ≤ f (xk, y)+ ρk. (2.27) Sau đó, từ (2.26), ta được ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 + 2ρk (f (xk, x∗)+ ρk)+ ρ2k∥∥gk∥∥2. (2.28) Vì x∗ là nghiệm, f(x∗, xk) ≥ 0, nên từ β− giả đơn điệu mạnh của f , kéo theo f ( xk, x∗ ) ≤ −β∥∥xk − x∗∥∥2. Kết hợp bất đẳng thức trước với (2.28) chúng ta có được ∥∥xk+1 − x∗∥∥2 ≤ ∥∥xk − x∗∥∥2 − 2βρk∥∥xk − x∗∥∥2 + 2ρ2k + ρ2k∥∥gk∥∥2 =(1− 2βρk) ∥∥xk − x∗∥∥2 + 2ρ2k + ρ2k∥∥gk∥∥2. (2.29) Bây giờ giả sử rằng thuật toán không kết thúc, và ∥∥gk∥∥ ≤ C với mọik. Thì nó kéo theo từ (2.29) ∥∥xk+1 − x∗∥∥2 ≤ (1− 2βρk) ∥∥xk − x∗∥∥2 + (2 + C2) ρ2k = ∥∥xk − x∗∥∥2 − λk∥∥xk − x∗∥∥2 + 2ρ2k + (2 + C2) ρ2k, (2.30) Khi λk := 2βρk. Vì ∑∞ k=1 ρ 2 k < ∞ trong hiệu quả của Bổ đề (2.2.4), chúng ta có thể kết luận rằng dãy {∥∥xk − x∗∥∥2} là hội tụ. Để chứng minh rằng giới hạn của dãy này là 0, ta áp dụng bất đẳng thức (2.30) với k = 1, ..., j +1 và tổng từ 1 tới j + 1 để có được ∥∥xj+1 − x∗∥∥2 ≤ ∥∥x1 − x∗∥∥2− j∑ k=1 λk ∥∥xk − x∗∥∥2 + (2 + C2) j∑ k=1 ρ2k, 28 nghĩa là ∥∥xj+1 − x∗∥∥2 + j∑ k=1 λk ∥∥xk − x∗∥∥2 ≤ ∥∥x1 − x∗∥∥2 + (2 + C2) j∑ k=1 ρ2j . (2.31) Từ (2.31) λk := 2βρk, chúng ta có ∞∑ k=1 λk = 2β ∞∑ k=1 ρk =∞. (2.32) Chú ý rằng { xj } là bị chặn và ∑∞ k=0 ρ 2 k <∞ chúng ta có thể suy luận từ (2.31) và (2.32) rằng ∥∥xj − x∗∥∥2 → 0 khi j →∞. Dưới đây là một ví dụ về song hàm giả đơn điệu mạnh Ví dụ: Cho 0 < R để cho K = B (r) := {x ∈ H : ‖x‖ ≤ r} và xác định bằng cách lấy f f (x