ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC -------------------------------
NGUYỄN THÀNH HUẾ
MỘT TIẾP CẬN CÂN BẰNG TÁCH CHO MÔ HÌNH NASH - COURNOT VỚI MỘT RÀNG BUỘC CHUNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC -------------------------------
NGUYỄN THÀNH HUẾ
MỘT TIẾP CẬN CÂN BẰNG TÁCH CHO MÔ HÌNH NASH - COURNOT VỚI MỘT RÀNG BUỘC CHUNG Chuyên ngành: Toán ứng dụng Mã số : 8 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 - 2019
i
Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn của GS.TSKH. Lê
Dũng Mưu (trường Đại học Thăng Long Hà Nội). Tác giả xin được bày
tỏ lòng biết ơn chân thành và sâu sắc tới thầy hướng dẫn khoa học của
mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn
và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm
luận văn.
Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích
cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm
ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp cao học
Toán, nhà trường và các phòng chức năng của trường, khoa Toán - Tin,
trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp
đỡ tác giả trong suốt thời gian học tập tại trường.
Xin chân thành cảm ơn anh chị em trong lớp cao học và bạn bè đồng
nghiệp đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập,
nghiên cứu và làm luận văn.
Thái Nguyên, 10 tháng 4 năm 2019
Tác giả luận văn
Nguyễn Thành Huế
ii
Mục lục
Lời cảm ơn i
Bảng ký hiệu iii
Lời nói đầu 1
Chương 1 Kiến thức chuẩn bị 3
1.1. Tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều . . 3
1.2. Các bổ đề hỗ trợ . . . . . . . . . . . . . . . . . . . . . . . . . 19
Chương 2 Một tiếp cận cân bằng tách cho mô hình Nash-
Cournot với một ràng buộc chung 21
2.1. Bài toán chấp nhận lồi tách . . . . . . . . . . . . . . . . . . . 21
2.2. Một thuật toán giải mô hình Nash–Cournot có ràng buộc chung 22
2.2.1.Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2.Một mô hình thực tế . . . . . . . . . . . . . . . . . . . 31
Kết luận 36
Tài liệu tham khảo 37
iii
Bảng ký hiệu
Rn +
R
R Góc không âm của Rn (tập các vectơ không âm) Trục số thực R = R1 Trục số thực mở rộng (R = R ∪ {−∞, +∞})
Tọa độ thứ i của x
xi xT Vectơ hàng (chuyển vị của x )
||x|| Chuẩn Euclid của x
riA Tập hợp các điểm trong tương đối của A
Nón lùi xa (nón các hướng vô hạn) của A
reA A∗ Đối cực của A
f Hàm bao đóng của f
Tập hữu dụng của f
domf f ∗ Hàm liên hợp của f
epif Trên đồ thị của f
∂f (x) Dưới vi phân của f tại x
ε -dưới vi phân của f tại x
Đạo hàm f tại x
∂∈f (x) ∇f (x) Hoặc đạo hàm của f tại x f (cid:48)(x) f (cid:48)(x, d) Đạo hàm theo hướng d của f tại x
1
Lời nói đầu
Bài toán chấp nhận tách là bài toán
Tìm x∗ ∈ C sao cho Ax∗ ∈ Q,
trong đó C là một tập lồi đóng trong không gian X, còn Q là một tập lồi
đóng trong không gian Y và A là một toán tử tuyến tính từ X vào Y .
Bài toán này có thể coi như một sự mở rộng của bài toán chấp nhận
lồi, là một bài toán cơ bản trong Toán ứng dụng. Bài toán chấp nhận
tách lần đầu tiên được nghiên cứu trong không gian Euclid hữu hạn chiều
bởi Censor và Elving năm 1994 trong tài liệu [2]. Trong bài báo này các
tác giả đã giới thiệu một số ứng dụng của bài toán chấp nhận tách trong
không gian hữu hạn chiều, như ứng dụng trong xạ trị khối u, trong xử
lý tín hiệu v.v... Sau công trình trên, bài toán chấp nhận tách được rất
nhiều người quan tâm nghiên cứu, do tính lý thú về mặt toán học, và đặc
biệt là phạm vi ứng dụng rộng rãi của bài toán này. Một hướng mở rộng
được quan tâm nhiều là xét trường hợp khi các tập C và Q là nghiệm của
những bài toán khác, như bài toán tối ưu lồi, bất đẳng thức biến phân
đơn điệu, tập điểm bất động của ánh xạ không giãn, hoặc tổng quát hơn
là tập nghiệm của bài toán cân bằng có một tính chất đơn điệu nào đó.
Mục đích của bản luận văn này là trình bày lại một cách có hệ thống
các kết quả về mô hình Nash–Cournot trong trường hợp mô hình có thêm
một ràng buộc chung, theo cách tiếp cận dựa trên việc mô tả mô hình
dưới dạng bài toán cân bằng tách.
Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục
2
các tài liệu tham khảo.
Chương 1 trình bày một số khái niệm cơ bản liên quan đến đề tài, đó
là tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều.
Chương 2 giới thiệu bài toán chấp nhận lồi tách, giới thiệu mô hình
Nash–Cournot và trình bày một thuật toán giải bài toán mô hình Nash–
Cournot có ràng buộc chung theo tiếp cận cân bằng tách.
3
Chương 1
Kiến thức chuẩn bị
Chương này trình bày các khái niệm, các tính chất cơ bản nhất của
giải tích lồi và các bổ đề hỗ trợ sẽ được dùng trong Chương 2. Các kiến
1.1. Tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều
thức ở chương này được tổng hợp từ tài liệu tham khảo [1], [3].
Định nghĩa 1.1 Một tập C ⊆ Rn được gọi là một tập lồi, nếu C chứa
mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ
khi
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
k (cid:88)
k (cid:88)
Ta nói x là tổ hợp lồi của các điểm (vectơ) x1, ..., xk nếu
j=1
j=1
x = λjxj, λj > 0 ∀j = 1, ..., k λj = 1.
k (cid:88)
k (cid:88)
Tương tự, x là tổ hợp aphin của các điểm (vectơ) x1, ..., xk nếu
j=1
j=1
x = λjxj, λj = 1.
Tập hợp của các tổ hợp aphin của x1, ..., xk thường được gọi là bao aphin
của các điểm này.
4
Mệnh đề 1.1 Tập hợp C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của
k (cid:88)
k (cid:88)
các điểm của nó. Tức là tập C lồi khi và chỉ khi
j=1
j=1
∀k ∈ N, ∀λ1, ..., λk > 0 : λj = 1, ∀x1, ..., xk ∈ C ⇒ λjxj ∈ C.
Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh
điều kiện cần bằng quy nạp theo số điểm. Với k = 2, điều cần chứng minh
suy ra ngay từ định nghĩa của tập lồi và tổ hợp lồi. Giả sử mệnh đề đúng
với k − 1 điểm. Ta cần chứng minh với k điểm.
k (cid:88)
k (cid:88)
Giả sử x là tổ hợp lồi của k điểm x1, ..., xk ∈ C. Tức là
j=1
j=1
x = λjxj, λj > 0 ∀j = 1, ..., k λj = 1.
k−1 (cid:88)
Đặt
j=1
ξ = λj.
k−1 (cid:88)
k−1 (cid:88)
Khi đó 0 < ξ < 1 và
j=1
j=1
x = xj + λkxk λjxj + λkxk = ξ λj ξ
k−1 (cid:88)
do
j=1
= 1. λj ξ
ξ > 0 với mọi j = 1, ..., k − 1, nên theo giả thiết quy nạp, điểm
k−1 (cid:88)
Với λj
j=1
y := xj ∈ C. λj ξ
Ta có
x = ξy + λkxk.
k (cid:88)
Do ξ > 0, λk > 0 và
j=1
λj = 1, ξ + λk =
5
nên x là một tổ hợp lồi của hai điểm y và xk đều thuộc C. Vậy x ∈ C.
(cid:3)
Định nghĩa 1.2 Một tập C được gọi là tập aphin nếu nó chứa đường
thẳng đi qua hai điểm bất kỳ của nó, tức là
∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C.
Vậy tập aphin là một trường hợp riêng của tập lồi. Ví dụ điển hình của
tập aphin là các không gian con, siêu phẳng được định nghĩa dưới đây.
Định nghĩa 1.3 Siêu phẳng trong không gian Rn là một tập hợp các
điểm có đạng
{x ∈ Rn|aT x = α},
trong đó a ∈ Rn là một vectơ khác 0 và α ∈ R.
Vectơ a thường được gọi là vectơ pháp tuyến của siêu phẳng. Một siêu
phẳng sẽ chia không gian ra hai nửa không gian. Nửa không gian được
định nghĩa như sau:
Định nghĩa 1.4 Nửa không gian là một tập hợp có dạng {x|aT x ≥ α}, trong đó a (cid:54)= 0 và α ∈ R. Đây là nửa không gian đóng. Tập {x| aT x > α}
là nửa không gian mở.
Định nghĩa 1.5 Các điểm x0, x1, ..., xk trong Rn được gọi là độc lập
aphin, nếu bao aphin của chúng có thứ nguyên là k.
Định nghĩa 1.6 Một tập hợp được gọi là tập lồi đa diện, nếu nó là giao
của một số hữu hạn các nửa không gian đóng.
Theo định nghĩa, tập lồi đa diện là tập hợp nghiệm của một hệ hữu
hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi
đa diện được cho như sau:
D := {x ∈ Rn| (cid:10)aj, x(cid:11) ≤ bj, j = 1, ..., m}.
6
Hoặc nếu ta ký hiệu A là ma trận có m hàng là các vectơ aj(j = 1, ..., m) và vectơ bT = (b1, ..., bm), thì hệ trên viết được là
D = {x ∈ Rn|Ax ≤ b}.
Chú ý rằng do một phương trình
(cid:104)a, x = b(cid:105)
có thể viết một cách tương đương dưới dạng hai bất phương trình
(cid:104)a, x(cid:105) ≤ b, (cid:104)−a, x(cid:105) ≤ b,
nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương
trình cũng là một tập lồi đa diện.
Một số các tính chất của tập lồi đa diện sẽ được trình bày trong các
phần tiếp theo.
Định nghĩa 1.7 Cho C (cid:54)= (cid:11) (không nhất thiết lồi) và y là một vectơ
bất kỳ, đặt
||x − y||. dC(y) := inf x∈C
Ta nói dC(y) là khoảng cách từ y đến C. Nếu tồn tại π ∈ C sao cho
dC(y) := ||π − y||, thì ta nói π là hình chiếu (vuông góc) của y trên C.
Theo định nghĩa, ta có hình chiếu pC(y) của y trên C sẽ là nghiệm của
bài toán tối ưu.
{ ||x − y||2 |x ∈ C} min x 1 2
Vậy việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu
của hàm toàn phương ||x − y||2 trên C.
Ta sẽ ký hiệu π = PC(y), hoặc đơn giản hơn là p(y) nếu không cần nhấn mạnh đến tập chiếu C. Chú ý rằng, nếu C (cid:54)= (cid:11), thì dC(y) hữu hạn, vì 0 ≤ dC(y) ≤ ||y − x|| với mọi x ∈ C.
Cho C ⊆ Rn, x0 ∈ C. Nhớ lại là nón pháp tuyến (ngoài) của tập C tại
x0 là tập hợp
NC(x0) := {w|wT (x − x0) ≤ 0 ∀x ∈ C}.
7
Mệnh đề 1.2 Cho C là một tập lồi đóng khác rỗng. Khi đó: (i) Với mọi y ∈ Rn, π ∈ C hai tính chất sau là tương đương:
a) π = PC(y), b) y − π ∈ NC(π).
(ii) Với mọi y ∈ Rn, hình chiếu PC(y) của y trên C luôn tồn tại và duy nhất.
(iii) Nếu y /∈ C, thì (cid:104)PC(y) − y, x − PC(y)(cid:105) = 0 là siêu phẳng tựa của C tại PC(y) và tách hẳn y khỏi C, tức là
(cid:104)PC(y) − y, x − PC(y)(cid:105) ≥ 0, ∀x ∈ C,
và
(cid:104)PC(y) − y, y − PC(y)(cid:105) < 0.
(iv) Ánh xạ y (cid:44)→ PC(y) có các tính chất sau:
a) ||PC(x) − PC(y)|| ≤ ||x − y|| ∀x, ∀y ( tính không giãn); b) (cid:104)PC(x) − PC(y)(cid:105) , x − y ≥ ||PC(x) − PC(y)||2, (tính đồng bức).
Chứng minh (i) Giả sử có a). Lấy x ∈ C và λ ∈ (0, 1). Đặt
xλ := λx + (1 − λ)π.
Do x, π ∈ C và C lồi, nên xλ ∈ C. Hơn nữa do π là hình chiếu của y, nên ||π − y|| ≤ ||y − xλ||. Hay
||π − y||2 ≤ ||λ(x − π|| + (π − y)||2.
Khai triển vế phải, ước lược và chia hai vế cho λ > 0, ta có
λ||x − π||2 + 2 (cid:104)x − π, π − y(cid:105) ≥ 0.
Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ tiến đến 0,
ta được
(cid:104)π − y, x − π(cid:105) ≥ 0 ∀x ∈ C.
Vậy y − π ∈ NC(π).
8
Bây giờ giả sử có b). Với mọi x ∈ C, có
0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π)
= ||y − π||2 + (y − π)T (x − y).
Từ đây và b), dùng bất đẳng thức Cauchy–Schwarz ta có:
||y − π||2 ≤ (y − π)T (y − x) ≤ ||y − π||||(y − x)||.
Suy ra ||(y − π)|| ≤ ||y − x|| ∀x ∈ C, và do đó π = p(y).
(ii) Do dC(y) = infx∈C||x − y||, nên theo định nghĩa của cận dưới đúng
(infimum), tồn tại một dãy xk ∈ C sao cho
||xk − y|| = dC(y) < +∞ lim k
Vậy dãy {xk} bị chặn, do đó nó có một dãy con {xkj} hội tụ đến một
điểm π nào đó. Do C đóng, nên π ∈ C. Vậy
j
||π − y|| = lim ||xk − y|| = dC(y). ||xkj − y|| = lim k
Chứng tỏ π là hình chiếu của y trên C.
Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại
hai điểm π và π1 đều là hình chiếu của y trên C, thì
y − π ∈ NC(π), y − π1 ∈ NC(π1).
Tức là
(cid:10)π − y, π1 − π(cid:11) ≥ 0
và
(cid:10)π1 − y, π − π1(cid:11) ≥ 0.
Cộng hai bất đẳng thức này ta suy ra ||π − π1|| ≤ 0, và do đó π = π1.
(iii) Do y − π ∈ NC(π), nên
(cid:104)π − y, x − π(cid:105) ≥ 0 ∀x ∈ C.
9
Vậy (cid:104)π − y, x(cid:105) = (cid:104)π − y, π(cid:105) là một siêu phẳng tựa của C tai π. Siêu phẳng
này tách y khỏi C vì y (cid:54)= π, nên
(cid:104)π − y, y − π(cid:105) = −||π − y||2 < 0.
(iv) Theo phần (ii) ánh xạ x (cid:44)→ p(x) xác định khắp nơi.
Do z − p(z) ∈ NC(p(z)) với mọi z, nên áp dụng với z = x và z = y, ta có:
(cid:104)x − p(x), p(y) − p(x)(cid:105) ≤ 0
và
(cid:104)y − p(y), p(x) − p(y)(cid:105) ≤ 0.
Cộng hai bất đẳng thức lại sẽ được
(cid:104)p(y) − p(x), p(y) − p(x) + x − y(cid:105) ≤ 0.
Từ đây và theo bất đẳng thức Cauchy–Schwarz, suy ra
||p(x) − p(y)|| ≤ ||x − y||.
Để chứng mnh tính đồng bức, áp dụng tính chất b của (i), lần lượt với
p(x) và p(y), ta có
(cid:104)p(x) − x, p(x) − p(y)(cid:105) ≤ 0.
(cid:104)y − p(y), p(x) − p(y)(cid:105) ≤ 0.
Cộng hai bất đẳng thức ta được
(cid:104)p(x) − p(y) + y − x, p(x) − p(y)(cid:105) ≤ 0
= (cid:104)p(x) − p(y), y − x(cid:105) + ||p(x) − p(y)||2 ≤ 0.
Chuyển vế ta có
(cid:104)p(x) − p(y), x − y(cid:105) ≥ ||p(x) − p(y)||2.
Đây chính là tính đồng bức cần được chứng minh.
(cid:3)
10
Định nghĩa 1.8 Một ánh xạ F : C −→ Rn được gọi là đơn điệu trên C,
nếu
(cid:104)F (x) − F (y), x − y(cid:105) ≥ 0 ∀x, y ∈ C
Ánh xạ F được gọi là đơn điệu mạnh trên C với hệ số β > 0, nếu
(cid:104)F (x) − F (y), x − y(cid:105) ≥ β||x − y||2 ∀x, y ∈ C
Cho C ⊆ Rn là tập lồi và f : C (cid:44)→ R. Ta sẽ ký hiệu
domf := {x ∈ C| f (x) < +∞}
Tập domf được gọi là miền hữu dụng của f . Tập
epif := {(x, µ) ∈ C × R|f (x) ≤ µ}
được gọi là trên đồ thị của hàm f .
Bằng cách cho f (x) = +∞ nếu x /∈ C, ta có thể coi f được xác định
trên toàn không gian và hiển nhiên là
domf = {x ∈ Rn| f (x) < +∞}
epif = {(x, µ) ∈ Rn| × R|f (x) ≤ µ}
Do sẽ làm việc với hàm số nhận cả giá trị −∞ và +∞, ta có quy ước sau:
Nếu λ = 0, thì λf (x) = 0 với mọi x.
Định nghĩa 1.9 Cho (cid:11) (cid:54)= C ⊆ Rn lồi và f : C → R. Ta nói f là hàm lồi trên C, nếu epif là một tập lồi trong Rn+1.
Ta sẽ chủ yếu làm việc với hàm f : Rn → R ∪ {+∞} . Trong trường
hợp này, dễ thấy rằng định nghĩa trên tương đương với
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀ λ(0, 1).
Hàm f : Rn → R ∪ {+∞} được gọi là lồi chặt trên C nếu
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀ λ ∈ (0, 1).
11
Hàm f : Rn → R ∪ {+∞} . được gọi là lồi mạnh trên C với hệ số η > 0,
nếu ∀x, y ∈ C, ∀λ ∈ (0, 1) có:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ηλ(1 − λ)||x − y||2. 1 2
Kiểm tra được rằng, f lồi mạnh trên C với hệ số η > 0 khi và chỉ khi
hàm
||.||2 h(.) := f (.) − η 2
lồi trên C.
j=1 λj = 1, ta có
m (cid:88)
m (cid:88)
Bằng quy nạp, dễ dàng chứng minh được rằng, nếu f nhận giá trị hữu hạn trên tập lồi C, thì với mọi số tự nhiên m và mọi x1, ..., xm ∈ C thỏa mãn λ1 ≥ 0, ..., λm ≥ 0, (cid:80)m
j=1
j=1
f ( λjxj) ≤ λjf (xj) (bất đẳng thức Jensen).
Hàm f được gọi là một hàm lõm trên C, nếu −f lồi trên C.
Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều
trường hợp.
Mệnh đề 1.3 Một hàm f : C → R là lồi trên C khi và chỉ khi
∀x, y ∈ C, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1]
=⇒ f (λx + (1 − λ)y) ≤ λα + (1 − λ)β).
(cid:48)
(cid:48)
Chứng minh Chứng minh điều kiện cần. Giả sử f lồi. Chọn x, y, α, β như đã nêu trong mệnh đề. Chọn α(cid:48) ∈ (f (x), α) và β (cid:48) ∈ (f (y), β). Vậy (x, α(cid:48)) và (y, β (cid:48)) thuộc epif . Do epif lồi, nên;
((1 − λ)x + λy), (1 − λ)α + λβ ) ∈ epif.
(cid:48)
(cid:48)
Do đó
f ((1 − λ)x + λy) ≤ (1 − λ)α + λβ < (1 − λ)α + λβ.
12
Chứng minh điều kiện đủ. Chọn (x, µ) và (y, ν) thuộc epif và λ ∈ (0, 1).
Thế thì với mọi ε > 0, ta có
f (x) < µ + ε, f (y) << ν + ε.
(cid:48)
(cid:48)
Do đó
f [(1 − λ)α + λβ ] < (1 − λ)(µ + ε) + λ(ν + ε) = (1 − λ)µ + λν + ε.
(cid:48)
(cid:48)
Điều này đúng với mọi ε > 0, nên cho ε → 0, ta được
f [(1 − λ)α + λβ ] ≤ (1 − λ)µ + λν.
Chứng tỏ
(1 − λ)(x, µ) + λ(y, ν) ∈ epif.
Vậy f lồi.
(cid:3)
Dưới đây là một định nghĩa khác, tương đương về hàm lồi, lồi mạnh
dựa vào khái niệm hệ số lồi,
Định nghĩa 1.10 Cho f : Rn → R ∪ {+∞} (không nhất thiết lồi), C ⊆ Rn là một tập lồi khác rỗng và η là một số thực. Ta nói η là hệ số
lồi của f trên C, nếu với mọi λ ∈ (0, 1), mọi x, y thuộc C, ta có
ηλ(1 − λ)||x − y||2. f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y) − 1 2
Hiển nhiên nếu η = 0 thì f lồi trên C. Nếu f có hệ số lồi trên C là
η > 0, thì f lồi mạnh trên C với hệ số η.
Một hàm f được gọi là chính thường nếu domf (cid:54)= (cid:11) và f (x) > −∞ với mọi x. Hàm f được gọi là đóng, nếu epif là một tập đóng trong Rn+1.
Như đã nói ở trên, nếu f là một hàm lồi trên tập một tập lồi C, thì có
thể thác triển f lên toàn không gian bằng cách đặt
(cid:40) f (x), nếu x ∈ C, fe(x) := +∞, nếu x /∈ C.
13
Hiển nhiên fe(x) = f (x) với ∀x ∈ C và fe lồi trên Rn. Hơn nữa fe là chính thường khi và chỉ khi f chính thường. Tương tự fe đóng khi và chỉ khi f đóng.
Chú ý rằng, nếu f là một hàm lồi trên Rn thì domf là một tập lồi, vì
domf chính là hình chiếu trên Rn của epif , tức là:
domf = {x|∃µ ∈ R : (x, µ) ∈ epif }.
Sau đây là một số ví dụ về hàm lồi.
Ví dụ 1.1 1. Hàm aphin. f (x) := aT x + α, trong đó a ∈ Rn, α ∈ R.
Dễ dàng kiểm tra được rằng f là một hàm vừa lồi vừa lõm trên toàn
không gian. Khi α = 0, thì hàm này được gọi là hàm tuyến tính.
Cho C (cid:54)= (cid:11) là một tập lồi.
2. Hàm chỉ. Đặt
(cid:40) 0, nếu x ∈ C, δC(x) := +∞, nếu x /∈ C.
Ta nói δC là hàm chỉ của C. Do C lồi nên δC là một hàm lồi.
3. Hàm mặt cầu. Cho S := {x ∈ Rn| ||x|| = 1} là một mặt cầu và
h : S → R+ là một hàm bất kỳ. Định nghĩa hàm f như sau:
0, nếu ||x|| < 1,
f (x) := h(x), nếu ||x|| = 1,
+∞, nếu ||x|| > 1.
Hàm này được gọi là hàm mặt cầu. Dễ thấy rằng f là một hàm lồi trên Rn, mặc dù h là một hàm không âm bất kỳ trên mặt cầu S.
4. Hàm tựa. Hàm dưới đây được gọi là hàm tựa của C.
(cid:104)y, x(cid:105) . SC(y) := sup x∈C
14
5. Hàm khoảng cách. Cho C lồi đóng, hàm khoảng cách đến tập C được
định nghĩa bởi
||x − y||. dC(x) := min y∈C
6. Hàm chuẩn. Giả sử x = (x1, ..., xn).
j
f (x) := ||x||1 := max |xj|
1
2 .
hoặc
1 + ... + x2 n)
f (x) := ||x|| := (x2
Định nghĩa 1.11 Cho f : Rn → R ∪ {+∞} và một điểm x0 ∈ Rn sao cho f (x0) < +∞. Nếu với một vectơ y ∈ Rn mà giới hạn
lim λ↓0 f (x0 + λy) − f (x0) λ
tồn tại (hữu hạn hay vô hạn), thì ta nói f có đạo hàm theo hướng y tại điểm x0.
Ta sẽ ký hiệu giới hạn này là f (cid:48)(x0, y). Ví dụ sau đây cho thấy hàm f (cid:48)(x, .) có thể không phải là hàm chính
thường mặc dù f là hàm chính thường và x ∈ domf . Cho
0, nếu x < 0,
f (x) := 1, nếu x = 0,
+∞, nếu x > 0.
Ta thấy f là hàm lồi, chính thường, domf = (−∞, 0). Dễ thấy rằng f (cid:48)(0, −1) = −∞, f (cid:48)(0, 0) = 0, f (cid:48)(0, 1) = +∞.
(cid:48)
Từ định nghĩa của hàm ξ ở trên, ta có
. f ξ(λ) − ξ(0) λ
(x0, y) = lim λ↓0 Vậy f (cid:48)(x0, y) chính là đạo hàm phải của ξ tại 0 nếu f (cid:48)(x0, y) hữu hạn.
Ta nhắc lại rằng một hàm f là thuần nhất dương (bậc 1), nếu
f (tx) = tf (x) với mọi t > 0 và mọi x trên miền xác định của f . Hàm f
15
được gọi là dưới cộng tính, nếu f (x + y) ≤ f (x) + f (y) với mọi x, y trên
miền xác định của f . Hàm dưới tuyến tính là một hàm vừa thuần nhất
dương, vừa dưới cộng tính.
Đặt
. ϕ(λ) := f (x + λy) − f (x) λ
Mệnh đề 1.4 Cho f : Rn → R ∪ {+∞} lồi. Khi đó với mọi x ∈ domf và mọi y ∈ Rn, ta có.
(i) ϕ là hàm đơn điệu không giảm trên (0, +∞); f (cid:48)(x, y) tồn tại với
(cid:48)
mọi y ∈ Rn và
f . (x, y) := inf λ>0 f (x + λy) − f (x) λ
(ii) Hàm f (cid:48)(x, .) thuần nhất dương bậc 1. Ngoài ra nếu f (cid:48)(x, .) > −∞
thì:
a) Hàm f (cid:48)(x, .) là dưới tuyến tính trên Rn (do đó nó là hàm lồi
chính thường trên Rn ).
b)−f (cid:48)(x, −y) ≤ f (cid:48)(x, y) ∀y ∈ Rn. c) Hàm f (cid:48)(x, .) nhận giá trị hữu hạn trên F khi và chỉ khi
x ∈ ri(domf ), trong đó F là không gian con của domf.
Chứng minh (i) Ta chứng minh hàm ϕ đơn điệu không giảm trên miền (0, +∞). Cho x ∈ domf và định nghĩa hàm h : R → R ∪ {+∞} bởi
h(λ) := f (x + λy) − f (x).
Khi đó h(0) = 0.
Giả sử 0 < λ(cid:48) ≤ λ. Khi đó, do h là hàm lồi không nhận giá trị −∞,
(cid:48)
nên ta có
h(λ ) = h( λ + (1 − )0) λ(cid:48) λ λ(cid:48) λ
h(λ) + (1 − )h(0) ≤ h(λ) ≤ λ(cid:48) λ λ(cid:48) λ λ(cid:48) λ
16
Do
ϕ(λ) := = . h(λ) λ
f (x + λy) − f (x) λ nên ϕ(λ(cid:48)) ≤ ϕ(λ). Vậy ϕ là hàm không giảm trên miền (0, +∞). Suy ra f (cid:48)(x, y) = limλ↓0 ϕ(λ) tồn tại và
ϕ(λ). lim λ↓0 ϕ(λ) = inf λ>0
(cid:48)
(ii) Theo định nghĩa, hiển nhiên ta có f (cid:48)(x, 0) = 0. Giả sử hàm f (cid:48)(x, .) > −∞. Để chứng tỏ tính thuần nhất dương, với t > 0, ta viết
f (x, ty) = lim λ↓0 f (x + λty) − f (x) λ
(cid:48)
(cid:48)
Đặt λ(cid:48) = λt, ta có tiếp
= tf (x, y). f f (x + λ(cid:48)y) − f (x) λ(cid:48) (x, ty) = t lim λ(cid:48) ↓0
Vậy f (cid:48)(x, .) thuần nhất dương.
(cid:48)
Ta chỉ ra tính chất dưới cộng tính. Với mọi u và v, ta có
2 (u + v)) − f (x)
f (x + λ f (x, u + v) = lim λ↓0
2 + λ
2 u + x
2 + λ
2f (x)
2 v) − 1 λ/2
f ( x λ/2 2f (x) − 1 . = lim λ↓0
Do f là hàm lồi không nhận giá trị −∞, nên
f ( + u + + v) − f (x) − f (x) x 2 λ 2 x 2 λ 2 1 2 1 2
≤ [f (x + λu) − f (x)] + [f (x + λv) − f (x)]. 1 2 1 2
(cid:48)
Do đó
(cid:48)
(cid:48)
f (x, u + v) ≤ lim λ↓0 f (x + λu) − f (x) λ f (x + λv) − f (x) λ + lim λ(cid:48) ↓0
= f (x, u) + f (x, v).
(Chú ý f (cid:48)(x, u)+f (cid:48)(x, v) có nghĩa vì f (cid:48)(x, .) > −∞). Vậy f (cid:48)(x, .) dưới cộng tính. Kết hợp lại ta có f (cid:48)(x, .) là dưới tuyến tính trên Rn. Vì f (cid:48)(x, .) > −∞,
17
f (cid:48)(x, 0) = 0 và f (cid:48)(x, .) là dưới tuyến tính trên Rn, nên nó là hàm lồi, chính
thường trên toàn không gian.
(cid:48)
(cid:48)
(cid:48)
(cid:48)
b) Do f (cid:48)(x, 0) = 0 và theo tính chất dưới cộng tính, ta có
0 = f (x, 0) = f (x, y − y) ≤ f (x, y) + f (x, −y) ∀y.
Từ đây suy ra b).
c) Giả sử x ∈ ri(domf ). Ta cần chứng tỏ f (x, .) hữu hạn trên F . Theo giả thiết, f (cid:48)(x, .) > −∞. Vậy chỉ cần chỉ ra f (cid:48)(x, y) < +∞ với mọi y ∈ F .
Do x ∈ri(domf ), nên với mọi y ∈ F có x + λy ∈ domf với mọi λ > 0 đủ
(cid:48)
nhỏ. Do đó
< +∞. f (x, y) = inf λ>0 f (x + λy) − f (x) λ
Ngược lại giả sử f (cid:48)(x, y) hữu hạn với mọi y ∈ F . Ta cần chứng tỏ
x ∈ri(domf ). Thật vậy, nếu trái lại sẽ tồn tại y ∈ F và một dãy {λk} các số dương hội tụ đến 0 và x + λky /∈ domf với mọi k đủ lớn. Do đó f (cid:48)(x, y) = +∞. Mâu thuẫn với giả thiết.
Vậy x ∈ ri(domf ).
(cid:3)
Định nghĩa 1.12 Cho f : Rn → R ∪ {+∞}. Ta nói x∗ ∈ Rn là dưới đạo
hàm của f tại x nếu
(cid:104)x∗, z − x(cid:105) + f (x) ≤ f (z) ∀z.
Ví dụ 1.2 1. f (x) = ||x||, x ∈ Rn. Tại điểm x = 0 hàm này không khả
vi, nhưng nó khả dưới vi phân và
δf (0) = {x∗| (cid:104)x∗, x(cid:105) ≤ ||x|| ∀x} .
2. f = δC là hàm chỉ của một tập lồi C (cid:54)= (cid:11). Khi đó với x0 ∈ C,
∂δC(x0) = {x∗| (cid:10)x∗, x − x0(cid:11) ≤ δC(x) ∀x}.
18
Với x /∈ C, thì δC(x) = +∞, nên bất đẳng thức này luôn đúng. Vậy ∂δC(x0) = {x∗| (cid:10)x∗, x − x0(cid:11) ≤ 0 ∀x ∈ C} = NC(x0).
Vậy dưới vi phân của hàm chỉ của một tập lồi C khác rỗng tại một điểm x0 ∈ C chính là nón pháp tuyến ngoài của C tại x0.
Mệnh đề 1.5 Cho f : Rn → R ∪ {+∞} lồi, chính thường.
(i) x∗ ∈ ∂f (x) khi và chỉ khi f (cid:48)(x, y) ≥ (cid:104)x∗, y(cid:105) ∀y. Nếu ∀x ∈ ri(domf ),
thì f (cid:48)(x, y) = supx∗∈∂f (x) (cid:104)x∗, y(cid:105) với mọi y.
(ii) Nếu f là hàm lồi chính thường trên Rn thì với mọi x ∈ dom(∂f ),
ta có f (x) = f (x), và ∂f (x) = ∂f (x).
Chứng minh (i) Theo định nghĩa
x∗ ∈ ∂f (x) ⇐⇒ (cid:104)x∗, z − x(cid:105) + f (x) ≤ f (z) ∀z.
Với bất kỳ y, lấy z = x + λy, λ > 0, ta có
(cid:104)x∗, λy(cid:105) + f (x) ≤ f (x + λy).
Từ đây suy ra
∀λ > 0. (cid:104)x∗, y(cid:105) ≤ f (x + λy) − f (x) λ
(cid:48)
Theo định nghĩa f (cid:48)(x, y), từ đây suy ra ngay
(cid:104)x∗, y(cid:105) ≤ f (x, y) ∀y. (1.1)
Ngược lại giả sử, bất đẳng thức trên thỏa mãn. Lấy z bất kỳ và áp dụng
(cid:48)
(cid:48)
(1.1) với y = z − x và λ = 1. ta có
f (x + y) − f (x) ≥ f (x, y) = f (x, z − x) ≥ (cid:104)x∗, z − x(cid:105) ∀z.
(cid:48)
Vậy x∗ ∈ ∂f (x). Chú ý rằng do f (cid:48)(x, .) là hàm lồi, thuần nhất dương, nên mọi hàm non a-phin của f (cid:48)(x, .) đều tuyến tính, tức là có dạng (cid:104)p, .(cid:105). Vậy nếu (cid:104)p, .(cid:105) là hàm non a-phin của f (cid:48)(x, .) trên Rn thì
(x, y) ∀y. (cid:104)p, y(cid:105) ≤ f
19
Theo Mệnh đề 1.5 ta có p ∈ ∂f (x). Hơn nữa do f (cid:48)(x, .) là một hàm lồi
đóng, nên theo định lý xấp xỉ tập lồi nó là bao trên của các hàm non của
(cid:48)
nó. Vậy
p∈∂f (x)
f (x, y) = sup (cid:104)p, y(cid:105) .
(ii) Cho x ∈ dom(∂f ) và x∗ ∈ ∂f (x). Theo định nghĩa của f , của hàm
liên hợp và do x∗ ∈ ∂f (x) ta có:
f (x) ≥ f (x) = f ∗∗(x) ≥ (cid:104)x∗, x(cid:105) − f ∗(x∗) = f (x).
Từ đây suy ra f (x) = f (x). Nếu y∗ ∈ ∂f (x), thì với mọi z có:
f (z) ≥ f (z) ≥ f (x) + (cid:104)y∗, z − x(cid:105) = f (x) + (cid:104)y∗, z − x(cid:105) .
Suy ra ∂f (x) ⊆ ∂f (x). Để chứng minh điều ngược lại, lấy z0 ∈ ri(dom)f . Với mọi z ta có
f (cid:2)(1 − t)z + tz0(cid:3) . f (z) = lim t(cid:38)0
Vậy, theo định nghĩa của dưới vi phân ta có:
f (cid:2)(1 − t)z + tz0(cid:3) ≥ f (x) + (cid:10)x∗, (1 − t)z + tz0 − x(cid:11) .
Cho t (cid:38) 0 ta được:
f (x) ≥ f (x) + (cid:104)x∗, z − x(cid:105) = f (x) + (cid:104)x∗, z − x(cid:105) .
Chứng tỏ x∗ ∈ ∂f (x).
1.2. Các bổ đề hỗ trợ
(cid:3)
Các bổ đề này sẽ được sử dụng để chứng minh tính hợp lệ và sự hội tụ
của thuật toán được xét phần sau.
20
Bổ đề 1.1 Cho x, y, z ∈ H và 0 ≤ a ≤ 1, ta có
||ax + (1 − a)y − z||2 ≤ a||x − z||2 + (1 − a)||y − z||2
Chứng minh
||ax + (1 − a)y − z||2
= a2||x − z||2 + (1 − a)2||y − z||2 + 2a(1 − a) (cid:104)x − z, y − z(cid:105)
= a||x − z||2 + (1 − a)||y − z||2
− a(1 − a) (cid:2)||x − z||2 + ||y − z||2 − 2 (cid:104)x − z, y − z(cid:105)(cid:3)
≤ a||x − z||2 + (1 − a)||y − z||2.
Bổ đề 1.2 Cho C là tập con lồi đóng khác rỗng trong không gian Hilbert
H và PC là phép chiếu của x lên C. Khi đó
k=1 <
(i) (cid:104)x − y, PC(x) − PC(y)(cid:105) ≥ ||PC(x) − PC(y)||2 ∀ x, y ∈ H. (ii) (cid:104)x − PC(x), PC(x) − y(cid:105) ≥ 0 ∀x ∈ H, y ∈ C.
Bổ đề 1.3 Cho {vk} và {δk} là dãy không âm vk+1 ≤ vk + δk với (cid:80)∞ δk + ∞. Khi đó dãy {vk} hội tụ.
Bổ đề 1.4 (xem Anh và Muu 2014). Cho H là không gian Hilbert thực,
{ak} là dãy các số thực có tính chất 0 < a < ak < b < 1 với k = 1, 2, ..., và {vk}, {wk} là hai dãy thuộc H sao cho
(cid:107)wk(cid:107) ≤ c, lim sup k→+∞ (cid:107)vk(cid:107) ≤ c, lim sup k→+∞
và
(cid:107)akvk + (1 − ak)wk(cid:107) = c, với mỗi c >0 lim k→+∞
Khi đó, limk→+∞ (cid:107)vk − wk(cid:107) = 0.
21
Chương 2
Một tiếp cận cân bằng tách cho
mô hình Nash-Cournot với một
ràng buộc chung
Trong chương này trước tiên chúng ta giới thiệu bài toán chấp nhận
lồi tách, tiếp theo giới thiệu mô hình Nash–Cournot, cuối cùng là trình
bày một thuật toán giải bài mô hình Nash–Cournot có ràng buộc chung
theo tiếp cận cân bằng tách. Các kết quả chương này được tổng hợp từ
2.1. Bài toán chấp nhận lồi tách
tài liệu tham khảo [2], [4].
Cho K là một tập lồi đóng thuộc không gian Euclid n chiều. Cho f : K ∗ K → R là một song hàm thỏa mãn điều kiện f (x, x) = 0 với mọi
x ∈ K. Ta xét bài toán cân bằng sau gọi là bài toán EP,
Tìm x ∈ K sao cho f (x, y) ≥ 0, ∀y ∈ K (EP)
Kí hiệu Sol(EP) là tập nghiệm của bài toán này.
Bất đẳng thức này lần đầu tiên được Nikaido và Isoda nghiên cứu năm
1995 trong trò chơi không hợp tác. Sau công trình nghiên cứu của Blum
22
và Oettli (1994), bài toán (EP) được rất nhiều người quan tâm.
Một điểm lý thú của bài toán (EP) là mặc dù có hình thức rất đơn
giản nhưng chứa rất nhiều bài toán quan trọng của toán học như bài toán
tối ưu, bất đẳng thức biến phân, điểm bất động Kakutami và bài toán
cân bằng Nash như là các trường hợp riêng. (xem tài liệu tham khảo Bigi
2013)(tài liệu 1).
Nhiều phương pháp giải bài toán (EP) đã được đề xuất, trong số đó
phương pháp chiếu được dùng nhiều hơn cả.
Bài toán chấp nhận tách trong không gian Hilbert hữu hạn chiều lần
đầu tiên được Censor và Elving (1994) đề xuất và chỉ ra nhiều ứng dụng
quan trọng của bài toán này như trị xạ ung thư, lưu trữ dữ liệu v.v...Một
số thuật toán đã được đề xuất để giải bài toán chấp nhận tách. Về mặt
toán học, bài toán chấp nhận tách được phát biểu như sau (xem [2]).
Tìm x∗ ∈ C sao cho Ax∗ ∈ Q. (SF)
trong đó C là một tập lồi đóng trong không gian H1. A là toán tử tuyến tính từ H1 vào không gian Euclid hữu hạn chiều H2. Gần đây bài toán này với C và Q là tập nghiệm của bài toán khác nhau như bài toán bất
đẳng thức biến phân, bài toán cân bằng, bài toán điểm bất động đã được
nhiều người quan tâm nghiên cứu.
Trong luận văn này, tôi xin trình bày một phương pháp giải bài toán
chấp nhận tách với C là tập nghiệm của bài toán cân bằng và Q là tập
nghiệm của bài toán quy hoạch lồi. Bài toán được phát biểu như sau
2.2. Một thuật toán giải mô hình Nash–Cournot có ràng buộc
chung
Tìm x∗ ∈ K : f (x, y) ≥ 0 ∀y ∈ K và g(Ax∗) ≤ g(u) ∀u ∈ H2, (SEO)
Chúng ta sẽ dùng các giả thiết sau cho thuật toán và sự hội tụ của nó
sẽ được trình bày dưới đây.
23
Giả thiết:
(A1) Với mỗi x∈ K và f (x, x) = 0 và f (x, .) là lồi nửa liên tục dưới
trên K.
(A2) ∂(cid:15)
2f (x, x) khác rỗng với mọi (cid:15) > 0 và x ∈ K và bị chặn trên mỗi 2f (x, x) kí hiệu là (cid:15)− dưới vi phân của
tập con bị chặn của C, trong đó ∂(cid:15)
hàm lồi f (x, .) có nghĩa là
∂(cid:15) 2f (x, x) := {g ∈ H| (cid:104)g, y − x(cid:105) + f (x, x) ≤ f (x, y) + (cid:15) ∀y} .
(A3) f là giả đơn điệu trên K theo mọi lời giải của bài toán (EP ), nghĩa là f (x, x∗) ≤ 0 với ∀x ∈ K, x∗ ∈ Sol(EP ), hơn nữa thỏa mãn điều
kiện tiền đơn điệu.
x∗ ∈ Sol(EP ), y ∈ K, f (x∗, y) = f (y, x∗) = 0 ⇒ y ∈ Sol(EP ).
(A4) Với mọi x ∈ K, f (., x) là nửa liên tục trên K.
Nhắc lại rằng toán tử gần kề của hàm g với tham số λ > 0 được định
nghĩa bởi
(P(u)) ||v − u||2 : v ∈ H2} proxλg(u) := argmin{g(v) + 1 λ
2(cid:107)(I − proxλgAx(cid:107)2. Khi đó theo điều kiện cần và đủ tối ưu ta có h(x) = 0 khi và chỉ khi Ax là lời giải của bài toán này. Hơn nữa đạo hàm của h(x) là ∇h(x) = A∗(I − proxλg)Ax. Do đó h(x) = 0 khi và chỉ khi ∇h(x) = 0.
Với λ > 0 cố định, ta đặt h(x) := 1
24
2.2.1. Thuật toán
Chọn các tham số dương δ, ξ và các dãy có {ak} , {δk} , {βk} , {(cid:15)k} , {ρk}
thỏa mãn điều kiện
(2.1)
(2.2) 0 < a < ak < b < 1, 0 < ξ ≤ ρk ≤ 4 − ξ, ∀k ∈ N; δk > δ > 0, βk > 0, (cid:15)k ≥ 0, ∀k ∈ N;
∞ (cid:88)
; (2.3) ak = lim k→+∞
k<+∞; β2
=+∞,
βk δk
k=1
k=1 ∞ (cid:88)
1 2 ∞ (cid:88) (2.4)
<+∞;
βk(cid:15)k δk
k=1
(2.5)
Bước 0: Chọn x1 ∈ K và để k := 1.
2 f (xk, xk) và lấy
Bước k: Đã có xk ∈ K Tính gk ∈ ∂(cid:15)k
αk = trong đó γk = max {δk, ||gk||} . βk γk
Tính yk = PK(xk − αkgk), tức là
(cid:104)yk − xk + αkgk, x − yk(cid:105) ≥ 0, ∀x ∈ K.
Lấy
h(yk) (cid:107)∇h(yk(cid:107)2
nếu ∇h(yk) = 0, 0 (2.6) µk := nếu ∇h(yk) (cid:54)= 0. ρk
Tính
zk = PK(yk − µkA∗(I − proxλg)(Ayk))
Đặt
xk+1 = akxk + (1 − ak)zk.
25
Chú ý nếu chọn (cid:15)k = 0 thì xk = yk và h(xk) = 0 kéo theo xk là nghiệm của bài toán. Do vậy ta gọi xk là ε -nghiệm nếu (cid:15)k ≤ (cid:15) và ||xk − yk|| ≤ (cid:15), |h(xk)| ≤ (cid:15).
Để chứng minh tính đúng đắn và sự hội tụ của thuật toán, chúng ta sẽ
cần đến các bổ đề sau:
Bổ đề 2.1 (Moudafi and Thakur 2014) Cho S là tập nghiệm của bài toán
(SEO) và z ∈ S. Nếu đạo hàm của h tại yk khác 0 thì ta có
(2.7) ||zk − z||2 ≤ ||yk − z||2 − ρk(4 − ρk) h2(yk) (cid:107)∇h(yk(cid:107)2
Bổ đề 2.2 (Santos and Scheimberg 2011) Với mọi k thì các bất đẳng thức
sau thỏa mãn
(i) αk||gk|| ≤ βk; (ii) ||yk − xk ≤ βk.
Bổ đề 2.3 (xem [4]) Cho z ∈ S. Khi đó với mọi k sao cho ∇h(yk) (cid:54)= 0, ta có
||xk+1 − z||2 ≤ ||xk − z||2 − (1 − ak)ρk(4 − ρk)
(9) h2(yk) (cid:107)∇h(yk(cid:107)2 +2(1 − ak)αkf (xk, z) + Ak,
và với mọi k sao cho ∇h(yk) (cid:54)= 0, ta có
(10) ||xk+1 − z||2 ≤ ||xk − z||2 + 2(1 − ak)αkf (xk, z) + Ak,
k).
Trong đó Ak = 2(1 − ak)(αk(cid:15)k + β2
Định lí 2.1 Giả sử bài toán (SEO) có nghiệm. Khi đó dưới các giả thiết
(A1)–(A4) thì dãy xk tạo nên bởi thuật toán hội tụ tới một nghiệm của bài toán (SEO).
26
Ta sẽ sử dụng các bổ đề trong Mục 2.2 để chứng minh sự hội tụ của
thuật toán.
Chứng minh. Từ định nghĩa của xk+1, theo Bổ đề 1.1 ta có
||xk+1 − z||2 = ||akxk − (1 − ak)zk − z||2
(11) ≤ ak||xk − z||2 + (1 − ak)||zk − z||2.
Xét hai trường hợp sau:
Trường hợp 1: Nếu ∇h(yk (cid:54)= 0, theo Bổ đề 2.1, ta có
(cid:21) . ||xk+1 − z||2 ≤ ak||xk − z||2 + (1 − ak) (cid:20) ||yk − z||2 − ρk(4 − ρk)
h2(yk) (cid:107)∇h(yk)(cid:107)2 (2.8)
Hơn nữa
||yk − z||2 = ||z − xk + xk − yk||2
= ||xk − z||2 − ||xk − yk||2 + 2 (cid:104).xk − yk, z − yk(cid:105) ≤ ||xk − z||2 + 2 (cid:104)xk − yk, z − yk(cid:105) .
Trong thuật toán trên, từ cách xác định yk ta được
(cid:104)yk − xk + αkgk, x − yk(cid:105) ≥ 0, ∀x ∈ K.
Bằng cách lấy x = z, ta có
(cid:104)yk − xk + αkgk, z − yk(cid:105) ≥ 0
⇔ (cid:104)αkgk, z − yk(cid:105) ≥ (cid:104)xk − yk, z − yk(cid:105) .
Vậy
||yk − z||2 ≤ ||xk − z||2 + 2 (cid:104)αkgk, z − yk(cid:105)
(2.9) ||xk − z||2 + 2 (cid:104)αkgk, z − xk(cid:105) + 2 (cid:104)αkgk, xk − yk(cid:105)
2 f (xk, xk) ta có
Từ điều kiện gk ∈ ∂(cid:15)k
f (xk, z) − f (xk, xk) ≥ (cid:104)gk, z − xk(cid:105) − (cid:15)k
(2.10) ⇔ f (xk, z) + (cid:15)k ≥ (cid:104)gk, z − xk(cid:105) .
27
Mặt khác theo Bổ đề 2.2(ii), ta lại có
(cid:104)αkgk, xk − yk(cid:105) ≤ αk||gk|| ||xk − yk|| ≤ β2 k.
Từ (2.9), (2.10) và αk > 0 ta có
(2.11) ||yk − z||2 ≤ ||xk − z||2 + 2αkf (xk, z) + 2αk(cid:15)k + 2β2 k.
Kết hợp bất đẳng thức (2.11) cùng với (2.8) ta thu được
h2(yk) ||xk+1−z||2 ≤ ||xk−z||2+2(1−ak)αkf (xk, z)−(1−ak)ρk(4−ρk) ||∇h(yk)||2 +Ak,
k).
Trong đó Ak = 2(1 − ak)(αk(cid:15)k + β2
Trường hợp 2: Nếu ∇h(yk) = 0 thì theo cách xác định xk+1, ta có
thể viết
||xk+1 − z||2 ≤ ak||xk − z||2 + (1 − ak)||yk − z||2.
Bây giờ, bằng cách suy luận như Trường hợp 1 ta có
||yk − z||2 ≤ ||xk − z||2 + 2αkf (xk, z) + 2αk(cid:15)k + 2β2 k.
Vậy
||xk+1 − z||2 ≤ ||xk − z||2 + 2(1 − ak)αkf (xk, z) + Ak,
trong đó Ak = 2(1 − ak)(αk(cid:15)k + 2β2 k). Chứng minh khẳng định 1: ||xk − z||2 là hội tụ với mọi z ∈ S. Thật vậy, đặt z ∈ S. Từ z ∈ Sol(EP ) và f là giả đơn điệu trên K với tập nghiệm
của (EP ), ta có
f (xk, z) ≤ 0.
Nếu ∇h(yk) (cid:54)= 0, thì do
h2(yk) ρk(4 − ρk) ||∇h(yk)||2 ≥ 0,
Theo Bổ đề 2.3 ta có
(16) ||xk+1 − z||2 ≤ ||xk − z||2 + Ak,
28
k). Vì αk = βk γk
với γk = max {δk, ||gk||},
+∞ (cid:88)
+∞ (cid:88)
+∞ (cid:88)
Trong đó Ak = 2(1 − ak)(αk(cid:15)k + β2 nên
k=1
k=1
k=1
αk(cid:15)k = (cid:15)k ≤ (cid:15)k < +∞. βk γk βk δk
k < +∞ và 0 < a < ak < b < 1, ta được
k=1 β2
+∞ (cid:88)
+∞ (cid:88)
Chú ý (cid:80)+∞
k < +∞.
k=1
k=1
Ak < 2(1 − a) αk(cid:15)k + β2
Bây giờ, dùng Bổ đề 1.3, ta thấy rằng dãy ||xk − z||2 hội tụ với mọi z ∈ S. Vậy, xk bị chặn. Do đó, theo Bổ đề 2.2, ta thấy dãy {yk} cũng bị chặn. Khẳng định 2: lim supk→+∞f (xk, z) = 0 với mọi z ∈ S. Theo Bổ đề 2.3, với mọi k, ta có
(2.12) −2(1 − ak)αkf (xk, z) ≤ ||xk − z||2 − ||xk+1 − z||2 + Ak.
+∞ (cid:88)
Lấy tổng từ 1 đến vô cùng ta được
k=1
(2.13) −2(1 − ak)αkf (xk, z) ≤ +∞.
Mặt khác dùng giả thiết (A2) và tính bị chặn của dãy xk, ta thấy rằng dãy {||gk||} cũng bị chặn. Do đó, tồn tại một số L > δ thỏa mãn chuẩn ||gk|| ≤ L với mọi k.
(cid:27) (cid:26) = max 1, ≤ L δ γk δk ||gk|| δk
Suy ra
≥ . αk = δ L βk γk βk δk
∞ (cid:88)
Do z là nghiệm và f là giả đơn điệu nên ta có −f (xk, z) ≥ 0 điều này cùng với 0 < a < ak < b < 1 kéo theo
k=1
(1 − b) [−f (xk, z)] < +∞. βk δk
29
βk δk
= +∞ ta lại có Nhưng từ (cid:80)∞ k=1
f (xk, z) = 0, ∀z ∈ S. lim sup k→+∞
Khẳng định 3: Với bất kì z ∈ S, giả sử rằng {xkj} là một dãy con của dãy {xk} sao cho
(2.14) f (xkj, z), f (xk, z) = lim j→+∞ lim sup k→+∞
và giả sử x∗ là một điểm hội tụ của xk. Khi đó x∗ là nghiệm của bài toán (EP ).
Không làm mất tính tổng quát, chúng ta giả sử xkj hội tụ tới x∗ khi
j → ∞. Do f (., z) là nửa liên tục nên theo Khẳng định 2 ta được
f (xkj, z) = 0. f (x∗, z) ≥ lim sup j→+∞
Từ z ∈ S và f là giả đơn điệu, ta có f (x∗, z) ≤ 0. Do đó f (x∗, z) = 0. Nên f (x∗, z) ≤ 0 cũng là giả đơn điệu. Vì vậy f (x∗, z) = f (z, x∗) = 0. Theo điều kiện tiền đơn điệu (giả thiết (A3)), ta thấy rằng x∗ là nghiệm
của bài toán (EP ).
k=1 β2
Khẳng định 4: Mọi điểm tụ ¯x của dãy {xk} thỏa mãn ¯x ∈ K và A¯x ∈ argmin g. Đặt ¯x là điểm tụ của dãy {xk} và {xkj} là dãy con của {xk} hội tụ tại k < +∞.
¯x. Vậy ¯x ∈ K. Mặt khác, ta biết rằng ||yk − xk|| ≤ βk và (cid:80)+∞ Suy ra,
||yk − xk|| = 0. lim k→+∞
Do đó, {yk} cũng hội tụ đến ¯x.
Từ Bổ đề 2.3, nếu ∇h(yk) (cid:54)= 0 thì
(1 − ak)ρk(4 − ρk) h2(yk) (cid:107)∇h(yk(cid:107)2 ≤ ||xk − z||2 − ||xk+1 − z||2 + Ak,
và nếu ∇h(yk) = 0 thì
0 ≤ ||xk − z||2 − ||xk+1 − z||2 + Ak.
30
∞ (cid:88)
Đặt N1 := {k : ∇h(yk (cid:54)= 0} và lấy tổng ta có
k=1
k∈N1
(cid:88) Ak < +∞. (1 − ak)ρk(4 − ρk) h2(yk) (cid:107)∇h(yk(cid:107)2 ≤ ||x0 − z||2 +
k∈N1
(cid:88) (20) Kết hợp điều này với giả thiết ξ ≤ ρk ≤ 4 − ξ (với mỗi ξ > 0) và 0 < a < ak < b < 1, ta có khẳng định h2(yk) (cid:107)∇h(yk(cid:107)2 ≤ +∞.
Hơn nữa, do ∇h là liên tục Lipschitz với hằng số ||A||2, ta thấy rằng ||∇h(yk)||2 là bị chặn. Vậy h(yk) −→ 0 khi k ∈ N1 và k −→ ∞. Lưu ý rằng h(yk) = 0 với k /∈ N1. Ta được
(21) h(yk) = 0. lim k→+∞
Theo tính nửa liên tục và tính dương của h ta có
(22) h(yk) = 0. 0 ≤ h(¯x) ≤ lim inf j→+∞ h(ykj) = lim k→+∞
Do đó kéo theo A¯x là điểm bất động của toán tử gần kề của g. Vậy, A¯x
là điểm cực tiểu của g. Định lý được chứng minh.
(cid:3)
Nhận xét 2.1 Ví dụ sau chứng tỏ rằng khi bài toán không có nghiệm
thì dãy {xk} có thể không bị chặn.
(cid:27) Lấy H1 = H2 = R2, A là một toán tử đồng nhất; (cid:26) ; K = x = (u, v) ∈ R|2 u ≥ 1, v ≥ 1 u
Q = (cid:8)x = (u, v) ∈ R2| u ≥ 1, v ≥ v = 0(cid:9) ;
f (x, y) = iK(y) − iK(x), và g(x) = iQ(x),
iK và iQ là các hàm chỉ của tập K và Q. Tức là
(cid:40) 0 nếu x ∈ K IK(x) = +∞ nếu x /∈ K
31
Rõ ràng trong trường hợp này thì bài toán trở thành việc tìm một điểm
trong tập S := K ∩ Q. Theo thuật toán, nếu ta chọn k ∈ N
. (cid:15)k = 0, βk = , δk = 1, ρk = 2, ak = 1 k 1 2
Do f (x, y) = iK(y)−iK(x), ta có (0, 0) ∈ ∂2f (u, u) với mọi x = (u, u) ∈ K. Vậy, tại mỗi bước lặp k, ta luôn lấy gk = (0, 0) và do đó xk = yk với mọi k. Từ K ∩ Q = ∅, ta có hk(yk) (cid:54)= 0. Lưu ý rằng proxλg(x) = PQ(x) với mọi λ > 0. Một tính toán đơn giản dựa vào yk = xk, chỉ ra rằng
a2
zk = PK(yk − µk(I − proxλg)(yk)) = PK(PQ(xk)).
(cid:48) k
Chọn xk := (uk), vk). Ta thấy rằng limk→+∞ uk = +∞. Thật vậy, theo định nghĩa của Q và K hình chiếu của xk = (uk, vk) trên Q là (uk, 0), trong khi hình chiếu của (uk, 0) trên K nằm trên biên của K. Giả sử rằng (ak, 1 ) là hình chiếu của (uk, 0) trên K. Khi đó ak là lời giải tối ưu của ak (cid:3) là một hàm lồi bài toán mina≥1ϕk(a), trong đó ϕk(a) = (cid:2)(uk − a)2 + 1 mạnh trên [1, +∞). Do uk ≥ 1, Vậy có (cid:18) (cid:19) ϕ < 0 uk +
(23) ak ≥ uk + 1 16 [uk]3 1 16 [uk]3 .
Do zk = PK(uk, 0) = (ak, 1/ak) và xk+1 := (uk+1, vk+1) = 1/2(xk + zk), từ (23), kéo theo
uk+1 ≥ uk + 1 32 [uk]3 .
Do uk ≥ 1 với mọi k, ta có thể khẳng định rằng limk→+∞ uk = +∞.
2.2.2. Một mô hình thực tế
Trong phần này chúng ta xét một mô hình cân bằng và tối ưu dựa trên
mô hình cân bằng Nash - Cournot trong thị trường điện.
32
Giả sử có n công ty sản xuất điện. Công ty thứ i (i = 1, 2, ..., n) có Ii
nhà máy điện.
xj: Tổng lượng điện sản xuất từ Ii nhà máy (lượng điện do (cid:80) j∈Ii
công ty thứ i sản xuất). Giá điện (phụ thuộc vào tổng lượng điện của tất
cả các công ty sản xuất ra)
pi(s) = α − βis
trong đó:
s: tổng lượng điện sản xuất
α > 0: cho trước
β > 0: (nhỏ), hệ số giảm giá
cj(xj). Vậy lợi nhuận của công Chi phí sản xuất cho công ty thứ i là (cid:80) j∈Ii
j∈Ii
j∈Ii
ty thứ i là (cid:88) (cid:88) fi(x) = p(s)( xj) − cj(xj)
(i = 1, 2, ..., n)
Mỗi công ty đều xác định xem mỗi nhà máy của mình cần sản xuất lượng
điện là bao nhiêu để lợi nhuận là cao nhất. Giả sử
Kj = [0, 100] ∀j
xj ∈ Ki (ví dụ Ki = là tập chiến lược của công ty thứ i. Nghĩa là (cid:80) j∈Ii
[10, 1000]). Do lợi nhuận của các công ty phụ thuộc nhau (thậm chí xung
khắc nhau) nên người ta đề xuất việc tìm một phương án cân bằng (tức
là phương án sao cho mọi công ty đều chấp nhận được). Đó là phương án
cân bằng Nash.
Định nghĩa 2.1 Một điểm x∗ ∈ K = K1 × K2 × ... × Kn là một điểm cân bằng của mô hình nếu thỏa mãn:
∀i = 1, 2, ..., n fi(x∗) ≥ fi(x∗ [xi]) ∀xi ∈ Ki,
33
trong đó x∗ [xi] là vec-to nhận được từ x∗ bằng cách thay tọa độ thứ i của vectơ x bằng xi.
Bằng cách lấy
f (x, y) := ϕ(x, y) − ϕ(x, x)
n (cid:88)
với
i=1
ϕ(x, y) := − fi(x [yi])
thì bài toán cân bằng Nash của mô hình có thể được mô tả dưới dạng bài
toán cân bằng (EP)
x∗ ∈ K : f (x∗, x) ≥ 0 ∀x ∈ K (EP)
Khi sản xuất điện người ta phải dùng một số nguyên vật liệu như than,...
(dùng m loại nguyên vật liệu). Kí hiệu al,j là lượng nguyên vật liệu thứ l để sản xuất đơn vị điện ở nhà máy thứ j. Như vậy, Ax là toàn bộ lượng
nguyên vật liệu để sản xuất ra lượng điện là x. Việc dùng nguyên vật liệu
có thể làm ô nhiễm môi trường, do đó phải trả phí môi trường. Gọi g(Ax)
là toàn bộ phí môi trường để sản xuất ra lượng điện x. Bài toán bây giờ
đặt ra phải tìm một điểm cân bằng Nash của mô hình sao cho phí môi
trường sản xuất điện là thấp nhất. Có thể viết dưới dạng toán như sau.
Tìm
x∗ ∈ K :f (x∗, x) ≥ 0 ∀x ∈ K
g(Ax∗) ≤ g(Ax) ∀x ∈ K. (SEP)
(cid:68) Với p(s) = α − βs thì bài toán (SEP) được viết dưới dạng Tìm x∗ ∈ K : f (x∗, x) := + ϕ(x) − ϕ(x∗) ≥ 0 ∀x ∈ K (cid:101)B1x∗ − ¯a, x − x∗(cid:69)
g(Ax∗) ≤ g(Ax) với ∀x ∈ K
34
với ¯a := (α, α, ..., α)T
β1 0 0... 0 0 β2 0... 0 B1 := ... 0 0 0... βn
(cid:101)B1 := 0 β1 β1... β1 0 β2... β2 β2 ... βn βn βn... 0
n (cid:80) j=1
ϕ(x) := xT B1x + Cj(xj). Sau khi biến đổi ta được bài toán
(cid:68) ≥ 0 ∀x ∈ K. Tìm x∗ ∈ K : (cid:101)B1x∗ − ¯a + ∇ϕ(x∗), x − x∗(cid:69)
Ví dụ 2.1 Có hai công ty. Công ty thứ nhất có ba nhà máy, công ty thứ
hai có một nhà máy. Điện của công ty thứ nhất x1, x2, x3. Điện của công ty thứ hai là x4. Khi đó giá điện là
p(x1 + x2 + x3 + x4) = α − 0, 1(x1 + x2 + x3 + x4)
Chi phí công ty thứ nhất: C1(x1), C2(x2), C3(x3). Chi phí công ty thứ
hai: C4(x4). Lợi nhuận của công ty thứ nhất:
f1(x1, x2, x3, x4) = p(x1+x2+x3+x4)(x1+x2+x3)−C1(x1)−C2(x2)−C3(x3)
Lợi nhuận của công ty thứ hai
f2(x1, x2, x3, x4) = p(x1 + x2 + x3 + x4)x4 − C4(x4)
Giả sử khi sản xuất điện, các công ty phải dùng một loại nguyên liệu (ví
dụ: than). Gọi a1,j là lượng than để sản xuất ra một đơn vị điện năng ở nhà
35
máy thứ j. Khi đó a11x1 + a12x2 + a13x3 + a14x4 là tổng lượng than để sản xuất ra (x1+x2+x3+x4) đơn vị điện. Khi dùng than để sản xuất điện, các nhà máy sẽ làm ô nhiễm môi trường. Giả sử g(a11x1+a12x2+a13x3+a14x4) là tiền phí phải trả do làm ô nhiễm môi trường khi dùng lượng than là
t := a11x1 + a12x2 + a13x3 + a14x4.
2t2
Ví dụ: g(t) = 1
(cid:68) f (x∗, x) = + ϕ(x) − ϕ(x∗) ≥ 0.
Vậy bài toán (SEP ) trong ví dụ này sẽ có (cid:101)B1x∗ − ¯α, x − x∗(cid:69) 0 0, 1 0, 1 0, 1 α
0, 1 0 0, 1 0, 1 α − , 0, 1 0, 1 0 0, 1 α 0, 1 0, 1 0, 1 0 α =(cid:104) x∗ 1 x∗ 2 x∗ 3 x∗ 4
x1 − x∗ 1 x2 − x∗ 2 x3 − x∗ 3 x4 − x∗ 1 0
2 + x∗ 1 + x∗ 1 + x∗ 1 + x∗
4(cid:105) lấy α = 10 4(cid:105)
3 + x∗ 4) 3 + x∗ 4) 2 + x∗ 4) 2 + x∗ 3)
1 0 , − 1 0 0, 1 (x∗ 0, 1 (x∗ 0, 1 (x∗ 0, 1 (x∗ 1 0
∀x ∈ K ,
4(cid:105) ≥
2 + x∗ 1 + x∗ 1 + x∗ 1 + x∗
3 + x∗ 3 + x∗ 2 + x∗ 2 + x∗
4) − 10 4) − 10 4) − 10 3) − 10
x1 − x∗ 1 x2 − x∗ 2 x3 − x∗ 3 x4 − x∗ 0 0 0 0 0, 1 (x∗ 0, 1 (x∗ 0, 1 (x∗ 0, 1 (x∗ =(cid:104) =(cid:104) x1 − x∗ 1 x2 − x∗ 2 x3 − x∗ 3 x4 − x∗
Với K được chọn là: K = K1 × K2 × K3 × K4. Trong đó Ki = [0, 100]
g(Ax∗) ≤ g(Ax), ∀x ∈ K
g(Ax) = g(a11x1 + a12x2 + a13x3 + a14x4)
= (a11x1 + a12x2 + a13x3 + a14x4)2. 1 2
36
Kết luận
Bản luận văn này đề cập đến các vấn đề sau:
1. Tổng hợp lại các kiến thức cơ bản nhất về tập lồi, hàm lồi.
2. Giới thiệu một số bổ đề cơ bản liên quan đến hình chiếu và tích vô
hướng.
3. Giới thiệu mô hình Nash - Cournot có thêm một ràng buộc tách. Cụ
thể: Trình bày thuật toán giải bài toán cân bằng tách liên quan đến mô
hình. Trình bày chi tiết định lý hội tụ và chứng minh của định lý này.
4. Trình bày một mô hình thực tế trong sản xuất điện với chi phí môi
trường thấp nhất, một số ví dụ cụ thể đã được đưa ra để minh họa cho
mô hình thực tế này.
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 (2001), Nhập
môn giải tích lồi ứng dụng, NXB Đại học Quốc gia Hà Nội.
Tiếng Anh
[2] Censor Y, Elving T (1994) "A multiprojections algorithm using Breg-
man projections in a product spaces". Numer Algorithms 8:221-239
[3] Hoàng Tụy, Convex Analysis and Global Optimization, Springer,
2016.
[4] Le Thi Hai Yen, Le Dung Muu, Nguyen Thi Thanh Huyen (2016),
"An algorithm for a class of split feasibility problems; application to a
model in electricity production", Math. Meth. Oper. Res. 84:549:565
