Kien thÉc chuan b% 5 1.1 Không gian Hilbert
Tắp loi và hàm loi trong khụng gian Hilbert
Trong không gian Hilbert H, một tập hợp C ⊂ H được gọi là tập hợp lồi nếu với mọi điểm a, b ∈ C và mọi số thực λ ∈ [0, 1], ta có λa + (1 − λ)b ∈ C Tập lồi cũng thỏa mãn các phép toán giao, cộng và nhân với các số thực; tức là nếu C và D là hai tập lồi trong H, thì C ∩ D và αC + βD cũng là các tập lồi Ngoài ra, một điểm x được gọi là tổ hợp lồi của các điểm (vector) x₁, x₂, , xₙ nếu tồn tại các hệ số λ₁, λ₂, , λₖ ≥ 0 sao cho x = Σ(λⱼ xⱼ) với điều kiện Σ(λⱼ) = 1, trong đó j chạy từ 1 đến k.
Mắnh đe 1.2.1 (Xem [3]) Tắp hap C là loi khi và chs khi nú chỳa MQI tő hap loi cua các điem cua nó Túc là, C loi khi và chs khi k k
Mắnh đe 1.2.2 (Xem [3]) Neu A, B, C là cỏc tắp loi đúng trong H, thỡ cỏc tắp sau là loi
1 αA + βB := {x : x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R}, A × C := {x ∈ H × H : x = (a, c), a ∈ A, c ∈ C}. Đ%nh nghĩa 1.2.3 (Xem [3]) Mđt tắp đưac GQI là tắp loi đa diắn neu nú là giao cua m®t so huu han các nua không gian đóng.
Tắp loi đa diắn là khái niệm liên quan đến việc tập hợp các phương trình tuyến tính với các biến số hữu hạn Định nghĩa này nhấn mạnh tính chất của tắp hợp và cách thức các phương trình tương tác với nhau trong không gian đa chiều.
Mắnh đe 1.2.3 (Xem [3]) Giao cua mđt HQ bat kỳ cỏc tắp loi là mđt tắp loi.
Chỳng minh Gia su {A α } α∈I là HQ cỏc tắp loi Can chỳng minh A = ∩ α∈I A α là mđt tắp loi.
Thắt vắy, vúi MQ i x 1 , x 2 ∈ A ⇒ x 1 , x 2 ∈ A α , ∀α ∈ I Do A α loi nờn vúi MQI λ ∈ [0, 1], ta có λx 1 + (1 − λ)x 2 ∈ A.
Theo đ%nh nghĩa, A = ∩ α∈I là mđt tắp loi. Đ%nh nghĩa 1.2.4 (Xem [3]) Mđt tắp C ∈ H đưac GQI là nún neu vỏi
Nếu MQI x ∈ C và vái m Q i λ > 0 thì λx ∈ C Một nón được gọi là nón lồi nếu nó là nón và là một tập lồi Định nghĩa nón pháp tuyến (ngoài) của tập C tại x 0 được xác định khi C ⊂ H và x 0 ∈ C.
≤ 0 ∀x ∈ C}. Đ%nh nghĩa 1.2.6 (Xem [3]) Cho hai tắp C, D ∈ H, ta núi siờu phang
= λ} i) tỏch hai tắp C và D neu
∀a ∈ C, b ∈ D; ii) tỏch chắt C và D neu
∀a ∈ C, b ∈ D; iii) tách manh C và D neu sup v, aΣ
Trong bài viết này, chúng ta sẽ khám phá các định lý cơ bản về việc phân tách các tập hợp trong không gian H Định lý 1.2.2 khẳng định rằng nếu C và D là hai tập hợp rỗng khác nhau trong H với C ∩ D = ∅, thì tồn tại một siêu phẳng có thể tách biệt C và D Định lý 1.2.3 tiếp tục phát triển ý tưởng này, cho rằng nếu ít nhất một trong hai tập hợp C hoặc D là compact, thì chúng có thể được tách mạnh mẽ bởi một siêu phẳng.
Cho H là không gian Hilbert và f : H → R ∪ {+∞} Tập domf = {x ∈ H : f(x) < +∞} được gọi là miền hữu hạn của hàm f Hàm f được gọi là hàm chính thức nếu domf ≠ ∅ và f(x) > −∞ với mọi x ∈ H Định nghĩa 1.2.7 (Xem [3]) cho rằng f : H → R ∪ {+∞} là hàm lồi nếu f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y) với mọi x, y ∈ domf và λ ∈ (0, 1) Định lý 1.2.4 (Xem [3]) khẳng định rằng nếu f và g là hai hàm lồi trên tập lồi C và D tương ứng, thì các hàm αf + βg (với mọi α, β ≥ 0) và max{f, g} cũng lồi trên C ∩ D.
M®t hàm loi có thể không liên tục tại một điểm trên biên miền xác định, tuy nhiên nó liên tục tại mọi điểm trong tập hợp theo định lý 1.2.5 Nếu hàm loi f được xác định trên tập hợp C, thì f liên tục tại mọi điểm trong C.
Tính chất sau đây đặc trưng cho một hàm số khả vi và thuận lợi để kiểm tra tính khả vi của hàm số Ta có thể hiểu f'(a) hoặc f(a) là đạo hàm của f tại a Định lý 1.2.6 (Xem [3]) nêu rõ rằng cho hàm f: C → R là một hàm khả vi trên tập hợp, thì
C Đieu kiắn can và đu đe f loi trờn C là f (x) +
Neu f kha vi hai lan thỡ đieu kiắn can và đu đe f loi trờn C là vỏi MQI x ∈
C, ma trắn Hessian H(x) cua f tai x xỏc đ%nh khụng õm, tỳc là y T H(x)y ≥ 0 ∀x ∈ C, y ∈ R n
Mẫu đa biến toàn phương là một mô hình hàm hồi quy, trong đó hàm hồi quy được xác định khi và chỉ khi ma trận hiệp phương sai là dương Mô hình này giúp phân tích mối quan hệ giữa các biến độc lập và biến phụ thuộc một cách hiệu quả.
Tính khả vi của một hàm lợi là yếu tố quan trọng trong các phương pháp tối ưu hóa Các lớp hàm lợi sở hữu những tính chất khả vi đặc biệt mà các lớp khác không có Giả sử f: H → R ∪ {+∞} là hàm lợi, chúng ta có thể tham khảo Định nghĩa 1.2.8 (Xem [3]) Đối với hàm f: H → R được xác định là nửa liên tục dưới, tại một điểm x và với một tập E ⊂ H, nếu như tồn tại một dãy {x_k} ⊂ E, x_k
Hàm f đưac GQI là nua liên tnc trên đoi vái E tai x neu −f nua liên tnc dưái đoi vái E tai x, hay là MQI dãy {x k } ⊂ E, x k → x thì lim sup f (x k )f (x). k→∞
Hàm f đưac GQI là liên tnc đoi vái E tai x neu như nó vùa nua liên tnc trên và nua liên tnc dưái đoi vái E tai x.
Hàm f được gọi là liên tục dưới một điểm E trong A nếu nó liên tục dưới E tại một điểm thuộc A Tương tự, chúng ta cũng có thể nói như vậy đối với hàm liên tục trên và hàm liên tục Khi hàm f liên tục (hoặc nửa liên tục) tại một điểm x trong toàn bộ không gian, thì ta nói đơn giản rằng f liên tục (hoặc nửa liên tục) tại x.
≤ Đ%nh nghĩa 1.2.9 (Xem [3]) Cho f : H → R ∪ {+∞}, s > 0 M®t vectơ w ∈ H đưac GQI là s−dưái đao hàm cua f tai x 0 ∈ H neu
Tắp hap tat ca cỏc s−dưỏi đao hàm GQI là s−dưỏi vi phõn cua hàm f tai x 0 , đưac kớ hiắu là
≤ f (x) − f (x 0 ) + s ∀x ∈ H}. Đ%nh nghĩa 1.2.10 (Xem [3]) Cho f : H → R ∪ {+∞}, s > 0 M®t vectơ w ∈ H đưac GQI là dưái đao hàm cua f tai x 0 ∈ H neu w, x − x 0 ≤ f (x) − f (x 0 ) ∀x ∈ H.
Tắp hap tat ca cỏc dưỏi đao hàm GQI là dưỏi vi phõn cua hàm f tai x 0 , đưac kớ hiắu là
Hàm f đưac GQI là kha dưái vi phân tai x 0 neu ∂f (x 0 ) ƒ= ∅.
Vói λ > 0 và f : H → R ∪ {+∞} là hàm loi chính thưòng, ta có tính chat
Đối với hàm số f và một số thực λ, ta có công thức ∂(λf )(x 0 ) = λ∂f (x 0 ) với x 0 thuộc không gian H Đối với vi phân của hai hàm lồi, ta áp dụng định lý Moreau - Rockafellar, cụ thể là Định lý 1.2.7 Giả sử f 1 và f 2 là hai hàm lồi chính quy từ H sang R ∪ {+∞}.
Ngoài ra, neu mđt trong hai hàm f 1 , f 2 liờn tnc tai điem thuđc mien huu hiắu cua hàm kia thì
Sau đây là m®t so ví du đien hình ve hàm kha dưói vi phân
Ví dn 1.2.1 Gia su a ∈ H và hàm f : H → R cho boi f (x) = 1 ǁx − aǁ 2 vói
MQI x ∈ H Khi đó, vói MQI x 0 ∈ H, ta có
Ví dn 1.2.2 Gia su δ C : H → R ∪ {+∞} là hàm chi cna C δ (x) := 0 neu x ∈ C,
Khi đó, vói MQI x 0 ∈ C, ta có
≤ 0 ∀x ∈ C} là nón pháp tuyen ngoài cna C tai x 0
1.3 Toán tE chieu trong không gian Hilbert
Cho C là tập con đúng khép kín trong không gian Hilbert H, ta xem xét hình chiếu của một phần tử x ∈ H lên C Định lý 1.3.1 (Xem [3]) khẳng định rằng C là tập con đúng khép kín trong không gian Hilbert.
Hilbert thnc H Khi đó, vái mői x ∈ H, ton tai duy nhat y ∈ C sao cho ǁx − yǁ = min ǁx − zǁ.
Khi đú, điem y ∈ C đưac GQI là hỡnh chieu cua x trờn C và đưac ký hiắu là
Trong không gian Hilbert H, cho C là tập hợp các điểm đúng khác rỗng, ánh xạ P_C: H → C xác định điểm P_C(x) sao cho khoảng cách ǁx − P_C(x)ǁ là nhỏ nhất, tức là ǁx − P_C(x)ǁ = min ǁx − zǁ với z thuộc C Đây là một toán tử chiếu trên C.
Ví dn 1.3.1 Gia su a, b ∈ R n , a =ƒ 0 Xét nua không gian C ⊂
R n và mắt phang K ⊂ R n cho boi
Khi đó, toán tu chieu lên C và K lan lưot cho boi
Ví dn 1.3.2 Gia su a ∈ R n , R > 0 và hình cau C xác đ%nh boi
Khi đó, toán tu chieu lên C cho boi
P C (x) a + ǁx − aǁ (x − a) neu ǁx − aǁ > R.
Bő đe sau cho ta mđt so tớnh chat cna toỏn tu chieu lờn tắp loi đúng khỏc rong C trong không gian Hilbert thnc H,
Bo đe 1.3.1 (Xem [3]) Cho x ∈ H và y ∈ C, khi đó
(ii) y = P C (x) khi và chs khi ǁx − yǁ ≤ ǁx − zǁ − ǁz − yǁ ∀z ∈ C.
Do đó, ánh xa P C (.) là không giãn, túc là ǁP C (x) − P C (y)ǁ ≤ ǁx − yǁ ∀x, y ∈ H.
Tiep theo là mđt so bő đe phuc vu chỳng minh sn hđi tu cna thuắt toỏn trong Chương 2.
Bo đe 1.3.2 (Xem [3]) Vái mői x, y, z ∈ H và 0 ≤ a ≤ 1, ta có ǁax + (1 − a)y − zǁ ≤ aǁx − zǁ + (1 − a)ǁy − zǁ
Bo đe 1.3.3 (Xem [3]) Cho {v k } và {δ k } là các dãy so thnc không âm thóa mãn v k+1 ≤ v k + δ k vái
Bo đê 1.3.4 (Xem [3]) đề cập đến không gian Hilbert H và dãy số thực {a k } thỏa mãn điều kiện 0 < a < a k < b < 1 với k = 1, 2, Bên cạnh đó, hai dãy {v k } và {ω k } trong H cũng thỏa mãn giới hạn lim sup ǁv k ǁ ≤ c và lim sup ǁω k ǁ ≤ c khi k tiến tới vô cùng.
Toán tu chieu trong không gian Hilbert
Bài toán cân bang tách và Éng dnng
Trong chương này, chúng ta sẽ khám phá bài toán cân bằng và các lớp bài toán liên quan Tiếp theo, chúng ta sẽ tìm hiểu về bài toán chap nhắn tách và mối liên hệ của nó với bài toán cân bằng tách Chúng ta cũng sẽ nghiên cứu các thuật toán cho bài toán cân bằng tách và xem xét các ứng dụng của chúng trong sản xuất điển hình.
Khi trình bày về bài toán cân bằng, chúng ta cần tìm hiểu một số khái niệm liên quan đến hàm f Để làm rõ, cho C là tập con trong không gian Hilbert H, chúng ta định nghĩa ánh xạ F: C → H.
1 γ-đơn điắu manh trờn C neu ton tai hang so γ > 0 sao cho
3 γ-gia đơn điắu manh trờn C neu ton tai hang so γ > 0 sao cho vúi MQI x, y ∈ C, ta có
4 gia đơn điắu trờn C neu vúi MQI x, y ∈ C, ta cú
Bài toán cân bang tách và Éng dnng 17
Bài toán cân bang
Khi trình bày bài toán cân bằng, chúng ta cần tìm hiểu mối quan hệ giữa các hàm f Cho C là tập con, có thể là đúng hoặc sai trong không gian Hilbert H Định nghĩa 2.1.1 (Xem [1]) chỉ ra rằng ánh xạ F : C → H được xác định là
1 γ-đơn điắu manh trờn C neu ton tai hang so γ > 0 sao cho
3 γ-gia đơn điắu manh trờn C neu ton tai hang so γ > 0 sao cho vúi MQI x, y ∈ C, ta có
4 gia đơn điắu trờn C neu vúi MQI x, y ∈ C, ta cú
Ví dn 2.1.1 Cho ánh xa F : C → R n vói F (x) = Ax Khi đó
1 Neu A là ma trắn vuụng, đoi xỳng, nua xỏc đ%nh dương thỡ F đơn điắu trờn C.
2 Neu A là ma trắn vuụng, đoi xỳng, xỏc đ%nh dương trờn C thỡ F γ- đơn điắu manh trờn C. Đ%nh nghĩa 2.1.2 (Xem [1]) Song hàm f : C × C → R đưoc GQ i là
1 γ-đơn điắu manh trờn C neu ton tai hang so γ > 0 sao cho f (x, y) + f (y, x) ≤ −γǁx − yǁ 2 ∀x, y ∈ C;
3 γ-gia đơn điắu manh trờn C neu ton tai hang so γ > 0 sao cho vúi MQI x, y ∈ C, ta có f (x, y) ≥ 0 ⇒ f (y, x) ≤ −γǁx − yǁ 2 ;
4 gia đơn điắu trờn C neu vúi MQI x, y ∈ C, ta cú f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0.
Chỳ ý rang neu ỏnh xa F là γ-đơn điắu manh (đơn điắu, γ-gia đơn điắu manh, gia đơn điắu) trờn C thỡ song hàm f (x, y) :=
F(x), y - xΣ cũng γ-đơn điắu manh (đơn điắu, γ-gia đơn điắu manh, gia đơn điắu) trền C Bên cạnh đó, các khối niắm đơn điắu cna toỏn tu và cna song hàm có các mối quan hệ như sau.
tớnh đơn điắu manh kộo theo tớnh đơn điắu và tớnh đơn điắu kộo theo tớnh gia đơn điắu;
tớnh đơn điắu manh kộo theo tớnh gia đơn điắu manh và tớnh gia đơn điắu manh kộo theo tớnh gia đơn điắu.
Tuy nhiên, tính gia đơn điệu không thể suy ngược ra được tính đơn điệu hay tính gia đơn điệu mạnh, do đó chúng ta cũng không thể có kết quả nào về mối quan hệ giữa tính đơn điệu và tính gia đơn điệu mạnh Các ví dụ sau sẽ chỉ ra điều này.
Ví dn 2.1.2 Xét trong R 2 , C := R 2 , cho
De thay, f (x, y)+ f (y, x) = 0 ∀x, y ∈ C nờn f đơn điắu trờn C nhưng khụng đơn điắu manh trờn C và do đú khụng gia đơn điắu manh trờn
Song hàm g gia đơn điắu trờn C, tuy nhiờn nú khụng gia đơn điắu manh và cũng khụng đơn điắu Thắt vắy, lay x = (1, 1), y = (0, 1), ta cú g(x, y) + g(y, x) = 1 > 0.
Trong bài viết này, chúng ta xem xét một tập hợp C = B(r) := {x ∈ H : ǁxǁ ≤ r} với 0 < r < R, và định nghĩa một song hàm f thông qua f(x, y) := h(x, y) + (R − ǁxǁ)g(x, y) Hàm h và g phải thỏa mãn các điều kiện sau: i) h(x, y) ≤ 0 cho mọi x, y thuộc C, và g là β-đơn điệu mạnh trên C; ii) tồn tại một y0 ∈ C sao cho
Khi xem xét hàm f(x, y) ≥ 0 trên tập C, ta có h(x, y) ≤ 0 dẫn đến g(x, y) ≥ 0 Từ tính đơn điệu mạnh của g, ta suy ra g(y, x) ≤ −βǁx − yǁ² Do đó, theo định nghĩa của f(y, x), ta có f(y, x) = h(y, x) + (R − ǁyǁ)g(y, x) ≤ −(R − r)βǁy − xǁ² với mọi x, y ∈ C.
Do đú, f gia đơn điắu manh hắ so (R − r)β trờn C.
Song hàm f khụng gia đơn điắu trờn C vỡ theo gia thiet ii) ta đưoc f (0, y 0 ) + f (y 0 , 0) = h(0, y 0 ) + Rg(0, y 0 ) + h(y 0 , 0) + (R − ǁy 0 ǁ)g(y 0 , 0) > 0.
Mđt vớ du cu the ve cỏc hàm g và h thoa món đieu kiắn i) và ii) là g(x, y) := x, y − xΣ
+ m(ǁyǁ 2 − ǁxǁ 2 ) vói m > 0 và h(x, y) := (x − y) T A(y − x) vói A : H → H là m®t toán tu tuyen tính thoa mãn h(x, y) ≤ 0 vói
De thay g là song hàm đơn điắu manh vúi MQI m > 0 Hơn nua, ta cú
Rg(0, y) + (R − ǁyǁ)g(y, 0) = [mR − (m + 1)R + (m + 1)ǁyǁ]ǁyǁ 2
− r r thỡ đieu kiắn ii) đưoc thoa món vúi MQI y 0 ∈ C B(r) vói y 0 > R m + 1 và (y 0 ) T Ay 0
Ngày nay, trong bối cảnh hợp tác toàn cầu và mối quan hệ phức tạp giữa các đối tác, một phương án tối ưu cho một đối tác có thể không thỏa mãn các đối tác khác Khi xem xét mô hình có nhiều đối tác tham gia, mỗi đối tác đều có một hàm lợi ích riêng Quyết định của một đối tác thường phụ thuộc vào chiến lược của các đối tác khác, và lợi ích giữa các đối tác thường mâu thuẫn nhau Trong trường hợp này, một phương án tối ưu cho tất cả các đối tác thường không tồn tại Do đó, cần xem xét một phương án cân bằng để "thu hút" các đối tác, nghĩa là nếu bất kỳ một đối tác nào đó ra khỏi điểm cân bằng, họ sẽ bị thua thiệt Để hiểu rõ hơn về khái niệm cân bằng, chúng ta sẽ phân tích bài toán cân bằng Nash trong trò chơi không hợp tác Bài toán cân bằng được mô tả như sau: Cho C là tập con lợi ích, đóng, khác rỗng trong không gian Hilbert H và f: C × C → R là song hàm phi tuyến Bài toán cân bằng liên kết f và C, viết tắt là EP(f, C), được phát biểu như sau:
Tìm x ∗ ∈ C sao cho f (x ∗ , y) ≥ 0 với mọi y ∈ C, trong đó f (x, x) = 0 với MQI x ∈ C Chúng ta xác định các song hàm thỏa mãn tính chất này là song hàm cân bằng trên C Như đã nêu, ta sẽ xác định C là tập hợp chặt chẽ và f là song hàm cân bằng trong bài toán EP (f, C).
Bài toán này mặc dù có vẻ đơn giản nhưng chứa đựng nhiều lớp vấn đề liên quan đến nhiều lĩnh vực khác nhau Nó bao gồm các bài toán tối ưu hóa, bất đẳng thức biến phân, điểm yên ngựa, cân bằng Nash trong lý thuyết trò chơi không hợp tác, và điểm bất động.
2.1.1 Bài toán toi ưu hóa
Như vắy, bài toỏn toi ưu trờn là mđt trưũng hop riờng cna bài toỏn EP (f, C).
2.1.2 Bat đang thÉc bien phân
Cho F : C → 2 R n là m®t ánh xa đa tr% (túc là moi x ∈ C, giá tr% F (x) là mđt tắp hop trong R n ) Xột bài toỏn
HQA đang thúc đẩy sự phát triển của phân VI dưới góc độ mô hình kinh tế Giả sử C là một mô hình tập hợp các chiến lược và phương pháp.
Trong sản xuất, tập hợp các phương án sản xuất x ∈ C và hàm chi phí F(x) biểu diễn chi phí tương ứng với mỗi phương án x Nhiệm vụ chính của bài toán là tìm phương án sản xuất tối ưu x ∗ trong tập chiến lược C và giá v ∗ tương ứng với x ∗ sao cho chi phí là thấp nhất Trong trường hợp này, hàm chi phí không phụ thuộc vào phương án sản xuất, tức là F không thay đổi theo x.
(x) = c vói MQI x ∈ C, khi đó, 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éctơ giá c không phu thu®c vào phương án san xuat.
Bài toán tìm điểm x∗ ∈ C trong không gian HQ nhằm xác định một phần tử trong tập F(x∗) sao cho nó là vectơ pháp tuyến (ngoài) của tập C tại điểm x∗ đang được nghiên cứu và phát triển.
Gia su x ∈ C, tắp F (x) loi, compact, khỏc rong Vúi MQI 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 suy ra f (x, y) ≥ 0 vúi MQI y ∈ C khi và chi khi x là nghiắm cna bài toán (VI) M®t trưòng hop riêng quan TRQNG cna bài toán (VI) là khi
C = R n và F đơn tr% Khi đó, bài toán (VI) tương đương vói bài toán sau và đưoc GQI là bài toán bù
Ta chi ra rang bài toán (CP) tương đương vói bat đang thúc bien phân
Sn tương đương ở đây được hiểu là sự tương ứng giữa hai bài toán ngược nhau Thắt chặt, nếu x là nghiệm của bài toán bất đẳng thức thì
Lan lưot cHQN y = x + e i (véctơ đơ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 là hien nhiờn.
Bài toán quy hoạch tối thiểu {u(x) : x ∈ C} (CO) liên quan đến việc tìm giá trị nhỏ nhất của hàm u, một hàm khả vi trên tập hợp C Đặc biệt, khi F = ∂u, bài toán có thể được biểu diễn dưới dạng bất đẳng thức biến phân (VI).
Neu x ∗ là nghiắm cna bat đang thỳc bien phõn, do v ∗ ∈ ∂u(x ∗ ) nờn theo đ
%nh nghĩa cna dưói vi phân, ta có
Từ đó, ta suy ra rằng \( f(x^*) \leq f(y) \) với mọi \( y \in C \) Điều này cho thấy \( x^* \) là điể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 của bài toán (CO), thì theo các điều kiện cần và đủ cho tối ưu hóa, ta có thể khẳng định rằng quy hoạch lồi sẽ đảm bảo tính tối ưu cho bài toán này.
Tự đõy theo đ%nh nghĩa 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 = ∂u.
2.1.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
(x) Gia su vói MQI x ∈ C, F (x) loi, compact, khác rong Khi đó, bài toán tìm m®t điem bat đ®ng cna F có the mô ta dưói dang bài toán cân bang EP
(f, C) Đe chỳng to đieu này, vúi moi x, y ∈ C, ta đắt f (x, y) :max v∈F (x)
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 (f, C), 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) Theo tính chat cna hình chieu, ta có x y, y x max v∈F (x)
Do x là nghiắm cna EP (f, C) nờn
Suy ra x = y ∈ F (x) Vắy x là điem bat đđng cna F
2.1.4 Cân bang Nash trong trò chơi không hap tác
Trong trò chơi có p người chơi, mỗi người chơi j thuộc tập hợp C j ⊂ R p j có các phương án lựa chọn khác nhau Tập C = C 1 ∪ C 2 ∪ ∪ C p chứa tất cả các chiến lược, và hàm lợi ích ϕ j : C → R phản ánh lợi ích của người chơi j khi lựa chọn phương án x j ∈ C j, trong khi các người chơi khác chọn x k ∈ C k với k ≠ j Định nghĩa điểm cân bằng x ∗ = (x ∗ 1 , , x ∗ p ) là khi hàm lợi ích ϕ = (ϕ 1 , , ϕ p ) trên tập C đạt giá trị tối ưu, tức là với mọi lựa chọn y j ∈ C j, có ϕ j (x ∗ 1 , , x ∗ j−1 , y j , x ∗ j+1 , , x ∗ p ) ≤ ϕ j (x ∗ 1 , , x ∗ j−1 , x ∗ j , x ∗ j+1 , , x ∗ p ).
Bài toán cân bang tách
Trưúc tiờn, ta tỡm hieu bài toỏn chap nhắn tỏch Cho cỏc khụng gian Hilbert H 1, H 2, C ⊂ H 1 và Q ⊂ H 2 là cỏc tắp con, loi, đúng, khỏc rong Cho
A : H 1 → H 2 là toỏn tu tuyen tớnh b% chắn Bài toỏn chap nhắn tỏch (SFP ) đưoc phát bieu như sau
Ta GQI Γ là tắp nghiắm cna SF P , tỳc là Γ := {x ∗ ∈ C : Ax ∗ ∈ Q} và gia su rang Γ ƒ= ∅.
Gia su x ∗ ∈ Γ, ta có Ax ∗ ∈ Q Khi đó, Ax ∗ −P Q Ax ∗ = 0 hay (I−P Q )Ax ∗ = 0.
Do đú, x ∗ là nghiắm cna bài toỏn cnc tieu húa vúi giỏ tr% toi ưu 0 sau đõy min f (x) :=1 ǁAx −
Bài toán chấp nhắn tách có nhiều ứng dụng thực tế trong các bài toán xử lý tín hiệu và khôi phục ảnh, cũng như trong các bài toán khác Bài toán này trong các không gian Hilbert hữu hạn chiều được giới thiệu lần đầu bởi Yair Censor và Tommy Elfving Để giải bài toán chấp nhắn tách trong không gian hữu hạn chiều, Charles Byrne đã đề xuất thuật toán CQ bằng cách sử dụng quy tắc cập nhật, với MQI k ≥ 0, x k+1 = P C (x k + γA T (P Q − I)Ax k), trong đó C, Q lần lượt là hai tập hợp lồi khác nhau trong R n và R m, A là một ma trận có kích thước m × n, và L là giá trị riêng lớn nhất của ma trận A T.
Gan đõy, Hong-Kun Xu đó giai bài toỏn chap nhắn tỏch trong khụng gianL
Hilbert đã trình bày một phương pháp giải bài toán tối ưu với công thức x k+1 = P C (x k + γA ∗ (P Q − I)Ax k), trong đó γ > 0, 2 ǁAǁ 2 và A ∗ là toán tử liên hợp của A Tác giả đã chứng minh rằng dãy {x k} hội tụ về nghiệm của bài toán, đảm bảo tính chính xác và hiệu quả trong việc giải quyết bài toán tối ưu này.
Để giải bài toán chap nhắn tách đũi, cần tìm hình chiếu trên các tắp C và Q Trong các trường hợp mà C và Q được cho dưới dạng ẩn, như tắp điểm bất định của một ánh xa hay tắp nghiắm của một bài toán bất đẳng thức, cũng như tắp nghiắm của bài toán cân bằng, việc xác định chính xác các yếu tố này là rất quan trọng.
Trong lĩnh vực toán học, việc tìm hiểu về các bài toán chap nhắn tách là rất quan trọng Một trong những dạng cơ bản của bài toán này là bài toán cân bằng tách Trong bài viết này, chúng ta sẽ xem xét bài toán cân bằng tách, trong đó C là tập nghiệm của bài toán.
Tìm x ∗ thuộc K sao cho f (x ∗ , x) ≥ 0 với mọi x thuộc K trong bài toán tối ưu hóa (EP) Bài toán quy hoạch này nhằm tìm giá trị tối thiểu của hàm g(y) với y thuộc A(K) Trong đó, K là tập hợp các điểm khả thi trong không gian H 1, A là phép toán tuyến tính liên tục từ H 1 đến H 2, và g là một hàm lợi hữu hạn trong không gian H 2.
Ta can mđt so gia thiet sau cho thuắt toỏn và sn hđi tu cna thuắt toỏn đưoc trình bày dưói đây Gia thiet
(A1) Vói moi x ∈ C, f (x, x) = 0 và f (x, ) loi nua liên tuc dưói yeu trên K.
(A2) ∂ G f (x, x) ƒ= ∅, vúi MQI s > 0 và x ∈ K, là tắp con b% chắn cna K, trong đú ∂ G f (x, x) kớ hiắu là s- dưúi vi phõn cna hàm loi f (x, ) tai x, túc là
(A3) f gia đơn điắu trờn C vúi MQI nghiắm cna bài toỏn cõn bang EP (f, K), đieu đó có nghĩa f (x, x ∗ ) ≤ 0 vói MQI x ∈ C, x ∗ ∈ Sol(f, K) và thoa món đieu kiắn sau x ∗ ∈ Sol(f, K), y ∈ C, f (x ∗ , y) = f (y, x ∗ ) = 0 ⇒ y ∈ Sol(f,
(A4) Vói moi x ∈ K, f (., x) nua liên tuc trên yeu trên K.
Tái nhắc lại, ảnh xa gần của hàm lồi g với λ > 0, được định nghĩa bởi prox λg, là nghiệm duy nhất của bài toán lồi mạnh sau: prox λg(u) := argmin g(v) + ǁv − uǁ², với v thuộc không gian H.
Vói λ > 0, ta đ%nh nghĩa h(x) := 1 ǁ(I − prox λg )Axǁ 2 Su dung đieu toi ưu can và đn cho bài toán loi, ta thay h(x) = 0 neu và chi neu Ax là nghiắm cna y
P (u) vúi u = Ax Chỳ ý rang, thắm trớ g cú the khụng kha vi, h luụn kha vi và Oh(x) = A ∗ (I − prox λg )Ax Do đó, h(x) = 0 neu và chi neu Oh(x) = 0.
Sau đây, chúng ta sẽ xem xét toán và các hàm số được đề xuất trong tài liệu [6] Giả sử các tham số dương δ, ξ và các dãy số thống kê {a_k}, {δ_k}, {β_k} được sử dụng để phân tích.
{s k }, {ρ k } thoa món cỏc đieu kiắn sau.
Bưác k Tù x k tính g k ∈ ∂ s k f (x k , x k ) và đ%nh nghĩa α =β k γ k trong đó γ k max{δ k
Nhắn xột 2.2.1 Chỳ ý rang khi g ≡ 0, bài toỏn (SEO) tro thành bài toỏn
Nhắn xột 2.2.2 Neu cHQN s k = 0, thỡ x k = y k và h(x k ) = 0, hay núi cỏch khỏc x k là nghiắm Tự thnc te này, ta GQI x k là s-nghiắm neu s k ≤ s và ǁx k −y k ǁ ≤ s,
Trong bài toán tối ưu hóa (SEO), ta có điều kiện |h(x_k)| ≤ s Theo định lý 2.2.1, giả sử bài toán (SEO) có ít nhất một điểm nghiệm Khi đó, với những điều kiện (A1) đến (A4), dãy {x_k} được xác định bởi thuật toán 1 sẽ hội tụ tới nghiệm tối ưu của bài toán (SEO).
Ta can nhung bő đe dưúi đõy đe chỳng minh sn hđi tu cna thuắt toỏn.
Bo đe 2.2.1 (Xem [6]) Cho S là tắp nghiắm cua bài toỏn (SEO) và z ∈ S.
Neu Oh(y k ) ƒ= 0 thì ta có ǁz − zǁ
Bo đe 2.2.2 (Xem [6]) Vái mői k, các bat đang thúc sau thóa mãn i) α k ǁg k ǁ ≤ β k ; ii) ǁy k − x k ǁ ≤ β k
Bo đe 2.2.3 (Xem [6]) Cho z ∈ S Khi đó, vái mői k sao cho Oh(y k ) ƒ= 0 ta có k+1 − z ǁ ≤ ǁx − z ǁ h 2 (y k )
− ρ k (4 − ρ k ) ǁOh(y k )ǁ 2 + 2(1 − a k )α k f (x k , z) + A k (2.8) và vái mői k sao cho Oh(y k ) = 0, ta có ǁx − zǁ ≤ ǁx − zǁ + 2(1 − a k )α k f (x , z) + A k ,
Chúng minh Do đ%nh nghĩa cna x k+1 và su dung Bő đe 1.3.2, ta có k+1 − z ǁ
Ta xét hai trưòng hop sau ≤ a k ǁx − z ǁ + (1 − a k )ǁz − z ǁ
Trưàng hap 1: Neu Oh(y k ) ƒ= 0, theo Bő đe 2.2.1, ta có k+1 −z ǁ ≤ a k ǁx −z ǁ
Hơn nua, ta lai có ǁy − zǁ = ǁz − x + x − y ǁ k
Trong Thuắt toỏn 1, do y k đưoc cHQN sao cho và the x = z, ta có
Mắt khỏc, tự Bő đe 2.2.2, ta cú
Tù (2.12) và (2.13) và α k > 0 suy ra ǁy k − zǁ 2 ≤ ǁx k − zǁ 2 + 2α k f (x k , z) + 2α k s k + 2β k 2
(2.14) Ket hop (2.11) và (2.15), ta có ǁx k+1 − zǁ 2 ǁx k − zǁ 2 + 2(1 − a k )f (x k , z)
Trong Trường hợp 2, nếu Oh(y k) = 0, ta định nghĩa cận x k+1 với bất đẳng thức ǁx − zǁ ≤ a k ǁx − zǁ + (1 − a k )ǁz − zǁ Khi áp dụng tương tự như trong Trường hợp 1, ta có ǁy − zǁ ≤ ǁx − zǁ + 2α k f (x , z) + 2α k s k + 2β k.
Khi đó, ta thu đưoc ǁx − zǁ ≤ ǁx − zǁ + 2(1 − a k )f (x , z) + A k , trong đó A k = 2(1 − a k )(α k s k + β k 2).
Tiep theo, ta chúng minh Đ%nh lý 2.2.1.
Chứng minh rằng với mọi z ∈ S, tồn tại một hàm f đơn điệu trên C với MQI, dẫn đến việc z thuộc Sol(f, C) Do đó, ta có thể kết luận rằng bài toán cân bằng (EP) được thỏa mãn.
Neu Oh(y k ) ƒ= 0 thì do ǁy
− ρ k (4 − ρ k ) ǁOh(y k )ǁ 2 ≥ 0 nên theo Bő đe 2.2.3, ta có ǁx − zǁ ≤ ǁx − zǁ + A k , (2.15) trong đó A k = 2(1 − a k )(α k s k + β k 2).
Su dung Bő đe 1.3.3, ta thay rang {ǁx k − zǁ 2 } h®i tu vói MQI z ∈ S Do đó,
{x k } b% chắn Vỡ vắy theo Bő đe 2.2.2, ta cũng nhỡn thay rang {y k } b% chắn.
Khang đ%nh 2 lim sup f (x k , z) = 0 vói moi z S. k→+∞
Theo Bő đe 2.2.3, vói moi k, ta có
Mắt khỏc, su dung đieu kiắn (A2) và {x k } b% chắn, ta nhắn thay rang {ǁg k ǁ} b% chắn Khi đú, ton tai L > δ sao cho ǁg k ǁ ≤ L vúi moi k Vỡ vắy
Do z là nghiắm, su dung tớnh gia đơn điắu cna f , ta cú
−f (x , z) ≥ 0. Đieu này ket hop vúi 0 < a < a k < b < 1, ta nhắn đưoc
k=1 + ∞ nên ta có lim sup f (x k , z) = 0 z S. k→+∞ ∈
Khang đ%nh 3 Vói moi z ∈ S bat kỳ, gia su rang {x k j } là dãy con cna {x k } sao cho lim sup f (x k , z) = lim sup f (x k j , z) (2.18) k→+∞ j→+∞ và x ∗ là điem tu yeu cna {x k j } Khi đó, x ∗ ∈ Sol(f, C).
Không mat tính tőng quát, ta có the gia su rang {x k j } h®i tu yeu tói x ∗ khi j → +∞ Do f (., z) nua liên tuc trên, su dung Khang đ%nh 2, ta có f (x ∗ , z) lim sup f (x k j , z) = 0. j→+∞
Do z ∈ S và f gia đơn điắu, ta cú f (x ∗ , z) ≤ 0.
Như vắy, f (x ∗ , z) = 0 Mđt lan nua theo tớnh gia đơn điắu ta nhắn đưoc f (z, x ∗ ) ≤ 0 Vì the f (x ∗ , z) = f (z, x ∗ ) = 0.
Khi đú, su dung tớnh tien đơn điắu (A3), ta cú the ket luắn rang x ∗ cũng là nghiắm cna bài toỏn EP (f, C).
Khang đ%nh 4 M QI điem tu yeu x cna dãy {x k } thoa mãn x ∈ C và
Lay x là điem tu yeu cna {x k } và {x k j } là dãy con cna {x k } h®i tu yeu tói x Khi đú, x ∈ C Mắt khỏc, ta biet rang ǁy k đó
Vỡ vắy {y k j } hđi tu yeu túi x. ǁy − x ǁ = 0.
Tù Bő đe 2.2.3, neu Oh(y k ) ƒ= 0 thì h 2 (y k ) k
≤ ǁx và neu Oh(y k ) = 0 thì
0 ≤ ǁx k − zǁ 2 − ǁx k+1 − zǁ 2 + A k Đắt N 1 := {k : Oh(y k ) ƒ= 0} và lay tőng ta cú the viet như sau k Σ ∈
Ket hop vói gia su ξ ≤ ρ k ≤ 4 − ρ và 0 < a < a k < b < 1, ta có the ket luắn rang k Σ ∈N k h 2 (y k ) ǁOh(y k )ǁ 2 < +∞ (2.19)
Hơn nua, do Oh liên tuc Lipschitz vói MQI hang so ǁAǁ 2 , ta có ǁOh(y k )ǁ 2 b% chắn Boi vắy h(y k ) → 0 vúi MQI k ∈ N 1 và k → +∞ Chỳ ý rang h(y k ) = 0 vói MQI k ∈/ N 1 Tương đương k→+lim
Boi tính nua liên tuc yeu cna h, ta có
0 ≤ h(x) ≤ lim inf h(y k j ) = lim inf h(y k ) = 0 (2.21) j→+∞ k→+∞ Đieu đó kéo theo Ax là điem co đ%nh cna toán tu gan ke cna g Do đó, Ax ∈ argming.
Khang đ%nh 5 lim k→+∞ x k = lim k→+ ∞ y k = lim k→+ ∞
P (x k ) = x ∗ , trong đó x ∗ là điem tu yeu cna dãy thoa mãn 2.18.
Tù Khang đ%nh 3 và Khang đ%nh 4, ta có the suy ra x ∗ ∈ S Boi Khang đ%nh 1, ta có the gia su rang
Do Bő đe 1.3.3, ta có k→+lim
∞ ǁx k − x ∗ ǁ = c < +∞. đieu đó kéo theo ǁz k − x ∗ ǁ ≤ ǁy k − x ∗ ǁ
≤ ǁx k − x ∗ ǁ + β k , lim sup ǁz k − x ∗ ǁ ≤ lim sup(ǁx k − x ∗ ǁ + β k ) = c.
Mắt khác k→+∞ k→+∞ k→+ ∞ lim k→+ ∞ ǁa k (x k − x ∗ ) + (1 − a k )(z k − x ∗ )ǁ lim ǁx k+1 − x ∗ ǁ = c.
Su dung Bő đe 1.3.4 vói v k := x k − x ∗ và w k := z k − x ∗ , ta có lim sup z k x k = 0 (2.22) k→+∞
Ket hop 2.22 vói x ∗ là điem tu cna dãy {x k }, ta thay rang x ∗ cũng là điem tu yeu cna dãy {z k } Gia su {z k j } h®i tu yeu tói x ∗ Chú ý rang ǁx k j +1 − P S (x k j +1 )ǁ 2 ≤ ǁx k j − P S (x k j )ǁ 2
Do đó ǁz k j − P S (x k j )ǁ 2 = ǁz k j − x k j ǁ 2 ǁx k j +1 − P S (x k j )ǁ 2
Dóy {x k j } b% chắn nờn dóy {x k j −P S (x k j } cũng b% chắn Su dung lim ǁz k j − x k j = 0 vàlim j→+∞ a k j
1, ta cú the ket luắn rang 2 j→+lim
Bõy giũ, ta chỳng minh {P S (x k j } là dóy Cauchy Thắt vắy, vúi MQI m > j, ta có ǁP S (x k m − P S (x k j )ǁ 2 = 2ǁx k m − P S (x k m )ǁ 2 + 2ǁx k m − P S (x k j ǁ 2 k m 1
Do đú, ỏp dung Bő đe 1.3.1 vúi z = P S (x k j ), ta nhắn đưoc ǁx k m − P S (x k j )ǁ 2 ≤ 2ǁx k m − − P S (x k m )ǁ 2 + A k −1
Tù 2.24 và 2.25, ta thu đưoc k m −1 ǁP S (x k m − P S (x k j )ǁ 2 ≤ 2ǁx k j − P S (x k j ǁ 2 + 2 A i − 2ǁx k m − P S (x k m )ǁ 2 i=k j
A i = 0, ta cú the ket luắn rang {P S (x k j } là dóy Cauchy. j→+∞ i=k j
Do đó, P S (x k j ) h®i tu manh tói x ∗ S Do lim j→+∞ ǁx k m +1 + P S (x k j +1 ǁ = 0, nên dãy {x k j } h®i tu manh tói x ∗ Cuoi cùng, su dung Khang đ%nh 1, ta có the ket luắn rang k→+lim
Nhắn xột 2.2.3 Trong trưũng hop, bài toỏn khụng ton tai nghiắm thỡ dóy phộp lắp đưoc xỏc đ%nh boi Thuắt toỏn 1 cú the khụng b% chắn Ta thay,
∈ k m k m trong đú, i M viet tat cna hàm chi cna tắp M Rừ ràng, trong trưũng hop bài toán SEO đưoc rút gQN thành tìm điem trong S := K ∩ Q = ∅.
K.Vỡ vắy, tai moi vũng lắp k, ta luụn cú g k (0, 0) = 0 và do đú x k = y k vói MQI k Do
S := K ∩ Q = ∅ nên h k (y k ) 0 Chú ý rang prox λ (x) = P Q (x) vói λ > 0 bat g kỳ Bang phép tính toán cơ ban, su dung y k = x k , ta chúng minh đưoc rang z k = P K (y k − à k (I − prox λ )(y k )) = P K (P Q (x k )).
Trong bài viết này, chúng ta xem xét dãy x k := (u k , v k ) với giới hạn khi k tiến tới vô cực, lim u k = +∞ Khi đó, hình chiếu của x k lên Q là (u k , 0), trong khi hình chiếu của (u k , 0) lên K nằm trên biên của K Giả sử rằng (a k 1
,a k ) là hình chieu cna (u k , 0) lờn K Khi đú a k là nghiắm toi ưu cna bài toỏn min ϕ a≥1 k (a), trong đú ϕ (a) = Σ (u k − a) 2 + 1 Σ loi manh trên [1, +∞) Do u k ≥ 1 nên ϕ J u k + 1 Σ < 0.
Do u k 1 vúi MQI k nờn ta cú the ket luắn rang lim k→+∞ u k = +∞.
2.3 Úng dnng vào bài toỏn san xuat điắn
Trong phần này, chúng ta sẽ xem xét mô hình cân bằng tối ưu, được coi là trường hợp mô hình hoàn hảo trong khuôn khổ lý thuyết trò chơi Nash - Cournot trong hệ thống hai người chơi.
Trong bài viết này, chúng ta giả sử rằng có một công ty sản xuất điện với ký hiệu x là vectơ của các TQA, trong đó xj đại diện cho năng lượng sinh ra bởi đơn vị j Giả sử rằng giá điện pi(s) là hàm affine tăng theo s = Σ xj, với N là tổng số nhà máy sản xuất điện, được biểu diễn bằng công thức pi(s) = α - βi s Lợi nhuận của công ty được tính theo công thức fi(x) = pi(s)(Σ xj) - Σ cj(xj), trong đó cj(xj) là chi phí để sản xuất ra xj với đơn vị j Giả sử Ki là tập chiến lược của công ty, tức là điều kiện sau được thỏa mãn với MQI i xj ∈ Ki.
Khi đú, tắp chien lưoc cna mụ hỡnh là K := K 1 ì K 2 ì ã ã ã ì K n
Trên thị trường toàn cầu, mọi công ty đều tìm cách tối đa hóa lợi nhuận của mình bằng cách cải thiện mức sản xuất tương ứng với giá thành sản xuất của các công ty khác Cách tiếp cận cho mục tiêu này là dựa trên lý thuyết trò chơi Nash.
Điểm cân bằng Nash trong mô hình được xác định khi x ∗ ∈ K = K 1 ∪ K 2 ∪ ∪ K n, thỏa mãn điều kiện f i (x ∗ ) ≥ f i (x ∗ [x i ]) cho mọi x i ∈ K i và mọi i = 1, 2, , n Trong đó, vectơ x ∗ [x i ] được biểu diễn bằng cách thay thế x ∗ i bằng x i Bằng cách sử dụng hàm f (x, y) := ψ(x, y) − ψ(y, x) với ψ(x, y) := − f i (x[y i ]), bài toán tìm điểm cân bằng Nash có thể được mô tả một cách chính xác.
