S
ố hóa bởi Trung tâm Học liệu
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

VŨ THỊ THU

VỀ TÍNH CO VÀ KHÔNG GIÃN
CỦA ÁNH XẠ NGHIỆM CHO BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN ĐA TRỊ

Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60. 46. 01. 12 Người hướng dẫn khoa học:
GS.TSKH. LÊ DŨNG MƯU


1.1.1 Khơng gian Hilbert . . . . . . . . . . . . . . . . . . 4
1.1.2 Tập lồi, hàm lồi và dưới vi phân . . . . . . . . . . . 6
1.1.3 Ánh xạ đa trị Lipschitz trong khơng gian Hilbert . 8
1.2 Ánh xạ đa trị đơn điệu . . . . . . . . . . . . . . . . . . . . 13
1.2.1 Định nghĩa ánh xạ đa trị đơn điệu . . . . . . . . . . 13
1.2.2 Định nghĩa ánh xạ đơn điệu mạ nh . . . . . . . . . . 15
1.2.3 Định nghĩa ánh xạ đồng bức . . . . . . . . . . . . . 15
1.3 Bài tốn bấ t đẳng thức bi ến phân đa trị . . . . . . . . . . 17
1.3.1 Phát biểu bài t ốn và ví dụ. . . . . . . . . . . . . . 17
1.3.2 Sự tồn tạ i nghiệm của bài t ốn (MVIP) . . . . . . 23
2 Phương pháp ánh xạ co và khơng giãn của ánh xạ nghiệm
cho bài tốn bất đẳng thức biến phân đa trị 26
2.1 Tính co và sự hội tụ của ánh xạ nghiệm . . . . . . . . . . 26
2.1.1 Tính co của ánh xạ nghiệm . . . . . . . . . . . . . 26
2.1.2 Mơ tả thuật tốn và sự hội tụ . . . . . . . . . . . . 33
2.2 Tính khơng giãn và sự hội tụ của ánh xạ nghiệm . . . . . . 37
2.2.1 Tính khơng giãn của ánh xạ nghiệm . . . . . . . . 37
2.2.2 Mơ tả thuật tốn và sự hội tụ . . . . . . . . . . . . 42
Số hóa bởi Trung tâm Học liệu />ii
Kết luận 45
Tài liệu tham khảo 46
Số hóa bởi Trung tâm Học liệu />iii
Lời cảm ơn
Trong suốt q trình làm luận văn, tơi ln nhận được sự hướng dẫn,
chỉ bảo tận tình và giúp đỡ nghiêm túc của GS.TSKH. Lê Dũng Mưu (Viện
Tốn học, Viện Hàn lâm Khoa học và Cơ ng nghệ Việt Nam). Tơi xin chân
thành bày tỏ lòng biết ơn sâu sắc đến Thầy, Thầy đã giành nhiều thời
gian hướng dẫn cũng như giải đáp thắc mắc của Tơi trong suốt q trình
làm luận văn. T hầy đã tạo điều kiện và giúp đỡ Tơi có thêm kiến thức,
khả năng nghiên cứu, chọn lọc và tổng hợp các tài liệu chính cũng như cơ

và đến năm 1980 Defermos đã chỉ ra rằng điểm cân bằng của bài tốn này
là nghiệm của bài tốn bất đẳng thức biến phân. Từ đó bài tốn bất đẳng
thức biến phân được phát tr iển trở thành một cơng cụ hữu hiệu để nghiên
cứu và giải các bài tốn cân bằng trong kinh tế tài chính, vận tải, lý thuyết
trò chơi và nhiều bài tốn khác. Bài tốn bất đẳng thức biến phân đa trị
có quan hệ mật thiết với nhiều bài tốn khác như: bài tốn bù phi tuyến,
bài tốn quy hoạch lồi, bài tốn xác định phương án sản xuất, các bài
tốn đó là một trong những trường hợp riêng của bài to án bất đẳng thức
biến phân đa trị. Gần đây bài tốn bất đẳng thức biến phân đa trị cũng là
một đề tài thu hút được nhiều sự q uan tâm của các nhà nghiên cứu khoa
học vì nó có nhiều vai trò và ứng dụng trong lý thuyết tốn học và các ứng
dụng trong thực tế. Một trong các hướng nghiên cứu quan trọ ng của bài
tốn bất đẳng thức biến phân đa trị là xây dựng phương pháp giải. Thơng
thường các phương pháp giải được chia thành các lo ại sau:
Loại thứ nhất là các phương pháp chuyển bài tốn về hệ phương trình
và dùng các phương pháp thơng dụng như phương pháp Newton, phương
Số hóa bởi Trung tâm Học liệu />2
pháp điểm trong hệ phương trình.
Loại t hứ hai l à phương pháp có tính chất kiểu đơn điệu điển hình của
phương pháp này là các phương pháp gradient sau này được tổng qt
bởi Cohen thành lý thuyết bài tốn phụ, phương pháp điểm gần kề của
Rockafellar, phương pháp hiệu chỉnh của Tikhonov, Các phương pháp này
khá là hiệu q uả, dễ thực hiện trên máy tính nhưng các điều kiện hội tụ chỉ
được đảm bảo dưới các giả thiết khác nha u về tính chất đơn điệu.
Loại t hứ ba là các phương pháp dựa trên kỹ thuật hàm đánh giá. Nội
dung chính của phương pháp này là chuyển bài tốn bất đẳng thức biến
phân đa trị về cực tiểu của hàm chắn và sau đó sử dụng k ỹ thuật tối ưu
trơn hoặc khơng trơn để t ìm cực tiểu của hàm chắn, phương pháp này có
thể giải được bà i tốn với giả thiết rất nhẹ. Tuy nhiên, tốc độ hội tụ của
thuật tốn được đề xuất là chậm và thường chỉ hội tụ với các giả thiết về

