BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
BÙI VĂN ĐỊNH
MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN
CÂN BẰNG GIẢ ĐƠN ĐIỆU VÀ ỨNG DỤNG
LUẬN ÁN TIẾN SĨ TOÁN HỌC
HÀ NỘI - 2014
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
BÙI VĂN ĐỊNH
MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN
CÂN BẰNG GIẢ ĐƠN ĐIỆU VÀ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng
Mã số: 62 46 01 12
LUẬN ÁN TIẾN SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. PGS. TS. NGUYỄN ĐỨC HIẾU
2. GS. TSKH. LÊ DŨNG MƯU
HÀ NỘI - 2014
1
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của tôi. Các kết quả viết
chung với các tác giả khác, đều đã được sự nhất trí của các đồng tác giả khi
đưa vào luận án. Các kết quả nêu trong luận án là hoàn toàn trung thực và
chưa từng được ai công bố trong bất cứ một công trình nào khác.
NCS. Bùi Văn Định
2
LỜI CẢM ƠN
Bản luận án này được hoàn thành tại Bộ môn Toán, Khoa Công nghệ
Thông tin, Học viện Kỹ thuật Quân sự, dưới sự hướng dẫn của PGS. TS.
Nguyễn Đức Hiếu và đặc biệt là GS. TSKH. Lê Dũng Mưu. Tác giả xin bày tỏ

4. Phương pháp nghiên cứu . . . . . . . . . . . . . . . . . . . . . . 12
5. Kết quả của luận án . . . . . . . . . . . . . . . . . . . . . . . . 13
6. Cấu trúc của luận án . . . . . . . . . . . . . . . . . . . . . . . . 15
Chương 1. MỘT SỐ KIẾN THỨC CHUẨN BỊ. . . . . . . . . 16
1.1. Các khái niệm và các kết quả cơ bản . . . . . . . . . . . . . . . 16
1.2. Bài toá n cân bằng và các trường hợp riêng . . . . . . . . . . . . 21
1.3. Bài toá n cân bằng tương đương . . . . . . . . . . . . . . . . . . 28
1.4. Bài toá n cân bằng hai cấp . . . . . . . . . . . . . . . . . . . . . 31
Chương 2. MỘT PHƯƠNG PHÁP CHIẾU CHO BÀI TOÁN CÂN BẰNG
GIẢ ĐƠN ĐIỆU VÀ ÁP DỤNG VÀO MỘT LỚP BÀI TOÁN CÂN
BẰNG HAI CẤP . . . . . . . 33
2.1. Đặt bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.2. Thuật toán chiếu cho bài toán cân bằng . . . . . . . . . . . . . 41
4
2.3. Áp dụng vào bài toán cân bằng Nash-Cournot trong mô hình
cân bằng thị trường điện bán độc quyền . . . . . . . . . . . . . 49
2.4. Áp dụng vào bài toán tìm cực tiểu của hàm chuẩn Euclide trên
tập nghiệm của bài toán cân bằng giả đơn điệu . . . . . . . . . 53
2.5. Áp dụng vào bài toán bất đẳng thức biến phân trên tập nghiệm
của bài toán cân bằng . . . . . . . . . . . . . . . . . . . . . . . 61
Chương 3. KẾT HỢP PHƯƠNG PHÁP HÀM PHẠT VÀ
HÀM ĐÁNH GIÁ GIẢI BÀI TOÁN CÂN BẰNG HAI CẤP . . . 77
3.1. Đặt bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.2. Phương pháp hàm phạt . . . . . . . . . . . . . . . . . . . . . . 78
3.3. Hàm đánh giá và hướng giảm . . . . . . . . . . . . . . . . . . . 84
3.4. Áp dụng vào phương pháp hiệu chỉnh Tikhonov . . . . . . . . 91
KẾT LUẬN . . . . . . . . . . . . . . . . 95
1. Kết quả đạt được . . . . . . . . . . . . . . . . . . . . . . . . . . 95
2. Kiến nghị một số hướng nghiên cứu tiếp theo . . . . . . . . . . 96
DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN

ϕ
′
(x; d) đạo hàm theo hướng d của ϕ tại x
∂ϕ(x ) dưới vi phân của ϕ tại x
∇
x
f(x, y) đạo hàm của hàm f (., y) tại x
∇
y
f(x, y) đạo hàm của hàm f (x, .) tại y
6
∂f ( x, x) dưới vi phân của hàm f ( x, .) tại x
C bao đóng của tập C
int C phần trong của tập C
ri C phần trong tương đối của tập C
lim = lim sup giới hạn trên
lim
= lim inf giới hạn dưới
x
k
→ x dãy x
k
hội tụ tới x
P
C
(x) hình chiếu của x lên tập C
N
C
(x) nón pháp tuyến ngoài của C tại x
EP(C, f) bài toán cân bằng

