Một số khái niệm và kết quả cơ bản
Giả sử H là một không gian Hilbert thực với tích vô hướng và chuẩn được xác định bởi kxk = p hx, xi cho mọi x ∈ H Dãy {x k } ⊂ H được gọi là hội tụ mạnh tới x ∗ ∈ H, ký hiệu x → x ∗, nếu kx − x ∗ k → 0 Ngược lại, dãy {x k } ⊂ H được gọi là hội tụ yếu tới x ∗ ∈ H, ký hiệu x * x ∗, nếu hu, x − x ∗ i → 0 với mọi u ∈ H Định nghĩa 1.1.1 cho rằng tập C ⊂ X là một không gian véc tơ trên R được gọi là lồi nếu với mọi x, y ∈ C và 0 ≤ λ ≤ 1 thì λx + (1 − λ)y ∈ C; là nón có đỉnh tại 0 nếu λx ∈ C với mọi x ∈ C và λ ≥ 0; và là nón lồi nếu nó vừa là nón có đỉnh tại 0 vừa là một tập lồi.
Mệnh đề 1.1.2 [3, 64] Tập hợp C ⊂X là lồi khi và chỉ khi C chứa mọi tổ hợp lồi của các điểm của nó Tức là, C lồi khi và chỉ khi
Các tập lồi có tính chất đóng kín đối với một số phép toán như phép giao, phép cộng và phép nhân với số thực Cụ thể, nếu C và D là hai tập lồi trong không gian X, thì các phép toán này vẫn giữ nguyên tính chất lồi của chúng.
Trong không gian Hilbert thực H, nếu C là một tập lồi khác rỗng và x₀ ∈ C, thì véc tơ w ∈ H được xác định là pháp tuyến của C tại điểm x₀ nếu thỏa mãn điều kiện hw, x - x₀i ≤ 0 cho mọi x ∈ C Hơn nữa, các tập hợp C ∩ D và αC + βD cũng là các tập lồi với mọi α, β thuộc R.
N C (x 0 ) ={w ∈H : hw, x − x 0 i ≤0, ∀x ∈ C} được gọi là nón pháp tuyến ngoài (normal cone) của C tại x 0 và tập −N C (x 0 ) được gọi là nón pháp tuyến trong của C tại x 0
Rõ ràng rằng 0 không thuộc vào N C (x 0 ) và từ định nghĩa, ta thấy N C (x 0 ) là một nón lồi đóng Định nghĩa 1.1.4 cho rằng nếu C là một tập hợp không rỗng trong không gian Hilbert H, và với bất kỳ véc tơ x ∈ H, ta định nghĩa d C (x) = inf y∈C kx − yk, thì d C (x) là khoảng cách từ x đến C Nếu tồn tại x ∗ ∈ C sao cho d C (x) = kx − x ∗ k, thì x ∗ được gọi là hình chiếu của x trên C và ký hiệu là x ∗ = P C (x).
Từ định nghĩa trên ta thấy hình chiếu của x ∈H trên C là điểm thuộcC gần x nhất được xác định bởi
Nếu C là một tập lồi, đóng, khác rỗng của H , khi đó với mỗi x ∈H , P C (x) luôn tồn tại và là phần tử duy nhất thuộc C thỏa mãn kx − P C (x)k ≤ kx − yk, ∀y ∈ C.
Chẳng hạn, nếu C =H ={y ∈H:ha, yi+b ≤0}, với a ∈H và b ∈R , là một nửa không gian, thì ta có
x nếu x ∈ H, x − ha,xi+b kak 2 a nếu x 6∈ H.
Phép chiếu trên tập lồi, đóng có một số tính chất sau.
Trong không gian Hilbert H, nếu C là một tập con lồi, đóng và khác rỗng, thì hình chiếu P_C(x) của x trên C luôn tồn tại và duy nhất với mọi x Để z = P_C(x), điều kiện cần và đủ là x − z thuộc N_C(z), tức là ≤ 0 với mọi y ∈ C Hơn nữa, ta có bất đẳng thức kP_C(x) − P_C(y)k² ≤ cho mọi x, y ∈ H Định nghĩa hàm số lồi trên C được đưa ra như sau: hàm f được gọi là lồi nếu thỏa mãn f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y) với mọi x, y ∈ C và λ ∈ [0; 1] Hàm f được gọi là lồi chặt nếu f(λx + (1−λ)y) < λf(x) + (1−λ)f(y) với mọi x, y ∈ C, x ≠ y và λ ∈ (0; 1) Cuối cùng, hàm f là lồi mạnh với hệ số β > 0 nếu thỏa mãn f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y) − λ(1−λ)β.
Hàm f được gọi là tựa lồi (quasiconvex) trên tập C nếu với mọi x, y ∈ C và mọi λ ∈ [0; 1], thì f(λx + (1 − λ)y) ≤ max{f(x), f(y)} Tập hợp domf = {x ∈ C : f(x) < +∞} và epif = {(x, γ) ∈ C × R : f(x) ≤ γ} được gọi là miền hữu hiệu (effective domain) và đồ thị (epigraph) của f Hàm f: C → R ∪ {±∞} được xem là chính thường (proper function) nếu f(x) > −∞ với mọi x ∈ C và domf ≠ ∅ Định nghĩa 1.1.7 nêu rõ rằng hàm f: H → R được gọi là nửa liên tục dưới (lower semicontinuous) tại điểm x¯ ∈ H.
Hàm số f được gọi là nửa liên tục dưới trên tập C nếu tại mọi điểm x ∈ C, điều kiện f(¯x) ≤ lim inf k→∞ f(x k) được thỏa mãn với mọi dãy {x k} ⊂ H Ngoài ra, f cũng được xem là nửa liên tục trên tại điểm x¯ ∈ H nếu điều kiện này đúng cho mọi dãy {x k} trong H.
H: x k → x¯ thì f(¯x) ≥lim sup k→∞ f(x k ); f được gọi là nửa liên tục trên trên C nếu nó là nửa liên tục trên tại mọi x ∈ C.
Hàmf được gọi là liên tục trên C nếu nó vừa nửa liên tục dưới và vừa nửa liên tục trên trên C.
Đạo hàm và dưới vi phân của một hàm lồi là các khái niệm quan trọng trong phân tích hàm Một hàm f: H → R được coi là khả vi tại điểm x nếu tồn tại véc tơ x* ∈ H sao cho giới hạn của tỉ số (f(y) - f(x) - hx*, y - xi)/(ky - xk) khi y tiến gần đến x bằng 0 Véc tơ x* này được gọi là đạo hàm của f tại x, ký hiệu là ∇f(x) hoặc f'(x) Ngoài ra, hàm f được gọi là có đạo hàm theo hướng d ∈ H \ {0} tại x nếu tồn tại giới hạn lim t→0+ (f(x + td) - f(x))/t, và giới hạn này được ký hiệu là f'(x; d) Đối với hàm lồi chính thường f: H → R ∪ {+∞}, véc tơ w ∈ H được định nghĩa là dưới đạo hàm của f tại x nếu f(y) ≥ hw, y - xi + f(x) cho mọi y ∈ H.
Dưới vi phân (subdifferential) của hàm f tại điểm x được ký hiệu là ∂f(x) và là tập hợp tất cả các dưới đạo hàm của f tại x Hàm f được coi là khả dưới vi phân tại x nếu ∂f(x) khác rỗng (∅) Ngoài ra, hàm f được gọi là khả dưới vi phân trên một tập hợp nếu nó thỏa mãn điều kiện này tại mọi điểm trong tập đó.
Theo Định lý 1.1.10, nếu f : H → R ∪ { +∞} là hàm lồi, chính thường và khả dưới vi phân, thì x ∗ thuộc arg min{f(x) : x ∈H} khi và chỉ khi 0 thuộc ∂f(x ∗ ) Định lý 1.1.11 chỉ ra rằng, với C ⊂ H là tập lồi, đóng và có miền trong không rỗng, nếu f : H → R ∪ { +∞} là hàm lồi, chính thường, nửa liên tục dưới và khả dưới vi phân trên C, thì x 0 là điểm cực tiểu của f trên C khi và chỉ khi
Bài toán cân bằng và sự tồn tại nghiệm
Một số trường hợp riêng của bài toán cân bằng
Cho C là một tập lồi, đóng, khác rỗng của H a Bài toán tối ưu
Cho hàm ϕ: C →R Xét Bài toán tối ưu, viết tắt là (OP), là bài toán được phát biểu như sau:
Bằng cách định nghĩa f(x, y) := ϕ(y)− ϕ(x) cho mọi x, y ∈ C, ta có thể chứng minh rằng ϕ(x ∗ )≤ ϕ(y) với mọi y ∈ C tương đương với f(x ∗ , y)≥0 cho mọi y ∈ C Điều này cho thấy bài toán tối ưu là một trường hợp đặc biệt của bài toán cân bằng Ngoài ra, bài toán bất đẳng thức biến phân cũng được đề cập trong bối cảnh này.
Giả sử ánh xạF :C →Hlà ánh xạ đơn trị Bài toán bất đẳng thức biến phân (đơn trị), viết tắt là VIP(C, F) là bài toán
Nếu đặt f(x, y) := hF(x), y − xi, x, y ∈ C, thì các tập nghiệm của bài toán bất đẳng thức biến phân VIP(C, F) và bài toán cân bằng EP(C, f) trùng nhau.
Tổng quát, bài toán bất đẳng thức biến phân đa trị (multivalued variational inequality), viết tắt là MVIP(C, F) là bài toán
Trong bài toán tối ưu, ta xem xét điều kiện Tìmx ∗ ∈ Cvà u ∗ ∈ F(x ∗ ) sao cho chohu ∗ , y − x ∗ i ≥0, ∀y ∈ C Ở đây, F : C →2 H là ánh xạ đa trị, với F(x) là tập compact khác rỗng cho mọi x ∈ C Bài toán này có thể được diễn đạt dưới dạng bài toán cân bằng Nhờ vào tính compact của tập F(x) với mỗi x ∈ C, ta có thể định nghĩa hàm f(x, y) = max{hu, y − xi: u ∈ F(x)}.
Khi đó, nếu x ∗ cùng với u ∗ ∈ F(x ∗ ) là nghiệm của bài toán MVI(C, F) thì f(x ∗ , y) = max u∈F(x ∗ ) hu, y − x ∗ i ≥ hu ∗ , y − x ∗ i ≥0, ∀y ∈ C, tức là x ∗ là nghiệm của bài toán EP(C, f).
Nếu x ∗ là nghiệm của bài toán EP(C, f), thì do tập giá trị F(x ∗ ) có tính compact, tồn tại u ∗ ∈ F(x ∗ ) sao cho hu ∗ , y − x ∗ i = max u∈F(x) hu, y − x ∗ i = f(x ∗ , y) ≥ 0, ∀y ∈ C Điều này chứng tỏ rằng x ∗ cùng với u ∗ ∈ F(x ∗ ) là nghiệm của bài toán MVIP(C, F).
Giả sử F : C → C là ánh xạ đơn trị Bài toán điểm bất động thông thường viết tắt là FP(C, F) là bài toán
Bằng cách đặt f(x, y) := hx − F(x), y − xi, x, y ∈ C, thì bài toán FP(C, F) và bài toán EP(C, f) là tương đương với nhau.
Thật vậy, nếu x ∗ là nghiệm của bài toán FP(C, F) thì f(x ∗ , y) = hx ∗ − F(x ∗ ), y − x ∗ i= 0≥0, ∀y ∈ C.
Ngược lại, nếu x ∗ là nghiệm của bài toán EP(C, f) thì
Từ đó, ta có x ∗ = F(x ∗ ) (Theo định lí điểm bất động Brower, mọi ánh xạ liên tục từ tập com pắc vào chính nó đều có điểm bất động).
Tổng quát, bài toán điểm bất động đa trị, viết tắt là MFP(C, F) là bài toán
Tìm x ∈ C sao cho x ∈ F(x), trong đó F: C → 2^H là ánh xạ đa trị với tập giá trị F(x) là tập lồi, compact và khác rỗng Bài toán này có thể được diễn đạt dưới dạng bài toán cân bằng.
Thật vậy, do F(x) là tập com pắc với mỗi x ∈ C nên ta đặt f(x, y) = max u∈F (x) hx − u, y − xi, ∀x, y ∈ C.
Dễ thấy, nếu x ∗ ∈ F(x ∗ ) thì f(x ∗ , y) = max u∈F (x ∗ ) hx ∗ − u, y − x ∗ i ≥ hx ∗ − x ∗ , y − x ∗ i= 0, ∀y ∈ C.
Vì 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à nghiệm của bài toán EP(C, f), tức là f(x ∗ , y) ≥ 0 với mọi y ∈ C Khi đó, lấy y là hình chiếu của x ∗ lên tập lồi, com pắc, khác rỗng
F(x ∗ ), ta được hx ∗ − y, y − x ∗ i= max u∈F (x ∗ ) hx ∗ − u, u − x ∗ i.
0≤ f(x ∗ , y) = hx ∗ − y, y − x ∗ i=−kx ∗ − yk 2 Điều đó chứng tỏ y=x ∗ ∈ F(x ∗ ), vậy x ∗ là điểm bất động của ánh xạ F. d 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 với p người chơi, trong đó I = {1, , p} là tập hữu hạn các chỉ số người chơi Mỗi người chơi i (với i ∈ I và n_i ∈ N) có tập chiến lược C_i ⊆ R^{n_i} là tập lồi, đóng và khác rỗng Hàm thua thiệt f_i: C = C_1 × × C_p → R xác định kết quả cho người chơi i, phụ thuộc vào tất cả các chiến lược của những người chơi khác Đối với x = (x_1, , x_p) và y = (y_1, , y_p) thuộc C, chúng ta sẽ tiến hành phân tích các chiến lược và kết quả trong trò chơi này.
Bài toán cân bằng Nash là bài toán
Điểm cân bằng Nash, ký hiệu là x ∗ ∈ C, được xác định bởi điều kiện f i (x ∗ ) ≤ f i (x ∗ [y i ]) cho mọi y i ∈ C i và mọi i ∈ I Trong bối cảnh kinh tế, điểm cân bằng Nash cho thấy rằng nếu một đối thủ chọn phương án khác ngoài điểm cân bằng, trong khi các đối thủ khác vẫn duy trì phương án tại điểm cân bằng, thì đối thủ đó sẽ gặp bất lợi Điều này nhấn mạnh tầm quan trọng của sự hợp tác và chiến lược trong các tình huống cạnh tranh.
{f i (x[y i ])− f i (x)}; x, y ∈ C, ta đưa được bài toán (NEP) về bài toán EP(C, f).
Sự tồn tại nghiệm của bài toán cân bằng
Trong phần này, chúng tôi tóm tắt các kết quả quan trọng liên quan đến sự tồn tại và tính duy nhất của nghiệm cho bài toán cân bằng EP(C, f) Chúng tôi chỉ nêu ra những kết quả chính mà không trình bày chứng minh chi tiết Độc giả có thể tham khảo các tài liệu để tìm hiểu thêm về các chứng minh của những kết quả này.
[11, 13, 27, 38, 45]. Để thuận lợi trong việc trình bày các kết quả, ta cần một số các giả thiết của song hàm f :C × C →R ∪ { +∞} như sau.
(G 1 ) f(ã, y) là hàm nửa liờn tục trờn trờn C theo biến thứ nhất với mỗi y ∈ C. (G 2 ) f(x, ã) là hàm tựa lồi trờn C theo biến thứ hai với mỗi x ∈ C.
(G 3 ) f(x, ã) là hàm nửa liờn tục dưới trờn C theo biến thứ hai với mỗi x ∈ C. Định lý 1.2.1 [13, Theorem 2.3.4], [27, Ky Fan’s Theorem] Giả sử f :C × C →
R ∪ { +∞} là một song hàm cân bằng đáp ứng các điều kiện (G 1 ),(G 2 ) Giả sử ít nhất một trong các giả thiết sau được thỏa mãn: i) C là tập compact; ii) Tồn tại một tập con khác rỗng W ⊂ C sao cho với mọi x ∈ C \ W, tồn tại y ∈ W để f(x, y) 0 nếu với mọi x, y ∈ C, f(x, y) + f(y, x) ≤ −τ||x − y||²; b) Đơn điệu chặt (strictly monotone) trên C nếu f(x, y) + f(y, x) < 0 với mọi x, y ∈ C; c) Đơn điệu (monotone) trên C nếu f(x, y) + f(y, x) ≤ 0 với mọi x, y ∈ C; d) Giả đơn điệu (pseudomonotone) trên C nếu f(x, y) ≥ 0 ⇒ f(y, x) ≤ 0 với mọi x, y ∈ C; e) Giả đơn điệu trên C tương ứng với D (pseudomonotone on C with respect to D).
∀x ∗ ∈ D, ∀y ∈ C, f(x ∗ , y)≥0⇒ f(y, x ∗ ) ≤0; f) para-đơn điệu (paramonotone) trên C nếuf là đơn điệu trên C và
{x ∈Sol(C, f), y ∈ C, f(x, y) =f(y, x) = 0} ⇒ y ∈Sol(C, f); g) para-giả đơn điệu (parapseudomonotone) trên C nếu f là giả đơn điệu trên
{x ∈Sol(C, f), y ∈ C, f(x, y) =f(y, x) = 0} ⇒ y ∈Sol(C, f); h) thỏa mãn điều kiện kiểu Lipschitz trên C nếu tồn tại các hằng số c 1 >0và c 2 >0, và với mọi x, y, z ∈ C, ta có f(x, y) +f(y, z)≥ f(x, z)− c 1 kx − yk 2 − c 2 ky − zk 2
Từ định nghĩa trên, ta có: a)⇒ b)⇒ c)⇒ d)⇒ e, f)⇒ g), f) ⇒ c) và g)⇒ d).
Nếu f(x, y) = hF(x), y − xi với ánh xạ F : H → H, thì tính đơn điệu của song hàm f tương ứng với tính đơn điệu của ánh xạ F Hơn nữa, nếu ánh xạ F là Lipschitz với hằng số L > 0 trên C, tức là kF(x)− F(y)k ≤ Lkx − yk cho mọi x, y ∈ C, thì f cũng thỏa mãn điều kiện kiểu.
Lipschitz trên C (xem [54, 62]), chẳng hạn, với các hằng số c 1 = 2 L , c 2 = L 2 , với mọi >0. Định lý 1.2.3 ([11, Proposition 4.2], [45, Proposition 2.1.16]).Giả sửf :C×C →
R ∪ { +∞} là một song hàm cân bằng Nếu f là đơn điệu chặt, bài toán EP(C, f) sẽ có tối đa một nghiệm Hơn nữa, nếu f(x, ã) là hàm lồi với mỗi x ∈ C, thỏa mãn các giả thiết (G 1) và (G 3), đồng thời là hàm đơn điệu mạnh trên C, thì bài toán EP(C, f) sẽ có nghiệm duy nhất.
Bài toán điểm bất động và một số phương pháp tìm điểm bất động 27 Chương 2 Một số thuật toán giải bài toán cân bằng không đơn điệu 32
Điểm bất động là khái niệm quan trọng trong ánh xạ, đặc biệt trong không gian Hilbert H Định nghĩa một điểm x ∈ C là điểm bất động của ánh xạ T : C → H khi x thuộc vào tập lồi, đóng và khác rỗng C Các kiến thức liên quan được tham khảo từ các tài liệu chuyên ngành.
Tập các điểm bất động của ánh xạ T được ký hiệu là
Trong không gian Hilbert H, tập lồi, đóng và khác rỗng C có ánh xạ T: C → H được định nghĩa với các loại ánh xạ khác nhau Ánh xạ co trên C thỏa mãn điều kiện kT(x)− T(y)k ≤ τkx − yk với 0 < τ < 1 cho mọi x, y ∈ C Ánh xạ không giãn (nonexpansive) đảm bảo kT(x)− T(y)k ≤ kx − yk cho mọi x, y ∈ C Ánh xạ Lipschitz có hằng số L > 0 khi kT(x)− T(y)k ≤ Lkx − yk Ánh xạ tựa không giãn (quasinonexpansive) có điều kiện Fix(T) ≠ ∅ và kT(x)− yk ≤ kx − yk cho mọi x ∈ C, y ∈ Fix(T) Ánh xạ giả co (pseudocontractive) thỏa mãn kT(x)− T(y)k² ≤ kx − yk² + k(I − T)x − (I − T)yk² Cuối cùng, ánh xạ κ-nửa co (κ-demicontractive) có điều kiện Fix(T) ≠ ∅ và tồn tại hằng số κ ∈ [0, 1) sao cho kT(x)− yk² ≤ kx − yk² + κkx − T(x)k² cho mọi x ∈ C, y ∈ Fix(T).
Từ định nghĩa trên ta có a) ⇒ b ⇒ c), b) ⇒ d), b) ⇒ e), d)⇒ f).
Giả sử T : C → C là một ánh xạ (đơn trị) Bài toán tìm điểm bất động của ánh xạ T là bài toán: Tìm x ∗ ∈ C sao cho T(x ∗ ) =x ∗
Nhiều bài toán trong Giải tích và Đại số có thể được chuyển thành bài toán tìm điểm bất động Tuy nhiên, hiện chưa có thuật toán tổng quát nào để xác định điểm bất động cho mọi ánh xạ T Để thực hiện việc này, cần phân loại và khai thác cấu trúc của ánh xạ T.
Nếu T là ánh xạ co, theo định lý Banach, trong không gian metric đầy đủ (X, d) với tập đóng không rỗng C, ánh xạ T : C → C sẽ có một điểm bất động duy nhất x ∗ ∈ X Hơn nữa, với mọi x 0 ∈ C, dãy {x n } được xác định bởi x n = T(x n−1) với n ≥ 1 sẽ hội tụ về x ∗ khi n tiến tới vô cực.
- Nếu T không phải là ánh xạ co, chẳng hạn T là ánh xạ không giãn thì định lý Banach có thể không còn đúng nữa.
Ví dụ 1.3.4 Xét phép tịnh tiếnT trong không gianH=R n , được xác định bởi:
T(x) = x+u, với06=u ∈R n là véc tơ cố định.
T là một ánh xạ không giãn và đẳng cự, nghĩa là nó bảo toàn khoảng cách giữa các điểm, nhưng không nhất thiết phải có điểm bất động Dù T có điểm bất động, phép lặp x n+1 = T(x n) vẫn có thể không hội tụ về điểm bất động đó Ví dụ dưới đây sẽ minh họa cho điều này.
Ví dụ 1.3.5 Xét phép quay một góc α(0< α 0, tồn tại η >0 và k ∈ N sao cho
∂ 2 f(x k , y k )⊂ ∂ 2 f(¯x, y¯) + η B, với mọi k ≥ k , trong đó B là hình cầu đơn vị trong H
Bổ đề 2.2.3 [54] Với các giả thiết (B 1) và (B 2), điểmx ∗ ∈ C là một nghiệm của bài toán EP(C, f) khi và chỉ khi nó là một nghiệm của bài toán cân bằng:
Bổ đề 2.2.4 khẳng định rằng, nếu C là một tập lồi, đóng và khác rỗng trong H, và {x_k} là một dãy trong H với u ∈ H, thì nếu mọi điểm giới hạn yếu của dãy {x_k} thuộc C và khoảng cách kx_k - uk nhỏ hơn hoặc bằng khoảng cách ku - P_C(u) với mọi k, thì dãy {x_k} sẽ hội tụ đến P_C(u).
Bổ đề 2.2.5 [21, Lemma 2.5] Với các giả thiết (B 1) và (B 2), nếu {z k } ⊂ C là một dãy hội tụ mạnh tới ¯z, và dãy {w k }, với w k ∈ ∂ 2 f(z k , z k ), hội tụ yếu tới w¯, thì w¯∈ ∂ 2 f(¯z,¯z).
Bổ đề 2.2.6 nêu rằng nếu song hàm cân bằng f đáp ứng các giả thiết (B 1) và (B 2) trên miền Ω và tập C, với dãy {x k } thuộc C và 0 < ρ ≤ ρ¯, cùng dãy {ρ k } nằm trong khoảng [ρ, ρ¯], thì dãy {y k } được xác định bởi y k = arg minn f(x k , y) + 1.
Khi đó, nếu dãy {x k } bị chặn, thì dãy {y k } cũng bị chặn.
Dưới đây, là một số thuật toán được đề xuất để giải bài toán cân bằng không đơn điệu trong không gian Hilbert thực H. a Thuật toán 2.1
Bước khởi tạo.Chọnx 0 =x g ∈ C, chọn cỏc tham sốη, à ∈(0,1),0< ρ ¯
, ρ¯], γ k ∈[γ ¯ , γ¯] ⊂(0,2), và đặt C 0 =C. Bước lặp k (k= 0,1,2, ) Có x k ta thực hiện các bước sau:
Bước 1 Giải bài toán quy hoạch lồi mạnh tìm nghiệm y k = arg minn f(x k , y) + 1
Nếu y k =x k , thì dừng thuật toán Trái lại, thực hiện Bước 2.
Bước 2.(Quy tắc tìm kiếm tia Armijo thứ nhất) Tìm m k là số nguyên dương nhỏ nhất m sao cho
Bước 3 Lấy w k ∈ ∂ 2 f(z k , x k ) và tính u k = P C (x k − γ k σ k w k ), trong đó σ k = f(z kw k k ,x k 2 k )
Bước 4 Tính x k+1 =P C k +1 (x g ), với C k+1 ={x ∈ C k :kx − u k k ≤ kx − x k k}, và quay về Bước lặp k với k được thay bởi k+ 1.
Nếu \( y_k = x_k \), thì \( x_k \) là một nghiệm của bài toán EP(C, f) Trước khi chứng minh sự hội tụ của Thuật toán 2.1, chúng tôi sẽ nhắc lại bổ đề đã được chứng minh trong tài liệu [62].
Bổ đề 2.2.8 [62, Lemma 4.3, Lemma 4.5] Giả sử song hàm f thỏa mãn các giả thiết (B 1) và (B 2), khi đó ta có:
(a) Quy tắc tìm kiếm theo tia (2.1) là xác định tốt, tức là với mọi k đều tồn tại số nguyên dương nhỏ nhất m k thỏa mãn (2.1);
Nếu tập S M khác rỗng, thì tồn tại một nghiệm x ∗ của bài toán cân bằng EP(C, f) mà các dãy {x k } và {u k } được sinh ra từ Thuật toán 2.1 sẽ hội tụ mạnh tới nghiệm này Định lý 2.2.9 chỉ ra rằng khi song hàm f thỏa mãn các giả thiết (B 1) và (B 2), điều kiện ku k − x ∗ k 2 ≤ kx k − x ∗ k 2 − γ k (2− γ k )(σ k kw k k) 2 cũng được áp dụng.
Chứng minh Lấy x¯∈ S M ⊂ C=C 0 Từ Bổ đề 2.2.8, ta có ku k − xk¯ 2 ≤ kx k − xk¯ 2 − γ k (2− γ k )(σ k kw k k) 2 (2.3)
Từ bất đẳng thức (2.4), bằng quy nạp ta có thể kết luận được rằng x¯∈ C k với mọi k.
Theo Bước 4, x k =P C k (x g ), ta có kx k − x g k ≤ kx − x g k, ∀x ∈ C k , (2.5) vì vậy, kx k − x g k ≤ k x¯− x g k, ∀k (2.6)
Do đó, dãy {x k } là bị chặn Kết hợp với (2.4) ta có dãy {u k } cũng bị chặn.
Vì x k+1 ∈ C k và từ bất đẳng thức (2.5), ta có kx k − x g k ≤ kx k+1 − x g k, ∀k (2.7) Mặt khác, do dãy {x k } bị chặn, nên ta nhận được k→∞lim kx k − x g k=τ ≥0 (2.8) Ngoài ra, kx k+1 − x k k 2 =kx k+1 − x g +x g − x k k 2
≤ kx k+1 − x g k 2 − kx k − x g k 2 , trong đó bất đẳng thức cuối cùng có được vì x k =P C k (x g ) và x k+1 ∈ C k , khi đó, hx k+1 − x k , x g − x k i ≤0.
Từ (2.8), ta được k→∞lim kx k+1 − x k k= 0 (2.9) Bởi vì x k+1 ∈ C k+1 , ta suy ra kx k − u k k ≤ kx k − x k+1 k+kx k+1 − u k k ≤2kx k − x k+1 k.
Kết hợp với (2.9) ta có k→∞lim ku k − x k k= 0 (2.10)
Tiếp theo, ta chỉ ra rằng các dãy{x k }, {u k }hội tụ mạnh tới x ∗ =P ∩ ∞ k =0 C k(x g ).
C k là tập lồi, đóng và không rỗng, do đó C k không đóng yếu Với C k+1 ⊂ C k và x k ∈ C k, ta có x k ∈ C k 0 với mọi k ≥ k 0 Giả sử ˆx là điểm tụ yếu của dãy {x k }, tồn tại dãy con {x k j } sao cho x k j tiến gần đến ˆx khi j → ∞ Vì {x k j } thuộc C k i và C k i là tập đóng yếu, nên ˆx thuộc C k i cho mọi i Do đó, ˆx thuộc C k cho mọi k, tức là ˆx thuộc ∩ ∞ k=0 C k Đặt x ∗ = P ∩ ∞ k =0 C k(x g ), ta có kx k − x g k ≤ kx ∗ − x g k cho mọi k.
Ta có thể kết luận rằng dãy {x k } hội tụ mạnh tới x ∗ theo Bổ đề 2.2.4 Cùng với (2.10) ta cũng có dãy {u k } hội tụ mạnh tới x ∗
Tiếp theo, ta chỉ ra rằng x ∗ là nghiệm của bài toán EP(C, f).
Theo (2.3), ta có bất đẳng thức γ k (2− γ k )(σ k kw k k) 2 ≤ kx k − u k k kx k − xk¯ +ku k − xk¯
,¯γ]⊂(0,2), và (2.10), ta nhận được từ (2.11) là k→∞lim σ k kw k k= 0 (2.12)
Dựa vào dãy {x k } bị chặn và Bổ đề 2.2.6, ta suy ra rằng dãy {y k } cũng bị chặn Hơn nữa, dãy {z k } cũng thỏa mãn tính chất bị chặn Áp dụng Bổ đề 2.2.5, dãy {w k } cũng được xác định là bị chặn Theo công thức (2.12), khi k tiến tới vô cùng, ta có giới hạn f(z k , x k ) = lim k→∞[σ k kw k k]kw k k = 0.
≤(1− η k )f(z k , x k ) +η k f(z k , y k ), vì vậy, ta nhận được từ (2.1) f(z k , x k )≥ η k [f(z k , x k )− f(z k , y k )]
2ρ k η k kx k − y k k 2 Kết hợp với (2.13) ta suy ra k→∞lim η k kx k − y k k 2 = 0 (2.14)Tiếp theo ta xét hai trường hợp sau:
Khi đó tồn tại η >¯ 0 và một dãy {η k i } ⊂ {η k } sao cho η k i > η,¯ ∀i, và từ (2.14), ta nhận được i→∞lim kx k i − y k i k= 0 (2.15) Lưu ý rằng x k → x ∗ và (2.15), điều này dẫn đến y k i → x ∗ khi i → ∞.
Theo định nghĩa của y k i ta có f(x k i , y) + 1
2ρ k i ky k i − x k i k 2 , ∀y ∈ C (2.16) Không mất tính tổng quát, ta giả thiết rằng lim i→∞ ρ k i = ρ ∗ Cho i → ∞, do x k i → x ∗ ,y k i → x ∗ và dựa vào tính liên tục yếu đồng thời của f, từ (2.16) ta nhận được f(x ∗ , y) + 1
2ρ ∗ ky − x ∗ k 2 ≥0. Theo Bổ đề 2.2.3, ta có f(x ∗ , y)≥0, ∀y ∈ C.
Do đó, x ∗ là một nghiệm của bài toán EP(C, f).
Vì dãy {y k } bị chặn, khi đó tồn tại dãy con {y k i } ⊂ {y k } sao cho y k i * y¯ khi i → ∞.
Theo định nghĩa của y k i , ta có f(x k i , y k i ) + 1
2ρ k i ky k i − x k i k 2 ≤0 (2.17) Mặt khác, theo quy tắc tìm kiếm tia Armijo (2.1), với m k i −1, ta có f(z k i ,m ki −1 , x k i )− f(z k i ,m ki −1 , y k i ) < à
2ρ k i ky k i − x k i k 2 (2.18) Kết hợp với (2.17) ta được f(x k i , y k i )≤ − 1
Theo quy tắc tìm kiếm tia, z k i ,m ki −1 hội tụ mạnh tới x ∗ khi i → ∞, với điều kiện η m ki −1 → 0 Trong khi đó, x k i hội tụ mạnh tới x ∗ và y k i hội tụ yếu tới y¯ Dãy { ρ 1 ki ky k i − x k i k 2 } bị chặn và có thể giả sử rằng lim i→+∞ ρ 1 ki ky k i − x k i k 2 tồn tại Từ giới hạn này, ta có f(x ∗ , y¯) ≤ − lim i→+∞.
Vì vậy, f(x ∗ ,¯y) = 0 và lim i→+∞ ky k i − x k i k 2 = 0 Theo Trường hợp 1, ta có x ∗ là một nghiệm của bài toán EP(C, f).
Thay thế quy tắc tìm kiếm tia thứ nhất (2.1) bởi một quy tắc khác, ta thu được thuật toán sau. b Thuật toán 2.2
Bước khởi tạo.Chọnx 0 =x g ∈ C, chọn cỏc tham sốη, à ∈(0,1),0< ρ ¯
, ρ¯], γ k ∈[γ ¯ , γ¯] ⊂(0,2), và đặt C 0 =C. Bước lặp k (k= 0,1,2, ) Có x k ta thực hiện các bước sau:
Bước 1 Giải bài toán quy hoạch lồi mạnh tìm y k = arg minn f(x k , y) + 1
Nếu y k =x k , thì dừng thuật toán Trái lại, thực hiện Bước 2.
Bước 2 (Quy tắc tìm kiếm tia Armijo thứ hai) Tìm m k là số nguyên dương nhỏ nhất m sao cho
(2.20) Đặt η k = η m k , z k = z k,m k Nếu 0 ∈ ∂ 2 f(z k , z k ), thì dừng thuật toán. Trái lại, thực hiện Bước 3.
Bước 3 Chọn w k ∈ ∂ 2 f(z k , z k ) và tính u k =P C (x k − γ k σ k w k ), trong đó σ k = f(z kw k k ,x k 2 k )
Bước 4 Tính x k+1 =P C k +1 (x g ), với C k+1 ={x ∈ C k : kx − u k k ≤ kx − x k k}, và quay lại Bước lặp k với k được thay bởi k+ 1.
Nếu y k =x k thì x k là một nghiệm của bài toán EP(C, f);
Nếu 0∈ ∂ 2 f(z k , z k ) thì z k là một nghiệm của bài toán EP(C, f).
Bổ đề 2.2.11 [62, Lemma 4.2, Lemma 4.5] Giả sử song hàm f thỏa mãn các giả thiết (B 1) và (B 2), khi đó ta có:
(a) Quy tắc tìm kiếm tia (2.20) là xác định tốt, tức là với mọi k đều tồn tại số nguyên dương nhỏ nhất m k thỏa mãn (2.20);
(c) Nếu S M 6=∅, thì ku k − x ∗ k 2 ≤ kx k − x ∗ k 2 − γ k (2− γ k )(σ k kw k k) 2 , với mọi x ∗ ∈ S M
Bằng cách áp dụng Bổ đề 2.2.11 và lập luận tương tự như trong chứng minh Định lý 2.2.9, chúng ta có thể chứng minh Định lý 2.2.12 về sự hội tụ của Thuật toán 2.2 Cụ thể, nếu hàm f thỏa mãn các giả thiết (B 1) và (B 2), thì tập
S M khác rỗng, thì dãy {x k }, {u k } sinh bởi Thuật toán 2.2 hội tụ mạnh tới một nghiệm x ∗ của bài toán EP(C, f).
Hệ bài toán cân bằng và bài toán cân bằng tổ hợp 49
Mở đầu
Cho C là một tập lồi, đóng, khác rỗng trong không gian Hilbert H, và f i : C × C → R, với i = 1, N là các song hàm xác định trên C Bài toán tìm nghiệm chung của một họ hữu hạn các bài toán cân bằng, được ký hiệu là CSEP, đã được đề cập trong các tài liệu [41, 66–68].
Tìm x ∗ ∈ C sao cho f i (x ∗ , y) ≥0, ∀y ∈ C và i= 1,2, , N, CSEP(C, f i ) hoặc tương đương, tìm x ∗ ∈ X :=∩ N i=1 Sol(C, f i).
Với α i ∈(0,1), i= 1, , N sao cho PN i=1 α i = 1, xét song hàm tổ hợp:
Bài toán cân bằng tổ hợp viết tắt là CEP(C,PN i=1 α i f i ) là bài toán:
Ta ký hiệu Sol(C,PN i=1 α i f i) là tập nghiệm của bài toán cân bằng tổ hợp.
Trong [66], với một số điều kiện nhất định các tác giả khẳng định rằng:
Các nghiệm chung của một họ hữu hạn bài toán cân bằng có thể được xác định bằng cách tìm nghiệm của tổ hợp lồi bất kỳ của các bài toán đó Kết quả này đã được các tác giả trong các bài báo [41, 42, 66–68] áp dụng để chuyển đổi các bài toán của họ thành bài toán liên quan đến bài toán cân bằng tổ hợp.
Trong phần này, chúng tôi chỉ ra rằng, với các điều kiện được đưa ra như trong [66], quan hệ
Kết quả Sol(C, f i) không phải lúc nào cũng chính xác, dẫn đến việc các kết quả trong các bài báo gần đây [41, 42, 66–68] cũng không đúng do dựa vào một bao hàm sai Chúng tôi cung cấp một điều kiện đủ để khẳng định rằng công thức trên không chỉ đúng khi N hữu hạn mà còn áp dụng cho trường hợp N = +∞.
Trước khi trình bày một số mệnh đề từ các bài báo liên quan đến khẳng định trong [66], chúng tôi sẽ nhắc lại một số giả thiết mà các tác giả đã áp dụng.
(C 3 ) ϕ là nửa liên tục trên theo tia (upper hemicontinuous), tức là, với mỗi x, y, z ∈ C, lim sup t→0 + ϕ(tz+ (1− t)x, y) ≤ ϕ(x, y);
(C 4 ) Với mỗix ∈ C, ϕ(x, ã) là nửa liờn tục dưới (lower semicontinuous) và lồi trờn
(C 5 ) Với r > 0 cố định, và z ∈ C, tồn tại tập con lồi, com pắc khác rỗng B ⊂H và x ∈ C ∩ B, sao cho ϕ(y, x) + 1 r hy − z, z − xi