Số hóa bởi Trung tâm Học liệu />4
Chương 1
Bài tốn bất đẳng thức biến phân đa
trị
Trong tồn bộ luận văn này, chúng ta sẽ làm việc trên khơng gian Hilbert
thực H. Ta có một số tính chất và định nghĩa cơ bản về khơng gian Hilbert.
Các kiến thức trong chương này được lấy trong tài liệu [1], [2], [3], [4], [5].
1.1 Một số khái n iệm và tính chất cơ bản
1.1.1 Khơng gian Hilbert
Định n ghĩa 1.1. Cho H là m ột khơng gian tuyến tính. Tích vơ hướng xác
định trên H là một ánh xạ được xác định:
., . :H ×H → R
(x, y) → x, y
thỏa mãn các điều k i ện sau:
i. x, y = y, x với mọi x, y ∈ H
ii. x + y, z = x, z + y, z với mọi x, y, z ∈ H
iii. λx, y = λx, y với mọi x, y ∈ H và λ ∈ R
iv. x, x ≥ 0 với m ọi x ∈ H, x, x = 0 ⇔ x = 0
x, y được gọi là t í ch vơ hướng của hai véctơ x và y
Cặp (H, ., .) đư ợc gọi là khơng gian tiề n Hilbert (hay còn gọi l à khơng
gian Unita). Từ định nghĩa trên ta thấy rằng tích vơ hướng là một dạng
song tuyến t ính trên H.
Ví dụ 1.1
Số hóa bởi Trung tâm Học liệu />5
1) Lấy H = R
n
với x = (x
1
, x
2

xác định một tích vơ hướng t rên C
[0,1]
. Khi đó khơng gian này là mộ t khơng
gian tiền Hilbert và thường kí hiệu là C
L
[0,1]
.
Định lí 1.1. Cho H là khơng gian tiền Hil bert, với mọi x, y ∈ H ta ln
có bất đẳng thức sau:
|x, y|
2
≤ x, xy, y
bấ t đẳng th ức này g ọi là bất đẳng thức Schwarz.
Định lí 1.2. Cho H là khơng tiền Hilbert. Khi đó ||x|| = x, x
1/2
, x ∈ H
xác định một chu ẩn t rên H.
Định nghĩa 1.2. Cho H là khơng tiền Hilbert. Khi đó ||x|| = x, x
1/2
, x ∈
H xác định một chuẩn trên H thì H là một khơng gian tuyến tính định
chuẩn. Nếu H là khơng gian đầy đủ thì ta gọ i H là khơng gian H i l bert.
Ví dụ 1.2
1) Nếu H = C
n
với tích vơ hướng xác định bở i hệ thức x, y =
n

i=1
x