thú săn mồi trong hệ sinh thái đó có tỉ lệ tương đồng với nhau.
Trong Kinh tế học, cân bằng kinh tế là một khái niệm cơ bản nhưng đồng
thời cũng là động lực và là mục đích của m ỗi nền kinh tế. Một ví dụ đơn giản
về lĩnh vực này là ở một thị trường xác định có sản xuất và tiêu thụ đồng
nhất một loại hàng hóa. Sức mua của thị trường phụ thuộc vào giá cả của
mặt hàng đó t rên thị trường, nói một cách chính xác hơn, nếu m ặt hàng được
bán ở mức giá p thì hàm cầu của thị trường là D(p), trong khi đó các nhà sản
xuất có thể cung cấp lượng hàng ở mức giá p là S(p) và ta có hàm vượt cầu là
E(p) = D(p) − S(p). Sự cân bằng xảy ra ở mức giá p
∗
nếu E(p
∗
) = 0, tức là
lượng cung bằng lượng cầu, điều này cũng giống như sự cân bằng xảy ra trong
8
cơ học khi hợp lực tác động lên hệ bằng không.
Có nhiều bài toán liên quan đến sự cân bằng có thể được nhìn nhận trong
một thể thống nhất qua các mô hình toán học khác nhau của nó, chẳng hạn
như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash
trong các trò chơ i không hợp tác, v.v Ngược lại, nếu có nhiều mô hình cùng
nằm trong một cấu trúc thống nhất sẽ cho phép thiết lập một công thức chung
cho cấu trúc thống nhất đó và do vậy chúng ta có thể phát triển các nghiên
cứu về lý thuyết cũng như thuật toán cho thể thống nhất chung đó mang lại
khả năng ứng dụng rộng lớn hơn các mô hình riêng lẻ. Mô hình chung cho bài
toán cân bằng EP(C, f ) đó là
Tìm x
∗
∈ C sao cho f (x
∗
, y) ≥ 0 với mọi y ∈ C,

(projection methods). Trong các phương pháp đó thì phương pháp chiếu đóng
một vai trò quan trọng vì sự đơn giản và thuận tiện khi tính to án. Các thuật
toán chiếu cho bài toán cân bằng thường được phát triển từ các t huật toán
chiếu cho bài toán bất đẳng thức biến phân và một số bài toán khác [15, 47],
trong các thuật toán chiếu đó thì thuật toán chiếu cho bài toán bất đẳng thức
biến phân được đề xuất bởi M. V. Solodov và B. F. Svaiter [59] (gọi là thuật
toán Solodov-Svaiter) có nhiều đặc điểm nổi bật, đó là nó có thể áp dụng được
cho một lớp khá rộng các bài toán bất đẳng thức biến phân VIP(C, F ) với
toán tử F chỉ cần đòi hỏi tính giả đơn điệu theo tập nghiệm, tính liên tục, mà
không nhất thiết phải có tính chất Lipchitz. Ngoài ra, cũng theo [59] thì nói
chung, số các bước lặp giải bài toán VIP(C , F ) theo thuật toán này là ít hơn
đáng kể so với các thuật toán khác.
Từ những đặc điểm nổi bật của thuật toán Solodov-Svaiter cho bài toán
VIP(C, F ) ở trên, dẫn đến việ c mở rộng thuật toán này cho bài toán cân bằng
EP(C, f ) là hết sức cần thiết. Đây là một vấn đề sẽ được giải quyết trong luận
án.
10
Ngoài các phươ ng pháp chiếu cho bài toán cân bằng thì các phương pháp
hiệu chỉnh đóng một vai trò quan trọng vì nó cho phép giải quyết các bài toán
đặt không chỉnh (ill-posed problem) theo nghĩa nghiệm của nó không duy nhất,
hoặc không phụ thuộc liên tục theo các dữ kiện ban đầu, tức là một thay đổi
nhỏ của các dữ liệu đ ầ u vào của bài toán có thể dẫn đến sự sai khác rất lớn
của nghiệm, thậm chí làm cho bài toán trở nên vô nghiệm hoặc vô định. Người
có c ông đặt nền móng cho lý thuyết các bài toán đặt không chỉnh đó là A. N.
Tikhonov [63, 64], do tầm quan trọng của lý thuyết này mà đã có nhiều nhà
toán học nước ngoài như A. N. Tikhonov, V. Y. Arsenin [63, 64], v.v và các
nhà toán học trong nước như P. K. Anh, N. Bường [1], L. D. Mưu [32], N. D.
Yên [62], v.v , dành nhiều công sức nghiên cứu. Năm 2006, phương pháp hiệu
chỉnh Tikhonov (Tikhonov regularization method) đã được áp dụng cho bài
toán bất đẳng thức biến phân giả đơn điệu trong không gian hữu hạn chiều

