ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
DƯƠNG THỊ BÌNH
PHƯƠNG PHÁP XẤP XỈ
TRONG ĐỂ GIẢI BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN
ĐA TRỊ GIẢ ĐƠN ĐIỆU
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
TS. PHẠM NGỌC ANH
THÁI NGUYÊN - NĂM 2010
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
i
Mục lục
Mục lục i
Lời cảm ơn iii
Mở đầu 1
1 Bài toán bất đẳng thức biến phân đa trị 3
1.1 Một số khái niệm và tính chất cơ bản . . . . . . . . . . . . . . . . . . . 3
1.1.1 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Ánh xạ đa trị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Bài toán bất đẳng thức biến phân đa trị . . . . . . . . . . . . . . . . . 12
1.3.1 Bất đẳng thức biến phân đa trị và các bài toán liên quan . . . . 12
1.3.2 Sự tồn tại nghiệm của bài toán (MV I) . . . . . . . . . . . . . . 18
2 Phương pháp xấp xỉ trong với điều kiện Lipschitz 20
2.1 Phương pháp hàm phạt điểm trong [1] . . . . . . . . . . . . . . . . . . 20
2.2 Thuật toán xấp xỉ trong và sự hội tụ . . . . . . . . . . . . . . . . . . . 23
3 Phương pháp xấp xỉ trong không Lipschitz 33
Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu xót và
hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các thầy, cô và bạn đọc
để luận văn được hoàn thiện hơn.
Xin trân trọng cảm ơn!
Thái Nguyên, tháng 9-2010
Người viết luận văn
Dương Thị Bình
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
1
Mở đầu
Bài toán bất đẳng thức biến phân là một công cụ rất hữu hiệu để nghiên cứu và giải
các bài toán ứng dụng như các bài toán cân bằng trong kinh tế, tài chính, vận tải, lí
thuyết trò chơi, bài toán cân bằng mạng, ···.
Bài toán bất đẳng thức biến phân được giới thiệu bởi Hartman và Stampacchia vào
năm 1966. Những nghiên cứu đầu tiên về bài toán này liên quan tới việc giải các bài
toán điều khiển tối ưu và các bài toán biên có dạng của phương trình đạo hàm riêng.
Bài toán bất đẳng thức biến phân trong không gian vô hạ n chiều và các ứng dụng
của nó được giới thiệu trong cuốn sách "An introduction to variational inequalities
and their application" của D.Kinderlehrer và G. Stampacchia xuất bản năm 1980 [8]
và trong cuố n sách "Variational and quasivariational inequalities: Application to free
boundary problem" của Baiocci và Capelo xuất bản năm 1984.
Từ đó, bài toán bất đẳng thức biến phân đã có những bước phát triển rất mạnh và
thu hút được sự quan tâm của nhiều nhà nghiên cứu. Một trong các hướng nghiên cứu
quan trọng của bài toán bất đẳng thức biến phân là việc xây dựng các phương pháp
giải. Thực tế cho thấy việc giải trực tiếp để tìm nghiệm của bài toán bất đẳng thức
biến phân là khó khăn và không phải trường hợp nào cũng thực hiện được. Vì vậy các
nhà toán học đã nghiên cứu và xây dựng nhiều thuật toán vô hạn để tìm nghiệm của
bài toán này, tuy nhiên việc tìm ra nghiệm chính xác là khó thực hiện được. Do đó
người ta thường phải lấy nghiệm xấp xỉ với độ chính xác nào đó.
Những năm gần đây việc nghiên cứu giải tích đa trị cũng phát triển mạnh, điều
Trong luận văn này, chúng ta sẽ làm việc trên không gian Euclid n chiều R
n
. Mỗi
phần tử x = (x
1
, x
2
, ··· , x
n
)
T
∈ R
n
là một véc tơ cột của R
n
. Với hai véc tơ bất kì
x = (x
1
, x
2
, ··· , x
n
)
T
∈ R
n
, y = (y
1
, y
2
được gọi là tập lồi nếu
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
Định nghĩa 1.2. [10] Một tập hợp là giao của một số hữu hạn các nửa không gian
đóng được gọi là tập lồi đa diện hay là khúc lồi.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
4
Định nghĩa 1.3. [10] Một tập C ⊆ R
n
được gọi là nón nếu
∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C.
Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi. Như vậy, một tập lồi C
là nón lồi khi và chỉ khi nó có các tính chất sau:
(a) λC ⊆ C, ∀λ > 0
(b) C + C ⊆ C
Tập C ⊆ R
n
dưới đây luôn giả thiết là một tập lồi (nếu không giải thích gì thêm).
Định nghĩa 1.4. Cho x ∈ C, nón pháp tuyến ngoài của C tại x, kí hiệu là N
C
(x),
được xác định bởi công thức
N
C
(x) := {w ∈ R
n
| w, y − x ≤ 0, ∀y ∈ C}.
Định nghĩa 1.5. Cho ánh xạ f : C →
¯
R. Khi đó, miền hữu hiệu của f, kí hiệu là
domf, được xác định bởi
. Ta có định nghĩa dưới vi phân của hàm
lồi như sau.
Định nghĩa 1.7. Véc tơ w ∈ R
n
được gọi là dưới gradient của f tại x
0
∈ C nếu
w, x − x
0
≤ f(x) − f(x
0
), ∀x ∈ C.
Tập tất cả các dưới gradient của hàm f tại x
0
được gọi là dưới vi phân của f tại x
0
,
kí hiệu ∂f (x
0
), tức là
∂f (x
0
) := {w ∈ R
n
: w, x − x
0
≤ f(x) − f(x
0
), ∀x ∈ C}.
Hàm f được gọi là khả dưới vi phân tại x
(x
0
) = 0 và
∂δ
C
(x
0
) = {w ∈ R
n
: δ
C
(x) ≥ w, x − x
0
, ∀x ∈ C}.
Hay
∂δ
C
(x
0
) = {w ∈ R
n
: 0 ≥ w, x − x
0
, ∀x ∈ C} = N
C
(x
0
). ✷
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
6
vào (1.1), ta có
w, x
0
≤ f(2x
0
) − f(x
0
) = f(x
0
). (1.2)
Còn nếu thay x = 0 vào (1.1), ta được
−w, x
0
≤ −f(x
0
). (1.3)
Kết hợp (1.2) và (1.3), suy ra
w, x
0
= f(x
0
).
Hơn nữa
w, x − x
0
= w, x − w, x
0
= w, x − f(x
0
|w, x| ≤ f (x), ∀x ∈ C.
Định lí 1.2. [10] Cho f
i
, i = 1, ··· , m là các hàm lồi chính thường trên R
n
. Khi đó,
với mọi x ∈ R
n
thì
∂(
m
i=1
f
i
(x)) ⊇
m
i=1
∂f
i
(x)
Nếu tồn tại một điểm a ∈ ∩
n
i=1
domf
i
mà tại điểm đó mọi hàm f
i
(có thể trừ ra
là một ánh xạ đa trị từ X vào R
2
.
Với ánh xạ đa trị F : X → Y , ta xác định đồ thị và miền hữu hiệu của ánh xạ F
tương ứng bằng các công thức
graphF : = {(x, y) ∈ X × Y | y ∈ F (x)},
domF : = {x ∈ X| F (x) = ∅}
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
8
Ta biết rằng, ánh xạ liên tục Lipschitz là một khái niệm có vai trò quan trọng trong
giải tích toán học. Trong mục này ta sẽ định nghĩa liên tục Lipschitz của một ánh xạ
đa trị dựa trên khoảng cách Hausdorff như sau:
Định nghĩa 1.9. (Khoảng cách Hausdorff)
Với A, B là hai tập con đóng và khác rỗng bất kì của R
n
, khoảng cách Hausdorff
giữa hai tập A và B được xác định bởi
ρ(A, B) := max{d(A, B), d(B, A)},
trong đó
d(A, B) = sup
a∈A
inf
b∈B
||a − b||
d(B, A) = sup
b∈B
inf
a∈A
||a − b||
Định nghĩa 1.10. (Ánh xạ đa trị liên tục Lipschitz)
< x
2
) thì
d(F (x
1
, 0), F (x
2
, 0)) = max
(x
1
,y
1
)∈F (x
1
,0)
min
(x
2
,y
2
)∈F (x
2
,0)
||(x
1
, y
1
) − (x
2
, y
2
= max
(x
1
,y
1
)∈F (x
1
,0)
|x
1
− x
2
|
= |x
1
− x
2
|
= ||(x
1
, 0) − (x
2
, 0)||.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
9
d(F (x
2
, 0), F (x
1
)∈F (x
2
,0)
min
(x
1
,y
1
)∈F (x
1
,0)
(x
1
− x
2
)
2
+ (y
1
− y
2
)
2
≤ max
(x
2
,y
1
)∈F (x
1
, 0) − (x
2
, 0)||, ∀(x
1
, 0), (x
2
, 0) ∈ C
hay F là ánh xạ đa trị liên tục Lipschitz, với hằng số L =
√
5. ✷
Định nghĩa 1.11. [3] Ánh xạ đa trị F : C → 2
R
n
, được gọi là:
(i) Nửa liên tục trên tại ¯x ∈ domF nếu với mọi tập mở V chứa F (¯x), tồn tại lân cận
mở U của ¯x sao cho
F (x) ⊆ V, ∀x ∈ U
(ii) Nửa liên tục dưới tại ¯x ∈ domF nếu với mọi tập mở V thỏa mãn F (¯x) ∩ V = ∅,
tồn tại lân cận mở U của ¯x sao cho
F (x) ∩ V = ∅, ∀x ∈ U ∩ domF.
Ánh xạ F được gọi là nửa liên tục trên (nửa liên tục dưới) trên C nếu nó nửa liên
tục trên (nửa liên tục dưới) tại mọi điểm thuộc domF .
Ta nói F là liên tục tại ¯x ∈ domF nếu F đồng thời là nửa liên tục trên và nửa liên
tục dưới tại ¯x. Nếu F liên tục tại mọi điểm thuộc domF , thì F được gọi là liên tục
trên C.
Ví dụ 1.5. Cho ánh xạ đa trị F : R → 2
R
thỏa mãn:
F (x) =
(a, b) ∩ F (0) = {0} = ∅,
tồn tại lân cận của 0, chẳng hạn U = (−
1
2
,
1
2
). Ta có
F (x) =
[0, 1] nếu x ∈ (−
1
2
,
1
2
)\{0},
{0} nếu x = 0
Do đó
F (x) ∩ (a, b) = 0, ∀x ∈ (−
1
2
,
1
2
)
Vậy F nửa liên tục dưới tại ¯x = 0. ✷
Định nghĩa 1.12. [3] Một ánh xạ F : R
n
→ 2
(i) đơn điệu mạnh trên C với hằng số β > 0, nếu
w − w
, x − x
≥ β||x − x
||
2
, ∀x, x
∈ C, w ∈ F (x), w
∈ F(x
)
(ii) đơn điệu ngặt trên C, nếu
w − w
, x − x
> 0, ∀x, x
∈ C, w ∈ F (x), w
∈ F(x
), x = x
(iii) đơn điệu trên C, nếu
, 0) ∈ C và với mọi (x, y) ∈ F (x, 0), (x
, y
) ∈
F (x
, 0), ta có
(x, y) − (x
, y
), (x, 0) − (x
, 0)
= (x −x
, y − y
), (x − x
, 0)
= (x −x
)
2
≥ 0.
Hơn nữa, F còn đơn điệu ngặt trên C vì bất đẳ ng thức trên là ngặt khi (x, 0) =
(x
− x ≤ f(x
) − f(x)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
12
với các giá trị f(x) và f(x
) hữu hạn. Cộng hai bất đẳng thức trên ta được
w
, x − x
+ w, x
− x ≤ 0
hay w − w
, x − x
≥ 0, ∀x, x
∈ dom(∂f), w ∈ ∂f(x), w
∈ ∂f(x
)
Vậy ∂f đơn điệu. ✷
1.3 Bài toán bất đẳng thức biến phân đa trị
1.3.1 Bất đẳng thức biến phân đa trị và các bài toán liên quan
Cho C là một tập lồi, đóng, khác rỗng trong R
Bài toán bất đẳng thức biến phân (MV I) có quan hệ mật thiết với nhiều bài toán
khác của giải tích, như là: Bài toán bù phi tuyến, bài toán điểm bất động và bài toán
quy hoạch lồi, ···.
Bài toán điểm bất động Kakutani
Cho C là tập lồi, đóng tùy ý trong R
n
và T là ánh xạ đa trị từ C vào chính nó. Bài
toán điểm bất động của ánh xạ đa trị T được phát biểu như sau:
Tìm x
∗
∈ C sao cho x
∗
∈ T(x
∗
). (1.4)
Đặc biệt, nếu T là ánh xạ đơn trị thì bài toán điểm bất động Kakutani trở thành
bài toán điểm bấ t động Brower có dạng:
Tìm x
∗
∈ C sao cho x
∗
= T(x
∗
).
Mệnh đề sa u cho ta thấy mối liên hệ giữa bài toán (MV I) với bài toán điểm bất
động (1.4).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
13
Mệnh đề 1.2. Nếu ánh xạ F được xác định bởi
F (x) := x − T (x), ∀x ∈ C
− ξ
∗
.
Ta có
x
∗
− ξ
∗
, x − x
∗
≥ 0, ∀x ∈ C
Cho x = ξ
∗
ta được
||x
∗
− ξ
∗
|| ≤ 0
Suy ra x
∗
= ξ
∗
hay x
∗
∈ T(x
∗
). Vậy nên x
∗
là nghiệm của bài toán (1.4).
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 (MV I).
Chứng minh. Nếu x
∗
là nghiệm của bài toán bất đẳng thức biến phân (MV I) và
w
∗
∈ F(x
∗
) thì
w
∗
, x − x
∗
≥ 0, ∀x ∈ C (1.5)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
14
Do C là nón lồi, x
∗
∈ C nên
x
∗
+ x ∈ C, ∀x ∈ C
Trong bất đẳng thức trên ta thay x bởi x
∗
+ x, ta được
w
∗
, x
∗
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ì
w
∗
, x
∗
= 0, w
∗
∈ F(x
∗
), w
∗
∈ C
.
Vì x
∗
∈ C
nên w
∗
, x
∗
≤ 0, ∀x ∈ C. Ta có
w
∗
, x − x
∗
∗
là nghiệm của bài toán (1.6), tức là:
f(x
∗
) ≤ f(x), ∀x ∈ C.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
15
Để chứng minh x
∗
là nghiệm của bài toán (V I), ta giả sử ngược lại rằng:
∇f(x
∗
), x − x
∗
< 0, ∀x ∈ C.
Khi đó, lấy α > 0 đủ nhỏ, do C là tập lồi nên
y
α
= x
∗
+ α(x − x
∗
) = αx + (1 − α)x
∗
∈ C, ∀x ∈ C.
và
f(y
α
) = f(x
∗
Suy ra
f(x) ≥ f(x
∗
), ∀x ∈ C.
hay x
∗
là nghiệm của bài toán (1.6). ✷
Trong trường hợp f là hàm không khả vi thì ta có cách tiếp cận dựa trên mệnh đề
sau:
Mệnh đề 1.5. Cho f : C → R là hàm lồi, khả dưới vi phân trên C. Khi đó, x
∗
là
nghiệm của bài toán (1.6 ) khi và chỉ khi x
∗
là nghiệm của bài toán bất đẳng thức biến
phân (MV I), với F(x) := ∂f(x).
Chứng minh. Giả sử x
∗
∈ C và w
∗
∈ ∂f(x
∗
) thỏa mãn
w
∗
, x − x
∗
≥ 0, ∀x ∈ C.
Vì w
∗
i
a
là mật độ giao thông của phương tiện i trên đoạn đường a ∈ A. Đặt f là véc tơ có
các thành phần là f
i
a
với i ∈ I và a ∈ A (I là tập hợp các phương tiện giao thông).
•c
i
a
là chi phí khi sử dụng phương tiện giao thông i trên đoạn đường A. Đặt c là véc tơ
có các thành phần là c
i
a
với i ∈ I, a ∈ A.
•d
i
w
là nhu cầu sử dụng loại phương tiện i ∈ I trên tuyến đường w = (O, D) với
O ∈ O, D ∈ D.
Giả sử rằng chi phí giao thông phụ thuộc vào lưu lượng, tức là c = c(f) là một hàm
của f.
•λ
i
w
là mức độ chi phí trên tuyến đường w của phương tiện giao thông i.
•x
i
w
là mật độ giao thông của phương tiện i ∈ I trên tuyến w ∈ O × D.
δ
ap
∀i ∈ I, w ∈ O ×D, (1.8)
trong đó
δ
ap
:=
1 nếu a ∈ p
0 nếu a /∈ p
Với mỗi tuyến đường p nối một điểm nguồn và một điểm đích, đặt
c
i
p
=
a∈A
c
i
a
δ
ap
.
Như vậy, c
i
p
là chi phí khi sử dụng phương tiện i trên tuyến đường p. Đặt d là
véc tơ có thành phần là d
i
w
∗
) khi x
i
p
= 0,
với mỗi i ∈ I và mỗi tuyến đường p. Theo định nghĩa này, tại điểm cân bằng đối với
mọi loại phương tiện giao thông và mọi tuyến đường, chi phí sẽ thấp nhất khi có lưu
lượng giao thông trên tuyến đó. Trái lại, chi phí sẽ không phải thấp nhất. Đặt
K = {(f, d) | ∃ x ≥ 0 sao cho (1.7) và (1.8) đúng}.
Khi đó ta có định lí sau.
Định lí 1.3. Một cặp véc tơ (f
∗
, d
∗
) ∈ K là một điểm cân bằng của mạng giao thông
khi và chỉ khi nó là nghiệm của bài toán bất đẳng thức biến phân sau:
Tìm (f
∗
, d
∗
) ∈ K sao cho
c(f
∗
), λ(d
∗
)
, (f, d) − (f
∗
p
i
n
j=1
x
j
− h
i
(x
i
) (i = 1, ··· , n), (1.9)
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
18
trong đó p(
n
j=1
x
j
) là giá của một đơn vị sản phẩm, phụ thuộc vào tổng sản phẩm,
còn hàm chi phí của một công ty i chỉ phụ thuộc vào mức độ sản xuất của công ty đó.
Đặt U
i
⊂ R, (i = 1, ··· , n) là tập chiến lược của công ty i. Lẽ dĩ nhiên, mỗi công
ty cần xác định cho mình một mức độ sản xuất để đạt được lợi nhuận cao nhất. Tuy
∗
n
) f
i
(x
∗
1
, ··· , x
∗
n
), ∀y
i
∈ U
i
, ∀i = 1, ··· , n.
Trong mô hình cân bằng Cournot cổ điển, hàm chi phí và hàm lợi nhuận của mỗi
công ty là affine có dạng
p
i
(σ) ≡ p(σ) = α
0
− βσ, α
0
≥ 0, β > 0, với σ =
n
i=1
x
i
,
0 β β ··· β
β 0 β ··· β
··· ··· ··· ··· ···
β β β ··· 0
và
α
T
= (α
0
, ··· , α
0
), µ
T
= (µ
1
, ··· , µ
n
).
Theo [9], điểm x
∗
là điểm cân bằng Nash khi và chỉ khi x
∗
là nghiệm của bài toán bất
đẳng thức biến phân:
và
F : C → 2
R
n
là ánh xạ đa trị. Khi đó:
(i) Nếu F đơn điệu ngặt trên C thì bài toán (MV I) có nhiều nhất một nghiệm.
(ii) Nếu F là đơn điệu mạnh, nửa liên tục trên và F (x) lồi, compact, khác rỗng với
mọi x ∈ C, thì bài toán (MV I) có duy nhất nghiệm.
Kết luận chương
Trong chương này, ta nhắc lại các kết quả quan trọng của giải tích lồi, mối quan hệ
giữa bài toán bất đẳng thức biến phân đa trị với các mô hình toán học khác, các khái
niệm về ánh xạ đa trị đơn điệu mạ nh, đơn điệu, g iả đơn điệu, đơn điệu ngặt và các
điều kiện tồn tại nghiệm của bài toán (MV I). Chương này cũng trình bày một cách
chi tiết các ví dụ minh họa cho một vài tính chất đơn điệu, Lipschitz theo khoảng cách
Hausdorff của ánh xạ đa trị.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
20
Chương 2
Phương pháp xấp xỉ trong với điều
kiện Lipschitz
Trong chương này, ta sẽ trình bày phương pháp xấp xỉ trong giải bài toán bất đẳng
thức biến phân (MV I), khi hàm giá F là đa trị giả đơn điệu, Lipschitz trên một tập
lồi đa diện C. Cơ sở của phương pháp này là thay thế dạng toàn phương thông thường
bởi một hàm đặc biệt, đó là sự kết hợp giữa dạng toàn phương thông thường với hàm
chắn dạng logarit để trở thành hàm xấp xỉ trong lồi mạnh. [4]
2.1 Phương pháp hàm phạt điểm trong [1]
Trước hết ta nhắc lại nội dung phương pháp điểm trong giải bài toán tối ưu sau:
min{f(x)|x ∈ D} (P )
trong đó D được xác định như sau:
D := {x ∈ R
D
0
:= {x ∈ R
n
: g
i
(x) < 0, ∀i = 1, , m}
(b) Với mọi dãy {x
k
} ⊂ D
0
hội tụ đến một điểm x ∈ D
0
ta có lim
k
ϕ(x
k
) = +∞ khi
k → +∞.
Hai hàm xấp xỉ trong được sử dụng nhiều, do Fiacco và McCormick đưa ra là
ϕ(x) = −
m
i=1
log(−g
i
(x))
hoặc
ϕ(x) = −
m
.
Đặt
F (x, t) := f(x) + s(t)ϕ(x),
với miền xác định là
C := {(x, t)| x ∈ intD, t > 0}.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
Copyright: Tài liệu đại học ©