Luận án Một số phương pháp giải bài toán cân bằng giả đơn điệu và ứng dụng

s(yki), xki − yki〉 ≥ 0. Kết hợp điều này với (2.56) ta được 〈s(xki), xki − yki〉 ≥ δ‖xki − yki‖2. Từ đây ta suy ra ‖xki − yki‖ ≤ 1√ δ ‖s(xki)‖, ∀s(xki) ∈ ∂fki(xki). (2.57) Bởi vì xki → x¯ và dãy {fki} hội tụ điểm trên C về hàm f¯ với f¯(y) = ρf(x¯, y) + h(y)− h(x¯)− 〈∇h(x¯), y − x¯〉, 69 nên theo Định lý 1.5 ta suy ra tồn tại số nguyên i0 > 0, đủ lớn sao cho ∂fki(x ki) ⊂ ∂f¯(x¯) +B[0; 1], ∀i > i0 (2.58) với B[0; 1] là hình cầu đơn vị đóng có tâm tại 0 và bán kính 1 trong không gian Rn. Mặt khác ta có ∂fki(x ki) = ρ∂2f(x ki , xki) ∀i và ∂2f¯(x¯) = ρ∂2f(x¯, x¯) nên (2.58) trở thành ∂2f(x ki , xki) ⊂ ∂2f(x¯, x¯) + 1 ρ B[0; 1], ∀i > i0 (2.59) Do tập hợp ∂2f(x¯, x¯) bị chặn, kết hợp với (2.57) và (2.59) ta suy ra dãy số {‖xki − yki‖} bị chặn. Mà dãy {xki} bị chặn nên ta suy ra dãy {yki} cũng bị chặn. Theo định nghĩa của zki : zki = (1− ηki)xki + ηkiyki nên {zki} cũng bị chặn. Không mất tính tổng quát, ta giả sử zki hội tụ về điểm z¯ nào đó. Bởi vì wki ∈ ∂2f(zki , zki), nên áp dụng Định lý 1.5 một lần nữa, ta suy ra dãy {wki} bị chặn. Bổ đề 2.11. Nếu dãy con {xki} ⊂ {xk} hội tụ về một điểm x¯ nào đó và ‖yki − xki‖4( ηki‖wki‖ ) 2 → 0 khi i→∞, (2.60) thì x¯ ∈ Sf . Chứng minh. Ta xét hai trường hợp phân biệt Trường hợp 1. lim inf ηki ‖wki‖ > 0. Từ (2.60), ta suy ra limi→∞ ‖yki−xki‖ = 0, do đó yki → x¯ và zki → x¯ khi i→∞. Theo định nghĩa của yki ta có f(xki , y) + 1ρ [h(y)− h(xki)− 〈∇h(xki), y − xki〉] ≥ f(xki , yki) + 1 ρ [h(yki)− h(xki)− 〈∇h(xki), yki − xki〉], ∀y ∈ C do f, h và ∇h liên tục, nên chuyển qua giới hạn bất đẳng thức trên khi i→∞ ta thu được f(x¯, y) + 1 ρ [h(y)− h(x¯)− 〈∇h(x¯), y − x¯〉] ≥ 0 ∀y ∈ C, 70 điều này có nghĩa là x¯ ∈ Sf . Trường hợp 2. lim ηki ‖wki‖ = 0. Trong trường hợp này do dãy {wki} bị chặn ta thu được lim ηki = 0, bởi vậy zki = (1− ηki)xki + ηkiyki → x¯ khi i→∞. Không giảm tổng quát, ta giả sử rằng wki → w¯ ∈ ∂2f(x¯, x¯) và yki → y¯ khi i→∞. Ta có f(xki , y) + 1 ρ [h(y)− h(xki)− 〈∇h(xki), y − xki〉] ≥ f(xki , yki) + 1 ρ [h(yki)− h(xki)− 〈∇h(xki), yki − xki〉] ∀y ∈ C. Cho i→∞, ta thu được f(x¯, y) + 1ρ [h(y)− h(x¯)− 〈∇h(x¯), y − x¯〉] ≥ f(x¯, y¯) + 1 ρ [h(y¯)− h(x¯)− 〈∇h(x¯), y¯ − x¯〉] ∀y ∈ C. Mặt khác, theo quy tắc tìm kiếm theo tia Armijo (2.46), với số mki − 1 tồn tại wki,mki−1 ∈ ∂2f(zki,mki−1, zki,mki−1) sao cho 〈wmki−1, xki − yki〉 < 1 ρ [ h(yki)− h(xki)− 〈∇h(xki), yki − xki〉 ] , (2.61) chuyển qua giới hạn khi i → ∞ và kết hợp với zki,mki−1 → x¯, wki,mki−1 → w¯ ∈ ∂2f(x¯, x¯), từ (2.61) ta thu được 〈w¯, x¯− y¯〉 ≤ 1 ρ [ h(y¯)− h(x¯)− 〈∇h(x¯), y¯ − x¯〉 ] , do đó 0 ≤ 〈w¯, y¯ − x¯〉+ 1 ρ [ h(y¯)− h(x¯)− 〈∇h(x¯), y¯ − x¯〉 ] , điều này dẫn đến f(x¯, y¯) + 1 ρ [ h(y¯)− h(x¯)− 〈∇h(x¯), y¯ − x¯〉 ] ≥ 0 vì vậy f(x¯, y) + 1 ρ [ h(y)− h(x¯)− 〈∇h(x¯), y − x¯〉 ] ≥ 0, ∀y ∈ C. Tức là x¯ ∈ Sf . 71 Định lí 2.3. Giả sử tập nghiệm Sf của bài toán cân bằng EP(C, f) là khác rỗng và hàm h(.), dãy {λk} thỏa mãn các điều kiện (B1), (B2) tương ứng, thì với các giả thiết (A1), (A2), (A3) và (A4), dãy {xk} sinh bởi Thuật toán 2.5 hội tụ về nghiệm duy nhất x∗ của bài toán VIEP(C, f,G). Chứng minh. Theo Bổ đề 2.8 ta có ‖xk+1 − x∗‖2 − ‖xk − x∗‖2 + ( ηkδ ρ‖wk‖ )2 ‖xk − yk‖4 ≤ −2λk〈uk − x∗, G(uk)〉 + λ2k‖G(uk)‖2 ∀k. (2.62) Từ Bổ đề 2.9 và tính Lipchitz của toán tử G, ta suy ra các dãy {xk}, {uk} và {G(uk)} bị chặn, do đó tồn tại các hằng số dương A,B sao cho |〈uk − x∗, G(uk)〉| ≤ A, ‖G(uk)‖2 ≤ B ∀k. Đặt ak = ‖xk − x∗‖2, kết hợp với bất đẳng thức trên, (2.62) trở thành ak+1 − ak + ( ηkδ ρ‖wk‖ )2 ‖xk − yk‖4 ≤ 2λkA+ λ2kB. (2.63) Ta xét hai trường hợp phân biệt: Trường hợp 1. Tồn tại số k0 sao cho {ak} là dãy giảm khi k ≥ k0. Khi đó, do ak ≥ 0 ∀k nên tồn tại giới hạn limk→∞ ak = a, lấy giới hạn hai vế của (2.63) ta nhận được lim k→∞ ( ηkδ ρ‖wk‖ )2 ‖xk − yk‖4 = 0. (2.64) Thêm vào đó, ‖xk+1 − uk‖ = ‖PC(uk − λkG(uk))− PC(uk)‖ ≤ ‖uk − λkG(uk)− uk‖ = λk‖G(uk)‖ → 0 khi k →∞. (2.65) Từ đây suy ra limk→∞ ‖uk − x∗‖2 = limk→∞ ‖xk+1 − x∗‖2 = a. Do {uk} bị chặn, nên tồn tại dãy con {uki} ⊂ {uk} sao cho uki → u¯ ∈ C và lim inf〈uk − x∗, G(x∗)〉 = limi→∞〈uki − x∗, G(x∗)〉. Kết hợp điều này với (2.64) và (2.65) ta thu được xki+1 → u¯ và ( ηki+1δ ρ‖wki+1‖ )2 ‖xki+1 − yki+1‖4 → 0 khi i→∞. 72 Theo Bổ đề 2.11 ta có u¯ ∈ Sf . Do đó lim inf k→∞ 〈uk − x∗, G(x∗)〉 = lim i→∞ 〈uki − x∗, G(x∗)〉 = 〈u¯− x∗, G(x∗)〉 ≥ 0. Bởi vì G là β-đơn điệu mạnh, nên 〈uk − x∗, G(uk)〉 = 〈uk − x∗, G(uk)−G(x∗)〉+ 〈uk − x∗, G(x∗)〉 ≥ β‖uk − x∗‖2 + 〈uk − x∗, G(x∗)〉. Chuyển qua giới hạn khi k →∞ và vì a = lim ‖uk − x∗‖2 ta thu được lim inf k→∞ 〈uk − x∗, G(uk)〉 ≥ βa. (2.66) Nếu a > 0, bằng cách chọn ǫ = 12βa, thì từ (2.66) ta suy ra, tồn tại k0 > 0 sao cho 〈uk − x∗, G(uk)〉 ≥ 1 2 βa, ∀k ≥ k0. Do (2.62) ta có ak+1 − ak ≤ −λkβa+ λ2kB, ∀k ≥ k0, lấy tổng liên tiếp từ k0 đến k ta được ak+1 − ak0 ≤ − k∑ j=k0 λjβa+B k∑ j=k0 λ2j . Mặt khác vì ∑∞ k=0 λk = ∞ và ∑∞ k=0 λ 2 k < ∞ nên ta suy ra lim inf ak = −∞. Ta gặp mâu thuẫn vì ak ≥ 0 ∀k. Vậy ta phải có a = 0. Tức là, limk→∞ ‖xk − x∗‖ = 0. Trường hợp 2. Tồn tại dãy con {aki}i≥0 ⊂ {ak}k≥0 sao cho aki < aki+1 với mọi i ≥ 0. Trong trường hợp này, ta xét dãy chỉ số {σ(k)} được xác định như trong Bổ đề 2.5. Khi đó ta có aσ(k)+1 − aσ(k) ≥ 0, kết hợp điều này với (2.63) dẫn đến ( ησ(k)δ ρ‖wσ(k)‖ )2 ‖xσ(k) − yσ(k)‖4 ≤ 2λσ(k)A+ λ2σ(k)B. Do đó lim k→∞ ( ησ(k)δ ρ‖wσ(k)‖ )2 ‖xσ(k) − yσ(k)‖4 = 0. Từ tính bị chặn của {xσ(k)}, không giảm tổng quát, ta giả sử xσ(k) → x¯. Theo Bổ đề 2.11 ta nhận được x¯ ∈ Sf . 73 Mặt khác, uσ(k) = PC∩Hσ(k)(xσ(k)) = PCσ(k)(xσ(k)), nên kết hợp với (2.52) ta suy ra ‖uσ(k) − x¯‖ ≤ ‖xσ(k) − x¯‖ → 0 khi k →∞, do đó limk→∞ uσ(k) = x¯. Từ (2.62) ta có 2λσ(k)〈uσ(k) − x∗, G(uσ(k))〉 ≤ aσ(k) − aσ(k)+1 − ( ησ(k)δ ρ‖wσ(k)‖ )2 ‖xσ(k) − yσ(k)‖4 + λ2σ(k)‖G(uσ(k))‖2 ≤ λ2σ(k)B, tức là 〈uσ(k) − x∗, G(uσ(k))〉 ≤ λσ(k) 2 B. (2.67) Vì G là β-đơn điệu mạnh, nên β‖uσ(k) − x∗‖2 ≤ 〈uσ(k) − x∗, G(uσ(k))−G(x∗)〉 = 〈uσ(k) − x∗, G(uσ(k))〉 − 〈uσ(k) − x∗, G(x∗)〉, kết hợp điều này với (2.67) ta suy ra ‖uσ(k) − x∗‖2 ≤ 1 β [λσ(k) 2 B − 〈uσ(k) − x∗, G(x∗)〉], bởi vậy lim k→∞ ‖uσ(k) − x∗‖2 ≤ − 1 β lim k→∞ 〈uσ(k) − x∗, G(x∗)〉 ≤ 0, từ đây suy ra lim k→∞ ‖uσ(k) − x∗‖ = 0. (2.68) Thêm vào đó, ‖xσ(k)+1 − uσ(k)‖ = ‖PC(uσ(k) − λσ(k)G(uσ(k)))− P(uσ(k))‖ ≤ λσ(k)‖G(uσ(k))‖ → 0 khi k →∞, kết hợp với (2.68), ta suy ra limk→∞ xσ(k)+1 = x∗, tức là limk→∞ aσ(k)+1 = 0. Theo (2.4) trong Bổ đề 2.5 ta có 0 ≤ ak ≤ aσ(k)+1 → 0 khi k →∞. Do đó {xk} hội tụ đến nghiệm duy nhất x∗ của bài toán VIEP(C, f,G). 74 2.5.3. Áp dụng vào bài toán bất đẳng thức biến phân hai cấp Trong mục này, ta xét một trường hợp riêng quan trọng của bài toán VIEP(C, f,G) là bài toán bất đẳng thức biến phân hai cấp BVIP(C,F,G) sau Tìm x∗ ∈ SF sao cho 〈G(x∗), y − x∗〉 ≥ 0 ∀y ∈ SF , (2.69) ở đó, SF = {u ∈ C : 〈F (u), y− u〉 ≥ 0, ∀y ∈ C}, tức là, SF là tập nghiệm của bài toán bất đẳng thức biến phân VIP(C,F ) sau: Tìm u ∈ C sao cho 〈F (u), y − u〉 ≥ 0 ∀y ∈ C, (2.70) trong đó F : Ω → Rn là toán tử xác định trên Ω. Trong trường hợp này, đặt f(x, y) = 〈F (x), y − x〉 thì bài toán BVIP(C,F,G) trở thành bài toán VIEP(C, f,G). Cần chú ý rằng, hàm f là giả đơn điệu theo tập S trên C khi và chỉ khi toán tử F là giả đơn điệu theo S trên C. Bằng cách chọn hàm h(x) = ‖x‖2 và áp dụng Thuật toán 2.5 cho bài toán BVIP(C,F,G) ta nhận được Thuật toán 2.6 sau Thuật toán 2.6. Bước khởi tạo. Chọn x0 ∈ C và các tham số η ∈ (0; 1), ρ > 0. Bước lặp thứ k (k = 0, 1, 2, ...). Có xk ta thực hiện các bước sau: Bước 1. Tính yk = PC(x k − ρ 2 F (xk)). Nếu yk = xk, thì đặt uk = xk và chuyển tới Bước 4. Ngược lại, chuyển sang Bước 2. Bước 2 (Quy tắc tìm kiếm theo tia Armijo). Tìm mk là số nguyên dương nhỏ nhất trong các số nguyên dương m thỏa mãn   zk,m = (1− ηm)xk + ηmyk : 〈F (zk,m), xk − yk〉 ≥ 1 ρ ‖yk − xk‖2. (2.71) 75 Bước 3. Đặt ηk = ηmk , zk = zk,mk , Ck = {x ∈ C : 〈F (zk), x− zk〉 ≤ 0}, và tính uk = PCk(xk). (2.72) Bước 4. Đặt xk+1 = PC(uk − λkG(uk)) và chuyển về Bước lặp thứ k với k được thay thế bởi k + 1. Áp dụng Định lý 2.3 vào Thuật toán 2.6 ta thu được hệ quả sau Hệ quả 2.5. Giả sử tập nghiệm SF của bài toán bất đẳng thức biến phân VIP(C,F ) là khác rỗng, toán tử F là liên tục trên Ω, giả đơn điệu theo tập SF trên C, toán tử G thỏa mãn giả thiết (A4) và dãy số {λk} thỏa mãn giả thiết (B2), thì dãy {xk} sinh bởi Thuật toán 2.6 hội tụ về nghiệm duy nhất x∗ của bài toán bất đẳng thức biến phân hai cấp BVIP(C,F,G). 76 KẾT LUẬN CHƯƠNG 2 Trong chương này, chúng tôi đã nghiên cứu phương pháp chiếu giải bài toán cân bằng giả đơn điệu và áp dụng vào một lớp bài toán cân bằng hai cấp. Các kết quả thu được bao gồm: (a) Xây dựng được thuật toán kiểu chiếu giải bài toán cân bằng giả đơn điệu theo tập nghiệm của nó (Thuật toán 2.1). Chứng minh được tính đúng đắn và sự hội tụ của thuật toán (Bổ đề 2.6 và Định lí 2.1). (b) Áp dụng Thuật toán 2.1 vào bài toán cân bằng Nash-Cournot trong mô hình cân bằng thị trường điện bán độc quyền. (c) Xây dựng được thuật toán kết hợp giữa thuật toán chiếu với kỹ thuật siêu phẳng cắt cho bài toán tìm cực tiểu của hàm chuẩn trên tập nghiệm của bài toán cân bằng giả đơn điệu MNEP(C, f) (Thuật toán 2.3). Bài toán này xuất hiện khi ta sử dụng phương pháp hiệu chỉnh Tikhonov cho bài toán cân bằng giả đơn điệu, chứng minh được tính đúng đắn và sự hội tụ của thuật toán (Bổ đề 2.7 và Định lí 2.2), đồng thời cũng xét đến trường hợp riêng là bài toán tìm hình chiếu của một điểm cho trước xuống tập nghiệm của bài toán bất đẳng thức biến phân giả đơn điệu. (d) Xây dựng được thuật toán lai ghép giữa thuật toán đạo hàm tăng cường với phương pháp siêu phẳng cắt giải bài toán bất đẳng thức biến phân đơn điệu mạnh trên tập nghiệm của bài toán cân bằng VIEP(C, f,G) (Thuật toán 2.5). Chứng minh được tính đúng đắn và sự hội tụ của thuật toán đã đưa ra (Bổ đề 2.7, Bổ đề 2.8, Bổ đề 2.9, Bổ đề 2.10 và Định lí 2.3), đồng thời đã áp dụng thuật toán đề xuất vào việc giải bài toán bất đẳng thức biến phân hai cấp (Thuật toán 2.6). 77 Chương 3 KẾT HỢP PHƯƠNG PHÁP HÀM PHẠT VÀ HÀM ĐÁNH GIÁ GIẢI BÀI TOÁN CÂN BẰNG HAI CẤP Trong chương này, chúng tôi sẽ xây dựng phương pháp giải cho một lớp bài toán cân bằng hai cấp (hay bài toán cân bằng trên tập nghiệm của bài toán cân bằng). Trước tiên, chúng tôi sử dụng phương pháp hàm phạt (penalty function method) để chuyển việc giải bài toán cân bằng hai cấp về giải một dãy các bài toán cân bằng phạt. Tiếp theo, chúng tôi sử dụng phương pháp hàm đánh giá (gap function method) để giải các bài toán cân bằng phạt. Chúng tôi sẽ chỉ ra rằng, nếu song hàm phạt hiệu chỉnh thỏa mãn các tính chất giả ∇-đơn điệu (pseudo ∇-monotonicity properties) thì bất kì điểm dừng (stationary point) của hàm đánh giá trên tập lồi C cũng là nghiệm của bài toán phạt. Cuối cùng, chúng tôi áp dụng phương pháp đã đề xuất vào bài toán nảy sinh khi sử dụng phương pháp hiệu chỉnh Tikhonov cho bài toán cân bằng giả đơn điệu. Nội dung của chương này dựa trên bài báo [1] trong Danh mục công trình khoa học của tác giả liên quan đến luận án. 3.1. Đặt bài toán Giả sử C là một tập lồi đóng trong không gian Rn và f, g : C×C → R là các song hàm cân bằng xác định trên C. Chúng tôi xét bài toán cân bằng hai cấp (bài toán cân bằng trên tập nghiệm của bài toán cân bằng) BEP(C, f, g) sau Tìm x∗ ∈ Sf sao cho g(x∗, y) ≥ 0, ∀y ∈ Sf , (3.1) 78 ở đó Sf = {u ∈ C : f(u, y) ≥ 0, ∀y ∈ C}, tức là, Sf là tập nghiệm của bài toán cân bằng sau Tìm u ∈ C sao cho f(u, y) ≥ 0, ∀y ∈ C. (3.2) Ta gọi (3.1) là bài toán cấp trên và (3.2) là bài toán cấp dưới. Bài toán cân bằng hai cấp BEP(C, f, g) là một bài toán khá tổng quát vì nó bao hàm nhiều lớp bài toán quan trọng. Bài toán bất đẳng thức biến phân hai cấp, một trường hợp riêng của bài toán (3.1) đã được quan tâm nghiên cứu trong các công trình [5, 34]. Bài toán bất đẳng thức biến phân trên tập nghiệm của bài toán cân bằng VIEP(C, f,G) mà ta đã xét trong mục 2.5 chương 2 cũng là một trường hợp riêng của bài toán (3.1) khi song hàm cân bằng g(x, y) = 〈G(x), y − x〉. Trong bài báo [45], A. Moudafi đã đề xuất sử dụng phương pháp điểm gần kề (proximal point method) cho bài toán cân bằng hai cấp đơn điệu BEP(C, f, g). Gần đây, X. P. Ding trong bài báo [26] đã sử dụng nguyên lý bài toán phụ cho bài toán BEP(C, f, g). Trong các bài báo này, các song hàm f và g đòi hỏi phải đơn điệu trên C. Trong tất cả các công trình này, bài toán cấp dưới luôn đòi hỏi là đơn điệu và do đó các bài toán phụ để giải luôn là các bài toán đơn điệu. Như ta đã biết, nếu song hàm f là giả đơn điệu trên C, thì tập nghiệm Sf của bài toán cấp dưới (3.2) là một tập lồi đóng khi f(x, .) là nửa liên tục dưới và lồi trên C với mỗi x cố định thuộc C. Tuy nhiên, sự khó khăn chính nằm ở chỗ, mặc dù tập ràng buộc Sf là lồi, nhưng nó không được cho dưới dạng tường minh như trong dạng chuẩn tắc của bài toán quy hoạch toán học, và do đó các phương pháp hiện có (xem [14, 41, 46, 47, 55, 56, 68] và các tài liệu trong đó) không thể áp dụng cho bài toán BEP(C, f, g) một cách trực tiếp. 3.2. Phương pháp hàm phạt Phương pháp hàm phạt (penalty function method) là một trong những công cụ cơ bản được sử dụng rộng rãi trong lý thuyết tối ưu để chuyển bài toán tối ưu có ràng buộc về bài toán tối ưu không ràng buộc hoặc có các ràng buộc 79 nhưng đơn giản hơn. Phương pháp này đã được áp dụng cho bài toán bất đẳng thức biến phân bởi tác giả L. D. Mưu (xem [50]) và cho bài toán cân bằng bởi L. D. Mưu và W. Oetli (xem [49]). Trong mục này, chúng tôi sử dụng phương pháp hàm phạt cho bài toán cân bằng hai cấp BEP(C, f, g) với f là song hàm giả đơn điệu theo tập nghiệm Sf của nó. Trước hết, để tiện theo dõi, ta nhắc lại rằng song hàm cân bằng ϕ : C ×C → R được gọi là đơn điệu mạnh trên C với hệ số β > 0 nếu ϕ(x, y) + ϕ(y, x) ≤ −β||x− y||2 ∀x, y ∈ C, và được gọi là thỏa mãn điều kiện bức (hay ngắn gọn là bức) trên C nếu tồn tại một tập con com pắc B ⊂ Rn và một véc tơ y0 ∈ B ∩ C sao cho ϕ(x, y0) < 0, ∀x ∈ C \B. Mệnh đề sau đây cho ta mối quan hệ giữa tính đơn điệu mạnh và tính bức của song hàm cân bằng ϕ. Mệnh đề 3.1. Giả sử song hàm cân bằng ϕ là đơn điệu mạnh trên C với hệ số β > 0, sao cho ϕ(x, .) là lồi và nửa liên tục dưới theo biến thứ hai với mọi x ∈ C, khi đó, với mỗi y ∈ C tồn tại một tập com pắc B sao cho y ∈ B và ϕ(x, y) < 0 ∀x ∈ C \B. Chứng minh. Ta chứng minh bằng phản chứng. Thật vậy, nếu kết luận của mệnh đề trên là không đúng thì tồn tại một phần tử y0 ∈ C sao cho với mọi tập com pắc B có một phần tử xB ∈ C \ B sao cho ϕ(xB, y0) ≥ 0. Chọn B = B[y0; r] là hình cầu đóng tâm tại điểm y0 và bán kính r với r > 1, suy ra, có điểm xr ∈ C \B[y0; r] sao cho ϕ(xr, y0) ≥ 0 (3.3) Gọi x là giao điểm của đoạn thẳng [y0, xr] với mặt cầu đơn vị S(y0; 1) có tâm tại y0 và bán kính 1. Khi đó ta có, xr = y0 + t(r)(x − y0), với t(r) > r. Do ϕ là đơn điệu mạnh trên C với hệ số β và kết hợp với (3.3) ta được ϕ(y0, xr) ≤ −ϕ(xr, y0)− β||xr − y0||2 = −ϕ(xr, y0)− βt(r)2||x− y0||2 ≤ −βt(r)2||x− y0||2. (3.4) 80 Mặt khác ϕ(y0, .) là hàm lồi trên C, nên ϕ(y0, x) = ϕ(y0, 1 t(r) xr + (1− 1 t(r) )y0) ≤ 1 t(r) ϕ(y0, xr) + t(r)− 1 t(r) ϕ(y0, y0) = 1 t(r) ϕ(y0, xr), kết hợp với (3.4) ta suy ra ϕ(y0, x) ≤ −βt(r)||x− y0||2 ≤ −βr. Do đó ϕ(y0, x)→ −∞ khi r→∞. (3.5) Theo giả thiết ϕ(y0, .) là hàm số nửa liên tục dưới trên C nên theo Định lý Weierstrass, ϕ(y0, .) đạt cực tiểu trên tập compắc S(y0; 1) ∩ C. Điều này là mâu thuẫn với (3.5). Từ Mệnh đề trên, ta rút ra các hệ quả sau Hệ quả 3.1. ([36, Proposition 2.1.16]) Nếu song hàm cân bằng ϕ là đơn điệu mạnh trên C, và ϕ(x, .) là lồi, nửa liên tục dưới theo biến thứ hai với mỗi x ∈ C, thì ϕ là bức trên C. Hệ quả 3.2. Giả sử song hàm cân bằng g là đơn điệu mạnh trên C sao cho g(x, .) là lồi, nửa liên tục dưới theo biến thứ hai với mỗi x ∈ Cvà song hàm cân bằng f là bức trên C, thì với mọi số ǫ > 0, song hàm cân bằng f + ǫg là bức đều theo ǫ trên C, tức là, tồn tại một điểm y0 ∈ C và một tập com pắc B không phụ thuộc vào ǫ sao cho f(x, y0) + ǫg(x, y0) < 0 ∀x ∈ C \B. Chứng minh. Theo giả thiết, hàm f bức trên C, nên tồn tại tập com pắc B1 và điểm y0 ∈ C sao cho f(x, y0) < 0 ∀x ∈ C \B1. Do g là đơn điệu manh, lồi và nửa liên tục dưới trên C nên bằng cách chọn y = y0, từ Mệnh đề 3.1, ta suy ra tồn tại com pắc B2 sao cho g(x, y0) < 0 ∀x ∈ C \B2. Đặt B = B1 ∪B2. Khi đó, B là tập com pắc và ta có f(x, y0) + ǫg(x, y0) < 0 ∀x ∈ C \B. Nhận xét 3.1. Hai song hàm cân bằng f và g là bức và giả đơn điệu trên C, thì tổng của nó f + g không nhất thiết là bức và giả đơn điệu trên C. Để minh chứng cho điều đó, ta xét ví dụ sau 81 Ví dụ 3.1. Xét hai song hàm cân bằng f(x, y) = (x2y1 − x1y2)ex2 g(x, y) = (x1y2 − x2y1)ex1 xác định trên tập C × C với C = {(x1, x2)T ∈ R2 : −1 ≤ x1, 1 10 (x1 − 9) ≤ x2 ≤ 10x1 + 9}. Khi đó, ta có (a) f(x, y), g(x, y) là giả đơn điệu và bức trên C; (b) Với mọi số ǫ > 0 hàm fǫ(x, y) = f(x, y) + ǫg(x, y) không là giả đơn điệu và cũng không thỏa mãn điệu kiện bức trên C. Thật vậy, (a) Nếu (x, y) ∈ C × C và f(x, y) ≥ 0 thì rõ ràng ta có f(y, x) ≤ 0, do đó f là giả đơn điệu trên C. Bằng cách chọn y0 = (0, y02)T , (0 < y02 ≤ 1) và tập B = {(x1, x2)T : x21 + x 2 2 ≤ r} (r > 1) thì B là tập compắc và ta có f(x, y0) = −x1y02ex1 < 0 ∀x ∈ C \B. Vậy f thỏa mãn điều kiện bức trên C. Hoàn toàn tương tự, ta cũng chứng minh được hàm g là giả đơn điệu và bức trên C. (b) Với mỗi số ǫ > 0, theo định nghĩa của hàm fǫ, ta có fǫ(x, y) = (x2y1 − x1y2)(ex2 − ǫex1). Chọn x(t) = (t, kt)T , y(t) = (kt, t)T với 1 < k < 10 thì x(t), y(t) ∈ C, ∀t > 0 và fǫ(x(t), y(t)) = (k2−1)t2(ekt−ǫet) > 0, nhưng fǫ(y(t), x(t)) = −(k2 − 1)t2(et − ǫekt) > 0 với t đủ lớn. Do đó fǫ không là giả đơn điệu 82 trên C. Bây giờ ta sẽ chỉ ra song hàm fǫ(x, y) = (x2y1−x1y2)(ex2 − ǫex1) không thỏa mãn điều kiện bức trên C. Thật vậy, bằng phản chứng, nếu fǫ là bức ở trên C thì phải tồn tại một tập com pắc B và y0 = (y01 , y02)T ∈ B ∩ C sao cho fǫ(x, y 0) = (x2y 0 1 − x1y02)(ex2 − ǫex1) < 0 ∀x ∈ C \B. (3.6) Bằng cách chọn x = x(t) = (t, kt)T thì (3.6) trở thành fǫ(x(t), y 0) = t(ky01 − y02)(ekt − ǫet) < 0 ∀x(t) ∈ C \B. (3.7) Ta xét các khả năng sau: - Nếu y01 = y02 thì bằng cách chọn k = 1 suy ra x(t) ∈ C \B với t đủ lớn và (3.7) trở thành 0 < 0 vô lý. - Nếu y01 0 thì bằng cách chọn 110 < k < 1 suy ra x(t) ∈ C \B và fǫ(x(t), y0) > 0 với t đủ lớn, điều này mâu thuẫn với (3.7). Hoàn toàn tương tự nếu y02 0 ta cũng suy ra mâu thuẫn. - Nếu y01 > y02 > 0, thì từ 1 0 với t đủ lớn, điều này mâu thuẫn với (3.7). - Nếu 0 < y01 < y02 , thì bằng cách chọn 110 < k < 1 ta được x(t) ∈ C và fǫ(x(t), y 0) > 0 với t đủ lớn. Mâu thuẫn với (3.7). - Nếu y01 < y02 < 0 hoặc y02 < y01 < 0 thì tương tự như trên ta cũng suy ra mâu thuẫn. Vậy fǫ không thỏa mãn điều kiện bức ở trên C. Bây giờ với mỗi số ǫ > 0 cố định, đặt fǫ = f + ǫg, ta xét bài toán cân bằng phạt (penalized equilibrium problem), viết tắt là PEP(C, fǫ) được xác định như sau Tìm x¯ǫ ∈ C sao cho fǫ(x¯ǫ, y) = f(x¯ǫ, y) + ǫg(x¯ǫ, y) ≥ 0 ∀y ∈ C. (3.8) 83 Tập nghiệm của bài toán phạt PEP(C, fǫ) được kí hiệu là Sfǫ . Định lý sau đây cho ta mối liên hệ giữa bài toán phạt và bài toán ban đầu. Định lí 3.1. Giả sử các song hàm cân bằng f, g là giả đơn điệu, nửa liên tục trên theo biến thứ nhất và nửa liên tục dưới, lồi theo biến thứ hai trên C. Khi đó bất kì điểm tụ nào của dãy {xk} với xk ∈ Sfǫk với mọi k, khi ǫk → 0 đều là nghiệm của bài toán cân bằng hai cấp ban đầu. Thêm vào đó, nếu hàm g là đơn điệu mạnh và hàm f là bức ở trên C, thì với mỗi ǫk > 0 bài toán phạt PEP(C, fǫk) có nghiệm và bất kì dãy {xk} với xk ∈ Sfǫk đều hội tụ tới nghiệm duy nhất của bài toán hai cấp (3.1) khi ǫk → 0. Chứng minh. Giả sử {xk} là một dãy bất kì với {xk} ∈ Sfǫk và x¯ là một điểm tụ bất kì của dãy {xk}. Không giảm tổng quát, ta giả sử xk → x¯ khi ǫk → 0. Vì xk là nghiệm của bài toán phạt PEP(C, fǫk ) nên ta có f(xk, y) + ǫkg(x k, y) ≥ 0 ∀ y ∈ C. (3.9) Với mỗi z ∈ Sf , ta có f(z, y) ≥ 0 ∀y ∈ C, đặc biệt là, f(z, xk) ≥ 0. Mà f là giả đơn điệu trên C theo tập Sf nên suy ra f(xk, z) ≤ 0. Thay thế y bởi z trong (3.9) ta thu được f(xk, z) + ǫkg(x k, z) ≥ 0, từ đây suy ra ǫkg(x k, z) ≥ −f(xk, z) ≥ 0⇒ g(xk, z) ≥ 0. Chuyển qua giới hạn khi ǫk → 0, do tính nửa liên tục trên của g, ta thu được g(x¯, z) ≥ 0 ∀z ∈ Sf . Để hoàn thành chứng minh ta còn phải chỉ ra x¯ ∈ Sf . Thật vậy, với bất kỳ y cố định thuộc C ta có f(xk, y) + ǫkg(x k, y) ≥ 0. Cũng giống như trên, do f và g là nửa liên tục trên, nên chuyển qua giới hạn bất đẳng thức trên khi ǫk → 0, ta suy ra f(x¯, y) ≥ 0. Do đó f(x¯, y) ≥ 0 ∀y ∈ C hay x¯ ∈ Sf . Giả sử thêm rằng hàm g là đơn điệu mạnh và hàm f là bức ở trên C, thì theo Hệ quả 3.2, hàm fǫk là bức đều trên C. Do đó, bài toán PEP(C, fǫk ) luôn 84 có nghiệm với mọi ǫk > 0, hơn nữa, tập nghiệm của những bài toán phạt này được chứa trong một tập com pắc B cố định với mọi ǫk. Do đó, bất kì dãy vô hạn {xk} nào (với xk là nghiệm của bài toán phạt PEP(C, fǫk )) cũng có điểm tụ, chẳng hạn, x¯. Không mất tính tổng quát, ta giả sử xk → x¯ khi ǫk → 0. Mặt khác, từ các giả thiết của hàm f ta suy ra, tập nghiệm Sf của bài toán cân bằng cấp dưới EP(C, f) là một tập lồi, đóng, com pắc và hàm g là nửa liên tục dưới, lồi theo biến thứ hai và đơn điệu mạnh trên Sf , do đó bài toán cân bằng hai cấp BEP(C, f, g) có nghiệm duy nhất. Theo chứng minh trên, nghiệm duy nhất này phải là điểm giới hạn của bất kì dãy {xk} với xk là nghiệm của bài toán phạt PEP(C, fǫk ). Tức là, limǫk→0 xk = x¯. Nhận xét 3.2. Định lý 3.1 giúp ta chuyển việc giải bài toán cân bằng hai cấp BEP(C, f, g) về giải một dãy các bài toán phạt PEP(C, fǫ). Một trường hợp riêng của bài toán cân bằng hai cấp BEP(C, f, g) được A. Moudafi xét đến trong [45], khi cả hai hàm f và g là đơn điệu, khi đó bài toán phạt PEP(C, fǫ) cũng là đơn điệu. Trong trường hợp này, bài toán phạt PEP(C, fǫ) có thể được giải bởi các phương pháp hiện có chẳng hạn như trong các công trình [44, 46, 47, 55, 56, 68] và các tài liệu trích dẫn trong đó. Tuy nhiên, nếu một trong hai song hàm này là giả đơn điệu thì bài toán phạt PEP(C, fǫ) , trong trường hợp tổng quát, không thừa hưởng bất kì tính chất đơn điệu nào từ f và g. Do vậy, trong trường hợp này, Bài toán phạt PEP(C, fǫ) không thể giải được bằng những phương pháp có sử dụng tính chất đơn điệu như đã đề cập ở trên. 3.3. Hàm đánh giá và hướng giảm Một trong những công cụ hữu hiệu nổi tiếng để giải bài toán bất đẳng thức biến phân và bài toán cân bằng là phương pháp hàm đánh giá (gap function method). Ý tưởng chính của phương pháp hàm đánh giá đó là tìm cách chuyển việc giải bài toán bất đẳng thức biến phân hay bài toán cân bằng về giải một bài toán tối ưu tương ứng của một hàm số thích hợp được gọi là hàm đánh giá. Hàm đánh giá đầu tiên cho bất đẳng thức biến phân được giới thiệu bởi A. Auslender trong [8]. Hàm đánh giá hiệu chỉnh cho bài toán bất đẳng thức biến phân được đề xuất bởi M. Fukushima trong [30] và một cách độc lập bởi 85 G. Auchumuty trong [7] và được G. Mastroeni mở rộng ra cho bài toán cân bằng [42]. Trong mục này, chúng tôi sử dụng hàm đánh giá hiệu chỉnh cho bài toán cân bằng phạt PEP(C, fǫ). Như chúng tôi đã đề cập ở trên, ngay cả với khi hàm f là giả đơn điệu và hàm g là đơn điệu mạnh, thì bài toán cân bằng hai cấp BEP(C, f, g) vẫn còn rất khó để giải. Trong mục này, chúng tôi giả thiết rằng các hàm f và g là nửa liên tục dưới, lồi trên C theo biến thứ hai. Trước tiên, chúng tôi nhắc lại khái niệm về hàm đánh giá cho bài toán cân bằng (xem [42]). Định nghĩa 3.1. Hàm ϕ : C → R ∪ {+∞} được gọi là một hàm đánh giá (gap function) cho bài toán PEP(C, fǫ) nếu (a) ϕ(x) ≥ 0 ∀x ∈ C; (b) ϕ(x¯) = 0 khi và chỉ khi x¯ là nghiệm của bài toán PEP(C, fǫ). Hàm ϕ(x) = −miny∈C fǫ(x, y) rõ ràng là một hàm đánh giá cho bài toán PEP(C, fǫ). Hàm đánh giá này có thể không xác định hữu hạn và trong trường hợp tổng quát, nó không khả vi. Để có được hàm đánh giá hữu hạn và khả vi, chúng tôi sử dụng kỹ thuật hiệu chỉnh được giới thiệu trong [7, 30] cho bài toán bất đẳng thức biến phân, và gần đây được sử dụng bởi Mastroeni trong [42] cho bài toán cân bằng. Từ Mệnh đề 2.1 và Định lý 2.1 trong [42] ta có mệnh đề sau. Mệnh đề 3.2. Giả sử l : C × C → R là hàm số khả vi, không âm, lồi mạnh theo biến thứ hai trên C và thỏa mãn các điều kiện sau (a) l(x, x) = 0 ∀x ∈ C; (b) ∇yl(x, x) = 0 ∀x ∈ C. Khi đó, hàm ϕǫ(x) = −min y∈C [f(x, y) + ǫ[g(x, y) + l(x, y)]] là một hàm đánh giá hữu hạn cho bài toán PEP(C, fǫ). Nếu thêm vào đó, các song hàm cân bằng f và g là khả vi theo biến thứ nhất sao cho ∇xf(x, y),∇xg(x, y) 86 là hàm liên tục trên C × C, thì ϕǫ(x) là hàm khả vi trên C và ∇ϕǫ(x) = −∇xf(x, yǫ(x))− ǫ∇x[g(x, yǫ(x)) + l(x, yǫ(x))] = −∇xgǫ(x, yǫ(x)), ở đó gǫ(x, y) = f(x, y) + ǫ[g(x, y) + l(x, y)] và yǫ(x) = argmin y∈C {gǫ(x, y)}. Chú ý rằng hàm l(x, y) = 12 〈M(y − x), y − x〉, với M là một ma trận đối xứng xác định dương cấp n thỏa mãn tất cả các giả thiết về hàm l. Ta cần các định nghĩa sau về tính ∇-đơn điệu. Định nghĩa 3.2. Song hàm cân bằng khả vi f : C × C → R được gọi là: (a) ∇-đơn điệu mạnh (strongly ∇-monotone) trên C nếu tồn tại hằng số τ > 0 sao cho: 〈∇xf(x, y) +∇yf(x, y), y − x〉 ≥ τ ||y − x||2 ∀x, y ∈ C; (b) ∇-đơn điệu chặt (strictly ∇-monotone) trên C nếu 〈∇xf(x, y) +∇yf(x, y), y − x〉 > 0 ∀x, y ∈ C và x 6= y; (c) ∇-đơn điệu (∇-monotone) trên C nếu 〈∇xf(x, y) +∇yf(x, y), y − x〉 ≥ 0 ∀x, y ∈ C; (d) giả ∇-đơn điệu chặt (strictly pseudo ∇-monotone) trên C nếu 〈∇xf(x, y), y − x〉 ≤ 0 =⇒ 〈∇yf(x, y), y − x〉 > 0 ∀x, y ∈ C, x 6= y; (e) giả ∇-đơn điệu (pseudo ∇-monotone) trên C nếu 〈∇xf(x, y), y − x〉 ≤ 0 =⇒ 〈∇yf(x, y), y − x〉 ≥ 0 ∀x, y ∈ C. Nhận xét 3.3. Các định nghĩa (a), (b), (c) có thể được tìm thấy trong các công trình, chẳng hạn [14, 42]. Các định nghĩa (d) và (e), như sự hiểu biết của chúng tôi, chưa được đưa ra trước đây. Từ các định nghĩa trên, ta thấy (a)⇒ (b)⇒ (c)⇒ (e) và (a)⇒ (b)⇒ (d)⇒ (e). Tuy nhiên, (c) có thể không kéo theo (d) và ngược lại, (d) có thể không suy ra (c) như trong các ví dụ sau. 87 Ví dụ 3.2. Xét song hàm f(x, y) = ex 2 (y2 − x2) xác định trên C × C với C = R. Song hàm này không là ∇-đơn điệu trên C, vì ta có 〈∇xf(x, y) +∇yf(x, y), y − x〉 = 2ex 2 (y − x)2(x2 + xy + 1) ∀x, y, nên 〈∇xf(−1, 3) +∇yf(−1, 3),−1− 3〉 = −32e < 0. Nhưng f(x, y) là giả ∇-đơn điệu chặt trên C. Thật vậy, xét 〈∇xf(x, y), y − x〉 = 2xex 2 (y2 − x2 − 1)(y − x) ≤ 0 ⇔ x(y2 − x2 − 1)(y − x) ≤ 0, 〈∇yf(x, y), y − x〉 = 2yex2(y − x) > 0⇔ y(y − x) > 0. Rõ ràng x(y2 − x2 − 1)(y − x) ≤ 0⇒ y(y − x) > 0 với mọi x 6= y. Do đó, hàm f là giả ∇-đơn điệu chặt, nhưng không là ∇-đơn điệu trên C. Ngược lại, với song hàm f(x, y) = (y − x)TM(y − x) xác định trên C × C với C = Rn và M là ma trận thực cấp n× n. Ta có (a) f là ∇-đơn điệu trên C, bởi vì 〈∇xf(x, y) +∇yf(x, y), y − x〉 = 〈−(M +MT )(y − x) + (M +MT )(y − x), y − x〉 = 0 ∀x, y. Suy ra f không là ∇-đơn điệu chặt trên C. (b) f là ∇-giả đơn điệu chặt trên C khi và chỉ khi 〈∇xf(x, y), y − x〉 = −〈(M +MT )(y − x), y − x〉 ≤ 0 kéo theo 〈∇yf(x, y), y − x〉 = 〈(M +MT )(y − x), y − x〉 > 0 ∀x, y, x 6= y. Bất đẳng thức này xảy ra khi và chỉ khi M +MT là ma trận xác định dương cấp n × n. Do đó, nếu M +MT không phải là ma trận xác định dương thì hàm f(x, y) = (y−x)TM(y−x) là ∇-đơn điệu trên Rn nhưng không là giả ∇-đơn điệu chặt trên đó. 88 Nhận xét 3.4. Như đã chỉ ra trong công trình [14] khi f(x, y) = 〈F (x), y−x〉 với F là một ánh xạ khả vi trên C, thì f là đơn điệu trên C khi và chỉ khi F là đơn điệu trên C, và trong trường hợp này, tính đơn điệu của f trên C và tính ∇-đơn điệu của f trên C là trùng nhau. Ví dụ dưới đây chỉ ra rằng, tính giả đơn điệu có thể không kéo theo tính giả ∇-đơn điệu. Ví dụ 3.3. Xét hàm f(x, y) = −ax(y − x), xác định trên R+ × R+, (a > 0). Khi đó f(x, y) ≥ 0 =⇒ f(y, x) ≤ 0 ∀x, y ≥ 0. Do vậy f là giả đơn điệu trên R+. Ta có 〈∇xf(x, y), y − x〉 = −a(y − x)(y − 2x) 2x > 0. Nhưng 〈∇yf(x, y), y − x〉 = −ax(y − x) 2x > 0. Do đó f không là giả ∇-đơn điệu trên R+. Từ định nghĩa của hàm đánh giá ta suy ra một điểm cực tiểu toàn cục của hàm đánh giá ϕǫ trên C là một nghiệm của bài toán cân bằng phạt PEP(C, fǫ). Do ϕǫ không phải là hàm lồi, nên trong trường hợp tổng quát việc tìm cực tiểu toàn cục của nó trên C là rất khó khăn. Do đó, để có thể tìm được cực tiểu toàn cục của nó, người ta thường cần thêm một số tính chất bổ sung áp đặt lên song hàm cân bằng. Trong bài báo [14] các tác giả đã chỉ ra rằng, nếu song hàm cân bằng là ∇-đơn điệu chặt thì bất kì một điểm dừng (stationary point) của hàm đánh giá cũng là nghiệm cực tiểu toàn cục của nó. Bằng phản ví dụ, các tác giả đó cũng đã chỉ ra rằng tính chất này không còn đúng trong trường hợp song hàm là ∇-đơn điệu. Định lý sau đây sẽ chỉ ra rằng tính chất dừng này (stationary property) vẫn còn đúng nếu song hàm là giả ∇-đơn điệu chặt. Định lí 3.2. Giả sử gǫ là giả ∇-đơn điệu chặt trên C và x¯ là một điểm dừng của hàm đánh giá ϕǫ trên C, tức là 〈∇ϕǫ(x¯), y − x¯〉 ≥ 0 ∀y ∈ C, 89 thì x¯ là nghiệm của bài toán phạt PEP(C, fǫ). Chứng minh. Ta chứng minh bằng phản chứng. Nếu x¯ không phải là nghiệm của bài toán PEP(C, fǫ), thì yǫ(x¯) 6= x¯. Do x¯ là điểm dừng của ϕǫ trên C, nên từ định nghĩa của hàm ϕǫ, ta có 〈∇ϕǫ(x¯), yǫ(x¯)− x¯〉 = −〈∇xgǫ(x¯, yǫ(x¯)), yǫ(x¯)− x¯〉 ≥ 0 Do gǫ là giả ∇-đơn điệu chặt trên C nên 〈∇ygǫ(x¯, yǫ(x¯)), yǫ(x¯)− x¯〉 > 0. (3.10) Mặt khác, vì yǫ(x¯) là điểm cực tiểu của hàm gǫ(x¯, .) trên C, ta suy ra 〈∇ygǫ(x¯, yǫ(x¯)), yǫ(x¯)− x¯〉 ≤ 0, điều này mâu thuẫn với (3.10). Do đó, x¯ là nghiệm của bài toán PEP(C, fǫ). Để tìm điểm dừng của một hàm khả vi trên một tập lồi đóng, ta có thể sử dụng các thuật toán đã có trong quy hoạch toán học, như các thuật toán hướng giảm (descent direction algorithms) (xem [12, Section 2]). Mệnh đề sau đây chỉ ra rằng nếu y(x) là nghiệm của bài toán tối ưu miny∈C gǫ(x, y), thì y(x)− x là một hướng giảm của hàm ϕǫ trên C tại x. Mệnh đề 3.3. Giả sử gǫ là giả ∇-đơn điệu chặt trên C và x không phải là nghiệm của bài toán PEP(C, fǫ), thì 〈∇ϕǫ(x), yǫ(x)− x〉 < 0. Chứng minh. Đặt dǫ(x) = yǫ(x)− x. Do x không phải là nghiệm của bài toán PEP(C, fǫ), nên dǫ(x) 6= 0. Do đó, nếu dǫ(x) không phải là một hướng giảm của hàm ϕǫ tại x trên C, thì 〈∇ϕǫ(x), yǫ(x)− x〉 ≥ 0 ⇔ −〈∇xgǫ(x, yǫ(x)), yǫ(x)− x〉 ≥ 0, kết hợp với gǫ là giả ∇-đơn điệu chặt trên C, ta suy ra 〈∇ygǫ(x, yǫ(x)), yǫ(x)− x〉 > 0. (3.11) Mặt khác, yǫ(x) là điểm cực tiểu của hàm gǫ(x, .) trên C, nên theo điều kiện tối ưu, ta có 〈∇ygǫ(x, yǫ(x)), yǫ(x)− x〉 ≤ 0 90 điều này mâu thuẫn với (3.11). Vậy ta phải có 〈∇ϕǫ(x), yǫ(x)− x〉 < 0. Mệnh đề 3.4. Giả sử C là tập com pắc, f, g là các song hàm khả vi liên tục trên C ×C sao cho f(x, .) là lồi chặt trên C với mỗi x ∈ C và f là giả ∇-đơn điệu chặt trên C. Khi đó, nếu x ∈ C không là nghiệm của bài toán EP(C, f), thì tồn tại số ǫ¯ > 0 sao cho yǫ(x)− x là một hướng giảm của hàm ϕǫ trên C tại x với mọi 0 < ǫ ≤ ǫ¯. Chứng minh. Ta chứng minh bằng phản chứng. Nếu khẳng định của mệnh đề trên là không đúng thì tồn tại dãy {ǫk} sao cho ǫk ց 0 và điểm x ∈ C thỏa mãn 〈∇ϕǫk(x), yǫk(x)− x〉 ≥ 0 ∀k. Hay −〈∇xgǫk(x, yǫk(x)), yǫk(x)− x〉 ≥ 0 ∀k. (3.12) Do gǫ(x, .) là hàm lồi chặt và khả vi trên C, nên theo Định lý 2.1 trong [19], hàm ǫ 7→ yǫ(x) là liên tục theo ǫ, do đó yǫk(x) hội tụ tới y0(x) khi ǫk → 0, với y0(x) = argminy∈C f(x, y). Vì x không là nghiệm của bài toán EP(C, f) nên y0(x) 6= x. Bởi vì gǫk(x, y) = f(x, y) + ǫk[g(x, y) + l(x, y)] là hàm khả vi liên tục, nên cho ǫk → 0 trong (3.12) ta thu được −〈∇xf(x, y0(x)), y0(x)− x〉 ≥ 0. Mà theo giả thiết f là giả ∇-đơn điệu chặt, nên 〈∇yf(x, y0(x)), y0(x)− x〉 > 0. (3.13) Mặt khác, từ yǫk(x) là điểm cực tiểu của hàm gǫk(x, .) trên C, ta suy ra 〈∇ygǫk(x, yǫk(x)), yǫk(x)− x〉 ≤ 0. Chuyển qua giới hạn khi ǫk → 0 ta được 〈∇yf(x, y0(x)), y0(x)− x〉 ≤ 0, điều này mâu thuẫn với (3.13). 91 Các ví dụ dưới đây, chỉ ra các giả thiết của Định lý 3.2 được thỏa mãn. Ví dụ 3.4. Xét hai song hàm f và g cho bởi f(x, y) = ex 2 (y2 − x2) và g(x, y) = 10x 2 (y2 − x2) xác định trên R×R. Khi đó ta có (a) f(x, y), g(x, y) là đơn điệu, và giả ∇-đơn điệu chặt trên R (b) Với mọi ǫ > 0 song hàm f(x, y) + ǫg(x, y) là đơn điệu, giả ∇-đơn điệu chặt trên R và thỏa mãn các giả thiết của Định lý 3.2. Ví dụ 3.5. Xét hai song hàm f(x, y) = −3x2y + xy2 + 2y3 và g(x, y) = −x2 − xy + 2y2 xác định trên R+ × R+, thì ta có (a) f, g là giả đơn điệu, ∇-đơn điệu chặt trên R+; (b) Với mọi ǫ > 0 song hàm f(x, y) + ǫg(x, y) là giả đơn điệu, ∇-đơn điệu chặt trên R+ và thỏa mãn các giả thiết của Định lý 3.2. 3.4. Áp dụng vào phương pháp hiệu chỉnh Tikhonov Phương pháp hiệu chỉnh Tikhonov là một trong những phương pháp cơ bản thường được sử dụng để giải các bài toán đặt không chỉnh (ill-posed problems). Gần đây, các tác giả P. G. Hưng và L. D. Muu (xem [32]) đã mở rộng phương pháp hiệu chỉnh Tikhonov cho bài toán cân bằng giả đơn điệu Tìm x∗ ∈ C sao cho f(x∗, y) ≥ 0 ∀y ∈ C, ở đó, cũng giống như trước đây, C là một tập lồi đóng trong Rn và f : C×C → R là song hàm giả đơn điệu trên C. 92 Theo phương pháp hiệu chỉnh Tikhonov được nghiên cứu trong [32], bài toán EP(C, f) được hiệu chỉnh bởi một họ các bài toán cân bằng EP(C, fǫ) Tìm x∗ǫ ∈ C sao cho fǫ(x∗ǫ , y) := f(x∗ǫ , y) + ǫg(x∗ǫ , y) ≥ 0 ∀y ∈ C, với g là một song hàm cân bằng trên C và ǫ > 0, đóng vai trò là song hàm hiệu chỉnh và tham số hiệu chỉnh. Định lý sau đã được chứng minh trong bài báo [32] . Định lí 3.3. Giả sử f(., y), g(., y) là nửa liên tục trên theo x, sao cho f(x, .), g(x, .) là lồi, nửa liên tục dưới trên C theo y và hàm f là giả đơn điệu trên C. Giả sử thêm rằng g là đơn điệu mạnh trên C và thỏa mãn điều kiện ∃δ > 0 |g(x, y)| ≤ δ‖x− xg‖‖y − x‖ ∀x, y ∈ C, (3.14) ở đó xg ∈ C là điểm cho trước (thường đóng vai trò là nghiệm phỏng đoán). Khi đó, các phát biểu sau là tương đương (a) Tập nghiệm của EP(C, fε) là khác rỗng với mỗi ε > 0 và tồn tại limε→0+ x(ε), ở đó x(ε) là một nghiệm bất kì của bài toán EP(C, fε); (b) Tập nghiệm của bài toán EP(C, fε) là khác rỗng với mỗi ε > 0 và limε→0+ sup ‖x(ε)‖ < ∞, với x(ε) là một điểm bất kì trong tập nghiệm của bài toán EP(C, fε); (c) Tập nghiệm của bài toán EP(C, f) là khác rỗng. Hơn nữa, nếu một trong số các phát biểu trên là đúng, thì limε→0+ x(ε) là nghiệm duy nhất của bài toán cân bằng đơn điệu mạnh EP(Sf , g), ở đó Sf là tập nghiệm của bài toán cân bằng EP(C, f) ban đầu. Chú ý rằng, nếu f là đơn điệu trên C, thì hàm hiệu chỉnh là đơn điệu mạnh, và do đó ta có thể giải nó bằng một số phương pháp hiện có (xem [46, 55, 56]) điều này giúp cho việc tìm quỹ đạo Tikhonov có thể thực hiện được, tuy nhiên khi f là giả đơn điệu, thì các bài toán hiệu chỉnh, trong trường hợp tổng quát, không còn là đơn điệu mạnh, hay đơn điệu, thậm chí không là giả đơn điệu. Do đó, việc giải nó là một nhiệm vụ rất khó khăn. Mặc dù vậy, từ định lý trên 93 ta có thể chuyển việc tìm điểm giới hạn của dãy nghiệm của các bài toán hiệu chỉnh về việc giải bài toán cân bằng hai cấp BEP(C, f, g). Để áp dụng phương pháp hàm phạt và phương pháp hàm đánh giá ở các mục ở trên, ta có thể chọn song hàm hiệu chỉnh g thỏa mãn các giả thiết của Định lý 3.3, chẳng hạn như., g(x, y) = 〈x− xg, y − x〉 Rõ ràng, g là đơn điệu mạnh và ∇-đơn điệu mạnh với cùng hệ số 1. Hơn nữa, g thỏa mãn điều kiện (3.14). Do đó, bài toán tìm điểm giới hạn của dãy nghiệm của bài toán hiệu chỉnh trong phương pháp hiệu chỉnh Tikhonov ở trên có thể được phát biểu dưới dạng bài toán cân bằng hai cấp như sau Tìm x∗ ∈ Sf sao cho g(x∗, y) ≥ 0 ∀y ∈ Sf , (3.15) đây là bài toán có dạng (3.1). Bây giờ, với mỗi số ǫk > 0 cố định, ta xét bài toán cân bằng phạt PEP(C, fǫk) được xác định như sau Tìm x¯k ∈ C sao cho fǫk(x¯k, y) = f(x¯k, y) + ǫkg(x¯k, y) ≥ 0 ∀y ∈ C. (3.16) Cũng như trước đây, ta kí hiệu Sfǫk là tập nghiệm của bài toán PEP(C, fǫk). Áp dụng Định lý 3.1 và Định lý 3.2 ta nhận được hệ quả sau. Hệ quả 3.3. Giả sử song hàm f thỏa mãn các điều kiện (a) f(x, .) là lồi, nửa liên tục dưới ∀x ∈ C; (b) f là giả đơn điệu và bức trên C. Khi đó, với bất kì ǫk > 0 bài toán phạt PEP(C, fǫk ) luôn có nghiệm và bất kì dãy {xk} trong đó xk ∈ Sfǫk với mọi k, đều hội tụ tới nghiệm duy nhất của bài toán (3.15) khi ǫk → 0. Nếu thêm vào đó, f(x, .) + ǫkg(x, .) là hàm lồi chặt trên C với mọi x ∈ C và f + ǫkg là giả ∇-đơn điệu chặt trên C (điều này được thỏa mãn, chẳng hạn khi, f(x, y) là ∇-đơn điệu), khi đó với x¯k là một điểm dừng bất kì của bài toán tối ưu minx∈C ϕk(x), ở đó ϕk(x) = min y∈C {f(x, y) + ǫkg(x, y)}, 94 thì {x¯k} hội tụ tới nghiệm duy nhất của bài toán (3.15) khi ǫk → 0. KẾT LUẬN CHƯƠNG 3 Trong chương này, chúng tôi đã đề xuất phương pháp hàm phạt giải bài toán cân bằng hai cấp, với hàm cân bằng cấp dưới là hàm giả đơn điệu theo tập nghiệm của nó và phương pháp hàm đánh giá giải bài toán phạt. Các kết quả đạt được bao gồm: (a) Để xuất phương pháp hàm phạt cho bài toán cân bằng hai cấp (3.1) (Mục 3.1). Chứng minh định lý về sự hội tụ của nghiệm của dãy các bài toán phạt tới nghiệm của bài toán cân bằng hai cấp ban đầu (Định lí 3.1). (b) Đề xuất phương pháp hàm đánh giá giải bài toán phạt (Mục 3.2). Mở rộng khái niệm giả ∇-đơn điệu từ khái niệm ∇-đơn điệu (Định nghĩa 3.2). (c) Chứng minh được rằng bất kì điểm dừng nào của hàm đánh giá cũng là nghiệm của bài toán cân bằng nếu song hàm cân bằng thỏa mãn giả thiết giả ∇-đơn điệu chặt (Định lí 3.2). Đồng thời chỉ ra hướng giảm của hàm đánh giá tại những điểm không phải là điểm dừng (Mệnh đề 3.3), cùng tính chất "độc lập" của hướng giảm đối với tham số phạt ǫ. (Mệnh đề 3.4). (d) Áp dụng các phương pháp đề xuất vào bài toán nảy sinh khi ta sử dụng phương pháp hiệu chỉnh Tikhonov cho bài toán cân bằng giả đơn điệu. 95 KẾT LUẬN 1. Kết quả đạt được Trong luận án này chúng tôi đã xây dựng một số phương pháp giải bài toán cân bằng giả đơn điệu và áp dụng vào một số lớp bài toán cân bằng hai cấp. Luận án đã đạt được các kết quả sau: (a) Xây dựng và chứng minh sự hội tụ của các thuật toán chiếu cho bài toán cân bằng giả đơn điệu và bài toán tìm cựu tiểu của hàm chuẩn Euclide trên tập nghiệm của bài toán cân bằng giả đơn điệu, đồng thời áp dụng thuật toán đề xuất vào mô hình Nash-Cournot trong vấn đề cân bằng thị trường điện bán độc quyền. Các kết quả này được thể hiện ở công trình [2]. (b) Xây dựng và chứng minh sự hội tụ của thuật toán lai ghép giữa thuật toán đạo hàm tăng cường và phương pháp siêu phẳng cắt cho bài toán bất đẳng thức biến phân đơn điệu mạnh trên tập nghiệm của bài toán cân bằng giả đơn điệu, đồng thời áp dụng vào bài toán bất đẳng thức biến phân hai cấp. Các kết quả này được thể hiện ở công trình [3]. (c) Đề xuất phương pháp hàm phạt cho bài toán cân bằng hai cấp và phương pháp hàm đánh giá giải bài toán phạt, mở rộng khái niệm giả ∇-đơn điệu và chứng minh được tính chất dừng của hàm đánh giá dưới giả thiết này. Áp dụng vào bài toán nảy sinh khi sử dụng phương pháp hiệu chỉnh Tikhonov cho bài toán cân bằng. Các kết quả này được thể hiện ở công trình [1]. 96 2. Kiến nghị một số hướng nghiên cứu tiếp theo Bên cạnh những kết quả đã đạt được trong luận án, một số vấn đề khác còn tồn tại cần được tiếp tục nghiên cứu, đó là: • Xây dựng thuật toán chiếu kết hợp với kỹ thuật siêu phẳng cắt cho bài toán VIEP(C, f,G). • Xây dựng thuật toán lai ghép giữa thuật toán đạo hàm tăng cường và phương pháp siêu phẳng cắt cho lớp bài toán BEP(C, f, g). • Nghiên cứu phương pháp hàm đánh giá giải bài toán EP(C, f) không trơn và áp dụng vào bài toán BEP(C, f, g) không trơn. 97 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN 1. On penalty and gap function methods for bilevel equilibrium problems, J. Appl. Math., DOI:10.1155/2011/646452. 2. A projection algorithm for solving pseudomonotone equilibrium prob- lems and it’s application to a class of bilevel equilibria, Optimization, DOI:10.1080/02331934.2013.773329. 3. An algorithm for variational inequalities with pseudomonotone equilib- rium constraints. submitted. 98 Tài liệu tham khảo Tiếng Việt [1] Phạm Kỳ Anh và Nguyễn Bường (2005), Bài toán đặt không chỉnh, Nxb Đại học Quốc gia Hà Nội, Hà Nội. [2] Đỗ Văn Lưu và Phan Huy Khải (2000), Giải tích lồi. Nxb Khoa học và Kỹ thuật, Hà Nội. [3] Lê Dũng Mưu (1998), Nhập môn các phương pháp tối ưu, Nxb Khoa học và Kỹ thuật, Hà Nội. Tiếng Anh [4] L. Q. Anh and P. Q. Khanh (2008), Semicontinuity of the approximate so- lution sets of multivalued quasiequilibrium problems, Numer. Funct. Anal. Optim., 29, pp. 24-42. [5] P. N. Anh, J. Kim, and L. D. Muu (2012), An extragradient algorithm for solving bilevel variational inequalities, J. Glob. Optim., 52, pp. 527-539. [6] J. B. Aubin and I. Ekeland (1984), Applied Nonlinear Analysis. John Wiley and Sons. [7] G. Auchumuty (1989), Variational principles for variational inequalities, Numer. Funct. Anal. Optim., 10, pp. 863-874. [8] A. Auslender (1976), Optimisation: Méthodes Numériqué, Masson, Paris. 99 [9] T. Q. Bao and P. Q. Khanh (2005), A projection-type algorithm for pseudomonotone nonlipschitzian multivalued variational inequalities, in: A. Eberhard, N. Hadjisavvas, and D. T. Luc, Generalized Convexity and Generalized Monotonicity and Applications., Springer. [10] H. H. Bauschke and P. L. Combettes (2010), Convex Analysis and Mono- tone Operator Theory in Hilbert Spaces. Springer. [11] C. Berge (1968), Topological Spaces. MacMillan, New York. [12] D. P. Bertsekas (1999), Nonlinear Programming, Second Edition. Athena Scientific. [13] M. Bianchi and S. Schaible (1996), Generalized monotone bifuntions and equilibrium problems, J. Optim. Theory Appl., 90, pp. 31-43. [14] G. Bigi, M. Castellani, and M. Pappalardo (2009), A new solution method for equilibrium problems, Optim. Methods Softw., 24, pp. 895-911. [15] G. Bigi, M. Castellani, M. Pappalardo, and Passacantando (2013), Ex- istence and solution methods for equilibria, Eur. J. Oper. Res., 227, pp. 1-11. [16] E. Blum and W. Oettli (1994), From optimization and variational inequal- ities to equilibrium problems, Math. Stud., 62, pp. 127-169. [17] S. Boyd and L. Vandenberghe (2004), Convex Optimization, Cambridge University Press. [18] N. Buong and L. T. Duong (2011), An explicit iterative algorithm for a class of variational inequalities in Hilbert spaces, J. Optim. Theory Appl., 151, pp. 513-524. [19] M. Castellani and M. Pappalardo (2009), Gap functions for nonsmooth equilibrium problems, Taiwanese J. Math., 13, pp. 1837-1846. 100 [20] M. Castellani and M. Giuli (2010), On equivalent equilibrium problems, J. Optim. Theory Appl., 147, pp. 157-168. [21] Y. Censor and A. Lent (1981), An iterative row-action method for interval convex programming, J. Optim. Theory Appl., 34, pp. 321-353. [22] G. Cohen (1998), Auxiliary problem principle extended to variational in- equalities, J. Optim.Theory Appl., 59, pp. 325-333. [23] J. Contreras, M. Klusch, and J. B. Krawczyk (2004), Numerical solution to Nash-Cournot equilibria in coupled constraint electricity markets, IEEE Trans. Power Syst., 19, pp. 195-206. [24] S. Dempe (2002), Foundations of Bilevel Programming, Kluwer Academic Press, Dordrecht. [25] B. V. Dinh, P. G. Hung, and L. D. Muu, Bilevel optimization as a regular- ization approach to pseudomonotone equilibrium problems, Numer. Funct. Anal. Appl., DOI: 10.1080/01630563.2013.813857. [26] X. P. Ding (2010), Auxiliary principle and algorithm for mixed equilibrium problems and bilevel equilibrium problems in Banach spaces, J. Optim. Theory Appl., 146, pp. 347-357. [27] T. T. T. Duong and N. X. Tan (2012), On the existence of solutions to generalized quasi-equilibrium problems, J. Glob. Optim., 4, pp. 711-728. [28] F. Facchinei and J. S. Pang (2003), Finite-Dimensional Variational In- equalities and Complementarity Problems, Springer, New York. [29] K. Fan (1972), A minimax inequality and applications, in: O. Shisha, In- equality III, Proceeding of the Third Symposium on Inequalities, Academic Press, New York. 101 [30] M. Fukushima (1992), Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems,Math. Program., 53, pp. 99-110. [31] N. T. Hao (2006), Tikhonov regularization algorithm for pseudomonotone variational inequalites, Acta Math. Vietnam., 31, pp. 283-289. [32] P. G. Hung and L. D. Muu (2011), The Tikhonov regularization extended to equilibrium problems involving pseudomonotone bifunctions, Nonlinear Anal., Theory Methods Appl., Ser. A, 74, pp. 6121-6129. [33] A. N. Iusem and W. Sosa (2003), Iterative algorithms for equilibrium problems, Optimization, 52, pp. 301-316. [34] V. V. Kalashnikov and N. I. Klashnikova (1996), Solving two-level varia- tional inequality, J. Glob. Optim., 8, pp. 289-294. [35] V. G. Karmanov (1989), Mathematical Programming. Mir Publishers, Moscow. [36] I. V. Konnov (2001), Combined Relaxation Methods for Variational In- equalities. Springer. [37] G. M. Korpelevich (1976), The extragradient method for finding saddle points and other problems, Ekon. Math. Methody, 12, pp. 747-756. [38] P. E. Mainge´ (2008), Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization, Set-Valued Anal., 16, pp. 899-912. [39] P. E. Mainge´ (2008), A hybrid extragradient viscosity methods for mono- tone operators and fixed point problems, SIAM J. Control. Optim., 47, pp. 1499-1515 102 [40] B. Martinet (1970), Regularisation d’inequations variationelles par ap- proximations successives, RAIRO, 4, pp. 154-159. [41] G. Mastroeni (2003), On auxiliary principle for equilibrium problems, in: P. Daniele, F. Giannessi, and A.Maugeri, (eds.), Equilibrium Problems and Variational Models, Kluwer Academic Publishers, Dordrecht. [42] G. Mastroeni (2003), Gap functions for equilibrium problems, J. Glob. Optim., 27, pp. 411-426. [43] M. A. Migdalas, P. Pardalos, and P. Varbrand (eds) (1988), Multilevel Optimization: Algorithms and Applications, Kluwer Academic Publishers Dordrecht. [44] A. Moudafi (1999), Proximal point algorithm extended to equilibrium problems, J. Nat. Geom., 15, pp. 91-100. [45] A. Moudafi (2010), Proximal methods for a class of bilevel monotone equilibrium problems, J. Glob. Optim., 47, pp. 287-292. [46] L. D. Muu and T. D. Quoc (2009), Regularization algorithms for solving monotone Ky Fan inequalities with application to a Nash-Cournot equilib- rium model, J. Optim. Theory Appl., 142, pp. 185-204. [47] L. D. Muu, V. H. Nguyen, and T. D. Quoc (2008), Extragradient algo- rithms extended to equilibrium problems, Optimization, 57, pp. 749-776. [48] L. D. Muu, N. V. Quy, and V. H. Nguyen (2007), On Nash-Cournot oligopolistic market equilibrium models with concave cost functions, J. Glob. Optim., 41, pp. 351-364. [49] L. D. Muu and W. Oettli (1992), Convergence of an adaptive penalty scheme for finding constrained equilibria, Nonlinear Anal., Theory Methods Appl., Ser. A, 18, pp. 1159-1166. 103 [50] L. D. Muu (1986), An augmented penalty function method for solving a class of variational inequalities, USSR Comput. Math. Math. Phys., 12, pp. 1788-1796. [51] L. D. Muu (1984), Stability property of a class of variational inequality, Optimization, 15, pp. 347-351. [52] J. F. Nash (1951), Non-cooperative games, Ann. Math., 54, pp. 286-295. [53] H. Nikaido and K. Isoda (1955), Note on noncooperative convex games, Pac. J. Math., 5, pp. 807-815. [54] M. A. Noor (2004), Auxiliary principle technique for equilibrium prob- lems, J. Optim. Theory Appl., 122, pp. 371-386. [55] T. D. Quoc and L. D. Muu (2012), Iterative methods for solving monotone equilibrium problems via dual gap functions, Comput. Optim. Appl., 51, pp. 709-728. [56] T. D. Quoc, P. N. Anh, and L. D. Muu (2012), Dual extragradient algo- rithms extended to equilibrium problems, J. Glob. Optim., 52, pp. 139-159. [57] R. T. Rockafellar (1997), Convex Analysis, Princeton Universty Press. Princeton, New Jersey. [58] R. T. Rockafellar (1976), Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 5, pp. 877-898. [59] M. V. Solodov and B. F. Svaiter (1999), A hybrid projection-proximal point algorithm, J. Convex Anal., 6, pp. 59-70. [60] M. V. Solodov and B. F. Svaiter (1999), A new projection method for variational inequality problems, SIAM J. Control. Optim., 37, pp. 765-776. 104 [61] A. Tada and W. Takahashi (2007), Weak and strong convergence theo- rem for nonexpansive mapping and equilibrium problem, J. Optim. Theory Appl., 133, pp. 359-370. [62] N. N. Tam, J. C. Yao, and N. D. Yen (2008), Solution methods for pseu- domonotone variational inequalities, J. Optim.Theory Appl., 138, pp. 253- 273. [63] A. N. Tikhonov and V. Y. Arsenin (1977), Solutions of Ill-Posed Problems, John Wiley and Sons, New York. [64] A. N. Tikhonov (1963), On the solutions of ill-posed problems and the method of regularization. Dokl. Akad. Nauk SSSR, 151, pp. 501-504. [65] L. A. Tuan, P. H. Sach, and N. B. Minh (2013), Existence results in a general equilibrium problem, Numer. Funct. Anal. Optim., 34, pp. 430- 450. [66] H. Tuy (1988), Convex Analysis and Global Optimization. Kluwer Aca- demic Publisher. [67] Y. Yao, J. C. Liou, and S. M. Kang (2010), Minimization of equilib- rium problems, variational inequality problems and fixed point problems, J. Glob. Optim., 48, pp. 643-655. [68] N. T. T. Van, J. J. Strodiot, and V. H. Nguyen (2009), A bundle method for solving equilibrium problems, Math. Program., 116, 529-552.