Ω
f(x)g( x)dµ , L
2
(Ω) là một khơng g ian hilbert
H.
Số hóa bởi Trung tâm Học liệu />6
Định lí 1.3. Ch o H là khơ ng gian Hilbe rt, khi đó
,  : H × H → R, là một hàm liên tục.
Định lí 1.4. (Đẳng thức hình bình hành)
Với m ọi x, y trong khơn g gi an tiền Hilbe rt H, ta có
||x + y||
2
+ ||x − y||
2
= 2(||x||
2
+ ||y||
2
).
Định lí 1.5. (T í ch vơ hướng sinh bởi chuẩn)
Cho (X, ||||) là một khơng gian tuyến tính định chuẩn trên khơng gian
Hilbert thự c H. Giả sử với mọi x, y ∈ X thỏa mãn
||x + y||
2
+ ||x − y||
2
= 2(||x||
2
+ ||y||
2

Tập domf được gọi là miền hữ u hiệu của f.
Hàm f được gọi là chí nh t hường nếu domf = ∅ v à f(x) > −∞, ∀x ∈ C.
Định nghĩa 1.6. Cho hàm f : H −→ R ∪ {+∞}, C ⊆ H. Khi đ ó hàm f
được gọi là
i) lồi trên C nếu
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y), ∀x, y ∈ C, λ ∈ [0, 1].
ii) lồi chặt trên C nếu
f(λx + (1 − λ)y) < λf(x) + (1 − λ)f(y), ∀x , y ∈ C, x = y, λ ∈ (0, 1).
iii) lồi mạn h với hệ số β > 0 trên C n ếu với mọi x, y ∈ C, λ ∈ (0, 1), ta có
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y) − λ(1 −λ)β||x − y||
2
.
Định nghĩa 1.7. Giả sử f : H −→ R ∪{+∞} là hàm lồi trên tập C ⊆ H
ta định nghĩa dưới vi phân của hàm lồi như s au:
Véc tơ w ∈ H được gọi là dưới đạo hàm (gradient) của f tại x
◦
∈ C ⊆ H
nếu
w, x −x
◦
 + f(x
◦
) ≤ f(x), ∀x ∈ C.
Tập tất cả các dưới đạo hàm (gradient) của hàm f tại x
◦
được gọi là dưới
vi phân của f tại x
◦
, kí hiệu là ∂f (x
◦

∗
| x
∗
, x −x
◦
 ≤ δ
C
(x), ∀x ∈ H}.
Nếu x /∈ C, thì δ
C
(x) = +∞ nên bất đẳng thức
x
∗
, x −x
◦
 ≤ δ
C
(x), ∀x ∈ H ln đúng.
Do đó
∂δ
C
(x
◦
) = {x
∗
| x
∗
, x − x
◦
 ≤ 0, ∀x ∈ C}

−1
: Y ⇉ X của ánh xạ đa trị F : X ⇉ Y được xác định
bở i cơng thức:
F
−1
(y) = {x ∈ X : y ∈ F ( x)}, y ∈ Y.
Số hóa bởi Trung tâm Học liệu />9
Nếu M ⊂ X là tập con cho trước thì hạn chế của ánh xạ F trên M (kí hiệu
F |
M
) là ánh xạ đa trị F |
M
: M ⇉ Y được cho bởi: F |
M
= F (x), ∀x ∈ M.
Ví dụ 1.9
1) Xét phương trình đa thức x
n
+ a
1
x
n−1
+ . . . + a
n−1
x + a
n
= 0
Trong đó n ∈ N là số ngun dương và a
i
∈ R, (i = 1, n) là các hệ số thực




(x, y) ∈ H | y =
1
|x|
, nếu x = 0
0 ×(0, +∞), nếu x = 0
là một ánh xạ đa trị từ X vào H.
Với ánh xạ đa trị F : X ⇉ Y , ta xác định đồ thị và m iền hữu hiệu của
ánh xạ F tương ứng bằng các cơng t hức
graphF := {(x, y) ∈ X ×Y | y ∈ F(x)},
domF := {x ∈ X | F (x) = ∅}
Định nghĩa 1.10. (Tí nh liên t ục)
Ánh xạ đa trị F : H → 2
H
đượ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 ⊂ 2
H
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.
ii) Nửa liên tục dưới tại ¯x ∈ domF nếu với mọi tập mở V ⊂ 2
H
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.
iii) Đóng trên W , nếu với mỗi cặp điểm của dãy u
k
→ u, q
k




0, nếu − 1 < x < 0 ,
[−1, 1] , nếu x = 0,
1, nếu 0 < x < 1.
Do đó F (x) ⊆ (a, b) với mọi x ∈ (−1, 1).
Như vậy, F là ánh xạ nửa l iên tục trên trên H = R.
2) Ánh xạ đa trị F : H → 2
H
thỏa mãn:
F (x ) =