∈ S
F
sao cho G(x
∗
), y − x
∗
 ≥ 0, ∀y ∈ S
F
.
Bằng cách phát triển các kỹ thuật lai ghép giữa phương pháp đạo hàm tăng
cường với kỹ thuật siêu phẳng cắt (hybrid extragradient-viscosity methods),
P. E. Maingé (xem [38, 39]) vào năm 2008 đã xây dựng được các thuật toán
giải bài toán bất đẳng thức biến phân liên tục Lipschitz và đơn điệu mạnh trên
tập S là giao giữa tập nghiệm của bài toán bấ t đẳng thức biến phân đơn điệu
và liên tục Lipschitz với tập các điểm bất động của ánh xạ demicontractive.
Do đó, việc mở rộng các thuật toán này cho những lớp bài toán tổng quát hơn
như bài toán bất đẳng thức biến phân đơn điệu mạnh và Lipschitz trên tập
nghiệm của bài toán cân bằng giả đơn điệu là hết sức cần thiết. Vấn đề này
cũng sẽ được nghiên cứu trong luận án.
Một phương pháp hiệu chỉnh quen thuộc khác là phương pháp điểm gần
kề. Phương pháp này được đề xuất bởi B. Martinet [40] vào năm 1970 cho bài
toán bất đẳng thức biến phân và được phát triển bởi R. T. Rockafellar [58]
năm 1976 cho bao hàm thức đơn điệu cực đ ạ i. Năm 1999, A. Moudafi [44] đã
mở rộng phương pháp điểm g ần kề cho bài toán cân bằng đơn điệu và đến
năm 2010, A. Moudafi [45] đã áp dụng phương pháp này cho lớp bài toán cân
bằng hai cấp đơn điệu. Ý tưởng chính của phương pháp này là kết hợp giữa
phương pháp hàm phạt và phương pháp điểm gần kề để đưa việc giải bài toán
cân bằng hai cấp về việc giải một dãy các bài toán cân bằng với song hàm cân
bằng là f + ǫ
k

của bài toán cân bằng giả đơn điệu.
• Nội dung 2. Nghiên cứu xây dựng thuật toán cho bài toán bất đẳng
thức biến phân đơn điệu mạnh trên tập nghiệm của bài toán cân bằng
giả đơ n điệu.
• Nội dung 3. Nghiên cứ u xây dựng phương pháp giải bài toán cân bằng
hai cấp.
4. Phương pháp nghiên cứu
Cùng với các phương pháp cơ bản của giải tích lồi, giải tích hàm, giải tích đa
trị và giải tích phi tuyến, chúng tôi còn sử dụng các phương pháp sau:
13
• Để xây dựng phương pháp giải bài toán cân bằng chúng tôi mở rộng
phương pháp chiếu của Solodov-Svaite r, kết hợp với quy tắc tìm kiếm
theo tia của Armijo;
• Để xây dựng thuật toán tìm cực tiểu của hàm chuẩn trên tập nghiệm
của bài toán cân bằng giả đơn điệu chúng tôi sử dụng phương pháp chiếu
kết hợp với kỹ thuật siêu phẳng cắt (chiếu siêu phẳng cắt) và quy tắc
tìm kiế m theo tia của Armijo;
• Để tìm nghiệm của bài toán bất đẳng thức biến phân trên tập nghiệm của
bài toán cân bằng chúng tôi sử dụng kỹ thuật lai ghép giữa thuật toán đạo
hàm tă ng cường với phương pháp siêu phẳng cắt (hybrid extragradient-
viscosity methods) kết hợp với quy tắc tìm kiếm theo tia của Armijo;
• Để xây dựng phương pháp giải bài toán cân bằng hai cấp chúng tôi sử
dụng phương pháp hàm phạt, kết hợp với phương pháp hàm đánh giá và
nguyên lý bài toán phụ.
5. Kết quả của luận án
Luận án đã đạt được những kết quả chính sau đây:
• Xây dựng được thuật toán chiếu giải bài toán cân bằng giả đơn điệu, đã
kết hợp thuật toán này với kỹ thuật siêu phẳng cắt để thu được thuật
toán tìm cực tiểu của hàm chuẩn trên tập nghiệm của bài toán cân bằng
giả đơn điệu. Đã chứng minh được tính đúng đắn và sự hội tụ của các

