ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ DUNG PHƯƠNG PHÁP ĐIỂM GẦN KỀ GIẢI MỘT BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN HỖN HỢP DC LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ DUNG PHƯƠNG PHÁP ĐIỂM GẦN KỀ
GIẢI MỘT BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN HỖN HỢP DC Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học: GS.TSKH. Lê Dũng Mưu
THÁI NGUYÊN - 2016
i
Mục lục
Lời mở đầu ii
1 Kiến thức cơ bản về hàm lồi và tập lồi 1
. 1.1 Tập lồi và tập lồi đa diện . . . . . . . . . . . . . . . . . . 1
. 1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
. 1.3 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . . 6
. 1.4 Tính đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Bài toán bất đẳng thức biến phân 9
2.1 Phát biểu bài toán và ví dụ . . . . . . . . . . . . . . . . . . 9
. 2.2 Môt số tính chất . . . . . . . . . . . . . . . . . . . . . . . 10
. 2.2.1 Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . 10
2.2.2 Các bài toán liên quan . . . . . . . . . . . . . . . . 15
3 Bài toán bất đẳng thức biến phân hỗn hợp DC 19
. . . . . . . . . . . . . . . . . 3.1 Hàm DC . . . . . . . . . . . 19
. . . . . . . . . . . . . . . . . 3.2 Phát biểu bài toán và ví dụ . 23
3.3 Phương pháp điểm gần kề giải bài toán bất đẳng thức biến
. . . . . . . . . . . phân hỗn hợp DC . . . . . . . . . . . . 24
. . . . . . . . . . . 3.4 Một mô hình cân bằng bán độc quyền . 33
Kết luận 36
Tài liệu tham khảo 37
ii
Lời mở đầu
Bất đẳng thức biến phân là một bài toán quan trọng trong toán học ứng
dụng. Do đó bài toán này đã được nhiều người quan tâm nghiên cứu.
Trong hướng nghiên cứu này, phương pháp điểm gần kề giải một bài toán
bất đẳng thức biến hỗn hợp DC là một đề tài quan trọng. Mục đích của luận
văn này là tập trung giới thiệu trình bày về bài toán bất đẳng thức biến phân,
một số tính chất về tập nghiệm của bất đẳng thức biến phân. Đặc biệt đi sâu
vào việc giới thiệu phương pháp giải lớp bài toán này. Luận văn bao gồm 3
chương.
Chương 1: Các kiến thức cơ bản về giải tích lồi, chương này nhắc lại và
trình bày các khái niệm, định lý, tính chất dùng để nghiên cứu bài toán bất
đẳng thức biến phân ở chương sau.
Chương 2: Bài toán bất đẳng thức biến phân, chương này trình bày định
nghĩa về bài toán bất đẳng thức biến phân và các ví dụ. Đồng thời cũng trình
bày về sự tồn tại và tính chất tập nghiệm bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều Rn.
Chương 3: Trình khái niệm, tính chất hàm DC, phương pháp điểm gần kề
giải một bài toán bất đẳng thức biến hỗn hợp DC.
Nhân dịp này tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy giáo hướng
dẫn GS. TSKH. Lê Dũng Mưu, người thầy đã tận tình hướng dẫn, giúp đỡ tôi
trong suốt quá trình làm và hoàn thiện luận văn.
Tôi cũng xin kính gửi lời cảm ơn tới các thầy, các cô trong Khoa Toán -
Tin, các bạn sinh viên trong lớp cao học toán K8A, trường Đại học Khoa học
đã tạo điều kiện thuận lợi, động viên, và giúp đỡ tôi trong suốt quá trình học
iii
tập và nghiên cứu tại trường. Tôi cũng xin bày tỏ lòng biết ơn sâu sắc tới gia
đình và người thân đã luôn khuyến khích, động viên giúp đỡ tôi trong suốt
quá trình học cao học và hoàn thành luận văn này.
Tôi xin trân trọng cảm ơn!
Thái Nguyên, 2016 Nguyễn Thị Dung
Học viên Cao học Toán K8A,
Trường ĐH Khoa học - ĐH Thái Nguyên
1
Chương 1
Kiến thức cơ bản về hàm lồi và tập lồi
Dưới đây, ta nhắc lại một số khái niệm và tính chất cơ bản của giải tích lồi
như: Tập lồi, hàm lồi, dưới vi phân,.... Các kiến thức trong chương này được
lấy chủ yếu từ các tài liệu ([1]), ([3]) và sẽ được sử dụng ở các chương sau.
1.1 Tập lồi và tập lồi đa diện
Cho hai điểm a, b ∈ Rn. Tập tất cả các điểm x = (1 − λ)a + λb với
λ ∈ [0, 1] gọi là đoạn thẳng (đóng) nối a, b và được kí hiệu là [a, b].
Định nghĩa 1.1. Một tập C ⊆ Rn được gọi là một tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kì thuộc nó. Tức là, nếu (1 − λ)a + λb ∈ C với
mọi a, b ∈ C và mọi λ ∈ [0, 1].
Hình 1.1: Tập A lồi. Tập B không lồi
k (cid:88)
Định nghĩa 1.2. Điểm x ∈ Rn có dạng
i=1
x = λ1a1 + λ2a2 + ... + λkak = λiai
2
k (cid:88)
với
i=1
ai ∈ Rn, λi ≥ 0, λi = 1
được gọi là một tổ hợp lồi của các điểm a1, a2, ..., ak.
Tập C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các phần tử thuộc
nó.
Thứ nguyên (số chiều) của một tập lồi C, kí hiệu là dimC, là thứ nguyên (số chiều) của bao affine của nó. Một tập lồi C trong Rn gọi là có thứ nguyên đầy nếu dimC = n.
Định nghĩa 1.3. Điểm x ∈ Rn có dạng
x = λ1a1 + λ2a2 + ... + λkak
k (cid:88)
và
i=1
ai ∈ Rn, λi = 1
được gọi là tổ hợp affine của các điểm a1, a2, ..., ak.
M là một tập affine khi và chỉ khi M chứa mọi tổ hợp affine các phần tử
thuộc nó.
Giao của một họ các tập affine cũng là một tập affine. Cho E là môt tập bất kì trong Rn, có ít nhất một tập affine chứa E, cụ thể
là Rn. Một số tập lồi đáng chú ý:
a) Siêu phẳng là tập có dạng
H = {x ∈ Rn : aT x =α, a ∈ R\{0}, α ∈ R}.
b) Nửa không gian đóng
H1 = {x ∈ Rn : aT x ≤ α}, H2 = {x ∈ Rn : aT x ≥ α}.
c) Nửa không gian mở
K1 = {x ∈ Rn : aT x < α}, K2 = {x ∈ Rn : aT x > α}.
3
d) Hình cầu đóng
B(a, r) = {x ∈ Rn : (cid:107)x − a(cid:107) ≤ r }, a ∈ Rn, r > 0
e) Tập lồi đa diện
D = {x ∈ Rn : Ax ≤ b}, trong đó A ∈ Rm×n, b ∈ Rm.
f) Nón lồi đa diện
K = {x ∈ Rn : Ax ≤ 0}, trong đó A ∈ Rm×n, 0 ∈ Rm.
Từ định nghĩa tập lồi trực tiếp suy ra một số tính chất đơn giản sau:
a) Giao của một họ bất kì các tập lồi là tập lồi.
b) Tổng, hiệu hai tập lồi cũng là tập lồi
C ± D = {x ± y : x ∈ C, y ∈ D}
c) Nếu C ⊂ Rm, D ⊂ Rn thì tích C × D = {(x, y) : x ∈ C, y ∈ D} là
một tập lồi trong Rm×n. (Có thể mở rộng cho tích của nhiều tập lồi).
Định nghĩa 1.4. Cho E là một tập bất kì trong Rn.
a) Giao của một tập affine chứa E gọi là bao affine của E, kí hiệu là
affE. Đó là tập affine nhỏ nhất chứa E.
b) Giao của tất cả các tập lồi chứa E gọi là bao lồi của E, kí hiệu là
conE. Đó là tập lồi nhỏ nhất chứa E.
Định nghĩa 1.5. Một tập con K của Rn được gọi là một nón hay tập nón nếu với mọi x ∈ K và mọi λ > 0 thì λx ∈ K. Nón K được gọi là một nón lồi nếu
K là tập lồi.
Định nghĩa 1.6. Một tập là giao của một số hữu hạn các nửa không gian đóng gọi là một tập lồi đa diện. Nói cách khác, đó là tập nghiệm của một hệ
hữu hạn bất phương trình tuyến tính:
i = 1, 2, ..., m ai1x1 + ai2x2 + ... + ainxn ≤ bi,
nghĩa là tập các x nghiệm đúng Ax ≤ b với A = (aij) ∈ Rm×n, b = (b1, ..., bm)T .
4
Nhận xét 1.7. Vì một phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất phương trình tuyến tính nên tập nghiệm của một hệ (hữu hạn)
phương trình và bất phương trình tuyến tính cũng là một tập lồi đa diện.
Một tập lồi đa diện có thể không bị chặn (không giới nội). Một tập lồi đa
diện bị chặn (giới nội) còn được gọi là một đa diện lồi.
Định nghĩa 1.8. Ta nói hai tập lồi khác rỗng C, D trong Rn tách được bởi siêu phẳng H = { x ∈ Rn : (cid:104)t, x(cid:105) = α} , t ∈ Rn\ { 0} và α ∈ R, nếu
(cid:104)t, y(cid:105) . (1.1) inf x∈C (cid:104)t, x(cid:105) ≥ α ≥ sup y∈D
Định lý 1.1. (Định lý tách I). Hai tập lồi C và D trong Rn khác rỗng, không có điểm chung có thể tách được bởi một siêu phẳng, nghĩa là tồn tại vectơ t ∈ Rn(t (cid:54)= 0) và một số α ∈ R sao cho (1.1) thỏa mãn.
Định nghĩa 1.9. Ta nói hai tập lồi khác rỗng C, D trong Rn là tách hẳn bởi siêu phẳng H = { x ∈ Rn : (cid:104)t, x(cid:105) = α} , t ∈ Rn\ { 0} và α ∈ R, nếu
(cid:104)t, y(cid:105) . (1.2) inf x∈C (cid:104)t, x(cid:105) > α > sup y∈D
Định lý 1.2. (Định lý tách II). Hai tập lồi đóng C và D trong Rn khác rỗng, không cắt nhau với ít nhất một trong hai tập này là compact, có thể tách hẳn bới một siêu phẳng, nghĩa là tồn tại một vectơ t ∈ Rn(t (cid:54)= 0) và một số α ∈ R
sao cho (1.2) thỏa mãn.
1.2 Hàm lồi
Định nghĩa 1.10. Hàm f : S → (−∞, +∞] xác định trên một tập hợp lồi S ⊆ Rn được gọi là một hàm lồi trên S nếu với mọi x1, x2 ∈ S và mọi số thực
λ ∈ [0, 1] ta có
f (cid:2)(1 − λ) x1 + λx2(cid:3) ≤ (1 − λ) f (cid:0)x1(cid:1) + λf (cid:0)x2(cid:1) .
5
• Hàm f được gọi là lồi chặt trên S nếu với mọi x1, x2 ∈ S, x1 (cid:54)= x2 và
mọi λ ∈ (0, 1) ta có
f (cid:2)(1 − λ) x1 + λx2(cid:3) < (1 − λ) f (cid:0)x1(cid:1) + λf (cid:0)x2(cid:1) .
Hiển nhiên một hàm lồi chặt là lồi, nhưng điều ngược lại không đúng.
• Hàm f được gọi là hàm lõm (lõm chặt) trêm S nếu −f là lồi (lồi chặt)
trên S, gọi là tuyến tính affine trên S nếu f hữu hạn và vừa lồi vừa lõm trên S. Một hàm affine trên Rn có dạng f (x) = (cid:104)a, x(cid:105) + α với a ∈ Rn, α ∈ R, bởi vì với mọi x1, x2 ∈ Rn và mọi λ ∈ [0, 1] ta có
f (cid:2)(1 − λ) x1 + λx2(cid:3) = (1 − λ) f (cid:0)x1(cid:1) + λf (cid:0)x2(cid:1) .
Tuy nhiên, hàm affine không lồi chặt hay lõm chặt.
Định nghĩa 1.11. Cho hàm bất kì f : S → (−∞, +∞] với S ⊆ Rn, các tập
domf = {x ∈ S : f (x) < +∞}
và
epif = {(x, α) ∈ S × R : f (x) ≤ α} ,
được gọi lần lượt là miền hữu dụng và tập trên đồ thị của hàm f . Nếu domf
khác rỗng (f không đồng nhất bằng +∞) và f (x) > −∞ với mọi x ∈ S thì
ta nói hàm f là chính thường. Nói cách khác, f chính thường nếu domf (cid:54)= ∅
và f hữu hạn trên domf .
Có thể chứng minh rằng hàm f lồi và không nhận giá trị −∞ trên S khi
và chỉ khi một trong hai điều kiện sau thỏa mãn
a) Tập trên đồ thị epif là một tập lồi.
m (cid:88)
k=1
k=1
b) (cid:33) (cid:32) m (cid:88) f ≤ λkxk λkf (cid:0)xk(cid:1)
m (cid:80) k=1
với mọi xk ∈ S, λk = 1, λk ≥ 0 với mọi k (bất đẳng thức Jensen).
6
Định lý 1.3. Cho C là một tập lồi, khác rỗng trong Rn và f : Rn → R là một hàm lồi. Mọi điểm cực tiểu địa phương của f trên C đều là điểm cực tiểu
toàn cục. Tập tất cả các điểm cực tiểu của f trên C:
Argminx∈Cf (x)
là một tập con lồi của C.
Định lý 1.4. Hàm lồi chính thường f trên Rn liên tục tại mọi điểm trong của miền hữu dụng của nó (f liên tục trên int(domf )).
Định lý 1.5. Giả sử f là một hàm lồi chính thường trên Rn. Khi đó các điều kiện sau là tương đương:
a) f liên tục tại điểm x. b) f bị chặn trên trong một tập mở chứa x0.
c) int(epif ) (cid:54)= ∅.
d) int(domf ) (cid:54)= ∅ và f liên tục trên int(domf ).
1.3 Dưới vi phân
Định nghĩa 1.12. Vectơ w ∈ Rn được gọi là dưới đạo hàm của f tại x0 ∈ Rn nếu
(cid:10)w, x − x0(cid:11) ≤ f (x) − f (cid:0)x0(cid:1) , ∀x ∈ Rn.
• Tập hợp tất cả các dưới đạo hàm của hàm f tại x0 được gọi là dưới vi
phân của f tại x0 và kí hiệu là ∂f (cid:0)x0(cid:1) . Vậy
∂f (cid:0)x0(cid:1) := (cid:8)w ∈ Rn : (cid:10)w, x − x0(cid:11) ≤ f (x) − f (cid:0)x0(cid:1) , ∀x ∈ Rn(cid:9) .
• Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂f (cid:0)x0(cid:1) (cid:54)= ∅.
Ví dụ 1.1. Cho C là một tập lồi, khác rỗng của không gian Rn. Xét hàm chỉ trên tập lồi C có dạng.
(cid:40) 0 nếu x ∈ C, δC (x) := +∞ nếu x /∈ C.
7
Khi đó
(cid:0)x0(cid:1) , ∀x0 ∈ C. ∂δC (cid:0)x0(cid:1) = NC
(cid:0)x0(cid:1) = 0 và Chứng minh. Thật vậy, nếu x0 ∈ C thì δC
∂δC (cid:0)x0(cid:1) = (cid:8)w ∈ Rn : δC (x) ≥ (cid:10)w, x − x0(cid:11) , ∀x ∈ C(cid:9) .
Hay
(cid:0)x0(cid:1) . ∂δC (cid:0)x0(cid:1) = (cid:8)w ∈ Rn : 0 ≥ (cid:10)w, x − x0(cid:11) , ∀x ∈ C(cid:9) = NC
1.4 Tính đơn điệu
Định nghĩa 1.13. Giả sử C ⊆ Rn và F : Rn → Rn. Toán tử F được gọi là:
a) Đơn điệu mạnh trên C với hằng số δ > 0 nếu
(cid:104)F (x) − F (y) , x − y(cid:105) ≥ δ(cid:107)x − y(cid:107)2, ∀x, y ∈ C.
b) Đơn điệu chặt trên C nếu
(cid:104)F (x) − F (y) , x − y(cid:105) > 0, ∀x, y ∈ C : x (cid:54)= y.
c) Đơn điệu trên C nếu
(cid:104)F (x) − F (y) , x − y(cid:105) ≥ 0, ∀x, y ∈ C.
d) Giả đơn điệu trên C nếu
(cid:104)F (y) , x − y(cid:105) ≥ 0 ⇒ (cid:104)F (x) , x − y(cid:105) ≥ 0, ∀x, y ∈ C.
Ví dụ 1.2. a) Hàm F (x) = x, ∀x ∈ R là đơn điệu mạnh với δ = 1/2. b) Hàm F (x) = x3, ∀x ∈ R là đơn điệu chặt. c) Hàm F (x) = c, ∀x ∈ R là đơn điệu.
8
Chứng minh. • ∇f là đơn điệu trên C nếu f là hàm lồi trên C. Thật vậy, ta
giả sử x, y ∈ C. Do f là hàm lồi ta có
f (x) ≥ f (y) + (cid:104)∇f (y) , x − y(cid:105)
f (y) ≥ f (x) + (cid:104)∇f (x) , y − x(cid:105) .
Cộng vế của hai bất đẳng thức trên ta được
(cid:104)∇f (y) − ∇f (x) , y − x(cid:105) ≥ 0, ∀x, y ∈ C
vậy ∇f đơn điệu trên C.
• ∇f là đơn điệu mạnh trên C nếu f là hàm lồi mạnh trên C.
• ∇f là đơn điệu chặt trên C nếu f là hàm lồi chặt trên C.
9
Chương 2
Bài toán bất đẳng thức biến phân
Bài toán bất đẳng thức biến phân là một công cụ mạnh được sử dụng
trong nhiều lĩnh vực khác nhau của toán học ứng dụng. Bài toán bất đẳng
thức biến phân nảy sinh trong quá trình nghiên cứu và giải các bài toán thực
tế như các bài toán cân bằng trong kinh tế, tài chính, phương trình vật lý toán,
giao thông đô thị, lí thuyết trò chơi, bài toán cân bằng mạng và nhiều bài toán
khác. Có rất nhiều phương pháp giải bài toán bất đẳng thức biến phân đã được
nghiên cứu như: phương pháp địa phương và toàn cục dựa trên việc chuyển
bài toán về hệ phương trình, phương pháp dựa trên kỹ thuật hàm chắn.v.v..
Dưới đây, ta sẽ trình bày một số kiến thức cơ bản về bất đẳng thức biến phân
và một số phương pháp giải. Các kiến thức trong chương này chủ yếu được
lấy từ các tài liệu ([1]), ([2]), ([4]) và ([5]).
2.1 Phát biểu bài toán và ví dụ
∗(cid:1) , x − x∗(cid:11) ≥ 0, ∀x ∈ C.
Định nghĩa 2.1. Cho C ⊂ Rn và ánh xạ F : C → Rn. Bài toán bất đẳng thức biến phân được ký hiệu VIP(C, F ), là bài toán:
Tìm x∗ ∈ C sao cho (cid:10)F (cid:0)x (2.1)
Ví dụ 2.1. Một trò chơi có N người chơi.
Gọi Ki là tập chiến lược của người chơi thứ i, Ki ⊂ Rni θi(x) : hàm giá trị, ví dụ là hàm chi phí của người chơi i, với x =
(cid:0)xi(cid:1) , xi ∈ Rni, i = 1, 2, ..., N.
10
Vấn đề của người chơi thứ i được xác định như sau: với mỗi vectơ ˜xi = (cid:0)yi, ˜xi(cid:1) đạt giá trị nhỏ nhất theo
(xi : j (cid:54)= i) tìm xi, sao cho hàm chi phí θi các biến yi. Nói một cách khác, xi chính là nghiệm của bài toán:
(cid:8)θi (cid:0)yi, ˜xi(cid:1)(cid:9) . M inyi∈Ki
(cid:0)˜xi(cid:1) .
(cid:0)˜xi(cid:1) , với
Giả sử tập nghiệm của bài toán này là Si Điểm cân bằng Nash là vectơ x = (xi, i = 1, 2, ..., N ) với xi ∈ Si mọi i = 1, 2, ...., N.
Ví dụ 2.2. Xét bài toán tối ưu
M in {f (x) , x ∈ K}
với f là hàm khả vi, liên tục và K là tập lồi đóng. Khi đó nếu x∗ ∈ K là nghiệm của bài toán tối ưu thì x∗ là nghiệm của bài toán bất đẳng thức biến
phân
∇f (x∗)T (x − x∗) ≥ 0, ∀x ∈ K. (2.2)
Chứng minh. Xét hàm số φ (t) = f (x∗ + t (x − x∗)) , t ∈ [0, 1] . Ta có
φ(cid:48) (0) = ∇f (x∗)T (x − x∗) .
Do K là tập lồi đóng nên φ (t) xác định với mọi t ∈ [0, 1]. Điều kiện để t∗ ∈ [0, 1] là điểm cực tiểu của hàm số ϕ : [a, b] → R trên [a, b] là ϕ(cid:48) (t∗) (t − t∗) ≥ 0, ∀t ∈ [a, b]. Do đó φ(cid:48) (0) ≥ 0 thì x∗ là nghiệm của bài toán (2.2).
2.2 Môt số tính chất
2.2.1 Sự tồn tại nghiệm
Việc chứng minh sự tồn tại nghiệm của bất đẳng thức biến phân thường
dựa vào định lý điểm bất động.
11
Định lý 2.1. (Brouwer) Cho C ⊂ Rn compact và lồi, ánh xạ F : C → C là liên tục trên C. Khi đó F có một điểm bất động.
Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân có thể chứng minh
dựa vào phép chiếu vuông góc. Cụ thể ta có kết quả sau:
Mệnh đề 2.1. Giả sử α > 0. Với mỗi x ∈ C, đặt
(cid:19) (cid:18) F (x) . x − h(x) = pC 1 α
Khi đó x∗ = h(x∗) khi và chỉ khi x∗ là nghiệm của bài toán (2.1)
Chứng minh. Theo tính chất của phép chiếu, h là ánh xạ đơn trị từ C vào C.
(cid:0)x∗ − 1
αF (x∗)(cid:1) αF (x∗) , x − x∗(cid:11) ≥ 0, ∀x ∈ C.
x∗ = h (x∗) = pC ⇔ (cid:10)x∗ − x∗ + 1
Bất đẳng thức cuối cùng đúng khi và chỉ khi (cid:104)F (x∗), x − x∗(cid:105) ≥ 0, ∀x ∈ C.
Định lý 2.2. Cho C là tập khác rỗng, C ⊂ Rn là tập compact lồi, ánh xạ F : C → C liên tục, khi đó bài toán (2.1) có nghiệm. Tức là tồn tại x∗ ∈ C thỏa mãn
(cid:104)F (x∗), x − x∗(cid:105) ≥ 0, ∀x ∈ C.
Chứng minh. Do phép chiếu lên tập lồi là đóng và liên tục, do F liên tục trên
tập C, nên h là ánh xạ liên tục trên tập C, vì nó là hợp của hai ánh xạ liên tục.
Do h là ánh xạ liên tục từ C vào C nên theo định lý điểm bất động Brouwer tồn tại điểm bất động x∗ của h. Theo Mệnh đề 2.1 x∗ là nghiệm của bài toán
(2.1).
Theo Mệnh đề 2.1 việc giải bài toán (2.1) có thể chuyển về việc tìm điểm
bất động của ánh xạ h. Trong trường hợp h là một ánh xạ co, nguyên lý ánh
12
xạ co Banach có thể áp dụng trực tiếp để giải bài toán (2.1). Khi F là ánh xạ
đơn điệu mạnh và liên tục Lipchits trên C thì có thể chọn α thích hợp để h là
ánh xạ co trên C. Cụ thể ta có mệnh đề sau:
Mệnh đề 2.2. Giả sử C là tập lồi đóng và ánh xạ F : C → Rn đơn điệu mạnh trên C với hệ số β và Lipchits trên C với hằng số L. Khi đó nếu α > L2 2β
thì (cid:18) (cid:19) x − F (x) h(x) = pC 1 α
là ánh xạ co trên C với hệ số co
(cid:114)
1 − + δ = 2β α L2 α2 .
Chứng minh. Do tính không giãn của phép chiếu, nên:
αF (x)(cid:1) − (cid:0)y − 1 α (cid:104)x − y, F (x) − F (y)(cid:105) + 1
αF (y)(cid:1)(cid:13) 2 (cid:13) α2 (cid:107)F (x) − F (y)(cid:107)2 .
(cid:107)h (x) − h (y)(cid:107)2 ≤ (cid:13) (cid:0)x − 1 (cid:13) = (cid:107)x − y(cid:107)2 − 2
Do F là đơn điệu mạnh với hệ số β và Lipchits với hằng số L, nên
(cid:104)x − y, F (x) − F (y)(cid:105) ≥ β(cid:107)x − y(cid:107)2
và
(cid:107)F (x) − F (y)(cid:107)2 ≤ L2(cid:107)x − y(cid:107)2.
α2 (cid:107)x − y(cid:107)2
Từ đây suy ra
α (cid:107)x − y(cid:107)2 + L2 (cid:107)x − y(cid:107)2.
α + L2
α2
(cid:16) (cid:17) (cid:107)h(x) − h(y)(cid:107)2 ≤ (cid:107)x − y(cid:107)2 − 2β ⇔ (cid:107)h(x) − h(y)(cid:107)2 ≤ 1 − 2β
Vậy h là ánh xạ co khi α > L2 2β .
Từ mệnh đề này ta có hệ quả sau:
Hệ quả 2.1. Nếu C là lồi đóng, ánh xạ F đơn điệu mạnh và Lipchits trên C thì bài toán (2.1) luôn có nghiệm duy nhất.
13
Định lý 2.3. Cho C ⊂ Rn là tập lồi đóng, ánh xạ F : C → Rn là liên tục. Giả sử tồn tại Y là tập con bị chặn của C sao cho với mọi x ∈ C\Y, ∃ y ∈ Y
thỏa mãn:
(cid:104)F (x) , x − y(cid:105) > 0.
Khi đó, bài toán (2.1) có nghiệm.
Chứng minh. Trong trường hợp C bị chặn thì C là tập compact nên theo Định
lý 2.2 bài toán (2.1) luôn có nghiệm. Do đó ta chỉ xét trong trường hợp C không bị chặn. Cho hình cầu đóng Br bán kính r tâm O ∈ Rn. Khi đó C ∩ Br
là tập compact.
Do Y bị chặn nên tồn tại r > (cid:107)y(cid:107) với mọi y ∈ Y. Khi đó, tồn tại nghiệm
xr ∈ C ∩ Br sao cho:
(2.3) (cid:104)F (xr) , z − xr(cid:105) ≥ 0, ∀z ∈ C ∩ Br.
Ta chứng minh rằng nếu (cid:107)xr(cid:107) < r thì xr là nghiệm của bài toán (2.1). Thật
vậy, do (cid:107)xr(cid:107) < r với mọi x bất kỳ, tồn tại ε > 0 đủ nhỏ:
xr + ε (x − xr) ∈ C ∩ Br.
Do xr ∈ C ∩ Br nên:
(cid:104)F (xr) , xr + ε (x − xr) − xr(cid:105) ≥ 0, ∀x ∈ C.
Chia cả hai vế cho ε, ta được
(cid:104)F (xr) , x − xr(cid:105) ≥ 0, ∀x ∈ C.
Vậy xr là nghiệm của bài toán (2.1)
Từ định lý này ta có thể rút ra được nhiều điều kiện đủ để tồn tại nghiệm.
Ta cần đến khái niệm về tính chất đồng bức sau:
14
Hệ quả 2.2. Nếu F : C → Rn thỏa mãn:
→ ∞ (cid:104)F (x) − F (x0) , x − x0(cid:105) |x − x0|
khi
x ∈ C, (cid:107)x(cid:107) → +∞.
Với x0 ∈ C thì tồn tại một nghiệm đối với bài toán (2.3).
Chứng minh. Chọn H > |f (x0)| và r > x0 sao cho:
(cid:104)F (x) − F (x0) , x − x0(cid:105) ≥ H |x − x0| , ∀x ∈ C.
Thì
(cid:104)F (x) , x − x0(cid:105) ≥ H |x − x0| + (cid:104)F (x0) , x − x0(cid:105)
≥ H |x − x0| − |F (x0)| |x − x0|
(2.4) ≥ (H − F (x0)) (|x − x0|) > 0, x (cid:54)= r.
Gọi xr ∈ C là nghiệm của bài toán (2.3) thì
(2.5) (cid:104)F (xr) , xr − x0(cid:105) ≥ − (cid:104)F (xr) , x0 − xr(cid:105) ≤ 0.
Từ (2.4) và (2.5) ta có |x| (cid:54)= r hay |x| < r.
Thông thường, bài toán bất đẳng thức biến phân không có nghiệm duy
nhất, tuy nhiên có điều kiện đảm bảo cho tính duy nhất cho nghiệm của nó.
Ta xét mệnh đề sau:
Mệnh đề 2.3. Nếu F là đơn điệu chặt thì bài toán bất đẳng thức biến phân (2.1) có nghiệm duy nhất.
Chứng minh. Giả sử (2.1) tồn tại hai nghiệm x(cid:48) và x(cid:48)(cid:48). Khi đó
x(cid:48) ∈ C : (cid:104)F (x(cid:48)) , x − x(cid:48)(cid:105) ≥ 0, ∀x ∈ C, x(cid:48)(cid:48) ∈ C : (cid:104)F (x(cid:48)(cid:48)) , x − x(cid:48)(cid:48)(cid:105) ≥ 0, ∀x ∈ C.
15
Áp dụng x = x(cid:48) và x = x(cid:48)(cid:48), ta có:
(cid:104)F (x(cid:48)(cid:48)) − F (x(cid:48)) , x(cid:48) − x(cid:48)(cid:48)(cid:105) ≥ 0, ∀x(cid:48), x(cid:48)(cid:48) ∈ C.
Do F là đơn điệu chặt nên
(cid:104)F (x(cid:48)(cid:48)) − F (x(cid:48)) , x(cid:48)(cid:48) − x(cid:48)(cid:105) = 0, ∀x(cid:48), x(cid:48)(cid:48) ∈ C.
Vậy x(cid:48) ≡ x(cid:48)(cid:48).
Định lý 2.4. Giả sử C là tập lồi đóng, ánh xạ F : C → Rn đơn điệu mạnh và liên tục. Khi đó bài toán (2.1) có nghiệm duy nhất.
Chứng minh. Ta cố định ˜x ∈ C và với mọi x ∈ C, do tính đơn điệu mạnh ta
có:
(cid:104)F (x) , x − ˜x(cid:105) ≥ (cid:104)F (˜x) , x − ˜x(cid:105) + β (cid:107)x − ˜x(cid:107) → +∞
khi (cid:107)x − ˜x(cid:107) → +∞. Vì thế, theo điều kiện của Định lý 2.3 ta có lời giải của
bài toán (2.1).
2.2.2 Các bài toán liên quan
Bài toán quy hoạch lồi Cho C ⊂ Rn là tập lồi đóng và f : C → R khả vi. Đặt F (x) = ∇f (x)
(đạo hàm của f ).
Định lý 2.5. Giả sử tồn tại x ∈ C sao cho:
f (x) := min {f (y) : y ∈ C}
thì x là một nghiệm của bài toán bất đẳng thức biến phân,
x ∈ C : (cid:104)F (x) , y − x(cid:105) ≥ 0, y ∈ C.
Chứng minh. Nếu y ∈ C, do C là hàm lồi nên ta đặt
z = x + λ (y − x) = λy + (1 − λ) x ∈ C
16
với λ ∈ [0, 1] .
Vì vậy hàm ϕ (λ) = f (x + λ (y − x)) , λ ∈ [0, 1] , đạt cực tiểu khi λ = 0
nên
0 ≤ ϕ(cid:48) (0) = (cid:104)∇f (x) , y − x(cid:105) = (cid:104)F (x) , y − x(cid:105) .
Điều ngược lại cũng đúng nếu f là hàm lồi, ta có định lý sau:
Định lý 2.6. Giả sử f là hàm lồi khả vi và thỏa mãn:
x ∈ C : (cid:104)F (x) , y − x(cid:105) ≥ 0, ∀y ∈ C,
thì
f (x) := min {f (y) : y ∈ C} .
Chứng minh. Thật vậy vì f lồi nên
f (y) ≥ f (x) + (cid:104)F (x) , y − x(cid:105) , ∀y ∈ C.
Nhưng (cid:104)F (x) , y − x(cid:105) ≥ 0, vì vậy f (y) ≥ f (x) .
Bài toán điểm bất động Brouwer Cho C là tập lồi đóng trong Rn và T : C → C, bài toán điểm bất động
được phát biểu như sau:
Tìm x∗ ∈ C sao cho x∗ = T (x∗) . (2.6)
Mệnh đề 2.4. Giả sử ánh xạ F được xác định bởi
F (x) := x − T (x) , ∀x ∈ C.
Khi đó, bài toán bất đẳng thức biến phân (VIP) tương đương với bài toán
điểm bất động (2.6).
17
Chứng minh. Giả sử x∗ là nghiệm của bài toán (VIP) và F (x) = x − T (x),
tức là
(cid:104)F (x∗) , x − x∗(cid:105) ≥ 0, ∀x ∈ C.
Do F (x∗) = x∗ − T (x∗) nên tồn tại ζ ∗ = T (x∗) sao cho F (x∗) = x∗ − ζ ∗.
Ta có
(cid:104)F (x∗) − ζ ∗, x − x∗(cid:105) ≥ 0, ∀x ∈ C.
Cho x = ζ ∗ ta được (cid:107)x∗ − ζ ∗(cid:107) ≤ 0.
Suy ra x∗ = ζ ∗ hay x∗ = T (x∗). Vậy nên x∗ nghiệm của bài toán (2.6).
Chiều ngược lại hiển nhiên đúng.
Bài toán bù phi tuyến Chú ý rằng khi C là một nón lồi trong Rn thì bài toán (VIP) trở thành bài
toán bù:
Tìm x∗ ∈ C, F (x∗) ∈ C (cid:48) sao cho (cid:104)F (x∗), x∗(cid:105) = 0, (CP)
trong đó
C (cid:48) := {y ∈ Rn| (cid:104)x, y(cid:105) ≥ 0, ∀x ∈ C}
là nón đối ngẫu của C.
Khi đó, ta có mệnh đề sau:
Mệnh đề 2.5. Nếu C là một nón lồi, đóng trong Rn thì bài toán bù (CP) tương đương với bài toán bất đẳng thức biến phân (VIP), theo nghĩa tập nghiệm của
các bài toán này trùng nhau.
Chứng minh. Nếu x∗ là ghiệm của bài toán bất đẳng thức biến phân (VIP) thì
(cid:104)F (x∗), x − x∗(cid:105) ≥ 0, ∀x ∈ C. (2.7)
Do C là nón lồi, x∗ ∈ C nên
(x∗ + x) ∈ C, ∀x ∈ C.
18
Trong bất đẳng thức trên, thay x bởi (x∗ + x) ta được
(cid:104)F (x∗) , x∗ + x − x∗(cid:105) = (cid:104)F (x∗) , x(cid:105) ≥ 0, ∀x ∈ C.
Suy ra F (x∗) thuộc nón đối ngẫu C (cid:48).
Còn nếu thay x = 0 vào (2.7), ta được
(cid:104)F (x∗) , x∗(cid:105) ≤ 0.
Suy ra (cid:104)F (x∗) , x∗(cid:105) = 0, hay x∗ ∈ C, F (x∗) ∈ C (cid:48) là nghiệm của bài toán bù
(CP).
Ngược lại, nếu x∗ ∈ C là nghiệm của bài toán bù thì
(cid:104)F (x∗) , x∗(cid:105) = 0, F (x∗) ∈ C (cid:48).
Vì F (x∗) ∈ C (cid:48) nên (cid:104)F (x∗) , x(cid:105) ≥ 0, ∀x ∈ C. Ta có
(cid:104)F (x∗) , x − x∗(cid:105) ≥ 0, ∀x ∈ C,
hay x∗ ∈ C là nghiệm của bài toán (VIP).
19
Chương 3
Bài toán bất đẳng thức biến phân hỗn hợp DC
Dưới đây, ta sẽ trình bày một số kiến thức cơ bản về hàm DC, sử dụng
phương pháp điểm gần kề giải bài toán bất đẳng thức biến phân hỗn hợp DC.
Tiếp theo chúng ta mở rộng phương pháp điểm gần để tìm một điểm dừng của
bài toán. Sau đó sẽ trình bày một mô hình bán độc quyền và chuyển mô hình
này về bài toán bất đẳng thức biến phân hỗn hợp DC. Các kiến thức trong
chương này được lấy chủ yếu từ các tài liệu ([6]), ([7]).
3.1 Hàm DC
Định nghĩa 3.1. Cho Ω là một tập lồi trên Rn. Một hàm là DC trên Ω nếu nó là hiệu của hai hàm lồi trên Ω, nghĩa là f (x) được gọi là DC nếu f (x) =
f1(x) − f2(x), trong đó f1, f2 là hàm lồi trên Ω.
Một hàm bậc hai f (x) = (cid:104)x, Qx(cid:105) , trong đó Q là một ma trận đối xứng,
là một hàm DC có thể không lồi không lõm.
Thật vậy, đặt x = U y trong đó U = (cid:2)u1, u2, ..., un(cid:3) là ma trận vectơ riêng
của Q, chúng ta có U T QU = diag(λ1,λ2, ..., λn), do đó
f (x) = f (U y) = (cid:104)U y, QU y(cid:105) = (cid:10)y, U T QU y(cid:11) ,
sao cho f (x) = f1(x) − f2(x) với
i , y = U −1x.
i , f2 (x) = −
λi<0
λi≥0
(cid:88) (cid:88) f1 (x) = λiy2 λiy2
20
i = 1, 2, ..., m là hàm DC trên Ω thì hàm sau đây
Mệnh đề 3.1. Nếu fi(x), cũng là DC trên Ω:
m (cid:80) i=1
(i) αifi (x), với mỗi αi;
(ii) g(x) = max {f1(x), ..., fm(x)} ;
(iii) h(x) = min {f1(x), ..., fm(x)} .
Chứng minh. Ta chứng minh (ii) như sau: Cho fi(x) = pi(x) − qi(x) với pi, qi
là lồi trên Ω. Từ đẳng thức
j
j(cid:54)=i
(cid:88) (cid:88) qj − qj fi = pi +
sao cho
i
j
j(cid:54)=i
(cid:88) (cid:88) max {f1, ..., fm} = max qj qj. pi + −
Như vậy, tập các hàm DC trên Ω là không gian tuyến tính chứa tất cả các
hàm lồi trên Ω. Không gian tuyến tính này kí hiệu là DC(Ω).
Một bất đẳng thức có dạng f (x) ≤ 0 (hoặc f (x) ≥ 0), trong đó hàm f (x)
là lồi, được gọi là một bất đẳng thức lồi. Nếu f (x) là lõm, bất đẳng thức là
phần bù của một tập lồi.
Nếu f (x) là một hàm DC thì bất đẳng thức f (x) ≤ 0 (hoặc f (x) ≥ 0)
được gọi là một bất đẳng thức DC.
Một hệ quả quan trọng của Mệnh đề 3.1 là bất kì hệ hữu hạn bất đẳng
thức DC, cho dù liên tục hay không liên tục, tương đương với một bất đẳng
thức DC.
Thật vậy một hệ liên tục
gi(x) ≤ 0, i = 1, 2, ..., m
có thể viết
(3.1) g(x) := max {g1(x), ..., gm(x)} ≤ 0
21
trong khi một hệ không liên tục gi(x) ≤ 0 ít nhất một i = 1, 2, ..., m tương
đương với
(3.2) g(x) := min {g1(x), ..., gm(x)} ≤ 0.
Hơn nữa, nếu g(x) = p(x) − q(x) với p(x), q(x) lồi, khi lấy một biến t, bất
đẳng thức DC (3.1) (hoặc (3.2)) có thể chia thành hai bất đẳng thức:
p(x) − t ≤ 0, t − q(x) ≤ 0 (3.3)
Mệnh đề 3.2. Mỗi hàm f ∈ C 2(Rn) là DC trên mọi tập compact lồi Ω ⊂ Rn.
Chứng minh. Chúng ta thấy rằng mỗi tập compact lồi Ω ⊂ Rn, hàm g (x) = f (x) + ρ(cid:107)x(cid:107)2 trở thành lồi trên Ω khi ρ là đủ lớn
Thật vậy
(cid:10)u, ∇2g (x) u(cid:11) = (cid:10)u, ∇2f (x) u(cid:11) + ρ(cid:107)u(cid:107)2,
nếu ρ là lớn nhất mà
− min (cid:8)(cid:10)u, ∇2f (x) u(cid:11) | x ∈ Ω, (cid:107)u(cid:107) = 1(cid:9) ≤ ρ
thì (cid:10)u, ∇2g (x) u(cid:11) ≥ 0, ∀u, do đó g(x) là lồi.
Hệ quả 3.1. Cho f (x) là liên tục trên một tập compact lồi Ω, khi đó với mỗi ε > 0 tồn tại một hàm DC g(x), sao cho
|f (x) − g (x)| ≤ ε. max x∈Ω
Chứng minh. Theo định lí Weierstrass tồn tại một đa thức g(x) thỏa mãn các điều kiện và rõ ràng g(x) ∈ C 2.
Một hàm f : D → R xác định trên một tập lồi D ⊂ Rn được gọi là DC địa phương nếu với mỗi x ∈ D tồn tại một lân cận mở U của x và hai hàm lồi
g, h trên U sao cho f |U = g |U − h |U.
22
Mệnh đề 3.3. Một hàm DC địa phương trên một tập lồi mở (hoặc đóng) là DC trên D.
Chứng minh. Từ giả thiết và tính compact của D có thể tìm thấy một tập
k (cid:80) i=1
{x1, ..., xk} ⊂ D cùng với lân cận lồi mở U1, ..., Uk của các điểm phủ D và hàm lồi hi : Rn → R, i = 1, ..., k sao cho (f + hi) |Ui là lồi. Cho h = hi
và xét hàm g : f + h. Cho mỗi i, (f + hi) |Ui là lồi, do đó
j(cid:54)=i
(cid:88) hj g|Ui = (f + hi) |Ui + |Ui
là lồi. Vậy g là lồi trên D nghĩa là f = g − h với g, h lồi.
Một ánh xạ F = (f1, ..., fm) : Ω → Rm xác định trên tập lồi Ω ⊂ Rn được gọi là DC trên Ω : F ∈ DC(Ω), nếu fi ∈ DC(Ω) với mỗi i = 1, ..., m.
Mệnh đề 3.4. Cho Ω1 ⊂ Rn, Ω2 ⊂ Rm là các tập lồi sao cho Ω1 là mở (hoặc đóng), Ω2 là mở. Nếu
F1 : Ω1 → Ω2, F2 : Ω2 → Rk
là ánh xạ DC thì
F2 ◦ F1 : Ω1 → Rk
cũng là ánh xạ DC
Chứng minh. Nếu F = (f1, ..., fm) : Ω1 → Ω2 là DC và g : Ω2 → R là lồi thì g (f1, ...., fm) ∈ DC (Ω1) . Cho x ∈ Ω1 và y = F (x) ∈ Ω2. Hàm lồi
g(y) có thể đại diện trong một lân cận U2 của y theo từng điểm của một hàm
affine:
t
g(y) = sup
+ (x) − fi
lt, trong đó lt = a0t + alt y1 + ... + amtym (y1, ..., ym là tọa − (x) |ait| < +∞. Cho fi (x) = fi độ của y trong Rm) và M = sup i,t
23
trong lân cận U1 của x sao cho F (U1) ⊂ U2. Thì
lt (f1, ..., fm)
i −
m (cid:80) i=1
aitf + aitf − i
m (cid:80) i=1
(cid:21) = a0t + (cid:20) = (M + ait) f + (M − ait) f − i
i + (cid:1) = pt − q
m (cid:80) i=1 m (cid:80) i=1 i + f − i
(cid:0)f + −M a0t + m (cid:80) i=1
với pt và q lồi, q không phụ thuộc vào t. Thì
t
t
t
g (f1, ..., fm) = sup lt (f1, ..., fm) = sup (pt − q) = sup pt − q = p − q,
nghĩa là g (f1, ..., fm) là DC địa phương trên Ω1. Do đó, theo Mệnh đề 3.3,
g ◦ f ∈ DC (Ω1) .
Hệ quả 3.2. Cho Ω1 ⊂ Rn, Ω2 ⊂ Rm là các tập lồi sao cho Ω1 là mở (hoặc đóng), Ω2 là mở. Nếu F1 : Ω1 → Ω2 là DC trên Ω1 ⊂ Rn và F2 : Ω2 → Rk là C 2 trơn thì F2 ◦ F1 là DC trên Ω1. Đặc biệt tích của hai hàm DC là DC, nếu f (x) là DC trên một tập lồi đóng (hoặc mở) Ω và f (x) (cid:54)= 0, ∀x ∈ Ω thì
1/m , |f (x)| 1 f (x)
là DC trên Ω.
Nhận xét 3.2. Khi một hàm f là DC và f = g − h là một DC biểu diễn của f với bất kì hàm lồi u,f = (g + u) − (h + u) là một hàm DC biểu diễn của f.
3.2 Phát biểu bài toán và ví dụ
Cho ∅ (cid:54)= C ⊂ Rn là một tập lồi đóng. F là một ánh xạ từ Rn → C và ϕ là một hàm (không nhất thiết lồi) định nghĩa trên Rn. Chúng ta xem xét giải
bài toán bất đẳng thức biến phân hỗn hợp (MVIP):
Lấy x∗ ∈ C sao cho F (x∗)T (y − x∗) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ C. (3.4)
24
Gọi x∗ là một lời giải địa phương của bài toán, tức là x∗ ∈ C thỏa mãn:
F (x∗)T (y − x∗) + ϕ (y) − ϕ (x∗) , ∀y ∈ C ∩ U, (3.5)
với U là một lân cận mở của x∗. Khi ϕ là lồi trên C, một lời giải địa phương là một toàn cục. Khi ϕ là không lồi, một lời giải địa phương có thể không là
toàn cục.
3.3 Phương pháp điểm gần kề giải bài toán bất đẳng thức
biến phân hỗn hợp DC
Định nghĩa 3.3. Cho NC := {(x, U ) : x ∈ C, U là một lân cận của x} , định nghĩa ánh xạ S : NC → 2c và hàm m : NC → R bằng cách lấy
(cid:110) (cid:111) S (x, U ) := argmin F (x)T (y − x) + ϕ (y) : y ∈ C ∩ U , (3.6)
(cid:110) (cid:111) m (x, U ) := min F (x)T (y − x) + ϕ (y) − ϕ (x) : y ∈ C ∩ U , (3.7)
Ta gọi m(x, U ) là hàm khoảng cách địa phương cho bài toán (3.4).
Mệnh đề 3.5. Giả sử S (x, U ) (cid:54)= ∅ với mỗi (x, U ) ∈ NC. Những điều kiện sau là tương đương
a) x∗ là lời giải địa phương của (3.4); b) x∗ ∈ C và x∗ ∈ S(x∗, U ); c) x∗ ∈ C và m(x∗, U ) = 0.
Chứng minh. Đầu tiên chúng tôi chứng minh (a) tương đương với (b).
Giả sử x∗ ∈ C và x∗ ∈ S(x∗, U ). Khi đó 0 = F (x∗)T (x∗ − x∗) + ϕ (x∗) − ϕ (x∗) ≤ F (x∗)T (y − x∗) + ϕ (y) −
ϕ (x∗) , ∀y ∈ C ∩ U.
Do đó, x∗ là một lời giải địa phương của bài toán (3.4). Ngược lại, nếu
F (x∗)T (y − x∗) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ C ∩ U (3.8)
25
rõ ràng x∗ ∈ S(x∗, U ).
Ta thấy rằng m(x, U ) ≤ 0 với mỗi x ∈ C ∩ U. Do đó x∗ ∈ C ∩ U và m(x∗, U ) = 0 khi và chỉ khi F (x∗)T (y − x∗) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ C ∩ U nghĩa là (a) và (c) tương đương.
Rõ ràng, nếu trong Mệnh đề 3.5, U chứa C thì x∗ là một lời giải địa
phương của bài toán (3.4). Không giống như bất đẳng thức biến phân hỗn
hợp lồi (bao gồm tối ưu hóa và bất đẳng thức biến phân), một bất đẳng thức
hỗn hợp DC có thể không có lời giải khi ánh xạ giá liên tục và tập C là
compact.
Ví dụ 3.1. Nếu chúng ta lấy C := [−1, 1] ⊂ R, F (x) = x và ϕ (x) = −x2 (một hàm lõm) bài toán (3.4) không có lời giải.
Ta kí hiệu ΓC là tập tất cả hàm lồi, khả dưới vi phân trên tập lồi C và
giả sử hai hàm g và h thuộc ΓC. Hơn nữa, do ϕ (x) = (g (x) + g1 (x)) −
(h (x) + g1 (x)) với hàm g1 ∈ ΓC tùy ý, ta có thể luôn giả sử rằng hai hàm g
và h lồi mạnh trên C.
Từ Mệnh đề 3.5, ta có x là một lời giải của bài toán (3.4) khi và chỉ khi x
là lời giải của bài toán tối ưu sau:
(cid:110) (cid:111) min F (x)T (y − x) + g (y) − h (y) : y ∈ C .
Trên cơ sở thực tế này chúng ta có thể định nghĩa điểm dừng của bài toán
(3.4) như sau :
Định nghĩa 3.4. Một điểm x ∈ C gọi là một điểm dừng của bài toán (3.4) nếu
(3.9) 0 ∈ F (x) + ∂g (x) − ∂h (x) + NC (x) ,
trong đó
NC (x) := (cid:8)w : wT (y − x) ≤ 0, ∀y ∈ C(cid:9) .
26
Do NC là một nón, với mỗi c > 0, thì (3.9) tương đương với
(3.10) 0 ∈ c {F (x) + ∂g (x) − ∂h (x)} + NC (x) .
Ta định nghĩa g1 (x) := g (x) + δC (x) , trong đó ∂δC (x) là dưới vi phân
của hàm chỉ số δC của C tại x. Sau đó áp dụng định lý Moreau-Rockafellar,
ta có ∂g1 (x) = ∂g (x) + ∂δC (x) . Như vậy, theo định nghĩa x là một điểm
dừng khi và chỉ khi
0 ∈ c (F (x) + ∂g (x) − ∂h (x)) + ∂δC (x) ,
trong đó c > 0 được gọi là tham số hiệu chỉnh của thuật toán sẽ được định
nghĩa dưới đây. Giống như trong tối ưu hóa từ Mệnh đề 3.5 ta có mọi lời giải
địa phương của bài toán (3.4) là một điểm dừng.
Do ∂δC(x) = NC(x), nên ta có
∂g1 (x) = ∂g (x) + NC (x) với mỗi x ∈ C.
Mệnh đề 3.6. Điều kiện cần và đủ để x là một điểm dừng cho bài toán (3.4) là:
(3.11) x ∈ (I + c∂g1)−1 (x − cF (x) + c∂h (x)) ,
trong đó c > 0 và I là viết tắt của ánh xạ đồng nhất.
Chứng minh. Do g1 là tập lồi đóng, (I + ∂g1)−1 là giá trị duy nhất. Do đó, x thỏa mãn (3.11) khi và chỉ khi x − cF (x) + cv (x) ∈ (I + c∂g1) (x) đối với
mỗi v (x) ∈ ∂h (x) . Do NC(x) là một nón và ∂g1 (x) = ∂g (x) + ∂δC (x) =
∂g (x) + NC (x) , x − cF (x) + cv (x) ∈ (I + c∂g1) (x) là tương đương
0 ∈ F (x) + ∂g (x) − ∂h (x) + NC (x) .
Nếu chúng ta kí hiệu vế phải của (3.11) bởi Z(x) thì (3.11) trở thành
x ∈ Z(x). Mệnh đề 3.6 cho thấy rằng việc tìm kiếm một điểm dừng của bài
toán (3.4) là tìm một điểm bất động ánh xạ Z. Theo khuân khổ phương pháp
điểm gần kề chúng ta có thể xây dựng một trình tự lặp như sau:
27
• Lấy tùy ý x0 ∈ C và k := 0.
• Với mỗi k = 0, 1, 2, ..., ta có xk, chúng ta xác định xk+1 bởi:
(3.12) xk+1 = (I + ck∂g1)−1 (cid:0)xk − ckF (cid:0)xk(cid:1) + ckv (cid:0)xk(cid:1)(cid:1) ,
trong đó v (cid:0)xk(cid:1) ∈ ∂h (cid:0)xk(cid:1) .
Nếu ta đặt
yk := xk − ckF (cid:0)xk(cid:1) + ckv (cid:0)xk(cid:1)
thì việc tính xk+1 trở về giải bài toán tối ưu lồi mạnh:
2
(cid:27) (cid:26) : x ∈ C g (x) + min (3.13) (cid:13)x − yk(cid:13) (cid:13) (cid:13) 1 2ck
Thật vậy, xk+1 là lời giải của bài toán (3.13) khi và chỉ khi
0 ∈ ∂g (cid:0)xk+1(cid:1) + (cid:0)xk+1(cid:1) . (cid:0)xk+1 − yk(cid:1) + NC 1 ck
Lưu ý rằng khi F ≡ 0 và h ≡ 0 bài toán (3.12) trở thành một thuật toán điểm
gần kề cho bài toán quy hoạch lồi, trong khi F ≡ 0 là thuật toán gần kề cho
tối ưu hóa DC. Để chứng minh sự hội tụ của thuật toán điểm gần kề chúng ta
cần các định nghĩa sau
Cho ánh xạ φ : C → 2Rn :
• Ta nói φ là đơn điệu trên C nếu
(u − v)T (x − y) ≥ 0, ∀x, y ∈ C, ∀u ∈ φ (x) , v ∈ φ (y) ;
• φ là đơn điệu cực đại nếu nó là đơn điệu và đồ thị của nó không bị chứa
thực sự trong đồ thị của toán tử đơn điệu khác;
• φ được gọi là đơn diệu mạnh với hệ số τ > 0, (τ đơn điệu mạnh) trên C
nếu
(u − v)T (x − y) ≥ τ (cid:107)x − y(cid:107) 2, ∀x, y ∈ C, ∀u ∈ φ (x) , v ∈ φ (y) ;
28
• φ được gọi là đơn điệu mạnh ngược với hệ số σ > 0, (σ đơn điệu mạnh
ngược) trên C nếu
(u − v)T (x − y) ≥ σ(cid:107)u − v(cid:107) 2, ∀x, y ∈ C, ∀u ∈ φ (x) , v ∈ φ (y) .
Rõ ràng, nếu φ là ánh xạ đơn trị và σ đơn điệu mạnh ngược, thì φ là 1 σ − Lipschitz.
Mệnh đề 3.7. Giả sử rằng nếu tập hợp điểm dừng S∗ của bài toán (3.4) khác rỗng và F là σ đơn điệu mạnh ngược, g là lồi mạnh trên C với hệ số τ > 0, và h là hàm số Lipschitz khả vi trên C với hằng số L. Khi đó, với mỗi x∗ ∈ S∗,
2
2
2
chúng ta có
, αk − βk ≥ ck (2σ − ck) (cid:13) (cid:13) (cid:13)xk − x∗(cid:107) (cid:13) (cid:13)xk+1 − x∗(cid:107) (cid:13)F (cid:0)xk(cid:1) − F (x∗)(cid:107)
(3.14)
trong đó
L t
(cid:1) , t > 0. αk = 1 + ckLt, βk = (cid:0)1 + 2ckτ − ck
Chứng minh. Cho g là xác định lồi đóng và C (cid:54)= ∅ lồi đóng, ánh xạ (I + ck∂g1)−1 là duy nhất có giá trị với mỗi ck > 0. Như vậy dãy (cid:8)xk(cid:9) được xây dựng bởi (3.12) được xác định. Từ (3.12) ta có
(3.15) xk+1 = xk − ckF (cid:0)xk(cid:1) + ckvk − ckzk+1,
(cid:0)xk+1(cid:1) = ∂g (cid:0)xk+1(cid:1) + NC
trong đó vk = ∇h (cid:0)xk(cid:1) và zk+1 ∈ ∂g1 (cid:0)xk+1(cid:1) . Để đơn giản chúng tôi viết F k cho F (xk) và F ∗ cho F (x∗). Theo định nghĩa, nếu x∗ là một điểm dừng để MVIP (3.4) khi
0 = z∗ + F (x∗) − v∗
trong đó
z∗ ∈ ∂g1 (x∗) , v∗ = ∇h (cid:0)xk(cid:1) .
29
Là đơn điệu mạnh ngược của F trên C có nghĩa là
(cid:13)F k − F ∗(cid:107) 2
0 ≤ (cid:0)F k − F ∗(cid:1)T (cid:0)xk − x∗(cid:1) − σ(cid:13) = (cid:0)F k − F ∗(cid:1)T (cid:0)xk − x∗ − ckF k + ckF ∗(cid:1) − ∆k,
2
trong đó
. ∆k = (σ − ck) (cid:13) (cid:13)F k − F ∗(cid:107)
Do F ∗ = v∗ − z∗ và xk+1 = xk − ckF k + ckvk − ckzk+1, chúng ta có được
bất đẳng thức
0 ≤ (cid:0)F k − F ∗(cid:1)T (cid:0)xk − ckF k + ckvk − ckzk+1 − x∗(cid:1) (cid:0)F k − F ∗(cid:1)T (cid:0)vk − v∗ − zk+1 + z∗(cid:1) − ∆k −ck
= (cid:0)F k − F ∗(cid:1)T (cid:0)xk+1 − x∗(cid:1) − ck
(cid:0)F k − F ∗(cid:1)T (cid:0)vk − v∗ − zk+1 + z∗(cid:1) − ∆k. (3.16)
Mặt khác, g là lồi mạnh với hệ số τ > 0, rõ ràng là ∂g là đơn điệu mạnh với
2
hệ số τ trong đó ánh xạ ∂g1 := ∂g + NC cũng là đơn điệu mạnh với hệ số τ. (cid:0)xk+1(cid:1) , chúng ta có thể viết Như vậy, từ zk+1 ∈ ∂g1
(cid:0)xk+1 − x∗(cid:1)T (cid:0)zk+1 − z∗(cid:1) − τ (cid:13) ≥ 0. (3.17) (cid:13)xk+1 −x∗(cid:107)
Từ (3.16) và (3.17), sử dụng z∗ + F (x∗) = v∗ và (3.15), ta được
0 ≤ (cid:0)F k − F ∗ + zk+1 − z∗(cid:1)T (cid:0)xk+1 − x∗(cid:1)
k
(cid:16) (cid:13)xk+1 − x∗(cid:107) 2 − ∆k (cid:19) −ck (cid:16) = F k − F ∗(cid:17)T (cid:0)vk − v∗ − zk+1 + z∗(cid:1) − τ (cid:13) xk+1 − x∗(cid:17)T (cid:18) vk + − v∗ (xk−x∗)−(xk+1−x∗) ck
2
(cid:16) F − F ∗(cid:17)T (cid:0)vk − v∗ − zk+1 + z∗(cid:1) − τ (cid:13) −ck − ∆k. (cid:13)xk+1 − x∗(cid:107)
Ta nói rằng
(cid:98)xk := xk − x∗, (cid:98)xk+1 := xk+1 − x∗, (cid:98)vk := vk − v∗, (cid:98)zk+1 := zk+1 − z∗
30
và (cid:98)F k := F k − F ∗. Chúng ta có thể viết bất đẳng thức cuối cùng là
2
k
(cid:16) (cid:0) −2ck∆k ≥ 0. 2ck (cid:98)F k(cid:17)T (cid:0) (cid:98)xk+1(cid:1)T (cid:98)vk−2(cid:0) (cid:98)xk+1(cid:1)T (cid:0) (cid:98)xk+1 − (cid:98)xk(cid:1)−2c2 (cid:98)vk − (cid:98)zk+1(cid:1)−2ckτ (cid:13)
(cid:13)(cid:98)xk+1 (cid:107) (3.18)
2
Từ (3.15), chúng ta có
(cid:16) ˆF k(cid:17)T (cid:0)ˆvk − ˆzk+1(cid:1) . (cid:13)ˆzk+1 − ˆvk(cid:13) (cid:13) (cid:13) (cid:107)ˆx k+1 − ˆxk(cid:13) 2 (cid:13) + c2 k − 2c2 k = c2 k ˆF k(cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13)
Khi đó bằng cách sử dụng
, − (cid:13) + (cid:13) 2(cid:0) (cid:13)(cid:98)xk(cid:13) 2 (cid:13) (cid:13)(cid:98)xk+1(cid:13) 2 (cid:13) (cid:13)(cid:98)xk+1 − (cid:98)xk(cid:13) 2 (cid:13) (cid:98)xk+1(cid:1)T (cid:0) (cid:98)xk+1 − (cid:98)xk(cid:1) = (cid:13)
có được từ (3.18) là
2 (cid:13) (cid:13)
(cid:0) (cid:13) (cid:13) −2ck∆k ≥ 0. 2ck −c2 k −c2 k (cid:13)(cid:98)xk+1(cid:13) 2 (cid:13) (cid:13)(cid:98)xk(cid:13) +(cid:13) 2 (cid:13) (cid:98)xk+1(cid:1)T (cid:98)vk−(1 + 2ckτ ) (cid:13) (cid:13)(cid:98)vk − (cid:98)zk+1(cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:98)F k(cid:13)
(3.19)
Do ∇h là L-Lipschitz liên tục, chúng ta có
(cid:13) ≤ L (cid:13) (cid:13)(cid:98)vk(cid:13) (cid:13) (cid:13)(cid:98)xk(cid:13) (cid:13) .
Ta có thể chứng minh bởi bất đẳng thức Chebyshev
(cid:32) (cid:33)
2(cid:0) + , ∀t > 0. (cid:13) ≤ 2L (cid:13) (cid:13) ≤ 2L (cid:98)xk+1(cid:1)T (cid:98)vk ≤ 2 (cid:13) (cid:13)(cid:98)xk+1(cid:13) (cid:13) (cid:13)(cid:98)vk(cid:13) (cid:13) (cid:13)(cid:98)xk(cid:13) (cid:13) (cid:13)(cid:98)xk+1(cid:13) (cid:13) (cid:13)(cid:98)xk(cid:13) t(cid:13) 2 (cid:13) (cid:13)(cid:98)xk+1(cid:13) (cid:13) 2 (cid:13) t
Như vậy chúng ta có thể thay thế 2(cid:0)
(cid:32) (cid:33)
2L + t(cid:13) (cid:13)(cid:98)xk(cid:13) 2 (cid:13) (cid:98)xk+1(cid:1)T (cid:98)vk bởi (cid:13) (cid:13)(cid:98)xk+1(cid:13) 2 (cid:13) t
vào (3.19) và sử dụng định nghĩa của ∆k để có được
2 (cid:13) (cid:13)
(cid:13) (cid:13) , (3.20) αk − βk ≥ ck (2σ − ck) + c2 k (cid:13) (cid:13)(cid:98)xk(cid:13) 2 (cid:13) (cid:13) (cid:13)(cid:98)xk+1(cid:13) 2 (cid:13) (cid:13) (cid:13)(cid:98)vk − (cid:98)zk+1(cid:13) 2 (cid:13)
L t
(cid:1) và t > 0. (cid:13) (cid:98)F k(cid:13) trong đó αk = 1 + ckLt, βk = (cid:0)1 + 2ckτ − ck
31
Hệ quả 3.3. Dưới giả thiết của Mệnh đề 3.7, chúng ta giả sử thêm rằng τ ≥ L. Khi đó dãy (cid:8)xk(cid:9) được tạo ra bởi (3.12) hội tụ đến một điểm dừng của bài toán (3.4). Hơn nữa, nếu τ > L hoặc F là µ đơn điệu mạnh, thì dãy (cid:8)xk(cid:9) hội tụ tuyến tính đến một điểm dừng của bài toán (3.4)
Chứng minh. Giả sử τ ≥ L. Lấy M và m là hai số thực sao cho
0 < m ≤ ck ≤ M < 2σ.
2
Nếu chúng ta cho t = 1, theo (3.20) ta có
≥ 0. − (cid:13) ≥ (cid:13)F (cid:0)xk(cid:1) − F (x∗)(cid:13) (cid:13) 2 (cid:13) (cid:13)xk − x∗(cid:13) (cid:13) (cid:13) (cid:13)xk+1 − x∗(cid:13) 2 (cid:13)
m (2σ − M ) 1 + M L 2(cid:111) (cid:110)(cid:13) (cid:13)xk − x∗(cid:13) (cid:13)
là hội tụ, vì nó là dãy không tăng F (cid:0)xk(cid:1) =
Do đó, (cid:8)xk(cid:9) bị chặn và dãy và bị chặn dưới bởi 0. Hơn nữa, bất đẳng thức này có nghĩa là lim k→∞ F (x∗) . Lưu ý rằng, từ (3.15) chúng ta có
k→∞
(cid:0)vk − zk+1 − F k(cid:1) = lim (cid:0)vk − zk+1(cid:1) − F ∗, 0 = lim k→∞ = lim k→∞ xk+1 − xk ck
(cid:0)vk − v∗ − zk+1 + z∗(cid:1) = 0. từ giả thiết −F ∗ = z∗ − v∗ mà lim k→∞
(cid:13) . Như vậy (cid:8)vk(cid:9) là bị chặn. Lấy dãy con (cid:8)vk : k ∈ K(cid:9) (cid:13)xk − x∗(cid:13) (cid:13) ≤ L (cid:13)
Để x∞ là điểm giới hạn của dãy bị chặn (cid:8)xk(cid:9) và (cid:8)xk : k ∈ K(cid:9) là dãy con F (cid:0)xk(cid:1) = hội tụ tới x∞. Do F là đơn điệu mạnh ngược, liên tục. Do đó lim k→∞ F (x∗) nghĩa là F (x∞) = F (x∗) . Giả sử ∇h là L-Lipschitz, chúng ta có (cid:13)vk − v∗(cid:13) (cid:13) hội tụ đến v∞. Sử dụng tính liên tục của ∇h, chúng ta có v∞ = ∇h (x∞) . Chúng ta thấy rằng v∞ − F (x∞) ∈ ∂g1 (x∞) . Lấy z ∈ ∂g1 (x) khi đó từ đơn điệu mạnh của ∂g1
(cid:13)xk − x(cid:13) 2 ≤ (cid:0)zk − z(cid:1)T (cid:0)xk − x(cid:1) = (cid:0)zk − z(cid:1)T (cid:0)xk − x∞(cid:1) + (cid:0)zk − z(cid:1)T (x∞ − x) (cid:13)
0 ≤ τ (cid:13) = (cid:0)zk − z(cid:1)T (cid:0)xk − x∞(cid:1) + (cid:0)zk − vk−1 − z(cid:1)T (x∞ − x) + (cid:0)vk−1(cid:1)T (x∞ − x) .
(cid:0)vk − v∗ − zk+1 + z∗(cid:1) = 0, chúng ta có Lưu ý rằng, từ lim k→∞
zk+1 − vk → z∗ − v∗ = −F (x∗) .
32
Khi đó, lấy giới hạn về bên trái của bất đẳng thức, chúng ta có
(v∞ − F (x∗) − x)T (x∞ − x) ≥ 0
trong đó, sự đơn điệu cực đại của ∂g1, v∞−F (x∗) ∈ ∂g1 (x∞) . Do F (x∞) = F (x∗) , chúng ta có v∞ − F (x∞) ∈ ∂g1 (x∞) . Lưu ý rằng v∞ = ∇h (x∞) chúng ta có 0 ∈ ∂g1 (x∞) + F (x∞) − ∇h (x∞) , có nghĩa là x∞ là một điểm (cid:13)xk − x∞(cid:13) dừng của bài toán (3.4). Thay x∗ bằng x∞ vào (3.14) thấy rằng (cid:8)(cid:13) (cid:9) (cid:13) là hội tụ, chúng ta có thể thấy toàn bộ dãy (cid:8)xk(cid:9) hội tụ tới x∞, bởi vì nó là dãy con hội tụ tới x∞, tiếp theo từ (3.14)
. αk (cid:13)xk − x∗(cid:13) (cid:13) 2 (cid:13) (cid:0)xk+1 − x∗(cid:1)(cid:13) (cid:13) 2 (cid:13) (cid:13)
Như vậy, nếu L < τ thì 0 < r := < 1 với mỗi k ≥ 0. Do đó ≥ βk (cid:113) αk βk
(cid:13) ≤ r (cid:13) (cid:13)xk − x∗(cid:13) (cid:13) ,
(cid:13)xk+1 − x∗(cid:13) (cid:13) ta thấy rằng dãy (cid:8)xk(cid:9) hội tụ tới x∗.
. Nếu F là đơn điệu mạnh với hệ số µ > 0 thì (cid:13)xk − x∗(cid:13) (cid:13) (cid:13)F (cid:0)xk(cid:1) − F (x∗)(cid:13) (cid:13) (cid:13) (cid:13) ≥ (cid:0)F (cid:0)xk(cid:1) − F (x∗)(cid:1)T (cid:0)xk − x∗(cid:1) ≥ µ(cid:13) (cid:13)xk − x∗(cid:13) 2 (cid:13)
Do đó
≥ µ2(cid:13) . (cid:13)F (cid:0)xk(cid:1) − F (x∗)(cid:13) (cid:13) 2 (cid:13) (cid:13)xk − x∗(cid:13) 2 (cid:13)
Thay bất đẳng thức này vào (3.14), chúng ta nhận được
. (cid:2)αk − µ2ck (2σ − ck)(cid:3) (cid:13) ≥ βk (cid:13)xk − x∗(cid:13) 2 (cid:13) (cid:13)xk+1 − x∗(cid:13) (cid:13) 2 (cid:13)
Sử dụng giả thiết 0 < m ≤ ck ≤ M < 2σ và lấy t = 1, chúng ta có bất đẳng
. thức (cid:2)1 + ckL − µ2ck (2σ − ck)(cid:3) (cid:13) ≥ (1 + 2ckτ − ckL) (cid:13) (cid:13)xk − x∗(cid:13) 2 (cid:13) (cid:13)xk+1 − x∗(cid:13) 2 (cid:13)
Do
(cid:17) τ + µ2 (cid:16) > L, 1 + ckL − µ2ck (2σ − ck) < 1 + 2ckτ − ckL, m 2
σ − ta thấy (cid:8)xk(cid:9) hội tụ đến x∗.
33
3.4 Một mô hình cân bằng bán độc quyền
Trong mô hình này chúng ta giả sử có n doanh nghiệp cùng sản xuất một
loại hàng hóa, kí hiệu x1, x2, .., xn là số lượng hàng hóa mà các doanh nghiệp
cần sản xuất. Giả sử Ci là tập chiến lược của doanh nghiệp thứ i (i=1,2,...,n)
(nghĩa là số lượng hàng hóa của doanh nghiệp thứ i nằm trong Ci).
n (cid:80) i=1
(i) Pi là giá thành của một đơn vị hàng hóa phụ thuộc vào xi.
(ii) hi (xi) là chi phí của doanh nghiệp i khi sản xuất một lượng hàng hóa
xi. Vậy lợi nhuận của doanh nghiệp thứ i là:
i=1
(cid:32) n (cid:33) (cid:88) (3.21) fi (x1, . . . , xn) = xipi xi − hi (xi) (i = 1, ..., n) .
Trong thực tế mỗi doanh nghiệp đều muốn tìm một phương án sản xuất trong
tập chiến lược của mình sao cho lợi nhuận là lớn nhất. Tuy nhiên một phương
án tối ưu cho tất cả các doanh nghiệp trong thực tế thường không tồn tại, vì lợi
ích của các doanh nghiệp thường mâu thuẫn, đối kháng nhau. Trong trường
hợp này chúng ta sử dụng cân bằng Nash.
1, ..., x∗
n) ∈ C := C1 × ... × Cn được coi là điểm cân
Một điểm x∗ = (x∗
bằng Nash nếu
1, ..., x∗
i−1, yi, x∗
i+1, ..., x∗
n) ≤ fi (x∗
1, ..., x∗
n) , ∀yi ∈ Ci, ∀i = 1, ..., n.
fi (x∗
(3.22)
Theo định nghĩa điểm cân bằng, khi một doanh nghiệp thay đổi phương án
sản xuất trong khi các doanh nghiệp khác giữ nguyên phương án sản xuất cân
bằng thì lợi ích của doanh nghiệp thay đổi sẽ bị thiệt.
Dưới đây ta sẽ chỉ ra rằng mô hình cân bằng Nash với hàm giá và cước
phí là affine sẽ được chuyển về bài toán tối ưu toàn phương lồi mạnh. Còn
nếu như hàm chi phí là lõm thì việc tìm điểm cân bằng Nash sẽ quay về bài
toán bất đẳng thức biến phân hỗn hợp DC.
34
n (cid:88)
Đặt
i=1
ψ (x, y) := − (3.23) fi(x1, ..., xi−1, yi, xi+1, ..., xn),
φ (x, y) := ψ (x, y) − ψ (x, x) . (3.24)
Khi đó bài toán tìm điểm cân bằng Nash có thể viết dưới dạng bài toán
cân bằng.
Cho x∗ ∈ C sao cho φ (x∗, y) ≥ 0 với mỗi y ∈ C. (EP)
Trong các mô hình cổ điển, giá cả và hàm chi phí cho mỗi doanh nghiệp
được giả thiết là affine
n (cid:80) i=1
pi (σ) ≡ p (σ) = α0 − βσ, α0 ≥ 0, β > 0, với σ = xi,
hi (xi) = µixi + ξi, µi ≥ 0, ξi ≥ 0 (i = 1, ..., n) . Trong trường hợp này
sử dụng (3.21)-(3.24) ta có
(cid:16) (cid:17)T φ (x, y) = (y − x) + yT Ay − xT Ax, (cid:101)Ax + µ − α
trong đó
β 0 0 ... 0 0 β β ... β
0 β 0 ... 0 β 0 β ... β A = , , (cid:101)A = ... ... ... ... 0 ... ... ... ... ... 0 0 0 0 β β β β ... 0
αT = (α0, ..., α0) , µT = (µ1, ..., µn) .
Vậy bài toán tìm điểm cân bằng Nash trở về bài toán:
(cid:16) (cid:17)T (y − x) + yT Ay − xT Ax ≥ 0, ∀y ∈ C. x ∈ C sao cho (cid:101)Ax + µ − α
(3.25) Với Q := 2A + (cid:101)A. Do β > 0 nên Q là ma trận đối xứng xác định dương. Khi
đó bất đẳng thức biến phân hỗn hợp (3.25) có thể định nghĩa tương đương với
một bài toán quy hoạch toàn phương bậc hai sau:
(cid:27) xT Qx + (µ − α)T x . (QP) min x∈U (cid:26)1 2
35
Vì vậy, bài toán này có một phương án tối ưu duy nhất và cũng là điểm
cân bằng của mô hình cân bằng thị trường toán độc quyền cổ điển Nash.
Hàm chi phí được giả định là phụ thuộc tuyến tính và số lượng của các
hàng hóa nói chung không thực tế, vì thường các chi phí để sản xuất cho một
đơn vị hàng hóa giảm đi khi số lượng sản xuất tăng. Từ mô hình này, trong
phần tiếp theo chúng ta xem xét mô hình cân bằng với chi phí lõm.
Giả sử
n (cid:88)
j=1
j=1
(cid:32) n (cid:33) (cid:88) pi (σ) := pi xj = αi − βi xj, αi ≥ 0, βi > 0 (i = 1, ..., n) .
(3.26)
Trong trường hợp này, chúng ta kí hiệu
αT = (α1, ..., αn) ,
0 ... ... 0 β1 0 0 β1 β1 β1
n (cid:88)
... 0 0 β2 0 ... β2 0 β2 β2 B := , , (cid:101)B := ... ... ... ... ... ... ... ... 0 ... 0 0 0 0 0 βn βn βn ... βn
i=1 Với hi(i = 1, ..., n) là hàm lõm. Rõ ràng, B là một ma trận xác định dương.
h (x) := hi (xi).
Khi đó, chúng ta có thể xây dựng bài toán (EP) như sau:
Cho x∗ ∈ C sao cho
f (x∗, y) := F (x∗)T (y − x∗) + ϕ (y) − ϕ (x∗) ≥ 0, ∀y ∈ C,
trong đó F (x) := (cid:101)B (x) − α và ϕ (x) := xT Bx + h (x) . Do B là đối xứng xác định dương và h là lõm, bài toán này có dạng (3.4).
36
Kết luận
Nội dung của luân văn nghiên cứu về phương pháp điểm gần kề giải bài
toán bất đẳng thức biến phân hỗn hợp DC.
Qua 3 chương, luận văn đã hoàn thành được những công việc sau:
1. Trình bày được các định nghĩa, các tính chất cơ bản của hàm lồi và tập
lồi, cùng các kiến thức của giải tích hàm có liên quan.
2. Trình bày được chi tiết bài toán bất đẳng thức biến phân, định nghĩa,
các ví dụ, các sự tồn tại nghiệm và tính chất của tập nghiệm bài toán.
3. Trình bày được phương pháp điểm gần kề giải bài toán bất đẳng thức
biến phân hỗn hợp DC.
37
Tài liệu tham khảo
Tiếng Việt
[1] Lê Dũng Mưu, Nguyễn Văn Hiền, Nguyễn Hữu Điển (2015), Nhập môn
giải tích lồi ứng dụng, NXB ĐHQG, Hà Nội.
Tiếng Anh
[2] Facchinei S. and Pang J. (2003), Finite-Dimensional Variation-
alInequalities and Complementarity Problems, Springr - Verlag,
NewYork.
[3] Heinz H. Bauschke Patrick L. Combettes, (2010), Convex Analysis and
Monotone Operator Theoryin Hilbert Spaces, Springer.
[4] Konnov, I. V. (2001), Combined Relaxation Methods for Variational In-
equalities., Springer, Berlin.
[5] Konnov I. V. (2007), Equilibrium Models and Variational Inequalities,
Mathematics in Science and Engineering.
[6] Muu L.D and Quoc T.D (2010), “One step from DC optimization to DC
mixed variational inequalities”,Optimization 59, 63-76.
[7] Tuy H. (2008), Convex Analysis and Global Optimization, Springer.