[0, 1], nếux = 0,
0, nếux = 0.
Khi đó F nửa liên tục dưới tại ¯x = 0.
Thật vậy, với mọi tập mở (a, b) thỏa mãn (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
,

a∈A
inf
b∈B
||a −b||
d(B, A) = sup
b∈B
d(b, A) = sup
b∈B
inf
a∈A
||a −b||
Định nghĩa 1.12. (Định nghĩa á nh xạ đa trị liên tụ c Lipschitz)
Cho ∅ = C ⊆ H, ánh xạ đa trị F : R
2
→ 2
R
2
được gọi là li ên tục
Lipschitz trên C ⊆ H với hệ số L > 0 (Được viết tắt là L- Lip s chitz) nếu
ρ(F (x), F (y) ) ≤ L||x − y||, ∀x, y ∈ C.
Khi
L < 1 thì F được gọi là á nh xạ co trên C.
L = 1 thì F được gọi là á nh xạ kh ơng giãn trên C.
Ví dụ 1.12
Cho C := {(x, 0) | x ≥ 0} ⊆ H và ánh xạ F : R
2
→ 2
R
2
xác đị nh bởi

(x
′
,y
′
)∈F (x
′
,0)

(x −x
′
)
2
+ (y −y
′
)
2
= max
(x,y)∈F (x,0)
|x −x
′
|
= ||(x, 0) − (x
′
, 0)||
d(F (x
′
, 0); F (x, 0)) = max
(x
′
,y

≤
√
2 max
(x
′
,y
′
)∈F (x
′
,0)
|x −x
′
|
=
√
2|x − x
′
|
=
√
2||(x, 0) −(x
′
, 0)||.
Do đó:
ρ(F (x, 0); F (x
′
, 0)) ≤
√
2||(x, 0) −(x
′

∗
∈ F (x
∗
) mà ρ(x
∗
, a) ≤
d(a, F (a))
α −θ
.
Số hóa bởi Trung tâm Học liệu />13
1.2 Ánh xạ đa t r ị đ ơn điệu
1.2.1 Định nghĩa ánh xạ đa trị đơn điệu
Định nghĩa 1.13. Với C ⊆ H, á nh xạ đa trị F : C −→ 2
C
, được gọi là
i) đơn điệu trên C, nếu
w − w
′
, x −x
′
 ≥ 0, ∀x, x
′
∈ C, w ∈ F(x), w
′
∈ F (x
′
)
Khi F đơn trị, bất đẳng thức trên trở thành
F (x) − F(x
′

 ≥ 0.
Ví dụ 1.13
1) Ánh xạ đa trị F được định nghĩa
F (x , 0) := {(x, y) | 0 ≤ y ≤ x}
là đơn điệu trên C = {(x , 0) | x ≥ 0}.
Thật vậy,
Với mọi (x, 0), (x
′
, 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

f(x
′
) ≥ f(x) + v, x
′
− x
với các giá trị f(x) và f (x
′
) hữu hạn. Cộ ng các bất đẳng thức trên với
nhau ta được
0 ≥ v
′
, x − x
′
 + v, x
′
− x
hay
v −v
′
, x −x
′
 ≥ 0, ∀x, x
′
∈ dom∂f, v ∈ ∂f(x), v
′
∈ ∂f (x
′
).
Vậy ∂f là đơn điệu.
∗ Tính chất (Phép bảo tồn tí nh đơn điệu).

(w
′
), theo
định nghĩa ánh xạ đa trị ngược thì w ∈ T (x) và w
′
∈ T (x
′
), ta có
x −x
′
, w − w
′
 = w − w
′
, x −x
′
 ≥ 0, ∀x ∈ T
−1
(w), x
′
∈ T
−1
(w
′
).
Vậy T
−1
là ánh xạ đơn điệu.
ii) Với λ > 0, ∀x, x
′

) = {u
′
+ w
′
| u
′
∈ T (x
′
), w
′
∈ T
′
(x
′
)}.
Số hóa bởi Trung tâm Học liệu />15
Ta có
v −v
′
, x −x
′
 = u + w −u
′
− w
′
, x − x
′

= u − u
′

− γx
′
), x − x
′
 ≥ 0, ∀v ∈ F (x), v
′
∈ F (x
′
).
Bất đẳng thức trên có thể đư ợc viết dưới dạng sau:
v −v
′
, x − x
′
 ≥ γ||x −x
′
||
2
, ∀v ∈ F(x), v
′
∈ F (x
′
).
Chú ý nếu F là đơn điệu mạnh thì F đơn điệu ngặt.
Ví dụ 1.14
Cho C = {(x, 0) | x ≥ 0} và ánh xạ F : R
2
−→ 2
R
2

