3.2 Một số bài toán tối ưu liên quan đến bài toán bù tuyến tính 42
3.2.3 Trò chơi song ma trận (Bimatrix Games)
Cho A và B là hai ma trận cấp m ×n.
Kí hiệu tập chiến lược của người chơi I và II lần lượt là σm = {x ∈ Rm+ : eTmx = 1} và σn = {y ∈ Rn+ : eTny = 1}.
trong đó em = (1,1, ....,1) ∈ Rm;en = (1,1, ....,1) ∈ Rn. Với x ∈ σm và y ∈ σn ta biểu thị hàm chi trả của người chơi I và II (trò chơi hợp tác) tương ứng là
xTAy và xTBy.
Trò chơi hợp tác song ma trận (Kí hiệu Γ(A, B)) được hiểu như sau.
Người chơi thứ 1 có m chiến lược "đơn" biểu thị là các véctơ chính tắc đơn vị của Rm. Tương tự người chơi thứ 2 có n chiến lược "đơn". Chiến lược x = (x1, ..., xm) ∈ σm, nghĩa là xi ≥ 0,∀i = 1, m và
m
P
i=1
xi = 1, các thành phần xi biểu thị xác suất chiến lược đơn thứ i xuất hiện. Tương tự với chiến lược y ∈ σn của người chơi thứ 2.
Hai ma trận A = (aij), B = (bij);i = 1, m;j = 1, n biểu thị chi phí hai người chơi phải trả cụ thể là: aij là chi phí người thứ 1 phải trả khi người chơi thứ 1 chọn chiến lược "đơn" thứ i, người chơi thứ 2 phải trả tương tự như trên. Khi hai người chơi chọn chiến lược x ∈ σm, y ∈ σn thì xTAy và xTBy lần lượt là chi phí của người chơi thứ 1, thứ 2 phải trả.
Cặp chiến lược (x∗, y∗) với x∗ ∈ σm, y∗ ∈ σn được gọi là một nghiệm cân bằng Nash nếu
(x∗)TAy∗ ≤xTAy∗, với mọi x ∈ σm (x∗)TBy∗ ≤ (x∗)TBy, với mọi y ∈ σn
Nói cách khác, cặp chiến lược (x∗, y∗) là nghiệm cân bằng Nash khi người chơi thứ 1 đã chọn chiến lược x∗ thì chiến lược y∗ là chiến lược tốt nhất người chơi thứ 2 chọn và ngược lại.
Ta biểu thị nghiệm cân bằng N ash(x∗, y∗) là nghiệm của bài toán tuyến tính LP:
min(Ay∗)Tx nếu eTx = 1, x ≥0 và
min(BTx∗)Ty nếu eTy = 1, y ≥ 0.
Để đưa mô hình trò chơi Γ(A, B) về bài toán bù tuyến tính, ta giả sử A và B là hai ma trận các thành phần aij ≥ 0;bij ≥ 0,∀i ∈ 1, m;j ∈ 1, n. Xét bài toán bù tuyến tính LCP
u = −em +Ay ≥ 0, x ≥ 0, xTu = 0, v = −en +BTx ≥0, y ≥0, yTv = 0, Trong trường hợp này, ta có
w = u
v
, q =
−em
−en
, M =
0 A BT 0
, z = x
y
. trong đó
em = (1, . . . ,1) ∈ Rm en = (1, . . . ,1) ∈ Rn.
Có thể thấy rằng nếu (x∗, y∗) là một điểm cân bằng Nash của Γ(A, B) thì
(x0, y0) =
x∗
(x∗)TBy∗, y∗ (x∗)TAy∗
là nghiệm của bài toán bù tuyến tính LCP (q, M) được cho ở trên. Ngược lại, nếu (x0, y0) là nghiệm của bài toán bù tuyến tính LCP (q, M) thì
(x∗, y∗) =
x0
eTmx0, y0 eTny0
là một điểm cân bằng Nash của Γ(A, B).
3.3 Mối liên hệ bài toán bù tuyến tính với hệ ràng buộc tuyến tính
Xét bài toán bù tuyến tính LCP(q, M) ở mục 3.1 x ≥0
q + M x≥ 0,
xT(q +M x) = 0.
Bài toán bù tuyến tính có thể được mô tả bởi hệ thống ràng buộc sau.
Đặt
A = M
E
∈ R(2n)×n, b = q
0
∈ R2n
trong đó E ∈ Rn×n là ma trân đơn vị và K =
u v
∈ Rn×Rn |u ≥ 0, v ≥ 0, vTu = 0
Ta thấy x ∈ Sol(M, q) khi và chỉ khi Ax+b ∈ K. Đặt W = R(2n)×n×Rn và xét hàm S : W ⇒Rn định nghĩa bởi
S(w) ={x ∈ Rn|Ax+b ∈ K} ∀w = (A, b) ∈ W.
Vì vậy tập nghiệm của bài toán bù tuyến tính LCP trên chính là tập nghiệm của hệ ràng buộc tuyến tính.
Để nghiên cứu tính liên tục tập nghiệm của bài toán bù tuyến tính ta nghiên cứu tính liên tục của tập nghiệm đối với hệ ràng buộc tuyến tính.
3.4 Tính tựa Lipschitz của tập nghiệm trong bài toán bù tuyến tính
Để thuận tiện, ta kí hiệu tập K ở phần trên về dạng K =
u v
∈ Rn×Rn | ui
vi
∈ Ki, i ∈ I = {1,2, ..., n}
, (3.1) trong đó
Ki =
ui vi
∈ R2 |ui ≥ 0, vi ≥ 0, uivi = 0
. (3.2)
Định nghĩa 3.4.1. Ta nói rằng ánh xạ tập nghiệm Sol(.) của bài toán LCP thoả mãn cận bị chặn đều địa phương tại điểm (( ¯M ,q),¯ x)¯ nếu
tồn tại hằng số r > 0, δ > 0 và một lân cận V của x¯ sao cho d(x;Sol(M, q)) ≤ r
n
X
i=1
d
(M x+q)i xi
;Ki
, (3.3)
với mọi x ∈ V và (M, q) thoả mãn kM −M¯k+kq −qk¯ < δ. Từ (3.3) ta có thể suy ra
d(x;Sol( ¯M ,q))¯ ≤r
n
X
i=1
d
( ¯M x+ ¯q)i xi
;Ki
. (3.4)
với mọi x ∈ V. Chú ý rằng (3.4) biểu thị cận bị chặn địa phương theo nghĩa thông thường: vế trái là khoảng cách từ x đến tập nghiệm S( ¯M ,q)¯ trong khi vế phải biểu thị cận bị chặn là r > 0. Nếu x ∈ Sol( ¯M ,q)¯ (tương ứng x ∈ Sol(M, q)), thì vế phải của (3.4) (tương ứng (3.3)) bằng 0. Bây giờ ta định nghĩa điều kiện chính quy tại x¯ ∈ Sol( ¯M ,q)¯ là:
Với x¯ ∈ Sol( ¯M ,q)¯, ta kí hiệu các tập chỉ số: I1 = {i ∈ I = {1,2, ..., n} :
¯
xi = 0,( ¯Mx¯+ ¯q)i > 0}
I2 = {i ∈ I : ¯xi > 0; ( ¯Mx¯+ ¯q)i = 0}
I3 = {i ∈ I : ¯xi = 0; ( ¯Mx¯+ ¯q)i = 0}.
Rõ ràng I = I1 ∪I2 ∪I3. Nếu u0 = (u01, . . . , u0n)T ∈ Rn thỏa mãn
với mỗi i ∈ I1, u0i = 0
với mỗi i ∈ I2,( ¯MTu0)i = 0
với mỗi i ∈ I3, u0i = 0 hoặc ( ¯MTu0)i = 0, hoặc u0i ≤ 0 và ( ¯MTu0)i ≥ 0, (3.5) thì u0 = 0.
Ta kí hiệu
L1 = {u0 = (u01, . . . , u0n)|u0i = 0 ∀i ∈ I1},
L2 = {u0 = (u01, . . . , u0n)|( ¯MTu0)i = 0 ∀i ∈ I2},
L3 = {u0 = (u01, . . . , u0n)|u0i = 0, hoặc ( ¯MTu0)i = 0,hoặc u0i ≤ 0 và ( ¯MTu0)i ≥
0,∀i ∈ I3}.
Khi đó L1 và L2 là các không gian con tuyến tính của Rn, L3 là hợp hữu hạn các nón đóng. Điều kiện chính qui (3.5) trở thành:
u0 ∈ L1 ∩ L2 ∩L3 ⇒u0 = 0 ,(∀u0 ∈ Rn).
Ví dụ. Cho n = 2, M =
1 −2 1 1
. Ta xét 3 tình huống sau:
(a) ¯q = √1
2
và x¯ = 0
0
. Ở đây I1 = I = {1,2}.
(b) ¯q = 1
−5
và x¯ = 3
2
. Ở đây I1 = I = {1,2} và detM¯ 6= 0.
(c) ¯q = 2
−1
và x¯ = 0
1
. Ở đây I1 = ∅, I2 = {2}, I3 = {1}.
Khi đó ta có L1 ∩L2 ∩L3 chứa duy nhất một phần tử u0 = 0. Sau đây là kết quả chính của chương.
Định lí 3.4.1. Giả sử x¯ ∈ Sol( ¯M ,q)¯. Nếu điều kiện chính quy (3.5) tại
¯
x được thoả mãn thì bài toán LCP có cận bị chặn đều địa phương trong (3.3) và có cận bị chặn địa phương (3.4) tại điểm (( ¯M ,q),¯ x)¯ . Hơn nữa ánh xạ tập nghiệm Sol(.) của nó là tựa Lipschitz địa phương xung quanh điểm (( ¯M ,q¯),x)¯ .
Chứng minh. Theo định lý 2.4.2, nếu (2.9) được thoả mãn thì tồn tại một hằng số r > 0, một lân cận U của w¯ và một lân cận bị chặn V của x¯ thoả mãn
d(x;S(w)) ≤ rd(Ax+b;K), (3.6) với mọi w = (A, b) ∈ U và x ∈ V. Do đó, ta có
d(Ax+b;K) =d
(M x+ q) x
;K
.
Nhắc lại rằng x ∈ S(w) nếu và chỉ nếu x ∈ Sol(M, q). Do đó, theo (3.6) tồn tạiδ > 0sao cho với bất kìx ∈ V và(M, q)vớikM−M¯k+kq−qk¯ < δ,
ta có
d(x;Sol(M, q)) ≤ rd
(M x+q) x
;K
= r
n
X
i=1
d
(M x+q)i xi
;Ki
. (3.7) Do đó, từ điều kiện (2.9), ta được (3.3),(3.4).
Hơn nữa, từ (3.7) và tương tự như trong chứng minh bổ đề 2.4.1 ,tồn tại một hằng số l = max{r, ra} thoả mãn
Sol(M1, q1)∩V ⊂ Sol(M2, q2) +l(kM2 −M1k+kq2 −q1k) ¯BRn với bất kì (M1, q1),(M2, q2) với kM1−M¯k+kq1−qk¯ < δ và kM2−M¯k+ kq2 −q¯k< δ.
Do đó, ánh xạ nghiệm Sol(.)là tựa Lipschitz địa phương xung quanh điểm (( ¯M ,q),¯ x)¯ .
Để kết thúc chứng minh, ta chỉ cần chỉ ra rằng(2.9)tương đương với(3.5). Lấy
u0 v0
∈ ker ¯AT ∩N(¯y;K).
Rõ ràng rằng u0
v0
∈ ker ¯AT nếu và chỉ nếu M¯Tu0+ v0 = 0. Do đó, ker ¯AT =
u0 v0
|u0 ∈ Rn, v0 ∈ −M¯Tu0
. (3.8)
Sử dụng biểu diễn (3.1) cho K mà các nón Ki được cho trong (3.2), suy ra
N(¯y;K) =N
M¯x¯+ ¯q
¯ x
;K
=
n
Y
i=1
N
( ¯Mx¯+ ¯q)i
¯ xi
;Ki
, với
N
( ¯Mx¯+ ¯q)i
¯ xi
;Ki
=
{0} ×R nếu i ∈ I1, R× {0} nếu i ∈ I2,
({0} ×R)∪(R× {0})∪Rn− nếu i ∈ I3.
Do đó, bởi (3.8), ta thấy rằng điều kiện chính quy (3.5) có thể được viết lại theo dạng (2.9).
Kết luận
Luận văn "Đối đạo hàm và ánh xạ tập nghiệm của hệ ràng buộc tuyến tính" đề cập đến các nội dung chính sau
1. Các khái niệm và tính chất của đối đạo hàm.
2. Ánh xạ tựa Lipschitz và mối liên hệ với đối đạo hàm.
3. Tính chính qui mêtric và mối liên hệ với tính tựa Lipschitz.
4. Tính tựa Lipschitz và chính qui mêtric đối với ánh xạ tập nghiệm của hệ ràng buộc tuyến tính.
5. Mối liên hệ giữa bài toán tối ưu và bài toán bù tuyến tính.
6. Tính tựa Lipschitz đối với tập nghiệm của bài toán bù tuyến tính.