International Conference on High Performance Scientific Com-
puting, Hanoi 2012.
15
6. Cấu trúc của luận án
Ngoài phần mở đầu, kết luận, danh mục công trình khoa học của tác giả liên
quan đến luận án và danh mục tài liệu tham khảo, luận án gồm 3 chương:
• Chương 1. Một số kiến thức chuẩn bị.
• Chương 2. Một phương pháp chiếu cho bài toán cân bằng giả đơn điệu
và áp dụng vào một lớp bài toán cân bằng hai cấp.
• Chương 3. Kết hợp phương pháp hàm phạt và hàm đánh giá giải bài
toán câ n bằng hai cấp.
16
Chương 1
MỘT SỐ KIẾN THỨC CHUẨN BỊ
Trong chương này, chúng tôi nhắc lại các khá i niệm cũng như các kết quả
bổ trợ cần thiết được sử dụng ở các chương sau.
Chương này gồm bốn phần. Phần thứ nhất trình bày một số khái niệm và
các kết quả cần thiết nhất về giải tích hàm, giải tích lồi. Phần thứ hai dành
để giới thiệu về bài t oán cân bằng và các trường hợp riêng của nó cùng một
số điều kiện về sự tồn tại nghiệm của bài toán cân bằng. Phần tiếp theo trình
bày về bài toán cân bằng tương đương. Phần cuối cùng trình bày về bài toán
cân bằng hai cấp và một số trường hợp riêng của bài toán này.
1.1. Các khái niệm và cá c kết quả cơ bản
1.1.1. Một số khái niệm về tập lồi và hàm lồi
Các khái niệm về tập lồi và hàm lồi là các khái niệm cơ bản của giải tích lồi
và lý thuyết tối ưu, các khái niệm này có thể tìm thấy trong các tài liệu tham
khảo [2, 3, 6, 10, 12, 57, 66].
Định nghĩa 1.1. Giả sử X là một không gian véc tơ trên R, tập C ⊂ X được
gọi là:
(a) lồi nếu ∀x, y ∈ C và 0 ≤ λ ≤ 1 ⇒ λx + (1 − λ) y ∈ C;

0
) và từ định nghĩa trên ta thấy N
C
(x
0
) là một nón lồi
đóng.
Định nghĩa 1.3. Giả sử C = ∅ (không nhất thiết lồi) là một tập con của
không gian Hilbert H và y ∈ H là một véc tơ bất kỳ, gọi
d
C
(y) = inf
x∈C
x − y.
Ta nói d
C
(y) là khoảng cách từ y đến C. Nếu tồn tại P
C
(y) ∈ C sao cho
d
C
(y) = y − P
C
(y) , thì ta nói P
C
(y) là hình chiếu của y trên C.
Từ định nghĩa trên ta thấy hình chiếu P
C
(y) của y trên C là nghiệm của
bài toán tối ưu

C
(x) −P
C
(y)
2
≤ P
C
(x) −P
C
(y), x −y, ∀x, y ∈ H (tính đồng bức).
Định nghĩa 1.4. Giả sử X là không gian véc tơ tô pô lồi địa phương thực,
C ⊂ X là một tập lồi và f : C → R ∪ {+∞}, khi đó
18
(a) hàm số f được gọi là lồi (convex function) trên C nếu
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y), ∀x, y ∈ C, ∀λ ∈ [0; 1];
lồi chặt (strictly convex function) trên C nế u
f(λx + (1 − λ)y) < λf(x) + (1 − λ)f(y), ∀x, y ∈ C, x = y, ∀λ ∈ (0; 1);
và là lồi mạnh (strongly convex function) trên C với hệ số δ > 0 nếu
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y) − λ(1 − λ)δy −x
2
,
∀x, y ∈ C, ∀λ ∈ [0; 1];
(b) hàm số f được gọi là lõm (lõm chặt, lõm mạnh) trên C nếu −f là lồi (lồi
chặt, lồi mạnh) trên C;
(c) các tập
domf = {x ∈ C : f(x) < +∞},
epif = {(x, t) ∈ C × R : f (x) ≤ t},
được gọi lần lượt là miền hữu hiệu (effective domain) và trên đồ thì
(epigraph) của f ;
(d) hàm f : C → R ∪ {±∞} được gọi là chín h thường (proper function) nếu