−→ 2
R
2
, với C = {(x, 0) | x ≥ 0} ⊆ H xác định bởi
F (x , 0) := {(x, y) | 0 ≥ y ≥ x}
Khi đó, F đồ ng bức trên C với hệ số δ = 1/2.
Thật vậy, theo Ví dụ 1.13 ta đã biết ánh xạ này Lipschitz trên C với hệ số
L =
√
2.
Lấy tùy ý (x, 0), (x
′
, 0) ∈ C, (x, y) ∈ F(x), (x
′
, y
′
) ∈ F(x
′
). Ta có
(x, y) − (x
′
, y
′
), (x, 0) − (x
′
, 0) = |x −x
′
|
2
= ||(x, 0) − (x

Mệnh đề 1.1. Nếu F : H −→ 2
H
là ánh xạ đồng bức thì F là ánh xạ
Lipschitz.
Chứng minh.
Giả sử ánh xạ F đồng bức với hệ số δ > 0 trên C ⊆ H, khi đó với
∀x, x
′
∈ C, v ∈ F(x), v
′
∈ F (x
′
) ta có
δρ
2
(F ( x), F (x
′
)) ≤ v − v
′
, x − x
′

≤ ||v − v
′
||||x −x
′
||.
Suy ra
δρ
2

||
= ||x − x
′
||d(F (x), F (x
′
)).
Số hóa bởi Trung tâm Học liệu />17
Tương tự thì ta có:
δρ
2
(F ( x), F (x
′
)) ≤ ||x −x
′
|| sup
v
′
∈F (x
′
)
inf
v∈F (x)
||v −v
′
||
= ||x − x
′
||d(F (x
′
), F (x)).

′
∈ C và
v ∈ F(x), v
′
∈ F (x
′
), ta có
v −v
′
, x − x
′
 ≥ δ||x − x
′
||
2
≥
δ
L
2
ρ
2
(F ( x), F (x
′
)).

1.3 Bài tốn bất đẳng thức biến p hân đa trị
Trong phần này, ta xét hai phần: Phần một ta phát biểu bài tốn bất
đẳng thức biến phân đa trị, các trường hợp riêng và các bài tốn ứng dụng
trong thực tế của bài tốn bất đảng thức biến phân đa trị.
Phần hai ta nêu về sự tồn tại nghiệm và các tính chất nghiệm của bài tốn

Bài tốn bất đẳng thức biến phân đa trị (MVIP) có quan hệ mật thiết
với nhiều bài tốn khác của giải tích phi tuyến như: Bài tốn bù phi tuyến,
bài tốn điểm bất động, bài tốn quy hoạch lồi, . Ngồi ra, còn có nhiều
ứng dụng trong thực tế như: Bài tốn xác định phương án sản xuất, bài
tốn cân bằng mạng giao thơng,
Dưới đây ta xét một vài trường hợp riêng điển hình của bài tốn bất đẳng
thức biến phân đa trị:
Bài tốn điểm bất động Kakutani
Cho C là tập tùy ý lồi, đóng tro ng khơng gian Hilbert H và T : C −→ 2
C
là ánh xạ đa trị. Bà i tốn điểm bất động của ánh xạ đa trị F được phát
biểu như sau:
Tìm x
∗
∈ C : x
∗
∈ T (x
∗
). (1.1)
Chú ý, nếu F là ánh xạ đơn trị thì bài tốn điểm bất động Kakutani trở
thành bài tốn điểm bất động Brouwer sau:
Tìm x
∗
∈ C : x
∗
= T (x
∗
).
Ta sẽ thấy mối quan hệ của bài tốn (MVIP) và bài tốn điểm bất động
(1.1) thơng qua mệnh đề sau:

) : w
∗
= x
∗
− ǫ
∗
. Ta có
x
∗
− ǫ
∗
, x −x
∗
 ≥ 0, ∀x ∈ C.
Cho x = ǫ
∗
ta được
||x
∗
− ǫ
∗
|| ≤ 0
Suy ra x
∗
= ǫ
∗
hay x
∗
∈ T(x
∗

∗
là nghiệm của bài tốn bất đẳng thức biến phân
(MVIP) và w
∗
∈ F (x
∗
) thì
w
∗
, x − x
∗
 ≥ 0, ∀x ∈ C (1.2)
Do C là nón lồi, x
∗
∈ C nên x
∗
+ x ∈ C. Trong bất đẳng thức (1.2) ta
thay x bởi x
∗
+ x, ta được
w
∗
, x
∗
+ x − x
∗
 = w
∗
, x ≥ 0, ∀x ∈ C
Suy ra w