Tong quan 4
Các trưòng hop riêng cna bài toán cân bang
∀y ∈ C Vắy bài toỏn toi ưu trờn là mđt trưũng hop riờng cna bài toỏn (EP).
1.3.2 Bài toán điem yên ngEa
Cho A ⊆ H, B ⊆ H và L : A× B → R Bài toán điem yên ngna là bài toán tìm (x ∗ , y ∗ ) ∈ A × B sao cho
Điểm (x∗, y∗) thuộc A × B thỏa mãn điều kiện cần thiết trên GQi là điểm yên ngựa trên A × B Chúng ta sẽ chỉ ra rằng bài toán điểm yên ngựa có thể được mô tả dưới dạng bài toán cân bằng.
Thắt vắy, vúi moi u = (x, y) T , v = (x J , y J ) T , ta đắt
Khi đú, neu u ∗ là nghiắm cna bài toỏn cõn bang vúi C và f , tỳc là u ∗ ∈ A × B, f (u ∗ , v) ≥ 0, ∀v ∈ C = A × B, thì L (x J , y ∗ ) ≥ L (x ∗ , y J ), ∀x J ∈ A, y J ∈ B.
Vói x J = x ∗ và sau đó vói y J = y ∗ , ta có:
Điểm yên ngna (x∗, y∗) là một yếu tố quan trọng trong bài toán cân bằng Ngược lại, nếu (x∗, y∗) là điểm yên ngna của L trên A × B, thì u∗ = (x∗, y∗)T chính là lời giải cho bài toán cân bằng được suy ra từ định nghĩa.
1.3.3 Bài toán điem bat đ®ng Kakutani
Cho F : C → 2 C Điem x đưoc GQI là điem bat đ®ng cna F neu x ∈ F
Gia sư vói MQI x ∈ C, F (x) là một hàm liên tục và compact, không rỗng Bài toán tìm một điểm bất động của F có thể được mô tả dưới dạng bài toán cân bằng (EP) Để chứng minh điều này, với mọi x, y ∈ C, ta định nghĩa hàm f (x, y) là giá trị lớn nhất của v trong F (x).
Thắt vắy, neu x ∈ F (x), thỡ theo đ%nh nghĩa cna f (x, y) ta cú f (x, y) ≥ 0, ∀y ∈ C.
Ngưoc lai, gia su x là nghiắm cna bài toỏn (EP), tỳc là x ∈ C và f (x, y) ≥
0, vúi MQI y ∈ C Khi đú, lay y là hỡnh chieu cna x lờn tắp loi, đúng F (x), ta có: x y, y x max v∈F (x)
Do x là nghiắm cna (EP) nờn
0 ≤ f (x, y) = (x − y, y − x) = − ǁx − yǁ 2 Suy ra x = y ∈ F (x) Vắy x là điem bat đđng cna F
1.3.4 Cân bang Nash trong trò chơi không hap tác
Xột mđt trũ chơi cú p ngưũi chơi (đau thn) là một vấn đề quan trọng trong lý thuyết trò chơi Gia su C j ⊂ R p j là tập phương án mà đau thn có thể xảy ra, trong đó GQI là tập chiến lược Đặt C := C 1 ∪ C 2 ∪ ∪ C p và GQI ϕ j : C → R là hàm lợi ích của đau thn j khi đau thn này có chiến lược chơi x j ∈ C j, còn các đau thn khác có chiến lược chơi x k ∈ C k với MQI k ≠ j Định nghĩa 1.3.1 (Điểm cân bằng Nash) cho biết rằng GQI x ∗ = x ∗ 1, , x ∗ p là điểm cân bằng của ϕ = (ϕ 1, , ϕ p) trên tập C nếu với MQI j và MQI y j ∈ C j, ta có: ϕ j.
Điểm cân bằng Nash là một khái niệm quan trọng trong lý thuyết trò chơi, được phát triển bởi nhà kinh tế học John Nash Nó mô tả tình huống trong đó, nếu một người chơi thay đổi chiến lược của mình trong khi những người chơi khác vẫn giữ nguyên chiến lược, thì người đó sẽ không đạt được kết quả tốt hơn Điều này có nghĩa là trong một hệ thống có nhiều người chơi, điểm cân bằng Nash là trạng thái mà không ai có động lực để thay đổi chiến lược của mình Bài toán cân bằng Nash có thể được hiểu như một bài toán tìm kiếm điểm cân bằng trên tập hợp các chiến lược khả thi.
Thắt vắy, xõy dnng hàm f : C ì C → R, bang cỏch đắt Σ p
Neu x ∗ là m®t điem cân bang Nash thì f (x ∗ , y) ≥ 0, ∀y ∈ C.
Ngưoc lai, gia su x ∗ ∈ C là nghiắm cna bài toỏn (EP), tỳc là f (x ∗ , y) ≥ 0, ∀y ∈ C
Ta se chúng to x ∗ = x ∗ 1 , , x ∗ p vói x ∗ j ∈ C j là m®t điem cân bang Nash.
Thắt vắy, neu trỏi lai, se ton tai j và mđt so y j ∈ C j sao cho ϕ j
Khi đó, vói phương án y =x ∗ 1 ,
Mõu thuan vúi x ∗ là nghiắm cna (EP)
Vắy x ∗ là mđt điem cõn bang Nash.
1.3.5 Bat đang thÉc bien phân
Xét bài toán bat đang thúc bien phân đa tr% sau:
Cho C là một tập hợp con, H và F là các không gian: C → H là một ánh xạ đa trị (tức là với mọi x ∈ C, giá trị F(x) là một tập hợp con khác trong H) Xét bài toán:
HQA có thể thúc đẩy biến phân (VI) dưới góc độ mô hình kinh tế, trong đó, tập hợp C đại diện cho các chiến lược (tập ràng buộc) của các phương án sản xuất khả thi Mỗi phương án sản xuất x thuộc C sẽ được đánh giá thông qua tập hợp các chỉ số đánh giá.
F(x) là tập hợp các giá thành chi phí có thể, ứng với phương án x Bài toán chính là tìm phương án sản xuất x* trong tập chiến lược C và giá v* ứng với x* sao cho chi phí là thấp nhất Trong trường hợp ánh xạ, giá không phụ thuộc vào phương án sản xuất, tức là F.
(x) = c vói MQI x, bat đang thúc bien phân (VI) tro thành bài toán quy hoach quen thu®c min c T x : x ∈ CΣ
(LP) Trong bài toán quy hoach này, véc-tơ giá c không phu thu®c vào phương án san xuat.
Ve mắt hình học HQ, bài toán tìm điểm x ∗ ∈ C sao cho tập F (x ∗ ) có một phần tử là vector pháp tuyến ngoài tập C tại điểm x ∗ đang được nghiên cứu.
Gia su vúi moi x ∈ C, tắp F (x) loi, compact, khỏc rong Vúi moi x, y ∈
C, đe mụ ta bài toỏn (VI) ve bài toỏn cõn bang ta đắt f (x, y) :max v∈F (x)
Tù đây ta suy ra f (x, y) ≥ 0 vói MQI y ∈ C khi và chi khi x là nghiắm cna
Mô hình bài toán trường hợp riêng quan trọng (VI) xảy ra khi C là một không gian R^n và F là một hàm đơn điệu Khi đó, bài toán (VI) có thể được chuyển đổi thành bài toán bù, được gọi là bài toán GQI.
Ta chi ra rang bài toán (CP) này tương đương vói bat đang thúc bien phân:
Sn tương đương o đõy đưoc hieu theo nghĩa tắp nghiắm cna hai bài toỏn này trùng nhau.
Thắt vắy, neu x là nghiắm cna bat đang thỳc bien phõn thỡ
Lan lưot c HQN y = x + e i (véc-tơ đơn v% thú i) ta có
Vắy F i (x) ≥ 0 vúi MQI i Ngoài ra, neu c HQN y = 0 ta cú
Suy ra x T F (x) = 0 Đieu ngưoc lai, MQI nghiắm cna bài toỏn bự đeu là nghiắm cna bat đang thỳc bien phõn luụn đỳng.
Ngoài ra, bài toán quy hoach loi min {f (x) : x ∈ C},
(CO) trong đú f là mđt hàm loi kha dưúi vi phõn trờn tắp loi C, cú the mụ ta dưói dang bat đang thúc bien phân (VI), vói F = ∂f
Thắt vắy, khi F = ∂f , bài toỏn (VI) viet đưoc là:
Neu x ∗ là nghiắm cna bat đang thỳc bien phõn này, thỡ do v ∗ ∈ ∂f (x ∗ ), nờn theo đ%nh nghĩa cna dưói vi phân, ta có:
The nhưng do x ∗ là nghiắm cna bat đang thỳc bien phõn nờn
Từ đó, có thể suy ra rằng f(x∗) ≤ f(y) với mọi y thuộc tập C Do đó, x∗ là nghiệm tối ưu của bài toán tối ưu hóa (CO) Hơn nữa, nếu x∗ là nghiệm tối ưu (CO), thì theo điều kiện cần và đủ cho tối ưu hóa, ta có thể kết luận về quy hoạch lồi.
Tù đây, theo đ%nh nghĩa cna nón pháp tuyen cna C tai x ∗ , ta suy ra x ∗ là nghiắm cna bat đang thỳc bien phõn (VI), vúi F = ∂f
Nhắn xột 1.3.1 Trong tat ca cỏc bài toỏn vựa ke trờn, song hàm f đeu cú tớnh chat f (y, y) = 0 vỏi MQI y ∈ C Như vắy f là mđt song hàm cân bang trên C.
Hai phương pháp cơ ban giai bài toán cân bang 25
Các dang tương đương
Mắnh đe 2.1.1 Gia su f : C ì C → R là song hàm cõn bang và cỏc đieu kiắn sau đưac thúa món:
(A1) f (., y) nua liờn tnc trờn trờn tắp C;
(A2) f (x, ) loi, nua liên tnc dưái và kha dưái vi phân trên C.
Khi đó, các đieu sau đây là tương đương:
(i) x ∗ là nghiắm cua bài toỏn cõn bang (EP);
(ii) min g (x) = 0 (dang minimax), trong đó hàm g (hàm đánh giá) đưac x∈C cho bái: g (x) := sup f (x, y); y∈C
(iii) x ∗ = arg min f (x ∗ , y) (dang điem bat đ®ng). y∈C
Gia su x ∗ là mđt nghiắm cna bài toỏn (EP).
Do f (x, x) = 0 vói MQI x ∈ C, nên inf f (x, y)0, x C. y∈C
Trong khi đó, do x ∗ ∈ C, nên sup inf f (x, y) ≥ inf f (x ∗ , y). x∈C y ∈C y∈C
Mắt khỏc, do x ∗ là nghiắm cna (EP), nờn f (x ∗ , y) ≥ 0 vúi MQI y ∈ C Vắy inf f (x ∗ , y) 0. y∈C
Ngưoc lai, gia su cú (ii) Khi đú theo lắp luắn o trờn ta cú: sup [−f (x ∗ , y)] = min sup [−f (x, y)] = 0 x∈C x∈ C x∈C
Chúng to −f (x ∗ , y) ≤ 0, vói MQI y ∈ C hay f (x ∗ , y) ≥ 0, vói MQI y ∈ C.
Vắy x ∗ là nghiắm cna (EP).
Thắt vắy, x ∗ là điem cnc tieu cna f (x ∗ , ) trờn C khi và chi khi f (x ∗ , y) ≥ f (x ∗ , x ∗ ) = 0, ∀y ∈ C
Mắnh đe đó đưoc chỳng minh.
Trong phương pháp giải bài toán cân bằng theo nguyên lý bài toán phụ, việc thay thế bài toán quy hoạch lồi không nhất thiết phải có và duy nhất Các bài toán quy hoạch lồi mạnh luôn đóng vai trò như một bài toán phụ trong các phương pháp giải.
Mắnh đe 2.1.2 Gia su H : C ì C → R là mđt song hàm cõn bang, khụng õm và thóa mãn các tính chat sau đây:
(i) H kha vi trên C và Q 2 H(x, x) = 0 vái MQI x ∈ C;
(ii) H(x,.) loi manh trên C vái mői x ∈ C.
Khi so sánh các giá trị (A1) và (A2), ta xác định x ∗ là nghiệm của bài toán cân bằng (EP) Nghiệm này cũng là kết quả của bài toán hiển thị (GQI) trong trường hợp cụ thể.
∀y ∈ C, trong đú ρ > 0 (tham so hiắu chsnh).
Do H là song hàm khụng õm, nờn hien nhiờn rang x ∗ là nghiắm cna (AEP), neu nú là nghiắm cna (EP) Trỏi lai gia su x ∗ là nghiắm cna
(AEP) Khi đú theo mắnh đe trưúc, ta cú x ∗ là nghiắm cna quy hoach loi manh sau: min{ρf (x ∗ , y) + H(x ∗ , y) : y ∈ C}.
Do các điều kiện của hàm f(x ∗, ) và hàm H(x ∗, y) là mạnh, bài toán này luôn có nghiệm duy nhất là s(x ∗) Theo các điều kiện cần thiết và điều kiện tối ưu của quy hoạch, tính chất Q 2 H(x, x) = 0 của hàm H cho thấy sự liên quan giữa các biến trong bài toán.
= ∂ 2 f (x ∗ , x ∗ ) + N C (x ∗ ) Vắy, ton tai u ∗ ∈ ∂ 2 f (x ∗ , x ∗ ) thoa món:
Do tính chat dưói vi phân cna hàm loi f (x ∗ , ), vói MQI y ∈ C, ta lai có:
Suy ra f (x ∗ , y) ≥ 0 vúi MQI y ∈ C Chỳng to x ∗ là nghiắm cna
(EP) Mắnh đe đó đưoc chỳng minh.
Hàm hiắu chinh hay đưoc dựng là hàm Bregman đưoc cho boi:
H(x, y) := g(y) − g(x) − ( Q g(x), y − x) , trong đó g là m®t hàm loi manh xác đ%nh trên toàn không gian, ví du g(x)
Phương pháp điem bat đ®ng và hàm đánh giá
2.2.1 Phương pháp điem bat đ®ng
Su dung dang điem bat đđng, ta cú thuắt toỏn lắp tőng quỏt sau:
Tai moi bưúc lắp k = 0, 1, , gia su đó cú x k ∈ C, ta xõy dnng dóy lắp theo quy tac x k+1 = s x k Σ := argmin{ϕ x k , yΣ
Bài toán (P k ) được xác định bởi ϕ(x, y) := ρf(x, y) + H(x, y), trong đó ρ > 0 là tham số hiếu chỉnh Cần lưu ý rằng do C là tập hợp lồi, f là hàm lồi, liên tục dưới điều kiện hai và H là hàm mạnh, khả vi theo biến thứ hai, nên bài toán (P k ) luôn có nghiệm duy nhất Do đó, x k+1 được xác định một cách rõ ràng.
Nếu trong quá trình lặp, có trường hợp x(k+1) = x(k), thì x(k) sẽ trở thành nghiệm của bài toán (AEP) và cũng là nghiệm của (EP) Ngược lại, nếu trường hợp này không xảy ra, quá trình lặp sẽ kéo dài và tạo ra một dãy nghiệm x(k) thuộc tập C Câu hỏi đặt ra là với những điều kiện nào, dãy nghiệm này sẽ hội tụ đến lời giải của bài toán (AEP)?
Trong mắnh đe dưúi đõy, ta lay H(x, y) := 1 ǁy − xǁ 2 Hien nhiên hàm này thoa món cỏc tớnh chat cho hàm hiắu chinh H, nờu o trờn.
Mắnh đe 2.2.1 Gia su f đơn điắu manh trờn C vỏi hắ so τ và thúa món đieu kiắn kieu Lipschitz, theo nghĩa sau:
(M ) ∃L 1 > 0, L 2 > 0 : ∀x, y, z ∈ C, ta có f (x, y) + f (y, z) ≥ f (x, z) − L 1 ǁx − yǁ − L 2 ǁy − zǁ
Khi đó vái bat kỳ x 0 ∈ C, dãy x k Σ đưac xác đ%nh theo công thúc (P k ) có tính chat y∈C 2 x k+1 − x ∗ 2 ≤ α x k − x ∗ 2 , ∀k ≥ 0, neu như 0 < ρ ≤ 1
, trong đú x ∗ là nghiắm duy nhat cua bài toỏn (EP) và f (x) := ρf x k , xΣ
Khi đó, do f x k , ãΣ loi, nờn hàm f k loi manh trờn C vúi hắ so 1 Vắy f x k+1 Σ
Do x k+1 là nghiắm cna bài toỏn (P k ), nờn w k , x − x k+1 ≥ 0 vúi MQI x ∈
+ 1 x − x k+1 2 ≤ f (x), ∀x ∈ C (2.2) Trong (2.2) thay x = x ∗ , theo đ%nh nghĩa cna f k ta đưoc: x k+1 − x ∗ ≤ 2ρ Σ f x k , x ∗ Σ
Do f đơn điắu manh vúi hắ so τ nờn: f x k , x ∗ Σ
Bây giò áp dung tính Lipschitz (M) vói x = x ∗ , y = x k và z = x k+1 , ta đưoc:
, nên tù đây suy ra: x k+1 − x ∗ 2 ≤ Σ
Vắy mắnh đe đưoc chỳng minh.
Dưúi đõy là hắ qua trnc tiep cna mắnh đe trờn.
, nờn ta cú 2ρ(τ − L 1) < 1 Vắy r đat giá tr% nho nhat tai ρ
Dna vào mắnh đe và hắ qua trờn, ta cú thuắt toỏn sau giai bài toỏn (EP) khi f đơn điắu manh và thoa món đieu kiắn Lipschitz (M).
Như đó thay, neu x k = x k+1 , thỡ x k là nghiắm, do đú ta GQI mđt điem x ∈
C là mđt nghiắm s− xap xi cna (EP) neu ǁx − x ∗ ǁ ≤ s, trong đú x ∗ là mđt nghiắm chớnh xỏc cna (EP).
Thuắt toỏn 1 (cho bài toỏn cõn bang đơn điắu manh)
Bưác khái đau CHQN sai so s 0 và 0 < ρ Lay x 0 C.
Bưỏc lắp k (k = 0, 1, ) Tớnh x k+1 bang cỏch giai quy hoach loi manh x k+1 argmin y∈ C {ρf (x , y) +
, vói r :=1 2ρ(τ L r nghiắm s -xap xi cna (EP).
Trái lai tăng k thêm 1 và thnc hiắn bưúc lắp k.
Chú ý rang do tính chat co x k+1 − x ∗ ≤ r x k − x ∗ vói r < 1, ta có: x k+1 − x ∗ ≤ r Σ x k+1 − x k , ∀k ≥ 0.
1 − x ∗ ≤ s Trong trưũng hop này, ta đưoc mđt nghiắm s -xap xi.
Trưàng hap bat đang thÉc bien phân
Gia su F là m®t ánh xa đa tr% sao cho
C ⊆ domF := {x ∈ R n : F (x) ƒ= ∅} và F (x) compact vói MQI x ∈ C.
Trong phan trưóc, ta đã thay bài toán bat đang thúc bien phân:
(v ∗ , y − x ∗ ) ≥ 0, ∀y ∈ C (VI) là m®t trưòng hop riêng cna bài toán cân bang (EP), và khi C là m®t nón loi, thì bài toán bat đang thúc bien phân tro thành bài toán bù:
(CP) trong đó C ∗ := {v| (v, x) ≥ 0, ∀x ∈ C} là nón đoi cnc cna C Nhó rang khi
C = R n thỡ C ∗ = C Ta núi rang F thoa món đieu kiắn Lipschitz trờn C vúi
+ hang so Lipschitz L (nói ngan GQN là L-Lipschitz), neu F là Lipschitz theo khoang cách Hausdorff, túc là vói MQI x, y ∈ C ta có: sup u∈F
Như đã thay o đau chương, đe mô ta bat đang thúc bien phân trên dưói dang bài toỏn cõn bang (EP), ta đắt: f (x, y) :max v∈F (x)
Khi đú, tắp nghiắm cna bài toỏn (EP) và bài toỏn bat đang thỳc bien phõn là trùng nhau Ta có bő đe sau:
Bo đe 2.2.1 Gia su f (x, y) :max v∈F (x)
Khi đú neu F Lipschitz trờn C vỏi hang so L > 0, thỡ f thúa món đieu kiắn Lipschitz (M), cn the là: f (x, y) + f (y, z) ≥ f L
− Lδ ǁ2 y − zǁ 2 , trong đó δ bat kỳ.
Để áp dụng thuật toán 1 trong việc giải bài toán biến phân đơn điều mạnh, cần chú ý rằng phải có điều kiện L1 < τ Để đảm bảo điều này, chỉ cần chọn δ lớn hơn L.
2τ Bài toán bù (CP) vói C = R n và F là ánh xa đơn tr%, bài toán bù viet đưoc dưói dang: Tìm x ∗ ≥ 0, sao cho F (x ∗ ) ≥ 0 : (F (x ∗ ), x ∗ ) = 0.
Trong trưòng hop này bài toán phu rat đơn gian: x y∈C
Khi đú Thuắt toỏn 1 vúi F đơn điắu manh trờn C cú hắ so τ , tro ve dang sau: x k+1 argmin y∈C
Theo đ%nh nghĩa cna toán tu chieu, ta viet đưoc: x k+1 = P R n
Trong không gian Euclidean R^n, P_R^n được định nghĩa là toán tử chiếu, cho phép chiếu điểm x_k - ρF(x_k) lên R^n Nhờ đó, chúng ta có thể tính được một cách tự nhiên các giá trị liên quan Cụ thể, nếu y = (y_1, , y_n)^T là hình chiếu của x = (x_1, , x_n), thì quá trình này giúp xác định các đặc điểm quan trọng của điểm chiếu trong không gian.
Thuắt toỏn giai bài toỏn bự đơn điắu manh bõy giũ cú the mụ ta như sau:
Thuắt toỏn 2 (cho bài toỏn bự đơn điắu manh)
Bưác khái đau Co đ%nh sai so s ≥ 0 CHQN δ và ρ sao cho δ >
Bưỏc lắp k (k = 0, 1, ) Tớnh x k+1 = x k+1 , , x k+1 Σ T theo công thúc: x k+1 = i i
− τ Σ , thỡ dựng thuắt toán: x k+1 là mđt nghiắm s- xap xi cna bài toỏn Trỏi lai tăng k thờm 1 và tro ve bưúc lắp k.
Tớnh đỳng đan và sn hđi tu cna thuắt toỏn này đưoc suy ra trnc tiep tự Thuắt toỏn 1 o trờn.
Giai phúng đieu kiắn Lipschitz
Các thuật toán trên đũi hội song hàm còn bàng thỏa mãn điều kiện Lipschitz (M) và cần xác định hằng số Lipschitz Trong nhiều trường hợp, song hàm còn bàng không có tính Lipschitz, hoặc nếu có thì việc tính hằng số Lipschitz cũng rất khó khăn Thuật toán dưới đây cho phép giải phức tạp điều kiện Lipschitz.
Bưác 0: CHQN các dãy so {σ k } ⊂ (0, 1) sao cho Σ σ k = ∞; 2
x k , neu ρF i (x k ) ≤ x k , trong đú ρ > 0 là tham so hiắu chinh. a) Neu w k = 0, thỡ dựng thuắt toỏn: x k là nghiắm cna (EP).b) Neu w k ƒ= 0, chuyen qua bưóc 2.
, trong đó P C là toán tu chieu lên C.
Bưác 3: Cho k := k + 1 và quay lai bưóc 1.
Chỳ ý rang bài toỏn chớnh phai giai trong thuắt toỏn trờn là bài toỏn tớnh w k o bưóc 1 Bài toán này có the giai như sau:
(i) Gia su quy hoach loi min y∈C f (x k , y) cú nghiắm Đắt m k := min f (x k , y) < + y∈C và c HQN w k sao cho w k , y − x k Σ
(ii) Do f (x, ã) loi, kha dưúi vi phõn trờn C, nờn vúi MQ i y ∈ C, g k ∈ ∂ 2 f
Do f (x k , x k ) = 0, nên tù đây ta thay rang w k = −ρ −1 g k thoa mãn bat đang thúc sau: ρf (x k , y) + w k , y − x k Σ
Do đó w k là điem can tìm.
Bõy giũ ta can chỳng minh sn hđi tu cna thuắt toỏn 3.
Định lý 2.2.1 khẳng định rằng, trong quá trình tối ưu hóa với gia số đơn điệu mạnh trên C, nếu các biến {x_k} được tạo ra bởi Thuật toán 3, thì ta có x_{k+1} − x^*² ≤ (1 − 2ρτσ)x_k − x^*² + σ²w_k², với mọi k ≥ 0, trong đó x^* là nghiệm duy nhất của bài toán (EP) Hơn nữa, điều kiện 0 < ρ < 1 cũng được yêu cầu để đảm bảo tính hiệu quả của thuật toán.
2τ và dóy {w k } b% chắn, thỡ {x k } hđi tn đen nghiắm x ∗ cua (EP).
Gia su x ∗ là nghiắm duy nhat cna (EP) Thay z k+1 = x k + σ k w k , ta đưoc: z k+1 − x ∗ 2 = x k + σ w k − x ∗ 2 = x k − x ∗ 2
Su dung đ%nh nghĩa cna w k vói y = x ∗ , ta có: 2 ρϕ(x k , x ∗ ) ≥ w k , x k − x ∗ Σ
Vỡ f đơn điắu manh trờn C vúi τ và x là nghiắm cna (EP), nờn ρf (x k , x ∗ ) ≤ −ρτ x k − x ∗ 2 − ρf (x ∗ , x k )
Tù (2.4), (2.5) và (2.6), ta suy ra: z k+1 − x ∗ 2 ≤ (1 − 2ρτσ ) x k − x ∗ 2 + σ 2 w k 2 (2.7) Mắt khỏc do x k+1 = P C
, nên theo tính chat cna toán tu chieu, ta có: x k+1 − x ∗ 2 ≤z k+1 − x ∗ 2
Tù đây và (2.7), ta đưoc: x k+1 − x ∗ 2 ≤ (1 − 2ρτσ ) x k − x ∗ 2 + σ 2 w k 2 Đe chỳng to lim k→∞ x k = x ∗ , ta gia su rang dóy {w k } b% chắn Theo đieu vựa đưoc chúng minh: x k+1 − x ∗ 2 ≤ (1 − 2ρτ σ ) x k − x ∗ 2 + σ 2 M, ∀k, (2.8) k
∗ k k k k k k k k k vói M > 0 là hang so Do
+∞ Đ%nh lý đưoc chúng minh. σ k = +∞, Σ ∞ k=1 σ 2 < +∞, nên tù (2.8), ta có
2.2.2 Phương pháp hàm đánh giá Đe kiem tra xem mđt điem lắp cú phai là mđt s - nghiắm, ta cú the dựng các hàm đánh giá cho bài toán cân bang Phương pháp hàm đánh giá ket hop vói nguyên lý bài toán phu (AEP) cho phép bieu th% bài toán cân bang (EP) bang cách cnc tieu hóa ràng bu®c cna m®t hàm kha vi liên tuc Trưóc tiên, ta nhac lai ve hàm đánh giá như sau: Đ%nh nghĩa 2.2.1 Hàm g : C → R đưac GQI là hàm đánh giá cho bài toán cân bang (EP) neu và chs neu:
(ii) g (x) = 0, x ∈ C ⇔ x là nghiắm cua (EP).
Hàm g(x) được định nghĩa là sup f(x, y) với y thuộc C, là hàm đánh giá cho bài toán cân bằng (EP) theo Định lý 2.2.2 Để áp dụng định lý này, cần đảm bảo rằng các điều kiện sau đây được thỏa mãn cho hàm f: C × C → R.
(ii) f (x, y) kha vi đoi vái x, ∀y ∈ C và f x J liên tnc trên C × C;
(iii) cắn trờn đỳng trong (2.9) là đat đưac vỏi ∀y ∈ C
Khi đó g (x) := sup [f (x, y)] y∈C là hàm đánh giá kha vi liên tnc cho bài toán cân bang (EP) và đao hàm cua nó đưac xác đ%nh như sau: Σ k trong đó
Vỡ f (x, y) loi chắt đoi vúi y, ∀x ∈ C nờn ton tai duy nhat mđt điem cnc tieu y (x) cna bài toán min f (x, y). y∈C
Theo Đ%nh lý 4.3.3 cna [13] ta có y (x) là nua liên tuc trên tai x và y (x) là đơn tr% Do đó y (x) liên tuc tai x.
Hơn nua, f x J trong đó là liên tuc nên g J (x) = f x J (x, y (x)), y (x) := arg min f (x, y). y∈C
Mắt khỏc, tự tớnh liờn tuc cna f x J Vắy g (x) kha vi liờn tuc trên C Đ%nh lý đã đưoc chúng minh. và y (x) ta suy ra g J (x) cũng liên tuc.
Rõ ràng, điều kiện (iii) được thỏa mãn nếu f(x, y) là nửa liên tục dưới đối với y và C là tập compact, hoặc nếu f(x, ) là lồi chắt Tuy nhiên, giả thiết về tính lồi chắt cho hàm f(x, ) không phải lúc nào cũng được thỏa mãn Ví dụ, trong bài toán bất đẳng thức tần biến phân (VI), f(x, ) là tuyến tính.
Chúng ta có the khac phuc khó khăn này bang cách đưa ra m®t bài toán cân bang phu, bő sung cho toỏn tu f mđt hàm loi chắt H (x, ) như sau:
Cho H (x, y) : C × C → R là hàm kha vi trên C đoi vói y sao cho
H y J (x, x) = 0, ∀x ∈ C (2.12) Khi đó, ta có bài toán cân bang phu (AEP) như sau:
Định lý 2.2.3 phát biểu rằng cho C là tập đúng và f(x, y) là hàm khả vi, liên tục tại điểm dưái Hàm f(x, y) khả vi đối với biến x và f(x, y) liên tục trên C × C.
Gia sú H (x, y) : C × C → R là hàm khả vi liên tục trên C, thỏa mãn các điều kiện (2.10), (2.11), (2.12) với x ∈ C Hàm đánh giá khả vi liên tục cho bài toán (EP) được xác định bởi h (x) := max [f (x, y) + H (x, y)], với y ∈ C Đạo hàm của hàm này được tính bằng h J (x) = f x J (x, y (x)) + H x J (x, y (x)), trong đó y (x) được xác định là arg min [f (x, y) + H (x, y)] với y ∈ C.
Ta se xột cỏc thuắt toỏn đe cnc tieu bài toỏn (2.9) hoắc (2.13) Khụng mat tính tőng quát, ta gia thiet như sau:
(i) C là mđt tắp loi trong H;
(ii) f (x, y) là hàm kha vi, loi đoi vói y, vói MQI x ∈ C;
(iii) f (x, y) là hàm kha vi đoi vói x, vói MQI y ∈ C;
Cho g đưoc đ%nh nghĩa như trong (2.9)
Bưỏc 2 Đắt x k+1 := x k + t k d k , trong đó d k := x k − y (x k ), y (x k ) là nghiắm cna bài toỏn: min f (x k , y), t k là nghiắm cna bài toỏn: min g (x y∈C k + td k ).
Bưỏc 3 Neu ǁx k+1 − x k ǁ ≤ à, vúi à > 0, thỡ STOP.
Ngưoc lai, cho k = k + 1 và quay tro lai Bưác 2.
Thuắt toỏn sau đõy thu đưoc bang cỏch ỏp dung Thuắt toỏn 4 cho bài toỏn cân bang phu (AEP).
Cho h đưoc đ%nh nghĩa như trong (2.13)
Bưỏc 2 Đắt x k+1 := x k + t k d k , trong đó d k := x k − y (x k ), y (x k ) là nghiắm cna bài toỏn: min [f (x k , y) + H (x k , y)], t k là nghiắm cna bài toỏn: min h (x y∈C k + td k ).
Bưỏc 3 Neu ǁx k+1 − x k ǁ ≤ à, vúi à > 0, thỡ STOP.
Ngưoc lai, cho k = k + 1 và quay tro lai Bưác 2.
Ta se chỳng minh sn hđi tu cna hai thuắt toỏn trờn Đe ỏp dung đưoc Thuắt toán 4 ta can thêm m®t gia thiet sau:
(2.14) Đe ỏp dung đưoc Thuắt toỏn 5 ta can thờm mđt gia thiet sau: f x J (x, y) + H x J (x, y) + f y J (x, y) + H y J (x, y) , x − y ≥ 0, ∀ (x, y) ∈ C × C.
Neu ta gia thiet H x J (x, y) + H y J (x, y) = 0, ∀ (x, y) ∈ C × C (2.16) thì (2.15) hien nhiên tro thành (2.14).
Ta thay gia thiet (2.16) đưoc thoa mãn neu
H (x, y) = 2 (M (x − y), x − y) là một biểu thức quan trọng trong lý thuyết ma trận Trong đó, M là ma trận đối xứng xác định dương cấp n Định lý 2.2.4 nêu rằng, giả sử C là một tập compact, thì biểu thức (2.14) được thỏa mãn và f (x, y) là hàm liên tục đối với y, với mọi x ∈ C.
Khi đú, vỏi x 0 ∈ C bat kỳ, dóy {x k } đưac đ%nh nghĩa trong Thuắt toỏn 4 nam trong tắp C và điem tn bat kỳ cua {x k } là nghiắm cua bài toỏn cõn bang (EP).
Vỡ C là tắp loi nờn ton tai dóy {x k } đưoc đ%nh nghĩa trong Thuắt toỏn 4 nam trong tắp C, vúi t k ∈ [0, 1].
Do y (x) là liên tuc nên d (x) := x − y (x) cũng liên tuc trên
0≤t≤1 là đóng neu g là m®t hàm liên tuc
Theo Định lý hằng số Zangwill, bất kỳ điểm nào {x_k} trong bài toán cân bằng (EP) đều thỏa mãn điều kiện của định lý này Định lý đã được chứng minh và khẳng định tính chính xác của nó trong lĩnh vực nghiên cứu.
Định lý 2.2.5 khẳng định rằng cho hàm H (x, y) : C × C → R là hàm khả vi liên tục trên C, với điều kiện tồn tại một số y nhất định cho mọi x ∈ C sao cho các điều kiện (2.10), (2.11), (2.12) được thỏa mãn Giả sử C là một tập compact và giả thiết (2.15) cũng được thỏa mãn.
Khi đú, vỏi x 0 ∈ C bat kỳ, dóy {x k } đưac đ%nh nghĩa trong Thuắt toỏn 5 nam trong tắp C và điem tn bat kỳ cua {x k } là nghiắm cua bài toỏn cõn bang (EP).
Ví du
Xét ví du sau: Giai bài toán cân bang vói f (x, y) = −x + y và C [−1, 1] Ta thay f (x, y) là hàm kha vi, loi đoi vói y, ∀x ∈ C.
Thắt vắy, vúi MQI x, y, u ∈ C, λ ∈ [0, 1] ta cú: f (x, λy + (1 − λ) u) = −x + λy + (1 − λ) u
Mắt khỏc f (x, y) kha vi đoi vúi x, ∀y ∈ C và f x J liờn tuc trờn C ì C.
Vì f x J (x, y) + f y J (x, y) , x − y = 0, ∀ (x, y) ∈ C × C nên áp dung Thuắt toỏn 4 cho bài toỏn trờn ta cú:
C Bưỏc 2: Đắt x 1 = x 0 + t 0 d 0 trong đó: d 0 = x 0 − y (x 0), y (x 0) là nghiắm cna bài toỏn: min y∈[−1,1] f (x 0 , y), t 0 là nghiắm cna bài toỏn: min g (x 0 + td 0).
Giai các bài toán ta đưoc: y (x 0) = −1, d 0 = 1, t 0 = −1 nên x 1 = −1.
Bưỏc 3:Ta thay ǁx 1 − x 0 ǁ = 1 > à vúi à = 1 > 0 nờn quay lai Bưỏc 2 ta cho k = 2.
Khi đó x 2 = x 1 + t 1 d 1 trong đó: d 1 = x 1 − y (x 1), y (x 1) là nghiắm cna bài toỏn: min y∈[−1,1] f (x 1 , y), t 1 là nghiắm cna bài toỏn: min g (x 1 + td 1).
Giai các bài toán ta đưoc: y (x 1) = −1, d 1 = 0, nên x 2 = x 1 = −1.
Vắy x = −1 là nghiắm cna bài toỏn cõn bang đó cho.
Bài toỏn trờn cũng cú the giai bang Thuắt toỏn 5 vúi cỏch làm tương tn neu ta c HQN H (x) = 1 (x − y) 2
Bài toán cân bằng có nhiều ứng dụng quan trọng trong các lĩnh vực như kinh tế, lý thuyết trò chơi, và kỹ thuật Nó bao gồm các bài toán nổi bật như bài toán lợi nhuận, điểm bắt đầu Kakutani, bài toán minimax, và mô hình cân bằng Nash Để giải quyết bài toán này, có thể áp dụng các phương pháp như điểm bắt đầu, tiếp cận theo nguyên lý bài toán phụ, tiếp cận theo phương pháp hiệu chỉnh Tikhonov, và tối ưu hóa dựa trên kỹ thuật hàm đánh giá Tính ứng dụng cao của bài toán này đã thu hút sự quan tâm của các nhà toán học trong việc nghiên cứu các phương pháp giải.
Luắn văn đó đe cắp nhung van đe sau:
1 Trỡnh bày mđt cỏch hắ thong cỏc khỏi niắm cơ ban nhat trong giai tớch loi, cỏc kien thỳc ve bài toỏn cõn bang: sn ton tai nghiắm, cỏc tớnh chat cơ ban và các trưòng hop riêng cna bài toán cân bang.
2 Giúi thiắu mđt vài phương phỏp cơ ban giai bài toỏn cõn bang cựng năm thuắt toỏn Trỡnh bày cơ so đe xõy dnng cỏc phương phỏp giai đú là dna trên các dang tương đương cna bài toán cân bang.
Mắc dự đó co gang, tuy nhiờn luắn văn khụng trỏnh khoi nhung sai sút, rat mong nhắn đưoc sn gúp ý cna quý thay cụ và ban ĐQ c.
[1] Nguyen Văn Hien, Lê Dũng Mưu, Nguyen Huu Đien, (2015), Giai tích loi úng dnng, NXB Đai HQ c Quoc gia Hà N®i.
[2] Đo Văn Lưu, (2009), Giai tớch hàm, NXB Khoa HQc ky thuắt, Hà Nđi.
[3] Tran Vũ Thiắu, Nguyen Th% Thu Thny, (2011), Giỏo trỡnh toi ưu phi tuyen, NXB Đai HQc Quoc gia Hà N®i.
[4] Anh, P N., (2011), A hybrid extragradient method extended to fixed point problems and equilibrium problems, 1, pp 1-13.
[5] Blum, E Oettli., (1994), "From optimization and variational inequality to equilibrium problem", Math Stud, 63, pp.127-149.
[6] Daniele, P., Giannessi, F., and Maugeri, A., (2003), Equilibrium Problems and Variational Models, Kluwer.
[7] Dinh, Q.T., Muu, L.D., Nguyen, V.H., (2008), "Extragradient methods extended to equilibrium problems", Optimization, 6, pp 749-776.
[8] Fan, K., (1972), "A Minimax Inequality and Applications", Academic Press, New York, pp 103-113.
[9] Konnov, I.V., (2003), "Application of the proximal point method to mon- monotone equilibrium problems", J Optim Theory App, 119, pp 317-333.
[10] Mastroeni, G., (2004), "Gap function for equilibrium problems", J Glob. Optim, 27, pp 411-426.
[11] Muu, L.D., Quoc, T.D., (2009), "Regularization Algorithms for Solving
Monotone Ky Fan Inequalities with Application to a Nash-Cournot Equi- librium Model", J Optim Theory Appl, 142, pp 185-204.
[12] Rockafellar, R.T., (1970), Conver Analysis, Princeton University Press, Princeton, New Jersey.
[13] Tammer, K., Kummer, B., Klatte, D., Guddat, J., and Bank, B., (1983),
Nonlinear Parametric Optimization, Birkhauser Verlag.
[14] Zangwill, W.I., (1969), Nonlinear Programming: a unifixed approach,Prentice-Hall, Englewood Cliffs, New York.