0
∈ H. Khi đó các khẳng định sau là tương đương
(a) f liên tục tại điểm x
0
;
(b) f bị chặn trên trong một lân cận mở của x
0
;
(c) int(epif) = ∅;
(d) int(domf ) = ∅ và f liên tục trên int(domf ) , đồng thời
int(epif) = {(x, t) ∈ H ×R : x ∈ int(domf ), f(x) < t}.
Từ Định lý 1.2 ta suy ra một hàm lồi chính thường chỉ có thể gián đoạn
tại những điểm biên của miền hữu hiệu của nó.
1.1.2. Đạo hàm và dưới vi phân của hàm lồi
Phép tính vi phân là một trong những phép tính cơ bản nhất của giải
tích. Nhờ những tính chất đặc thù của hàm lồi mà phép tính vi phân của nó
càng trở nên đa dạng và phong phú hơn.
Định nghĩa 1.6. Giả sử f : H → R, x ∈ H và d ∈ H\{0}. Khi đó hàm f được
gọi là
(a) khả vi (Fréche t ) tại x nếu tồn tại véc tơ x
∗
∈ H sao cho
lim
y→x
f(y) − f(x) − x
∗
, y − x
y − x
= 0,
khi đó x

≤ f(x) − f (x
∗
), ∀x ∈ C và x
∗
= arg min
x∈C
f(x). Nếu
thêm vào đó hàm f khả vi trên C thì
(b) δy −x
2
≤ ∇f (y) − ∇f(x), y −x, ∀x, y ∈ C;
(c) 0 ≤ f(x) −f(x
∗
) ≤
1
δ
∇f(x)
2
, ∀x ∈ C.
Nhận xét 1.1. Nếu f là hàm khả vi và δ lồi mạnh trên tập lồi đóng C ⊂ R
n
,
thì ta có
f(y) − f(x) ≥ ∇f(x), y − x + δ y − x
2
, ∀x, y ∈ C.
Định nghĩa 1.7. Giả sử f : H → R ∪ {+∞} là hàm lồi chính thường trên H,
w ∈ H được gọi là dưới đạo hàm (subg radient) của f tại x nếu
f(y) ≥ w , y −x + f(x), ∀y ∈ H. (1.1)
Tập tất cả các dưới đạo hàm của f tại x được gọi là dưới vi phân (subdiffer-

k → ∞
x
k
= x, thì với bất kì y ∈ R
n
và bất kì dãy {y
k
} hội tụ về y ta có
lim sup
k → ∞
f
′
k
(x
k
; y
k
) ≤ f
′
(x; y).
21
Hơn nữa, với bất kì số ǫ > 0, tồn tại chỉ số k
0
sao cho
∂f
k
(x
k
) ⊂ ∂f(x) + ǫB[0; 1], ∀k ≥ k
0

Hệ quả 1.1. Với các giả thiết như trong Định lý 1.7 thì điểm x
0
∈ intC là
điểm cực tiểu của f trên C khi và chỉ khi 0 ∈ ∂f (x
0
). Đặc biệt, nếu hàm f
khả vi thì điều kiện này trở thành ∇f(x
0
) = 0.
1.2. Bài toán cân bằng và các trường hợp riêng
Giả sử C là tập lồi đóng khác rỗng trong không gian Hilbert H và f : C×C →
¯
R
thỏa mãn f(x, x) = 0 với mọi x ∈ C; một hàm f như vậy được gọi là song
hàm cân bằng (equilibrium bifunction). Chúng tôi xét bài toán cân bằng hay
bất đằng thức Ky Fan như sau
Tìm x
∗
∈ C sao cho f (x
∗
, y) ≥ 0, ∀y ∈ C.
Ta sẽ ký hiệu bài toán này là EP(C, f ) và tập nghiệm của nó là S
f
.
Bài toán này đượ c đặt tên là bài t oán cân bằng (equilibrium probl em) bởi các
tác giả L. D. Muu và W. Oettli [49] năm 1992, E. Blum và W. Oettli [16] năm
1994, nhưng công thức này được đưa ra lần đầu tiên bởi các tác giả Nikaido và
Isoda năm 19 55 [53] khi tổng quát hóa bài toán cân bằng Nash trong trò chơi
22
không hợp tác, Ky Fan đưa ra năm 1972 [29] (thường được gọi là bất đẳng

Bằng cách đặt f(x, y) = F (x), y −x, ta đưa được bài toán VIP(C , F ) về bài
toán EP(C, f).
Một trường hợp riêng quan trọng của bài toán VIP(C, F ) là khi C là một nón
lồi đóng khác rỗng trong R
n
. Ký hiệu C
+
= { x ∈ R
n
: x, y ≥ 0, ∀y ∈ C} là
nón cực của C. Khi đó bài toán bất đẳng thức biến phân VIP(C, F ) trở thành
bài toán bù CP(C, F ) (complementarity problem) được định nghĩa như là bài