ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
HÀ THỊ NGỌC BÍCH
VỀ SỰ TỒN TẠI NGHIỆM CỦA BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN
Chuyên ngành: Toán ứng dụng
Mã số: 8460112
LUẬN VĂN THẠC SĨ TOÁN HỌC
CÁN BỘ HƯỚNG DẪN KHOA HỌC
TS. Nguyễn Song Hà
THÁI NGUYÊN - 2020
i
LỜI CẢM ƠN
Luận văn này được hoàn thành tại trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn của Tiến sĩ Nguyễn Song Hà. Tôi xin bày tỏ
lòng kính trọng và sự biết ơn sâu sắc tới người thầy đã dành nhiều thời gian trực tiếp hướng dẫn cũng như giải đáp những thắc mắc của tôi trong suốt
quá trình làm và hoàn thiện luận văn. Qua đây, tôi cũng xin được gửi lời cảm
ơn tới các thầy cô giáo tại Trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình giảng dạy và giúp đỡ tôi hoàn thành khóa học. Cuối cùng, xin gửi lời cảm ơn tới Ban giám hiệu, tập thể giáo viên trường THPT Nam Phù Cừ, nơi tôi đang công tác đã động viên và tạo điều kiện thuận lợi cho tôi trong
thời gian tôi học tập và làm luận văn tốt nghiệp.
Tác giả Hà Thị Ngọc Bích
ii
Mục lục
Trang b…a ph(cid:246) i
Lời cảm ơn ii
Mục lục iii
Danh mục ký hiệu và chữ viết tắt iv
Danh sách bảng v
Mở đầu 1
Chương 1. Kiến thức chuẩn bị
1.1. Một số vấn đề về điểm bất động và phép chiếu mêtric . . . . . 1.2. Dưới vi phân hàm lồi . . . . . . . . . . . . . . . . . . . . . . . 1.3. Ánh xạ đơn điệu và liên tục . . . . . . . . . . . . . . . . . . . 1.4. Ánh xạ KKM . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 12 16 21
Chương 2. Sự tồn tại nghiệm của bài toán bất đẳng thức biến
phân trong Rn 2.1. Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 24 24
2.2. Sự tồn tại nghiệm trường hợp miền ràng buộc là tập compact 2.3. Sự tồn tại nghiệm trường hợp miền ràng buộc không compact 2.4. Một vài phương pháp xấp xỉ nghiệm bài toán (VIP) . . . . . . 28 31 40
Kết luận chung và đề nghị 51
Tài liệu tham khảo 52
iii
Danh mục ký hiệu và chữ viết tắt
Rn Không gian thực hữu hạn chiều
co(C) Bao lồi của tập C
cl(C) Bao đóng của tập C
C\D Phần bù của tập hợp D trong C
(cid:104)x, y(cid:105) Tích vô hướng của hai véctơ x và y
(cid:107)x(cid:107) Chuẩn của véctơ x
∀x Với mọi x
F : X → Y Ánh xạ đơn trị từ X vào Y
F : X ⇒ Y Ánh xạ đa trị từ X vào Y
Phép chiếu mêtric phần tử x lên tập C PC(x)
α ↓ 0 α giảm dần về 0
∇f (x) Gradient của ánh xạ f tại x
∂f (x) Dưới vi phân của ánh xạ f tại x
xn → x Dãy {xn} hội tụ đến x khi n → +∞
(VIP) Bài toán bất đẳng thức biến phân
(MVIP) Bài toán bất đẳng thức biến phân Minty
Fix(T ) Tập điểm bất động của ánh xạ T
KKM Knaster-Kuratowski-Mazurkiewicz
iv
Danh sách bảng
2.1 Kết quả tính toán cho phương pháp (2.14) với ρ = 1/4 . . . . 43
2.2 Kết quả tính toán cho phương pháp (2.14) tương ứng với các
giá trị ρ thay đổi 43
giá trị λ thay đổi
45 49
. . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Kết quả tính toán cho phương pháp (2.16) tương ứng với các . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Kết quả tính toán cho phương pháp (2.17) với τ = 1/4 . . . . 2.5 Kết quả tính toán cho phương pháp (2.17) tương ứng với các . . . . . . . . . . . . . . . . . . . . . . . . . giá trị τ thay đổi 50
1
Mở đầu
Bài toán bất đẳng thức biến phân được hình thành từ những công trình nghiên cứu của Lion, Stampacchia và Minty [1, 6] vào những năm 50 của
thế kỉ trước. Bài toán này có liên hệ mật thiết với nhiều bài toán lí thuyết như: bài toán tối ưu, bài toán cân bằng, bài toán điểm bất động, bài toán
minimax, bài toán điểm yên ngựa, phương trình với toán tử đơn điệu, bài
toán biên có dạng của phương trình đạo hàm riêng ... và đóng vai trò rất quan trọng trong nghiên cứu nhiều lĩnh vực thực tiễn như: công nghệ thông tin và truyền thông, giao thông, kinh tế, y học, quân sự ... Vì lẽ đó, trong suốt hơn 70 mươi năm qua, bài toán này đã và đang thu hút được sự quan tâm nghiên cứu của nhiều nhà toán học trong và ngoài nước.
Những nghiên cứu về bài toán này chủ yếu theo ba hướng chính: Một là, nghiên cứu các tính chất định tính của bài toán về sự tồn tại và tính duy nhất nghiệm, tính ổn định nghiệm, độ nhạy nghiệm hay tính chất tôpô của tập nghiệm. Hai là, nghiên cứu đề xuất các thuật toán hoặc phương pháp giải số hữu hiệu tìm nghiệm xấp xỉ của bài toán. Ba là, nghiên cứu ứng dụng lí thuyết bài toán này vào giải quyết các mô hình thực tiễn.
Mục đích chính của luận văn này là nghiên cứu và trình bày lại có hệ thống về sự tồn tại nghiệm của bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều cùng một số phương pháp xấp xỉ nghiệm.
Với mục tiêu như vậy, ngoài phần mở đầu, luận văn gồm có hai chương, kết luận và tài liệu tham khảo. Chương 1, hệ thống lại một số kiến thức cơ bản của giải tích lồi và giải tích hàm nhằm phục vụ cho việc trình bày các nội dung chính ở phần sau của luận văn. Chương 2, dành để giới thiệu lớp bài toán nghiên cứu cùng các kết quả tồn tại nghiệm được xây dựng trên
tính chất loại đơn điệu của ánh xạ mục tiêu và cấu trúc tôpô của miền ràng buộc. Phần cuối chương, chúng tôi trình bày ba phương pháp chiếu (phương
pháp chiếu gradient, phương pháp chiếu lai ghép và phương pháp chiếu tăng
cường) tìm nghiệm xấp xỉ của bài toán cùng các ví dụ số minh họa cụ thể.
2
Chương 1
Kiến thức chuẩn bị
Trong chương này, chúng tôi hệ thống lại một số kiến thức cơ bản phục vụ cho việc trình bày các nội dung chính ở phần sau của luận văn. Cấu trúc
của chương được chia thành ba phần: Mục 1.1 chúng tôi trình bày một số nội dung cơ bản về lý thuyết điểm bất động và phép chiếu mêtric trên tập con
lồi khác rỗng trong không gian hữu hạn chiều. Mục 1.2 trình bày một số khái niệm và tính chất cơ bản về dưới vi phân hàm lồi. Các khái niệm về ánh xạ loại đơn điệu và liên tục được cụ thể hóa trong Mục 1.3. Phần cuối chương, Mục 1.4 dùng để giới thiệu về lớp ánh xạ đa trị KKM và nguyên lí ánh xạ KKM. Đây là công cụ chính để chứng minh các kết quả tồn tại nghiệm trong Chương 2.
1.1. Một số vấn đề về điểm bất động và phép chiếu mêtric
1 + x2
2 + ... + x2 n.
Giả sử Rn là không gian Euclide n chiều, tích vô hướng và chuẩn trên không gian này được kí hiệu lần lượt là (cid:104)., .(cid:105) và (cid:107).(cid:107). Tích vô hướng của hai véctơ x = (x1, x2, ..., xn) ∈ Rn và y = (y1, y2, ..., yn) ∈ Rn xác định bởi (cid:104)x, y(cid:105) = x1y1 + x2y2 + ... + xnyn và chuẩn của véctơ x = (x1, x2, ..., xn) ∈ Rn tương ứng sinh bởi tích vô hướng này là (cid:107)x(cid:107) = (cid:112)x2
Định nghĩa 1.1. Tập C ⊆ Rn được gọi là tập lồi nếu với mọi x, y ∈ C và với mọi λ ∈ [0, 1] ta có
λx + (1 − λ)y ∈ C.
Hay nói cách khác, tập C ⊆ Rn là tập lồi nếu nó chứa mọi đoạn thẳng nối hai điểm bất kì thuộc nó.
Ví dụ 1.1. Trong không gian Rn, các tập hợp
S = {x = (x1, x2, ..., xn) ∈ Rn : (cid:107)x − x0(cid:107) ≤ r},
Hα = {x = (x1, x2, ..., xn) ∈ Rn : (cid:104)a, x(cid:105) ≤ α},
3
∆ = {x = (x1, x2, ..., xn) ∈ Rn : (cid:104)A, x(cid:105) ≤ b}, trong đó x0 ∈ Rn, r là số thực dương, a ∈ Rn, α ∈ R, A là ma trận thực cỡ m × n và b ∈ Rm, tương ứng là hình cầu tâm x0 với bán kính r, nửa không gian đóng, hình đa diện. Các tập hợp này là các tập lồi.
Ví dụ 1.2. Một số ví dụ đơn giản về tập hợp không là tập lồi trong không gian R2 và R3 là
1 + x2
2 > 1},
C1 = {x = (x1, x2) ∈ R2 : x2
C2 = {x = (x1, x2) ∈ R2 : x1x2 > 1},
1 + x2
2},
C3 = {x = (x1, x2, x3) ∈ R3 : x3 = x2
C4 = {x = (x1, x2, x3) ∈ R3 : |x1| + |x2| + |x3| = 1}.
Một số tính chất cơ bản về tập lồi được phát biểu trong mệnh đề sau.
Mệnh đề 1.1. Trong không gian Rn, ta có các khẳng định sau:
(i) Giao của một họ tùy ý các tập lồi là tập lồi.
(ii) Nếu C là tập lồi thì αC cũng là tập lồi với mọi số thực α.
(iii) Tổng của hai tập lồi là tập lồi.
(iv) Tích Descartes của hai tập lồi là tập lồi.
(v) Ảnh và nghịch ảnh của một tập lồi qua một phép biến đổi tuyến tính là
tập lồi.
i∈I
Chứng minh. (i) Giả sử {Ci}, i ∈ I là một họ tùy ý các tập lồi, ở đây I là tập (cid:92) chỉ số nào đó. Khi đó, với mọi x, y ∈ Ci và với mọi λ ∈ [0, 1] ta có:
∀i ∈ I. x, y ∈ Ci,
Vì Ci là tập lồi nên
∀i ∈ I. λx + (1 − λ)y ∈ Ci,
i∈I
Từ đây suy ra (cid:92) λx + (1 − λ)y ∈ Ci.
4
i∈I
(cid:92) Hay nói cách khác, Ci là tập lồi.
(ii) Lấy tùy ý hai phần tử x, y ∈ αC và λ ∈ [0, 1]. Khi đó, x và y tương
ứng có dạng x = αu và y = λv với u, v ∈ C. Do C lồi nên λu + (1 − λ)v ∈ C. Điều này dẫn đến
λx + (1 − λ)y = λ(αu) + (1 − λ)(αv) = α[λu + (1 − λ)v] ∈ αC.
Do đó, αC là tập lồi.
(iii) Giả sử C và D là hai tập lồi. Lấy tùy ý hai phần tử x, y ∈ C + D và
λ ∈ [0, 1]. Khi đó, x và y lần lượt có dạng x = u + v và y = w + z, trong đó u, w ∈ C và v, z ∈ D. Do C, D lồi nên λu+(1−λ)w ∈ C và λv +(1−λ)z ∈ D.
Từ đó suy ra
λx + (1 − λ)y = λ(u + v) + (1 − λ)(w + z)
= [λu + (1 − λ)w] + [λv + (1 − λ)z] ∈ C + D.
Vì vậy, C + D là tập lồi.
(iv) Giả sử H và K là hai tập lồi. Lấy tùy ý hai phần tử x = (u, v) ∈
H × K, y = (w, z) ∈ H × K và λ ∈ [0, 1]. Từ tính lồi của H, K suy ra λu + (1 − λ)w ∈ H và λv + (1 − λ)z ∈ K. Mặt khác, để ý rằng
λx + (1 − λ)y = (λu, λv) + ((1 − λ)w, (1 − λ)z)
= (λu + (1 − λ)w, λv + (1 − λ)z) ∈ H × K.
Vì thế, ta có H × K là tập lồi.
(v) Giả sử f là một toán tử tuyến tính, C và D là các tập lồi. Khi đó,
∀x, y ∈ f (C), ∀λ ∈ [0, 1] ta có
λx + (1 − λ)y = λf (u) + (1 − λ)f (v) = f (λu + (1 − λ)v),
ở đây, u, v ∈ C và x = f (u), y = f (v) ∈ f (C). Vì C lồi nên λu + (1 − λ)v ∈ C
và vì thế suy ra λx + (1 − λ)y ∈ f (C). Hay nói cách khác ảnh của C qua phép biến đổi f là tập lồi.
Bây giờ, nếu x, y ∈ f −1(D) thì f (x) ∈ D và f (y) ∈ D. Vì D lồi nên
f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y) ∈ D.
5
Điều này dẫn đến
λx + (1 − λ)y ∈ f −1(D).
Do đó, f −1(D) là tập lồi.
m (cid:88)
Định nghĩa 1.2. Véctơ x ∈ Rn được gọi là tổ hợp lồi của các véctơ xi ∈ Rn
i=1
m (cid:88)
(i = 1, 2, · · · , m) nếu tồn tại λi ≥ 0 (i = 1, 2, · · · , m) với λi = 1 sao cho
i=1
x = λixi.
Mệnh đề 1.2. Cho C ⊂ Rn là tập lồi và x1, x2, · · · , xm ∈ C. Khi đó, C chứa tất cả các tổ hợp lồi của x1, x2, · · · , xm.
Chứng minh. Ta chứng minh quy nạp theo m.
Trường hợp m = 2, ta có
λ1x1 + λ2x2 ∈ C,
vì C là tập lồi. Do đó, kết luận của mệnh đề là đúng trong trường hợp này.
k+1 (cid:88)
Giả sử khẳng định của mệnh đề đúng với m = k ≥ 2. Ta cần chứng minh
i=1
k+1 (cid:88)
x = λixi ∈ C.
i=1
với λi ≥ 0, i = 1, 2, · · · , k + 1, λi = 1.
Thật vậy, nếu λk+1 = 1 thì λi = 0 với mọi 1 ≤ i ≤ k. Do đó, ta nhận được
x = λk+1xk+1 = xk+1 ∈ C.
Bây giờ, giả sử λk+1 < 1. Khi đó, ta thấy
≥ 0, ∀i = 1, 2, · · · , k 1 − λk+1 = λ1 + · · · + λk > 0, λi 1 − λk+1
k (cid:88)
và
i=1
= 1. λi 1 − λk+1
6
k (cid:88)
Do đó, theo giả thiết quy nạp ta có
i=1
k+1 (cid:88)
y = ∈ C. λixi 1 − λk+1
i=1
Từ đây suy ra x = λixi = (1 − λk+1)y + λk+1xk+1 ∈ C. Ta có điều cần
chứng minh.
Định nghĩa 1.3. Cho C ⊆ Rn. Giao của các tập con lồi chứa C được gọi là bao lồi của tập C và kí hiệu là co(C).
Nhận xét 1.1. co(C) là một tập lồi (Mệnh đề 1.1) và đó là tập lồi nhỏ nhất
chứa C. Nếu C là tập lồi thì co(C) = C. Hơn nữa, co(C) trùng với tập tất cả các tổ hợp lồi của C, tức là x ∈ co(C) khi và chỉ khi x biểu diễn được
m (cid:88)
m (cid:88)
dưới dạng
i=1
i=1
x = λixi, λi ∈ [0, 1], λi = 1, xi ∈ C.
Thật vậy, vì C ⊆ co(C) nên co(C) chứa tất cả các tổ hợp của C (Mệnh đề 1.2). Mặt khác, tập tất cả các tổ hợp lồi của C là lồi và chứa C nên nó
chứa co(C).
Định nghĩa 1.4. Tập con C ⊆ Rn được gọi là:
(i) tập bị chặn nếu với mọi x ∈ C đều tồn tại số thực dương M sao cho
(cid:107)x(cid:107) ≤ M .
(ii) tập đóng nếu với mọi dãy {xn} ⊆ C, xn → x thì ta đều có x ∈ C.
(iii) tập compact nếu với mọi dãy {xn} ⊆ C đều tồn tại một dãy con {xnk}
thỏa mãn xnk → x và x ∈ C.
Mệnh đề 1.3. [1, 2] Trong Rn, ta có các khẳng định sau:
(i) Tập con đóng của một tập compact là tập comapct.
(ii) Một tập là compact khi và chỉ khi tập đó đóng và bị chặn.
Định nghĩa 1.5. Cho C là một tập con khác rỗng của Rn và F : C → C là một ánh xạ xác định trên C. Điểm x ∈ C được gọi là điểm bất động của
7
F nếu F (x) = x. Tập tất các điểm bất động của ánh xạ F được kí hiệu là Fix(F ), tức là
Fix(F ) = {x ∈ C : F (x) = x}.
Ví dụ 1.3. Cho C = [0, 1] ⊂ R. Nếu ánh xạ F xác định bởi F (x) = 1 − x thì F có duy nhất điểm bất động và Fix(F ) = {1/2}, nếu ánh xạ F xác định bởi F (x) = x2 thì F có hai điểm bất động và Fix(F ) = {0, 1}, nếu ánh xạ F xác định bởi F (x) = x thì F có vô số điểm bất động và Fix(F ) = [0, 1]. Tuy nhiên, nếu ánh xạ F xác định bởi
, cos(x) nếu 0 ≤ x < F (x) = 1 2 ≤ x ≤ 1, nếu 0 1 2
thì F không có điểm bất động.
2, x1) thì F có hai điểm
2 + 1, x4
3 + 1) thì F không
(cid:17) thì F có duy , , Ví dụ 1.4. Xét trường hợp tập C = R3. Với mỗi x = (x1, x2, x3) ∈ C, khi đó ta có: Nếu ánh xạ F : R3 → R3 xác định bởi F (x) = (cid:16)x1 2 x2 3 x3 4
nhất điểm bất động và Fix(F ) = {(0, 0, 0)}. Nếu ánh xạ F : R3 → R3 xác định bởi F (x) = (−x3, x4 bất động và Fix(F ) = {(0, 0, 0), (0, 1, 0)}. Nếu ánh xạ F : R3 → R3 xác định bởi F (x) = (x1, 1, x3) thì F có vô số điểm bất động và Fix(F ) = R × {1} × R. Nếu ánh xạ F : R3 → R3 xác định bởi F (x) = (x1, x2 có điểm bất động.
Định nghĩa 1.6. Cho C là một tập con khác rỗng của Rn và F : C → Rn là một ánh xạ xác định trên C. Ánh xạ F được gọi là L-liên tục Lipschitz nếu tồn tại L ≥ 0 sao cho
(cid:107)F (x) − F (y)(cid:107) ≤ L(cid:107)x − y(cid:107) ∀x, y ∈ C.
Bất đẳng thức trên đúng với 0 ≤ L < 1 thì F được gọi là ánh xạ co còn nếu
L = 1 thì F được gọi là ánh xạ không giãn.
x (hoặc F (x) = cos(x)) Ví dụ 1.5. Ánh xạ F : R → R xác định bởi F (x) = 1 2 là ánh xạ co (tương ứng, là ánh xạ không giãn).
8
Ánh xạ F : R2 → R2 xác định bởi F (x) = Ax (hoặc F (x) = Ax) với 1 3 1 √ 2 (cid:32) (cid:33)
là ánh xạ co (tương ứng, là ánh xạ không giãn). A = 1 1 −1 1
Định lí 1.1. [6] (Nguyên lí ánh xạ co)
Nếu ánh xạ F : Rn → Rn là ánh xạ co thì F có duy nhất điểm bất động.
Nhận xét 1.2. Định lí trên nói chung là không còn đúng trong trường hợp F là ánh xạ không giãn. Chẳng hạn, tính duy nhất của điểm bất động không còn bảo đảm với ánh xạ F : Rn → Rn xác định bởi F (x) = x vì trong trường hợp này Fix(F ) = Rn. Ngoài ra, điều kiện ánh xạ co chỉ là điều kiện cần. Chẳng hạn, F : R → R xác định bởi F (x) = sin(x) là ánh xạ không giãn và F có duy nhất điểm bất động với Fix(F ) = {0}.
Định lí 1.2. [6] (Brouwer)
Cho F : S → S là một ánh xạ liên tục trên hình cầu đóng S ⊂ Rn. Khi đó,
ánh xạ F có ít nhất một điểm bất động.
Nhận xét 1.3. Nếu F là một ánh xạ liên tục trên hình cầu đóng S ⊂ Rn vào chính nó thì tập điểm bất động của F có thể không duy nhất. Chẳng hạn, xét hình cầu đóng S = {x ∈ R : |x| ≤ 1} và ánh xạ F : S → S xác định bởi
1 + 2x nếu − 1 ≤ x < 0, F (x) = nếu 0 ≤ x ≤ 1. 1
Khi đó, dễ thấy rằng F là ánh xạ liên tục trên S và Fix(F ) = {−1, 1}.
Hơn nữa, điều kiện F liên tục chỉ là điều kiện cần. Thật vậy, ta xét ánh
xạ F : S → S sau đây
0 nếu − 1 ≤ x < 1, F (x) = 1 nếu x = 1.
Khi đó, dễ thấy rằng ánh xạ F không liên tục trên S nhưng Fix(F ) = {0, 1}.
Định lí 1.3. [6] (Brouwer)
Cho C là tập con lồi compact trong không gian Rn và F : C → C là ánh
xạ liên tục. Khi đó, ánh xạ F có điểm bất động.
9
Định nghĩa 1.7. Cho C là tập con khác rỗng trong không gian Rn. Khi đó với mỗi x ∈ Rn, ánh xạ PC : Rn → C thỏa mãn điều kiện
(cid:107)x − z(cid:107). (cid:107)x − PC(x)(cid:107) = inf z∈C
gọi là phép chiếu mêtric trên Rn và y = PC(x) được gọi là hình chiếu của x trên C.
Sự tồn tại và tính duy nhất của phép chiếu mêtric được phát biểu trong
mệnh đề dưới đây.
Mệnh đề 1.4. [2]
Cho C là tập con lồi đóng khác rỗng trong không gian Rn. Khi đó với mỗi
x ∈ Rn tồn tại duy nhất một phần tử y ∈ C sao cho
(cid:107)x − z(cid:107). (cid:107)x − y(cid:107) = inf z∈C
(cid:107)x − z(cid:107) > 0 và tồn tại một dãy {yn} ⊂ C sao cho Chứng minh. Nếu x ∈ C thì chọn y = x. Nếu x /∈ C, khi đó vì C đóng nên d := inf z∈C
(cid:107)x − yn(cid:107) → d.
Để ý rằng
(cid:107)yn − ym(cid:107)2 = (cid:107)(x − yn) − (x − ym)(cid:107)2
x − = 2(cid:107)x − yn(cid:107)2 + 2(cid:107)x − ym(cid:107)2 − 4
= 2(cid:107)x − yn(cid:107)2 + 2(cid:107)x − ym(cid:107)2 − (cid:107)2x − (yn + ym)(cid:107)2 (cid:13) 2 yn + ym (cid:13) (cid:13) 2 (cid:13) ∀m, n ∈ N, (cid:13) (cid:13) (cid:13) (cid:13) ≤ 2(cid:107)x − yn(cid:107)2 + 2(cid:107)x − ym(cid:107)2 − 4d2,
(vì C là tập lồi nên ∈ C). Cho m, n → ∞ trong bất đẳng thức trên yn + ym 2 ta nhận được
(cid:107)yn − ym(cid:107) → 0. Điều này suy ra {yn} là dãy Cauchy trong không gian đầy đủ Rn. Do đó, tồn tại giới hạn của dãy trên và giả sử rằng
yn → y.
10
Vì C là tập đóng nên y ∈ C. Hơn nữa, ta lại có
(cid:107)x − yn(cid:107) → (cid:107)x − y(cid:107).
Từ đó dẫn đến d = (cid:107)x − y(cid:107).
Cuối cùng, giả sử tồn tại z ∈ C thỏa mãn (cid:107)x − z(cid:107) = d. Khi đó, ta có
(cid:107)y − z(cid:107)2 = (cid:107)(x − y) − (x − z)(cid:107)2
= 2(cid:107)x − y(cid:107)2 + 2(cid:107)x − z(cid:107)2 − 4 x − y + z 2 = 2(cid:107)x − y(cid:107)2 + 2(cid:107)x − z(cid:107)2 − (cid:107)2x − (y + z)(cid:107)2 (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13)
≤ 2d2 + 2d2 − 4d2 = 0.
Điều này suy ra y = z hay y là phần tử xác định duy nhất.
Dưới đây là một số ví dụ cụ thể về phép chiếu mêtric lên các nửa không
gian đóng, hình cầu đóng trong không gian hữu hạn chiều.
Ví dụ 1.6. [2]
Giả sử C := {x ∈ Rn : (cid:104)x, u(cid:105) ≤ ζ} là nửa không gian đóng trong Rn với
nếu (cid:104)x, u(cid:105) ≤ ζ, ζ ∈ R và u ∈ Rn là phần tử cố định. Khi ấy, ta có (i) Nếu u = 0 và ζ ≥ 0 thì C = Rn và PC = I. (ii) Nếu u = 0 và ζ < 0 thì C = ∅. (iii) Nếu u (cid:54)= 0 thì C (cid:54)= ∅ và với mọi x ∈ Rn ta có x PC(x) = u nếu (cid:104)x, u(cid:105) > ζ. x + ζ − (cid:104)x, u(cid:105) (cid:107)u(cid:107)2
Ví dụ 1.7. [2]
Cho C := {x ∈ Rn : (cid:107)x − x0(cid:107) ≤ r} là hình cầu đóng tâm x0 ∈ Rn và bán
kính r > 0. Khi ấy, với mọi x ∈ Rn ta có
nếu (cid:107)x − x0(cid:107) ≤ r, x PC(x) = x0 + r nếu (cid:107)x − x0(cid:107) > r. x − x0 (cid:107)x − x0(cid:107)
Mệnh đề sau cho ta một đặc trưng hình học về phép chiếu mêtric.
11
Mệnh đề 1.5. [2]
Cho C ⊆ Rn là tập con lồi đóng khác rỗng. Khi đó, y = PC(x) là hình
chiếu của x trên C khi và chỉ khi
y ∈ C : (cid:104)y, z − y(cid:105) ≥ (cid:104)x, z − y(cid:105) ∀z ∈ C.
Chứng minh. Từ Mệnh đề 1.4, ta thấy
(cid:107)x − z(cid:107). y = PC(x) ⇔ (cid:107)x − y(cid:107) = inf z∈C
Mặt khác, với mọi z ∈ C và λ ∈ (0, 1) ta có
uλ = λz + (1 − λ)y ∈ C,
(vì tính lồi của C) và vì thế ta nhận được y = PC(x) khi và chỉ
∀z ∈ C, ∀λ ∈ (0, 1). (cid:107)x − y(cid:107) ≤ (cid:107)x − uλ(cid:107),
Bất đẳng thức này tương đương với
(cid:107)x − y(cid:107)2 ≤ (cid:107)x − y + λ(y − z)(cid:107)2
= (cid:107)x − y(cid:107)2 + λ2(cid:107)y − z(cid:107)2 + 2λ(cid:104)x − y, y − z(cid:105), ∀z ∈ C, ∀λ ∈ (0, 1).
hay
(cid:107)y − z(cid:107)2, ∀z ∈ C, ∀λ ∈ (0, 1). (cid:104)x − y, z − y(cid:105) ≤ λ 2
Từ đây suy ra y = PC(x) nếu và chỉ nếu
(cid:104)x − y, z − y(cid:105) ≤ 0, ∀z ∈ C.
Ta có điều cần chứng minh.
Hệ quả 1.1. Cho C là tập con lồi đóng khác rỗng trong không gian Rn. Khi đó, phép chiếu mêtric PC là ánh xạ không giãn, tức là
(cid:107)PC(x) − PC(y)(cid:107) ≤ (cid:107)x − y(cid:107) ∀x, y ∈ Rn.
Chứng minh. Với mọi x, y ∈ Rn, từ Mệnh đề 1.5 ta có
(cid:104)PC(y) − PC(x), x − PC(x)(cid:105) ≤ 0,
và
(cid:104)PC(x) − PC(y), y − PC(y)(cid:105) ≤ 0.
12
Cộng hai bất đẳng thức trên ta nhận được
(cid:104)PC(x) − PC(y), −(x − PC(x)) + (y − PC(y))(cid:105) ≤ 0.
Bất đẳng thức này suy ra
(cid:107)PC(x) − PC(y)(cid:107)2 ≤ (cid:104)PC(x) − PC(y), x − y(cid:105)
≤ (cid:107)PC(x) − PC(y)(cid:107)(cid:107)x − y(cid:107).
Từ đây, ta có điều cần chứng minh.
1.2. Dưới vi phân hàm lồi
Định nghĩa 1.8. Cho C ⊆ Rn là một tập con lồi và khác rỗng. Hàm số f : C → R được gọi là
(i) hàm lồi trên C nếu với mọi x, y ∈ C và với mọi λ ∈ [0, 1] ta có
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y).
(ii) hàm lồi chặt trên C nếu với mọi x (cid:54)= y ∈ C và với mọi λ ∈ [0, 1] ta có
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y).
Ví dụ 1.8. Xét C = Rn và hàm số f : Rn → R xác định bởi f (x) = (cid:107)x(cid:107) là một hàm lồi.
Ví dụ 1.9. Xét C = R và hàm số f : R → R xác định bởi f (x) = x2 là một hàm lồi và cũng là hàm lồi chặt. Tuy nhiên, hàm số
0 nếu x < 0, f (x) = x nếu x ≥ 0.
là một hàm lồi nhưng không là hàm lồi chặt.
Định lí 1.4. [2]
m (cid:88)
Cho C ⊆ Rn là tập lồi khác rỗng. Hàm f : C → R là hàm lồi khi và chỉ
i=1
λi = 1 và ∀x1, . . . , xm ∈ C ta có khi ∀λi ≥ 0 (i = 1, . . . , m),
f (λ1x1 + · · · + λmxm) ≤ λ1f (x1) + · · · + λmf (xm).
13
Định nghĩa 1.9. Cho f : C → R là hàm xác định trên C ⊆ Rn. Khi đó, hàm f được gọi là
(i) khả vi Gâteaux tại x ∈ C nếu tồn tại phiếm hàm tuyến tính liên tục x∗
trên C thỏa mãn
= (cid:104)x∗, y(cid:105), ∀y ∈ C. lim α↓0 f (x + αy) − f (x) α
G(x) hoặc ∇f (x).
Toán tử x∗ được gọi là đạo hàm Gâteaux của f tại x và thường được kí hiệu là f (cid:48)
(ii) khả vi Gâteaux nếu f khả vi Gâteaux tại mọi x ∈ C.
(iii) khả vi Fréchet tại x ∈ C nếu tồn tại phiếm hàm tuyến tính liên tục x∗
trên C thỏa mãn
= 0. lim (cid:107)y(cid:107)→0 |f (x + y) − f (x) − (cid:104)x∗, y(cid:105)| (cid:107)y(cid:107)
F (x) hoặc f (cid:48)(x).
Toán tử x∗ được gọi là đạo hàm Fréchet của f tại x và thường được kí hiệu là f (cid:48)
(iv) khả vi Fréchet nếu f khả vi Fréchet tại mọi x ∈ C.
Nhận xét 1.4. Nếu f : C → R khả vi Fréchet tại x ∈ C thì nó cũng khả vi Gâteaux. Thật vậy, điều cần chứng minh được suy ra trực tiếp từ mối liên
hệ sau:
= 0 lim (cid:107)y(cid:107)→0
= 0 ⇒ lim α→0
= 0, ⇒ lim α→0 |f (x + y) − f (x) − (cid:104)x∗, y(cid:105)| (cid:107)y(cid:107) |f (x + αz) − f (x) − α(cid:104)x∗, z(cid:105)| α(cid:107)z(cid:107) f (x + αz) − f (x) α (cid:12) (cid:12) − (cid:104)x∗, z(cid:105) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
ở đây, ta thay y = αz với α > 0 và z (cid:54)= 0 là phần tử cố định tùy ý trong C. Tuy nhiên, một hàm f : C → R khả vi Gâteaux tại x ∈ C thì nó có thể không khả vi Fréchet. Thật vậy, chẳng hạn ta xét hàm số f : R2 → R xác định bởi
nếu (u, v) (cid:54)= (0, 0), f (u, v) =
nếu (u, v) = (0, 0). u3v u4 + v2 0
14
Khi đó, hàm số trên khả vi Gâteaux tại 0 vì
G(0) = 0. Trong khi đó, f không khả vi Fréchet tại điểm này vì với
= 0 = (cid:104)0, y(cid:105), ∀y = (u, v) ∈ R2. lim α↓0 = lim α↓0 α4u3v α4u4 + α2v2 α f (0 + αy) − f (0) α
hay f (cid:48) y = (u, v) mà v = u2, ta lại có
√ = . = |f (y)| (cid:107)y(cid:107) (cid:12) (cid:12) u5 (cid:12) (cid:12) (cid:12) (cid:12) u4 + u4 (cid:12) (cid:12) √ u2 + u4 2 1 u2 + 1
Từ đó suy ra
= (cid:54)= 0. lim (cid:107)y(cid:107)→0 = lim (cid:107)y(cid:107)→0 |f (0 + y) − f (0)| (cid:107)y(cid:107) |f (y)| (cid:107)y(cid:107) 1 2
Định nghĩa 1.10. Cho f : C → R là hàm lồi trên C ⊆ Rn. (i) Phần tử x∗ ∈ Rn được gọi là dưới gradient của hàm f tại điểm ¯x ∈ E nếu
f (x) − f (¯x) ≥ (cid:104)x∗, x − ¯x(cid:105) ∀x ∈ C.
(ii) Tập tất cả các dưới gradient của 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), tức là
∂f (¯x) = {x∗ ∈ Rn : f (x) − f (¯x) ≥ (cid:104)x∗, x − ¯x(cid:105), ∀x ∈ C}.
(iii) Hàm f được gọi là khả dưới vi phân tại ¯x nếu ∂f (¯x) (cid:54)= ∅.
Ví dụ 1.10. Cho f : R → R xác định bởi f (x) =| x − a |. Khi đó, ta có dưới vi phân của hàm f là
nếu x < a,
∂f (x) =
nếu x > a. {−1} {[−1, 1]} nếu x = a, {1}
Mối liên hệ giữa dưới vi phân và tính khả vi Gâteaux (hoặc khả vi Frétchet)
được phát biểu trong mệnh đề dưới đây.
Mệnh đề 1.6. [2]
Cho f : Rn → R là hàm lồi. Khi đó, ta có các khẳng định sau:
15
G(x) = x∗ và f khả dưới vi phân
(i) Nếu f khả vi Gâteaux tại x ∈ Rn với f (cid:48)
tại x thì
∂f (x) = {x∗}.
(ii) Nếu f là hàm liên tục tại x ∈ Rn và ∂f (x) chỉ gồm một phần tử duy nhất
(cid:48)
x∗ thì f khả vi Gâteaux tại x và
G(x) = x∗.
f
G(x) = x∗. Ta có
Chứng minh. (i) Giả sử f khả vi Gâteaux tại x ∈ Rn với f (cid:48)
= (cid:104)x∗, y(cid:105), ∀y ∈ Rn. lim α↓0 f (x + αy) − f (x) α
Mặt khác, từ tính lồi của f ta lại có
f (x + λ(z − x)) ≤ λf (z) + (1 − λ)f (x), ∀λ ∈ (0, 1).
Ta đặt y = z − x. Khi đó, ta nhận được
f (x + λy) ≤ f (x) + λ(f (y + x) − f (x)), ∀λ ∈ (0, 1).
Từ đó suy ra
≤ f (y + x) − f (x), ∀λ ∈ (0, 1). f (x + λy) − f (x) λ
Điều này dẫn đến
f (x) − f (y + x) ≤ −(cid:104)x∗, y(cid:105),
hay tương đương với
f (x) − f (y + x) ≤ (cid:104)x∗, x − (y + x)(cid:105), ∀y ∈ Rn.
Vì thế, ta có x∗ ∈ ∂f (x). Mặt khác, nếu y∗ ∈ ∂f (x) thì
(cid:104)y∗, y(cid:105) = (cid:104)y∗, (x + λy) − x(cid:105) ≤ , ∀y ∈ Rn, ∀λ > 0. 1 λ f (x + λy) − f (x) λ
Cho λ → 0 ta được
(cid:104)y∗, y(cid:105) ≤ (cid:104)x∗, y(cid:105), ∀y ∈ Rn,
hay
(cid:104)y∗ − x∗, y(cid:105) ≤ 0, ∀y ∈ Rn,
16
Bất đẳng thức này suy ra x∗ = y∗. Vì thế, ta có ∂f (x) = {x∗}.
(ii) Giả sử ∂f (x) = {x∗}. Khi đó, từ định nghĩa ta có
f (u) − f (x) ≥ (cid:104)x∗, u − x(cid:105), ∀u ∈ Rn.
Do đó, với u = x + λy ta nhận được
≥ (cid:104)x∗, y(cid:105), ∀λ > 0, ∀y ∈ Rn. f (x + λy) − f (x) λ
Bất đẳng thức trên dẫn đến
= (cid:104)x∗, y(cid:105), ∀y ∈ Rn. lim λ↓0 = inf λ>0 f (x + λy) − f (x) λ f (x + λy) − f (x) λ
Từ đây suy ra điều cần chứng minh.
1.3. Ánh xạ đơn điệu và liên tục
Định nghĩa 1.11. Cho C ⊆ Rn là tập con khác rỗng và F : C → Rn là ánh xạ xác định trên C. Ánh xạ F được gọi là:
(i) đơn điệu trên C nếu
(cid:104)F (x) − F (y), x − y(cid:105) ≥ 0 ∀x, y ∈ C. (1.1)
(ii) đơn điệu chặt trên C nếu
(cid:104)F (x) − F (y), x − y(cid:105) > 0 ∀x (cid:54)= y ∈ C. (1.2)
(iii) α-đơn điệu mạnh trên C nếu tồn tại số thực dương α sao cho
(cid:104)F (x) − F (y), x − y(cid:105) ≥ α(cid:107)x − y(cid:107)2 ∀x, y ∈ C. (1.3)
Nhận xét 1.5. Nếu ánh xạ F là α-đơn điệu mạnh trên C thì đơn điệu chặt trên C, nếu ánh xạ F đơn điệu chặt trên C thì đơn điệu trên C. Tuy nhiên,
chiều ngược lại của các khẳng định trên nói chung không đúng.
Ví dụ 1.11. Cho C = R. Ánh xạ F : R → R xác định bởi F (x) = x là ánh xạ 1-đơn điệu mạnh và vì thế F cũng là ánh xạ đơn điệu chặt và đơn điệu trên R. Ánh xạ F : R → R xác định bởi
1 + x2 nếu x ≥ 0, F (x) = 1 − x2 nếu x ≤ 0,
17
là ánh xạ đơn điệu chặt trên R nhưng không đơn điệu mạnh.
0 nếu x < 0, Ánh xạ F : R → R xác định bởi F (x) = x nếu x ≥ 0,
là ánh xạ đơn điệu trên R nhưng không đơn điệu chặt.
Định nghĩa 1.12. Cho C ⊆ Rn là tập con khác rỗng. Ánh xạ F : C → Rn được gọi là 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.
Nhận xét 1.6. Mọi ánh xạ đơn điệu là giả đơn điệu nhưng khẳng định ngược lại nói chung không đúng. Chẳng hạn, ánh xạ F : [0, +∞) → R xác định bởi
F (x) = là ánh xạ giả đơn điệu nhưng không đơn điệu. Thật vậy, với 1 1 + x mọi x, y ∈ [0, +∞) ta luôn có
(cid:104)F (y), x − y(cid:105) ≥ 0 ⇔ ≥ 0 ⇒ ≥ 0 ⇔ (cid:104)F (x), x − y(cid:105) ≥ 0. x − y 1 + y x − y 1 + x
Tuy nhiên, với mọi x, y ∈ [0, +∞) ta lại có
(cid:17) (cid:16) 1 (cid:104)F (x) − F (y), x − y(cid:105) = − ≤ 0. (x − y) = − 1 + x 1 1 + y (x − y)2 (1 + x)(1 + y)
Định nghĩa 1.13. Cho C ⊆ Rn là tập con khác rỗng. Ánh xạ F : C → Rn được gọi là tựa đơn điệu chính tắc trên C nếu ∀J = {x1, x2, · · · , xm} ⊆ C và ∀y ∈ co(J) đều tồn tại 1 ≤ i ≤ m sao cho
(cid:104)F (xi), y − xi(cid:105) ≤ 0.
Nhận xét 1.7. Mọi ánh xạ đơn điệu hoặc giả đơn điệu đều là tựa đơn điệu
chính tắc.
Định nghĩa 1.14. Cho C ⊆ Rn là tập con khác rỗng. Ánh xạ F : C → Rn được gọi là B-giả đơn điệu (đơn diệu theo nghĩa Brézis) nếu với mỗi x ∈ C và mọi dãy {xn} trong C hội tụ đến x với
(cid:104)F (xn), x − xn(cid:105) ≥ 0 lim inf n→∞
18
thì ta đều có
n→∞
(cid:104)F (x), y − x(cid:105) ≥ lim sup ∀y ∈ C. (cid:104)F (xn), y − xn(cid:105),
Chú ý 1.1. Trong không gian hữu hạn chiều, mọi ánh xạ liên tục hoặc ánh
xạ đơn điệu mà h-liên tục đều là ánh xạ B-giả đơn điệu (Mệnh đề 27.6, trang 586, [9]).
Ví dụ 1.12. Một ánh xạ B-giả đơn điệu có thể không giả đơn điệu. Chẳng hạn, trong không gian R2, xét tập
1 + x2
2 ≤ 1}
C = {x = (x1, x2) ∈ R2 : x2
và ánh xạ F : C → R2 được cho bởi
2).
F (x1, x2) = (−x1, x2
Khi đó, theo Chú ý 1.1 thì dễ thấy F là B-giả đơn điệu. Tuy nhiên, F không
giả đơn điệu. Thật vậy, lấy x = (1, 0) và y = (−1, 0), ta có
(cid:104)F (y), x − y(cid:105) = 2 ≥ 0,
nhưng
(cid:104)F (x), x − y(cid:105) = −2 < 0.
Tiếp theo, ta có tính lồi của một hàm f khả vi Gâteaux có thể đặc trưng
bởi tính đơn điệu của ∇f như dưới đây.
Mệnh đề 1.7. [2]
Cho C ⊆ Rn là tập lồi mở và f : C → R là hàm khả vi Gâteaux trên C.
Khi đó, các khẳng định sau tương đương:
(i) f là hàm lồi.
(ii) ∇f là đơn điệu, tức là
(cid:104)∇f (x) − ∇f (y), x − y(cid:105) ≥ 0, ∀x, y ∈ C.
Chứng minh. Giả sử f là hàm lồi. Từ Mệnh đề 1.6 và tính khả vi Gâteaux
của f , ta có
f (y) − f (x) ≥ (cid:104)∇f (x), y − x(cid:105), ∀x, y ∈ C.
19
Đổi vai trò x và y ta lại có
f (x) − f (y) ≥ (cid:104)∇f (y), x − y(cid:105), ∀x, y ∈ C.
Cộng hai vế các bất đẳng thức trên ta nhận được
(cid:104)∇f (x) − ∇f (y), x − y(cid:105) ≥ 0, ∀x, y ∈ C.
Ngược lại, giả sử ta có (ii). Ta xét hàm số h : R → R xác định bởi
h(t) = f (y + t(x − y)). Khi đó, với mọi t ∈ [0, 1], h là hàm số khả vi và
h(cid:48)(t) = (cid:104)∇f (y + t(x − y)), x − y(cid:105).
Với mọi x, y ∈ C, lấy tùy ý 0 < α < β < 1 và đặt
yα = y + α(x − y) ∈ C, yβ = y + β(x − y) ∈ C.
Khi đó, kết hợp với giả thiết (ii) ta có
h(cid:48)(β) − h(cid:48)(α) = (cid:104)∇f (yβ), x − y(cid:105) − (cid:104)∇f (yα), x − y(cid:105)
= (cid:104)∇f (yβ) − ∇f (yα), yβ − yα(cid:105) 1 β − α
≥ 0.
Điều này suy ra h(cid:48) là hàm không giảm trên (0, 1). Từ đây dẫn đến
0
t
(cid:90) t (cid:90) 1 h(cid:48)(w)dw ≤ h(cid:48)(w)dw = = h(t) − h(0) t 1 t 1 1 − t h(1) − h(t) 1 − t
với mọi t ∈ (0, 1). Từ ước lượng trên suy ra
th(1) + (1 − t)h(0) ≥ h(t).
Do đó, ta nhận được
tf (y) + (1 − t)f (x) ≤ f (x + t(y − x)), ∀x, y ∈ C.
Hay f là hàm lồi.
Định nghĩa 1.15. Cho C ⊆ Rn là tập con lồi khác rỗng và F : C → Rm là ánh xạ xác định trên C. Khi đó, F được gọi là:
(i) h-liên tục tại x ∈ C nếu với bất kì dãy {xn} các phần tử trong C mà hội tụ tới x dọc theo một tia thì ta đều có {F (xn)} hội tụ tới F (x), tức là F (xn) := F (x + tny) → F (x) khi tn → 0 với mọi y ∈ C.
20
(ii) h-liên tục trên C nếu nó h-liên tục tại mọi điểm x ∈ C.
Định nghĩa 1.16. Cho C ⊆ Rn là tập con lồi khác rỗng và f : C → R là ánh xạ xác định trên C. Khi đó, f được gọi là:
(i) nửa liên tục trên tại x ∈ C nếu với mọi dãy {xn} các phần tử trong C
mà hội tụ tới x ta đều có
n→∞
f (x) ≥ lim sup f (xn)
(ii) nửa liên tục trên trên C nếu nó nửa liên tục trên tại mọi điểm x ∈ C.
(iii) nửa liên tục dưới tại x ∈ C nếu với mọi dãy {xn} các phần tử trong C
mà hội tụ tới x ta đều có
f (xn) f (x) ≤ lim inf n→∞
(iv) nửa liên tục dưới trên C nếu nó nửa liên tục dưới tại mọi điểm x ∈ C.
(v) liên tục tại x ∈ C (trên C) nếu nó vừa nửa liên tục trên và nửa liên tục
dưới tại x ∈ C (trên C).
Ví dụ 1.13. Hàm số f : R → R xác định bởi
x + 1 nếu x ≥ 0, f (x) = nếu x < 0, 0
là nửa liên tục trên tại x = 0 nhưng không nửa liên tục dưới tại điểm này.
−x2 nếu x ≤ 0, Hàm số g : R → R xác định bởi g(x) = nếu x > 0, 1
là nửa liên tục dưới tại x = 0 nhưng không nửa liên tục trên tại điểm này.
Hàm số h : R → R xác định bởi
(cid:19) sin nếu x (cid:54)= 0, (cid:18) 1 x h(x) =
nếu x = 0, 1
là nửa liên tục trên tại x = 0 nhưng không tồn tại giới hạn trái (không liên
tục trái) cũng như giới hạn phải (không liên tục phải) của hàm số h(x) tại điểm này.
21
Ví dụ 1.14. Mọi ánh xạ liên tục là h-liên tục. Tuy nhiên, khẳng định ngược lại có thể không đúng. Chẳng hạn, ta xét ánh xạ F : R2 → R xác định bởi
nếu (x, y) (cid:54)= (0, 0), F (x, y) =
nếu (x, y) = (0, 0), x2y x4 + y2 0
là ánh xạ h-liên tục tại (0, 0) nhưng không liên tục tại điểm này.
1.4. Ánh xạ KKM
Cho C, D là hai tập hợp bất kì. Cho F : C ⇒ D là ánh xạ từ C vào tập hợp gồm toàn bộ các tập con của D. Ta nói F là ánh xạ đa trị từ C vào D.
Như vậy, với mỗi x ∈ C, F (x) là một tập hợp con của D. Không loại trừ khả
năng với một số phần tử x ∈ C nào đó ta có F (x) là tập rỗng. Một ví dụ đơn giản về ánh xạ đa trị là ánh xạ dưới vi phân hàm lồi.
n (cid:91)
Định nghĩa 1.17. Cho C ⊆ Rn là tập con lồi khác rỗng. Ánh xạ F : C ⇒ Rn được gọi là ánh xạ KKM nếu với mọi tập con hữu hạn J := {x1, x2, · · · , xn} ⊂ C ta có
i=1
co(J) ⊆ F (xi).
Để ý rằng, nếu F là ánh xạ KKM thì x ∈ F (x) với mọi x. Một số ví dụ về
ánh xạ KKM được cho dưới đây.
Ví dụ 1.15. Cho C ⊆ Rn là tập con lồi khác rỗng. Cho f : C → R là hàm lồi. Ta xét ánh xạ F : C ⇒ C xác định bởi
F (x) = {y ∈ C : f (y) ≤ f (x)},
với mỗi x ∈ C. Khi đó, F là ánh xạ KKM.
Thật vậy, với mọi tập con hữu hạn J := {x1, x2, · · · , xn} ⊂ C và y ∈ co(J),
n (cid:88)
n (cid:88)
ta có
i=1
i=1
y = λixi, λi ∈ [0, 1], λi = 1.
i=1 F (xi) thì
Nếu y /∈ (cid:83)n
∀i = 1, 2, · · · , n. f (y) > f (xi),
22
n (cid:88)
n (cid:88)
Từ đó suy ra
i=1
i=1
f (y) = λif (y) > λif (xi).
n (cid:88)
n (cid:88)
Mặt khác, f là hàm lồi nên
i=1
i=1
f ( λixi) ≤ λif (xi).
n (cid:88)
Kết hợp với bất đẳng thức trên ta nhận được
i=1
n (cid:91)
f (y) = f ( λixi) < f (y),
i=1
mâu thuẫn. Do đó, ta phải có y ∈ F (xi) hay F là ánh xạ KKM.
Ví dụ 1.16. Cho C ⊆ Rn là tập con lồi khác rỗng và ánh xạ g : C → Rn. Ta xét ánh xạ F : C ⇒ C xác định bởi
F (x) = {y ∈ C : (cid:107)g(y) − y(cid:107) ≤ (cid:107)g(y) − x(cid:107)},
với mỗi x ∈ C. Khi đó, F là ánh xạ KKM.
Thật vậy, với mọi tập con hữu hạn J := {x1, x2, · · · , xn} ⊂ C và y ∈ co(J),
n (cid:88)
n (cid:88)
ta có
i=1
i=1
y = λixi, λi ∈ [0, 1], λi = 1.
i=1 F (xi) thì
Nếu y /∈ (cid:83)n
∀i = 1, 2, · · · , n. (cid:107)g(y) − y(cid:107) > (cid:107)g(y) − xi(cid:107),
n (cid:88)
n (cid:88)
Từ đó suy ra
i=1
i=1
(cid:107)g(y) − y(cid:107) = λi(cid:107)g(y) − y(cid:107) > λi(cid:107)g(y) − xi(cid:107).
n (cid:88)
n (cid:88)
n (cid:88)
Mặt khác, hàm chuẩn là hàm lồi nên
i=1
i=1
i=1
(cid:107)g(y) − y(cid:107) = (cid:107)g(y) − λixi(cid:107) = (cid:107) λi(g(y) − xi)(cid:107) ≤ λi(cid:107)g(y) − xi(cid:107).
Kết hợp với bất đẳng thức trên ta nhận được
(cid:107)g(y) − y(cid:107) < (cid:107)g(y) − y(cid:107),
23
n (cid:91)
i=1
mâu thuẫn. Do đó, ta phải có y ∈ F (xi) hay F là ánh xạ KKM.
Nguyên lí ánh xạ KKM-Fan sau đây là một trong những công cụ chủ yếu
chúng tôi sử dụng trong nhiều chứng minh về sự tồn tại nghiệm của lớp bài toán nghiên cứu.
Định lí 1.5. [1] (KKM-Fan)
Cho C là tập con lồi, khác rỗng của Rn và P : C ⇒ C là ánh xạ KKM.
Khi đó, nếu các giả thiết sau bảo đảm:
(i) P (x) là tập con đóng với mọi x ∈ C,
(ii) P (x) là tập con compact với ít nhất một x ∈ C,
y∈C
thì ta có (cid:92) P (y) (cid:54)= ∅.
Chứng minh chi tiết Định lí trên có thể xem trong tài liệu [3].
24
Chương 2
Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân trong Rn
Trong chương này, chúng tôi trình bày một số kết quả về sự tồn tại nghiệm
cho bài toán bất đẳng thức biến phân (VIP). Cấu trúc của chương gồm bốn phần: Mục 2.1 chúng tôi phát biểu mô hình bài toán nghiên cứu và mối liên
hệ cơ bản với bất đẳng thức biến phân Minty; Sự tồn tại nghiệm của bài toán
trong các trường hợp miền ràng buộc có hoặc không có tính chất compact được cụ thể hóa lần lượt trong các Mục 2.2 và Mục 2.3. Phần cuối chương, Mục 2.4 dùng để trình bày ba phương pháp lặp tìm nghiệm xấp xỉ của bài toán (VIP) cùng các ví dụ minh họa.
2.1. Mô hình bài toán
Cho C là tập con khác rỗng của Rn và ánh xạ F : C → Rn. Bài toán bất
đẳng thức biến phân (VIP) có dạng: Tìm x ∈ C sao cho
(cid:104)F (x), y − x(cid:105) ≥ 0, ∀y ∈ C. (2.1)
Phần tử x ∈ C thỏa mãn (2.1) được gọi là nghiệm của bài toán (VIP). Tập tất cả các nghiệm của bài toán này được kí hiệu là Sol(VIP(F, C)), nghĩa là
Sol(VIP(F, C)) = {x ∈ C : (cid:104)F (x), y − x(cid:105) ≥ 0, ∀y ∈ C}.
Ánh xạ F và tập C tương ứng được gọi là ánh xạ mục tiêu và miền ràng buộc của bài toán.
Nhận xét 2.1. Nón pháp tuyến N (x, C) của một tập lồi đóng C ⊆ Rn tại x được định nghĩa và xác định bởi
{¯x ∈ Rn : (cid:104)¯x, y − x(cid:105) ≤ 0, ∀y ∈ C}, nếu x ∈ C, N (x, C) = ∅, nếu x /∈ C.
25
Khi đó, dễ thấy rằng x ∈ C là một nghiệm của bài toán (VIP) khi và chỉ khi
0 ∈ F (x) + N (x, C).
Ví dụ 2.1. Một ví dụ đơn giản về bài toán bất đẳng thức biến phân là bài toán giải hệ phương trình tuyến tính. Cụ thể, nếu C = Rn và F : Rn → Rn là ánh xạ tuyến tính xác định bởi ma trận vuông
A =
a11 a12 a21 a22 · · · · · · an1 an2 · · · a1n · · · a2n · · · · · · · · · ann
thì bài toán (2.1) có dạng: Tìm x = (x1, x2, · · · , xn) ∈ Rn sao cho
(cid:104)A(x), y − x(cid:105) ≥ 0, ∀y ∈ Rn. (2.2)
Để ý rằng, bất đẳng thức trên đúng khi và chỉ khi A(x) = 0. Thật vậy,
nếu A(x) = 0 thì (2.2) được bảo đảm. Ngược lại, nếu ta có (2.2) thì thay
y = x − A(x) trong (2.2) ta nhận được
(cid:104)A(x), −A(x)(cid:105) ≥ 0 ⇔ (cid:104)A(x), A(x)(cid:105) ≤ 0 ⇔ A(x) = 0.
Do đó, việc tìm nghiệm của bài toán (VIP) trở thành tìm nghiệm của hệ phương trình tuyến tính bậc nhất n ẩn
a11x1 + a12x2 + · · · + a1nxn = 0,
a21x1 + a22x2 + · · · + a2nxn = 0,
· · ·
an1x1 + an2x2 + · · · + annxn = 0.
Tổng quát hơn ta có mệnh đề sau đây.
Mệnh đề 2.1. Cho ánh xạ F : Rn → Rn. Khi đó, x ∈ Sol(VIP(F, Rn)) khi và chỉ khi F (x) = 0.
Ví dụ 2.2. Cho C là tập con lồi đóng trong không gian Rn và f : C → R là hàm số khả vi (Gâteaux hoặc Fréchet) liên tục trên C. Bài toán cực trị được
phát biểu như sau:
Tìm x ∈ C sao cho: f (y). (2.3) f (x) = min y∈C
26
Kí hiệu F (x) = ∇f (x) là gradient của f tại x. Khi đó, mối quan hệ giữa nghiệm của bài toán (VIP) và bài toán cực trị được phát biểu trong các
mệnh đề sau.
Mệnh đề 2.2. [1, 6]
Nếu x là nghiệm của bài toán (2.3) thì x là nghiệm của bài toán (VIP).
Chứng minh. Ta có z = x + t(y − x) ∈ C với mọi y ∈ C và t ∈ [0, 1]. Nếu x
là nghiệm của bài toán (2.3) thì φ(t) = f (x + t(y − x)), t ∈ [0, 1] đạt cực tiểu tại t = 0. Do đó ta có
0 ≤ φ(cid:48)(0) = (cid:104)∇f (x), y − x(cid:105) = (cid:104)F (x), y − x(cid:105) ∀y ∈ C.
Hay suy ra x là nghiệm của bài toán (VIP).
Khẳng định ngược lại của phát biểu trên nói chung không đúng. Chẳng hạn, xét f : R → R xác định bởi f (x) = x3. Khi đó, bài toán (VIP) có duy nhất nghiệm x = 0 nhưng x = 0 không là nghiệm của bài toán (2.3).
Tuy nhiên, nếu có thêm giả thiết về tính lồi của hàm f ta có khẳng định
ngược lại như dưới đây.
Mệnh đề 2.3. [1, 6]
Giả sử f là hàm lồi và khả vi trên C. Nếu x là nghiệm bài toán (VIP) thì
x là nghiệm của bài toán (2.3).
Chứng minh. Vì f là hàm lồi khả vi trên C nên ta có
f (y) ≥ f (x) + (cid:104)F (x), y − x(cid:105) ∀y ∈ C.
(Suy ra từ Mệnh đề 1.6). Mặt khác, vì x là nghiệm bài toán bất đẳng thức biến phân trên nên
(cid:104)F (x), y − x(cid:105) ≥ 0 ∀y ∈ C.
Do đó
f (y) ≥ f (x) ∀y ∈ C.
Hay suy ra x là nghiệm của bài toán (2.3).
Năm 1962, Minty đã xác định một đặc trưng đầy đủ về nghiệm của bài
toán (VIP) thông qua nghiệm của bài toán sau đây:
Tìm x ∈ C sao cho (cid:104)F (y), y − x(cid:105) ≥ 0, ∀y ∈ C. (2.4)
27
Bài toán trên còn được gọi là bài toán bất đẳng thức biến phân Minty (MVIP). Tập nghiệm của bài toán được kí hiệu là Sol(MVIP(F, C)).
Bổ đề Minty dưới đây là một công cụ hữu ích và quan trọng cho các nghiên cứu về sự tồn tại nghiệm của bài toán (VIP) khi ánh xạ mục tiêu có tính chất
đơn điệu và miền ràng buộc có tính lồi.
Bổ đề 2.1. [1, 6] (Minty)
Cho C là tập con khác rỗng của Rn và F : C → Rn là ánh xạ xác định trên
C. Khi đó, ta có các khẳng định sau:
(i) Nếu C là tập lồi và F là ánh xạ h-liên tục thì mọi nghiệm của bài toán
(MVIP) đều là nghiệm của bài toán (VIP).
(ii) Nếu F là ánh xạ giả đơn điệu thì mọi nghiệm của bài toán (VIP) đều là
nghiệm của bài toán (MVIP).
Chứng minh. (i) Giả sử x ∈ Sol(MVIP(F, C)). Vì C là tập lồi nên với mọi y ∈ C và t ∈ (0, 1) ta có zt = x + t(y − x) ∈ C. Do đó
0 ≤ (cid:104)F (zt), zt − x(cid:105) = t(cid:104)F (x + t(y − x)), y − x(cid:105).
Từ đó suy ra
(cid:104)F (x + t(y − x)), y − x(cid:105) ≥ 0 ∀y ∈ C, ∀t ∈ (0, 1).
Cho t → 0 và kết hợp với tính h-liên tục của F ta nhận được
(cid:104)F (x), y − x(cid:105) ≥ 0 ∀y ∈ C.
Do đó, x là nghiệm của bài toán (VIP).
(ii) Nếu x ∈ Sol(VIP(F, C)) thì
(cid:104)F (x), y − x(cid:105) ≥ 0 ∀y ∈ C.
Vì ánh xạ F giả đơn điệu nên suy ra
(cid:104)F (y), y − x(cid:105) ≥ 0 ∀y ∈ C.
Hay ta có x là nghiệm của bài toán (MVIP).
Bổ đề sau cho ta vài thông tin quan trọng về tính chất của tập nghiệm bài
toán (VIP).
28
Bổ đề 2.2. Cho C là tập con lồi, đóng, khác rỗng của Rn và F : C → Rn là ánh xạ h-liên tục và giả đơn điệu trên C. Khi đó, Sol(VIP(F, C)) là tập
đóng lồi.
Chứng minh. Theo Bổ đề Minty ta có tập nghiệm của hai bài toán (VIP) và
(MVIP) trùng nhau. Do đó, thay vì chứng minh Sol(VIP(F, C)) là tập đóng lồi ta sẽ chứng minh Sol(MVIP(F, C)) có tính chất này.
Giả sử u, v là hai phần tử tùy ý thuộc Sol(MVIP(F, C)) và λ ∈ [0, 1]. Vì
C là tập lồi nên λu + (1 − λ)v ∈ C. Hơn nữa, ta lại có
λ(cid:104)F (y), y − u(cid:105) = (cid:104)F (y), λ(y − u)(cid:105) ≥ 0 ∀y ∈ C,
và
(1 − λ)(cid:104)F (y), y − v(cid:105) = (cid:104)F (y), (1 − λ)(y − v)(cid:105) ≥ 0 ∀y ∈ C.
Cộng hai vế các bất đẳng thức trên ta nhận được
(cid:104)F (y), y − (λu + (1 − λ)v)(cid:105) ≥ 0 ∀y ∈ C.
Do đó, λu + (1 − λ)v ∈ Sol(MVIP(F, C) hay Sol(MVIP(F, C) là tập lồi.
Giả sử {xn} là một dãy các nghiệm của bài toán (MVIP) và xn → x. Vì C
là tập đóng nên x ∈ C. Mặt khác, với mọi y ∈ C ta có
(cid:104)F (y), y − xn(cid:105) ≥ 0 ∀n ∈ N.
Cho n → ∞ và kết hợp với tính liên tục của tích vô hướng ta nhận được
(cid:104)F (y), y − x(cid:105) ≥ 0 ∀y ∈ C.
Điều này dẫn đến x ∈ Sol(MVIP(F, C) hay Sol(MVIP(F, C) là tập đóng.
2.2. Sự tồn tại nghiệm trường hợp miền ràng buộc là tập compact
Định lí 2.1. [1, 6]
Cho C là tập con lồi compact trong không gian Rn và F : C → Rn là ánh
xạ liên tục. Khi đó, bài toán (VIP) có nghiệm.
Chứng minh. Dễ thấy rằng, việc chứng minh bài toán (VIP) có nghiệm là
tương đương với việc chứng minh sự tồn tại x ∈ C sao cho
(cid:104)x, y − x(cid:105) ≥ (cid:104)x − F (x), y − x(cid:105) ∀y ∈ C.
29
Để ý rằng, ánh xạ PC(I − F ) : C → C, trong đó I(x) = x, là ánh xạ liên tục. Do đó theo Bổ đề 1.3, ánh xạ này có điểm bất động x ∈ C, nghĩa là
x = PC(I − F )(x).
Vì thế, kết hợp điều này và Mệnh đề 1.5 ta nhận được
(cid:104)x, y − x(cid:105) ≥ (cid:104)(I − F )(x), y − x(cid:105) ∀y ∈ C.
Ta có điều cần chứng minh.
Định lí 2.2. [1]
Cho C là tập con lồi, compact, khác rỗng của Rn và F : C → Rn là ánh xạ
h-liên tục và giả đơn điệu trên C. Khi đó, Sol(VIP(F, C)) (cid:54)= ∅.
Chứng minh. Ta xác định hai ánh xạ đa trị P : C ⇒ C và Q : C ⇒ C tương ứng bởi
P (y) = {x ∈ C : (cid:104)F (x), y − x(cid:105) ≥ 0}
và
Q(y) = {x ∈ C : (cid:104)F (y), y − x(cid:105) ≥ 0},
với mỗi y ∈ C.
Ta chứng minh P là ánh xạ KKM. Thật vậy, lấy tùy ý tập con hữu hạn
n (cid:88)
n (cid:88)
J := {y1, y2, · · · , yn} ⊆ C và ¯x ∈ co(J). Ta có
i=1
i=1
n (cid:91)
¯x = λiyi, λi ∈ [0, 1], λi = 1.
i=1
Nếu ¯x /∈ P (yi) thì
∀i = 1, · · · , n. (cid:104)F (¯x), yi − ¯x(cid:105) < 0,
n (cid:88)
Từ đó suy ra
i=1
∀i = 1, · · · , n. λi(cid:104)F (¯x), yi − ¯x(cid:105) < 0,
Do đó, ta có
0 = (cid:104)F (¯x), ¯x − ¯x(cid:105)
30
n (cid:88)
i=1
n (cid:88)
= (cid:104)F (¯x), λi(yi − ¯x)(cid:105)
i=1
n (cid:91)
= λi(cid:104)F (¯x), yi − ¯x(cid:105) < 0,
i=1
mâu thuẫn. Vì thế, ta phải có ¯x ∈ P (yi) hay P là ánh xạ KKM.
Vì F là ánh xạ giả đơn điệu nên P (y) ⊆ Q(y) và vì thế Q cũng là ánh
xạ KKM. Mặt khác, với mỗi y ∈ C, không khó khăn để chỉ ra rằng Q(y) là tập con đóng của tập compact C và vì thế nó là tập con compact. Do đó, áp
dụng Định lí KKM-Fan, ta có
y∈C
(cid:92) Q(y) (cid:54)= ∅.
Điều này nghĩa là tồn tại x ∈ C sao cho
(cid:104)F (y), y − x(cid:105) ≥ 0, ∀y ∈ C,
hay x ∈ Sol(MVIP(F, C). Cuối cùng, áp dụng Bổ đề Minty ta nhận được
x ∈ Sol(VIP(F, C).
Nhận xét 2.2. Điều kiện miền ràng buộc C là tập compact của Định lí 2.2
chỉ là điều kiện đủ để bài toán (VIP) có nghiệm khi ánh xạ mục tiêu F có tính chất h-liên tục và giả đơn điệu. Chẳng hạn, nếu xét trường hợp C = [1, ∞)
và F (x) = x. Khi đó, C không compact nên không áp dụng được Định lí 2.2. Tuy nhiên, dễ thấy rằng bài toán vẫn có nghiệm x = 1.
Nhận xét 2.3. Điều kiện ánh xạ F liên tục và miền C compact không bảo đảm để bài toán (MVIP) có nghiệm. Đó là một sự khác biệt khi bàn về sự
tồn tại nghiệm giữa các bài toán (VIP) và (MVIP) mà không đề cập đến tính đơn điệu của ánh xạ mục tiêu. Dưới đây là một ví dụ đơn giản minh họa.
Xét C = [0, 4] và F = cos(πx/2). Trong trường hợp này, ta thấy
Sol(MVIP(F, C) = ∅,
nhưng dễ thấy x = 1 là một nghiệm của bài toán (VIP).
Định lí dưới đây cho ta một điều kiện đủ về sự tồn tại nghiệm của bài toán
(MVIP).
31
Định lí 2.3. [1]
Cho C là tập con lồi, compact, khác rỗng của Rn và F : C → Rn là ánh xạ
tựa đơn điệu chính tắc trên C. Khi đó, Sol(MVIP(F, C)) (cid:54)= ∅.
Chứng minh. Ta xác định ánh xạ đa trị Q : C ⇒ C bởi
Q(y) = {x ∈ C : (cid:104)F (y), y − x(cid:105) ≥ 0},
với mỗi y ∈ C.
Lấy tùy ý J := {y1, y2, · · · , yn} ⊆ C và ¯y ∈ co(J). Vì F là ánh xạ tựa đơn
n (cid:91)
điệu chính tắc nên
i=1
¯y ∈ Q(yi).
Hay Q là ánh xạ KKM.
Mặt khác, với mỗi y ∈ C, không khó khăn để chỉ ra rằng Q(y) là tập con
y∈C
đóng của C. Vì C compact nên Q(y) cũng là tập compact. Do đó, áp dụng Định lí KKM-Fan, ta có (cid:92) Q(y) (cid:54)= ∅.
Phần còn lại lập luận tương tự chứng minh của Định lí 2.2, ta có điều cần
chứng minh.
2.3. Sự tồn tại nghiệm trường hợp miền ràng buộc không compact
Mục này sẽ trình bày một số kết quả tồn tại nghiệm cho trường hợp miền
ràng buộc không nhất thiết có tính chất compact.
Nhận xét 2.4. Cho C ⊂ Rn là một tập con lồi khác rỗng. Ta kí hiệu
CR = C ∩ SR,
trong đó SR là hình cầu đóng tâm 0 ∈ Rn có bán kính R > 0. Trong trường hợp tập CR (cid:54)= ∅ và nếu F : CR → Rn là ánh xạ liên tục thì theo Định lí 2.1 sẽ tồn tại ít nhất một xR ∈ CR thỏa mãn
(2.5) (cid:104)F (xR), y − xR(cid:105) ≥ 0 ∀y ∈ CR,
hay nói cách khác Sol(VIP(F, CR)) (cid:54)= ∅.
32
Từ nhận xét trên, chúng ta có kết quả dưới đây về sự tồn tại nghiệm của
bài toán (VIP) trong trường hợp C không là tập compact.
Định lí 2.4. [1]
Cho C là tập con lồi đóng trong không gian Rn và F : C → Rn là ánh xạ liên tục. Bài toán (VIP) có nghiệm khi và chỉ khi tồn tại một số thực R > 0 và một nghiệm xR ∈ CR của (2.5) thỏa mãn
(cid:107)xR(cid:107) < R.
Chứng minh. Giả sử bài toán (VIP) có nghiệm x ∈ C. Hiển nhiên, tồn tại một số thực R > 0 sao cho (cid:107)x(cid:107) < R và x ∈ CR ⊂ C. Dễ thấy rằng x cũng là một nghiệm của (2.5).
Ngược lại, giả sử rằng tồn tại một số thực R > 0 sao cho nghiệm xR ∈ CR của (2.5) thỏa mãn (cid:107)xR(cid:107) < R. Khi đó, ta có xR ∈ Sol(VIP(F, C)). Thật vậy, vì (cid:107)xR(cid:107) < R nên với mọi y ∈ C và với (cid:15) ≥ 0 đủ bé, ta có z = xR + (cid:15)(y − xR) ∈ CR. Do đó ta nhận được
xR ∈ C : (cid:15)(cid:104)F (xR), y − xR(cid:105) = (cid:104)F (xR), z − xR(cid:105) ≥ 0 ∀y ∈ C.
Hay tương đương với
xR ∈ C : (cid:104)F (xR), y − xR(cid:105) ≥ 0 ∀y ∈ C.
Ta có điều cần chứng minh.
Định lí 2.5. [1]
Cho C là tập con lồi đóng trong không gian Rn và F : C → Rn là ánh xạ
liên tục. Nếu tồn tại x0 ∈ C thỏa mãn
= +∞, (2.6) lim (cid:107)x(cid:107)→+∞ (cid:104)F (x) − F (x0), x − x0(cid:105) (cid:107)x − x0(cid:107)
thì bài toán (VIP) có nghiệm.
Chứng minh. Chọn α > (cid:107)F (x0)(cid:107) và R > (cid:107)x0(cid:107) sao cho
∀x ∈ C, (cid:107)x(cid:107) ≥ R. (cid:104)F (x) − F (x0), x − x0(cid:105) ≥ α(cid:107)x − x0(cid:107),
Dễ thấy rằng
(cid:104)F (x), x − x0(cid:105) ≥ α(cid:107)x − x0(cid:107) + (cid:104)F (x0), x − x0(cid:105)
33
≥ α(cid:107)x − x0(cid:107) − (cid:107)F (x0)(cid:107)(cid:107)x − x0(cid:107)
với (cid:107)x(cid:107) ≥ R. ≥ (α − F (x0))((cid:107)x(cid:107) − (cid:107)x0(cid:107)) > 0,
Mặt khác, xét phần tử xR ∈ CR là nghiệm của (2.5), ta có
(cid:104)F (xR), xR − x0(cid:105) = −(cid:104)F (xR), x0 − xR(cid:105) ≤ 0.
Do đó, (cid:107)xR(cid:107) < R. Áp dụng Định lí 2.4 ta có điều phải chứng minh.
Nhận xét 2.5. Biểu thức (2.6) có nghĩa là với mọi α > 0 cho trước, có thể
tìm được một số ρ > 0 sao cho
≥ α ∀x ∈ C, (cid:107)x(cid:107) ≥ ρ. (cid:104)F (x) − F (x0), x − x0(cid:105) (cid:107)x − x0(cid:107)
Dễ dàng nhận thấy rằng nếu C là một tập compact thì với mọi x0 ∈ C điều kiện (2.6) được thỏa mãn. Nếu tồn tại x0 ∈ C sao cho (2.6) xảy ra thì ta nói rằng điều kiện bức được thỏa mãn.
Điều kiện bức đóng vai trò quan trọng trong nghiên cứu bất đẳng thức
biến phân khi miền ràng buộc C không compact. Cũng lưu ý rằng, điều kiện (2.6) chỉ là một trong rất nhiều dạng của điều kiện bức.
Nhận xét 2.6. Nếu F là ánh xạ α-đơn điệu mạnh thì điều kiện bức thỏa mãn. Hơn nữa, trong trường hợp này bài toán có duy nhất nghiệm. Thật vậy,
giả sử u và v là hai nghiệm thỏa mãn (2.1). Khi đó, ta có
(cid:104)F (u), v − u(cid:105) ≥ 0 và (cid:104)F (v), u − v(cid:105) ≥ 0.
Từ đây suy ra
(cid:104)F (u) − F (v), v − u(cid:105) ≥ 0.
Vì F là ánh xạ α-đơn điệu mạnh nên tồn tại α > 0 sao cho
(cid:104)F (u) − F (v), u − v(cid:105) ≥ α(cid:107)u − v(cid:107)2.
Kết hợp hai bất đẳng thức trên ta suy ra u = v.
Hệ quả 2.1. Cho C ⊂ Rn là tập con lồi đóng. Cho F : C → Rn là ánh xạ đơn điệu chặt và liên tục. Khi đó, bài toán (VIP) có duy nhất nghiệm.
Trong phần tiếp theo, chúng tôi sẽ trình bày điều kiện tồn tại nghiệm dưới
giả thiết nhẹ hơn đặt lên hàm mục tiêu F .
34
Định lí 2.6. [1]
Cho C là tập con lồi, khác rỗng của Rn và F : C → Rn là ánh xạ h-liên tục và giả đơn điệu trên C. Khi đó, nếu tồn tại một tập con compact D của Rn và u ∈ D ∩ C thỏa mãn
(cid:104)F (x), u − x(cid:105) < 0 ∀x ∈ C\D, (2.7)
thì Sol(VIP(F, C)) (cid:54)= ∅.
Chứng minh. Ta xác định hai ánh xạ đa trị P : C ⇒ C và Q : C ⇒ C tương ứng bởi
P (y) = {x ∈ C : (cid:104)F (x), y − x(cid:105) ≥ 0}
và
Q(y) = {x ∈ C : (cid:104)F (y), y − x(cid:105) ≥ 0},
với mỗi y ∈ C.
Ta sẽ chứng minh cl(P (u)) là tập compact. Trước hết, để ý rằng nếu
P (u) (cid:42) D thì tồn tại x ∈ P (u) và x ∈ C\D. Điều này dẫn đến
(cid:104)F (x), u − x(cid:105) ≥ 0,
mâu thuẫn với (2.7). Do đó, P (u) ⊆ D. Từ đó dẫn đến cl(P (u)) là tập con
compact của tập compact D.
Mặt khác, P là ánh xạ KKM (xem chứng minh Định lí 2.2) nên áp dụng
y∈C
Bổ đề 1.5 ta có (cid:92) cl(P (y)) (cid:54)= ∅.
Hơn nữa, với mỗi y ∈ C, Q(y) là tập con đóng, P (y) ⊆ Q(y) nên
cl(P (y)) ⊆ Q(y),
y∈C
và vì vậy (cid:92) Q(y) (cid:54)= ∅.
Từ đây suy ra tồn tại x ∈ C sao cho
(cid:104)F (y), y − x(cid:105) ≥ 0, ∀y ∈ C,
hay x ∈ Sol(MVIP(F, C). Áp dụng Bổ đề Minty, ta có x ∈ Sol(VIP(F, C). Định lí được chứng minh.
35
Định lí 2.7. [1]
Cho C là tập con lồi, đóng, khác rỗng của Rn và F : C → Rn là ánh xạ h-liên tục và giả đơn điệu trên C. Khi đó, nếu tồn tại một tập con compact D của Rn và u ∈ D ∩ C thỏa mãn
(cid:104)F (u), u − x(cid:105) < 0 ∀x ∈ C\D, (2.8)
thì Sol(VIP(F, C)) (cid:54)= ∅.
Chứng minh. Ta xác định hai ánh xạ đa trị P : C ⇒ C và Q : C ⇒ C tương tự như trong chứng minh Định lí 2.6. Ngoài ra, như chứng minh Định lí 2.2
ta có Q là ánh xạ KKM và Q(y) là tập con đóng của C với mỗi y ∈ C.
Ta sẽ chứng minh Q(u) là tập compact. Trước hết, để ý rằng nếu Q(u) (cid:42) D
thì tồn tại x ∈ Q(u) và x ∈ C\D. Điều này dẫn đến
(cid:104)F (u), u − x(cid:105) ≥ 0,
mâu thuẫn với (2.8). Do đó, Q(u) ⊆ D. Từ đó dẫn đến Q(u) ⊆ C ∩ D là tập
con compact của tập compact D.
Áp dụng Bổ đề 1.5 ta có
y∈C
(cid:92) Q(y) (cid:54)= ∅.
Từ đây suy ra tồn tại x ∈ C sao cho
(cid:104)F (y), y − x(cid:105) ≥ 0, ∀y ∈ C,
hay x ∈ Sol(MVIP(F, C). Áp dụng Bổ đề Minty, ta có x ∈ Sol(VIP(F, C).
Định lí được chứng minh.
Bổ đề 2.3. [1]
Cho C là tập con lồi, khác rỗng của Rn và P, Q : C ⇒ C là các ánh xạ đa
trị. Khi đó, nếu các giả thiết sau bảo đảm:
(i) Với mỗi x ∈ C, co(P (x)) ⊆ Q(x) và P (x) (cid:54)= ∅,
(ii) Với mỗi y ∈ C, P −1(y) := {x ∈ C : y ∈ P (x)} là tập mở trong C,
(iii) Nếu C không compact, giả sử rằng tồn tại một tập con compact lồi B của
C và một tập con compact khác rỗng D của C sao cho với mỗi x ∈ C\D đều tồn tại u ∈ B sao cho u ∈ P (x),
36
thì tồn tại x ∈ C thỏa mãn x ∈ Q(x).
Định lí 2.8. [1]
Cho C là tập con lồi, khác rỗng của Rn và F : C → Rn là ánh xạ h-liên tục và giả đơn điệu trên C. Khi đó, nếu tồn tại một tập con compact lồi B của C và một tập con compact khác rỗng D của C sao cho với mỗi x ∈ C\D
đều tồn tại u ∈ B thỏa mãn
(cid:104)F (x), u − x(cid:105) < 0, (2.9)
thì Sol(VIP(F, C)) (cid:54)= ∅.
Chứng minh. Ta xác định hai ánh xạ đa trị P : C ⇒ C và Q : C ⇒ C tương ứng bởi
P (x) = {y ∈ C : (cid:104)F (y), y − x(cid:105) < 0}
và
Q(x) = {y ∈ C : (cid:104)F (x), y − x(cid:105) < 0},
với mỗi x ∈ C.
Ta sẽ chứng minh Q(x) là tập lồi. Thật vậy, với mọi y1, y2 ∈ Q(x) và
λ ∈ [0, 1] ta có
λ(cid:104)F (x), y1 − x(cid:105) = (cid:104)F (x), λ(y1 − x)(cid:105) ≤ 0,
và
(1 − λ)(cid:104)F (x), y2 − x(cid:105) = (cid:104)F (x), (1 − λ)(y2 − x)(cid:105) ≤ 0.
Cộng hai vế các bất đẳng thức trên ta được
(cid:104)F (x), [λy1 + (1 − λ)y2] − x(cid:105) < 0.
Suy ra λy1 + (1 − λ)y2 ∈ Q(x) hay Q(x) là tập lồi. Vì F là giả đơn điệu nên P (x) ⊆ Q(x) và vì thế
co(P (x)) ⊆ co(Q(x)) = Q(x), ∀x ∈ C.
Với mỗi y ∈ C, tập phần bù của P −1(y)
[P −1(y)]c := {x ∈ C : (cid:104)F (y), y − x(cid:105) ≥ 0}
là tập con đóng trong C nên P −1(y) là tập con mở trong C.
37
Giả sử rằng, với mọi x ∈ C, tập P (x) khác rỗng. Khi đó, các giả thiết của
Bổ đề 2.3 được thỏa mãn. Khi đó, tồn tại ¯x ∈ C sao cho
¯x ∈ Q(¯x).
Điều này dẫn đến
0 = (cid:104)F (¯x), ¯x − ¯x(cid:105) < 0,
mâu thuẫn. Vì vậy, tồn tại x ∈ C để mà
P (x) = ∅.
Điều này tương đương với
(cid:104)F (y), y − x(cid:105) ≥ 0, ∀y ∈ C,
hay suy ra x là nghiệm của bài toán (MVIP). Áp dụng Bổ đề Minty ta có
điều cần chứng minh.
Tiếp theo, chúng tôi trình bày kết quả tồn tại nghiệm cho bài toán (VIP)
dưới giả thiết giả đơn điệu theo nghĩa Brézis.
Bổ đề 2.4. [1]
Cho C là tập con lồi, khác rỗng của Rn và ánh xạ đa trị P : C ⇒ C. Khi
đó, nếu các giả thiết sau bảo đảm:
(i) Với mỗi x ∈ C, P (x) là tập lồi,
(ii) Với mỗi tập con hữu hạn A của C và với mỗi y ∈ co(A) tập P −1(y)∩co(A)
là mở trong co(A),
(iii) Với mỗi tập con hữu hạn A của C, nếu với mọi x, y ∈ co(A) và mọi dãy {xn} trong C hội tụ đến x sao cho λy + (1 − λ)x /∈ P (xn), ∀n ∈ N, ∀λ ∈ [0, 1] thì ta có y /∈ P (x),
(iv) Tồn tại một tập con compact khác rỗng D của C và một phần tử ˜y ∈ D
mà ˜y ∈ P (x) với mọi x ∈ C\D,
(v) Với mọi x ∈ D, tập P (x) khác rỗng,
thì tồn tại ˆx ∈ C thỏa mãn ˆx ∈ P (ˆx).
38
Định lí 2.9. [1]
Cho C là một tập con lồi, khác rỗng của Rn và F : C → Rn là B-giả đơn điệu sao cho với mỗi tập con A hữu hạn của C, ánh xạ x (cid:55)→ (cid:104)F (x), y − x(cid:105) là nửa liên tục trên ở trên co(A). Khi đó, nếu tồn tại một tập con compact khác
rỗng D của C và một phần tử ˜y ∈ D thỏa mãn
(cid:104)F (x), ˜y − x(cid:105) < 0 ∀x ∈ C\D,
thì Sol(VIP(F, C)) (cid:54)= ∅.
Chứng minh. Với mỗi x ∈ C, ta xét ánh xạ đa trị P : C ⇒ C xác định bởi
P (x) = {y ∈ C : (cid:104)F (x), y − x(cid:105) < 0} .
Dễ thấy, với mọi x ∈ C, P (x) là tập lồi. Giả sử A là một tập con hữu hạn của C. Khi đó, với mọi y ∈ co(A), ta thấy
(cid:2)P −1(y)(cid:3)c ∩ co(A) = {x ∈ co(A) : (cid:104)F (x), y − x(cid:105) ≥ 0}
là tập con đóng của co(A) bởi giả thiết về tính nửa liên tục trên của ánh xạ x (cid:55)→ (cid:104)F (x), y − x(cid:105) trên co(A). Do đó, tập P −1(y) ∩ co(A) là mở trong co(A). Tiếp theo, giả sử rằng x, y ∈ co(A) và {xn} là một dãy trong C mà hội tụ
tới x thỏa mãn
∀n ∈ N, ∀λ ∈ [0, 1]. (cid:104)F (xn), λy + (1 − λ)x − xn(cid:105) ≥ 0,
Với λ = 0 ta có
∀n ∈ N (cid:104)F (xn), x − xn(cid:105) ≥ 0,
và vì thế
(cid:104)F (xn), x − xn(cid:105) ≥ 0. lim inf n→∞
Từ tính chất B-giả tính đơn điệu của F dẫn đến
n→∞
(cid:104)F (x), y − x(cid:105) ≥ lim sup (2.10) (cid:104)F (xn), x − xn(cid:105) .
Mặt khác, với λ = 1, ta lại có
∀n ∈ N (cid:104)F (xn), y − xn(cid:105) ≥ 0,
và do đó
(2.11) (cid:104)F (xn), y − xn(cid:105) ≥ 0. lim inf n→∞
39
Từ các bất đẳng thức (2.10) và (2.11), ta nhận được
(cid:104)F (x), y − x(cid:105) ≥ 0,
Điều này suy ra rằng y (cid:54)∈ P (x). Bây giờ, giả sử rằng với mọi x ∈ D, tập P (x)
khác rỗng. Khi đó, mọi giả thiết của Bổ đề 2.4 được thỏa mãn. Do đó, tồn tại ˆx ∈ C sao cho ˆx ∈ P (ˆx), tức là,
0 = (cid:104)F (ˆx), ˆx − ˆx(cid:105) < 0.
Mâu thuẫn. Do vậy, tồn tại ¯x ∈ D ⊆ C sao cho P (¯x) = ∅. Điều này dẫn đến
(cid:104)F (¯x), y − ¯x(cid:105) ≥ 0 ∀y ∈ C.
Hay nói cách khác ¯x là một nghiệm của bài toán (VIP).
Từ Định lí 2.9 ta có các hệ quả sau đây.
Hệ quả 2.2. [1]
Cho C là một tập con lồi, khác rỗng của Rn và F : C → Rn là B-giả đơn điệu sao cho với mỗi tập con A hữu hạn của C, ánh xạ x (cid:55)→ (cid:104)F (x), y − x(cid:105) là nửa liên tục trên ở trên co(A). Giả sử rằng tồn tại ˜y ∈ C thỏa mãn
(cid:104)F (x), ˜y − x(cid:105) < 0. (2.12) lim (cid:107)x(cid:107)→∞, x∈C
Khi đó, Sol(VIP(F, C)) (cid:54)= ∅.
Chứng minh. Ta đặt
α = (cid:104)F (x), ˜y − x(cid:105) . lim (cid:107)x(cid:107)→∞, x∈C
Từ bất đẳng thức (2.13) suy ra α < 0. Giả sử r > 0 sao cho (cid:107)˜y(cid:107) ≤ r và
∀x ∈ C mà (cid:107)x(cid:107) > r. , (cid:104)F (x), ˜y − x(cid:105) < α 2
Để ý rằng
Sr = {x ∈ C : (cid:107)x(cid:107) ≤ r}
là tập con đóng, bị chặn, khác rỗng (˜y ∈ Sr) của C và vì thế nó là tập con compact khác rỗng của C. Mặt khác, với mọi x ∈ C\Sr, ta thấy
< 0. (cid:104)F (x), ˜y − x(cid:105) < α 2
Do đó, bằng cách chọn D = Sr thì các giả thiết của Định lý 2.9 thỏa mãn. Vì thế, áp dụng Định lí 2.9 ta có điều cần chứng minh.
40
Hệ quả 2.3. [1]
Cho C là một tập con lồi, khác rỗng của Rn và F : C → Rn là B-giả đơn điệu sao cho với mỗi tập con A hữu hạn của C, ánh xạ x (cid:55)→ (cid:104)F (x), y − x(cid:105) là nửa liên tục dưới ở trên co(A). Giả sử rằng tồn tại ˜y ∈ C thỏa mãn
(cid:104)x − F (x), ˜y − x(cid:105) < 0. (2.13) lim (cid:107)x(cid:107)→∞, x∈C
Khi đó, tồn tại ¯x ∈ C là điểm bất động của ánh xạ F .
Chứng minh. Ta xét ánh xạ S : C → Rn xác định bởi
S(x) = x − F (x) ∀x ∈ C.
Khi đó, dễ thấy rằng S thỏa mãn các điều kiện giả thiết trong Hệ quả 2.2.
Do đó, tồn tại ¯x ∈ C sao cho
(cid:104)S(¯x), y − ¯x(cid:105) ≥ 0, ∀y ∈ C.
Trong bất đẳng thức trên, nếu lấy y = F (¯x) thì ta có (cid:107)¯x − F (¯x)(cid:107)2 ≤ 0. Điều này suy ra F (¯x) = ¯x. Ta có điều cần chứng minh.
2.4. Một vài phương pháp xấp xỉ nghiệm bài toán (VIP)
Để có thể ứng dụng bài toán bất đẳng thức biến phân vào thực tiễn, một
đòi hỏi tất yếu là phải có những phương pháp giải số hiệu quả cho bài toán này. Vì lẽ đó, một trong những hướng nghiên cứu quan trọng hiện nay dành
được sự quan tâm của nhiều nhà toán học trong và ngoài nước đó là việc đề xuất các phương pháp mới tìm nghiệm của bài toán (2.1) hoặc cải tiến hiệu
quả của nhiều phương pháp đã có. Cho đến nay, người ta đã thiết lập được nhiều kĩ thuật giải bất đẳng thức biến phân dựa trên phương pháp chiếu của
Goldstein hay Polyak, phương pháp điểm gần kề của Martinet, nguyên lý bài toán phụ của Cohen ... hoặc dựa trên một số kĩ thuật tìm điểm bất động như
phương pháp lặp Krasnosel’skii-Mann, phương pháp lặp Halpern và phương pháp xấp xỉ mềm ...
Tuy nhiên, trong khuôn khổ nghiên cứu của luận văn, chúng tôi chỉ trình
bày lại ba trong số những kết quả đã biết về các phương pháp xấp xỉ nghiệm cho bài toán (VIP) cùng với việc xây dựng các ví số cụ thể minh họa cho
41
các phương pháp này. Các ví dụ trong phần này được lập trình tính toán trên phần mềm Matlab 7.0 và đã chạy thử nghiệm trên máy tính ASUSPRO,
CPU Intel Core i5-4210U, 1.7 GHz upto 2.4 GHz., RAM 4G.
Khi hàm mục tiêu có tính đơn điệu mạnh, phương pháp lặp điển hình để
giải bài toán (2.1) là phương pháp chiếu gradient [5, 9] được mô tả như sau:
x0 ∈ C, (2.14) k = 0, 1, 2, . . . xk+1 = PC(I − ρF )(xk),
trong đó PC là phép chiếu mêtric từ Rn lên C, I là ánh xạ đơn vị trên Rn và ρ là một hằng số dương cố định. Sự hội tụ của thuật toán được phát biểu
trong định lí dưới đây.
Định lí 2.10. [9]
Cho C là tập con lồi đóng khác rỗng của Rn và F : C → Rn là ánh xạ xác
định trên Rn. Giả sử các điều kiện sau thỏa mãn:
(i) F là ánh xạ L-liên tục Lipschitz và η-đơn điệu mạnh,
(ii) ρ ∈ (0, 2η/L2).
Khi đó, dãy lặp (2.14) hội tụ tới nghiệm duy nhất x∗ của bài toán (2.1).
Chứng minh. Vì F là ánh xạ L-liên tục Lipschitz và η-đơn điệu mạnh nên bài toán (VIP) có duy nhất nghiệm x∗ (Nhận xét 2.6). Hơn nữa, ta có
x∗ = PC(x∗ − ρF (x∗)).
Từ tính không giãn của PC và các giả thiết đặt lên F ta có ước lượng sau
(cid:107)xk+1 − x∗(cid:107)2 = (cid:107)PC(I − ρF )(xk) − x∗(cid:107)2
= (cid:107)PC(I − ρF )(xk) − PC(x∗ − ρF (x∗))(cid:107)2 ≤ (cid:107)[xk − ρF (xk)] − [x∗ − ρF (x∗)](cid:107)2 = (cid:107)(xk − x∗) − ρ(F (xk) − F (x∗))(cid:107)2 = (cid:107)xk − x∗(cid:107)2 − 2ρ(cid:104)xk − x∗, F (xk) − F (x∗)(cid:105)
+ ρ2(cid:107)F (xk) − F (x∗)(cid:107)2
≤ (cid:107)xk − x∗(cid:107)2 − 2ρη(cid:107)xk − x∗(cid:107)2
42
+ ρ2(cid:107)F (xk) − F (x∗)(cid:107)2
≤ (1 − 2ρη + ρ2L2)(cid:107)xk − x∗(cid:107)2.
Từ đó suy ra
∀k ≥ 0, (cid:107)xk+1 − x∗(cid:107) ≤ β(cid:107)xk − x∗(cid:107),
trong đó, β = (cid:112)1 − 2ρη + ρ2L2.
Mặt khác, vì 0 < ρ < 2η/L2 nên ta có β ∈ (0, 1) và
0 ≤ (cid:107)xk+1 − x∗(cid:107) ≤ βk(cid:107)x0 − x∗(cid:107) → 0.
Do đó, ta nhận được xk → x∗.
Tiếp theo, chúng tôi trình bày một ví dụ đơn giản vận dụng phương pháp
chiếu gradient tìm nghiệm xấp xỉ của bài toán bất đẳng thức biến phân có hàm mục tiêu là gradient của một hàm khả vi liên tục.
Ví dụ 2.3. Tìm x∗ ∈ C sao cho
ϕ(x). (2.15) ϕ(x∗) = min x∈C
trong đó, hàm mục tiêu ϕ : R2 → R có dạng
1 + x2
2 với x = (x1, x2),
ϕ(x) := (cid:107)x(cid:107)2 = x2
và C được cho bởi
C = {x = (x1, x2) ∈ R2 : x1 + x2 ≥ 0}.
Trong trường hợp này, dễ thấy x∗ = (0; 0) là nghiệm duy nhất của bài toán.
Mặt khác, gradient ∇ϕ : R2 → R2 của hàm ϕ là
∇ϕ(x) = 2x,
và điều kiện tối ưu cho bài toán (2.15) là bất đẳng thức biến phân
(cid:104)∇ϕ(x∗), y − x∗(cid:105) ≥ 0 ∀y ∈ C.
Áp dụng phương pháp (2.14) cho ví dụ này với hàm F (x) = ∇ϕ(x). Để ý rằng, ánh xạ F là 1-đơn điệu mạnh và 2-liên tục Lipschitz trên R2. Thật vậy, vì với mọi x, y ∈ R2 ta có
(cid:107)F (x) − F (y)(cid:107) = 2(cid:107)x − y(cid:107)
43
và
(cid:104)F (x) − F (y), x − y(cid:105) = 2(cid:107)x − y(cid:107)2.
2 ) được cho trong bảng sau:
1 , u(k)
Bây giờ, chọn điểm ban đầu x0 = (10, 2) và tham số ρ ∈ (0, 1/2). Khi đó, nghiệm xấp xỉ xk = (u(k)
k k u(k) 1 u(k) 2 u(k) 1 u(k) 2
2 2.500000000 0.500000000 12 0.002441406 0.000488281
4 0.625000000 0.125000000 14 0.000610351 0.000122070
6 0.156250000 0.031250000 16 0.000152587 0.000030517
8 0.039062500 0.007812500 18 0.000038146 0.000007629
Bảng 2.1: Kết quả tính toán cho phương pháp (2.14) với ρ = 1/4
10 0.009765625 0.001953125 20 0.000009536 0.000001907
Kết quả trên cho thấy phương pháp (2.14) hội tụ khá nhanh đến nghiệm chính xác của bài toán.
Tiếp theo, để thấy rõ hơn tác động của tham số ρ đến sự hội tụ của phương pháp (2.14), với cùng điểm ban đầu x0 = (10, 2), ta có bảng kết quả tính toán sau đây:
ρ k u(k) 1 u(k) 2
499/1000 20
49/100 20
4/10 20
1/10 20
1/10 50
1/100 20
1/100 500
1/1000 20
Bảng 2.2: Kết quả tính toán cho phương pháp (2.14) tương ứng với các giá trị ρ thay đổi
1/1000 5000 0.10485759 × 10−52 0.02097152 × 10−52 0.10486000 × 10−32 0.02097152 × 10−32 0.10486000 × 10−12 0.02097152 × 10−12 0.02305843009214 0.11529215046068 0.02854495 × 10−3 0.14272476 × 10−3 1.33521594351019 6.67607971755095 0.08204797 × 10−3 0.41023985 × 10−3 1.92150191405269 9.60750957026343 0.44947592 × 10−3 0.44947592 × 10−3
Ta thấy rằng, nếu tham số ρ càng gần giá trị 1/2 thì tốc độ hội tụ càng
nhanh và nếu nó càng gần 0 thì ngược lại.
44
Nếu hàm mục tiêu F đơn điệu thì ta có thể sử dụng phương pháp chiếu lai ghép được đề xuất năm 2019 bởi Dương Việt Thông và cộng sự. Định lí
sau là Hệ quả trực tiếp của Định lí 3.2 trong [8].
Định lí 2.11. [8]
Cho C là tập con lồi đóng khác rỗng của Rn. Cho Cho F : Rn → Rn là ánh xạ đơn điệu và L-liên tục Lipschitz. Giả sử {αk} là dãy các số thực thỏa mãn 0 ≤ αk < α < 1 và λ ∈ (0, 1/L). Khi đó, dãy lặp {xk} xác định bởi
x0 ∈ Rn,
yk = PC(xk − λF (xk)),
(2.16)
tk = αkxk + (1 − αk)(yk − λ(F (yk) − F (xk))), Ck = {z ∈ Rn : (cid:107)tk − z(cid:107) ≤ (cid:107)xk − z(cid:107)}, Qk = {z ∈ Rn : (cid:104)xk − z, xk − x0(cid:105) ≤ 0},
xk+1 = PCk∩Qk(x0), k ≥ 0,
hội tụ tới một nghiệm x∗ = PSol(VIP(F,C))(x0) của bài toán (2.1) khi k → ∞.
Ví dụ 2.4. Xét bài toán (2.1) với hàm mục tiêu F : R2 → R2 xác định bởi
F (x) = Ax
với A là ma trận vuông cấp hai có dạng
(cid:32) (cid:33) 1 −1 A = −1 1
và miền ràng buộc C = R2. Ta có ước lượng sau
(cid:104)F (x) − F (y), x − y(cid:105) = (cid:104)A(x) − A(y), x − y(cid:105)
= (cid:104)A(x − y), x − y(cid:105) = ((x1 − y1) − (x2 − y2))2 ≥ 0,
với mọi x = (x1, x2), y = (y1, y2) ∈ C. Suy ra, F là ánh xạ đơn điệu trên C. Ngoài ra, F không đơn điệu mạnh trên C. Thật vậy, chẳng hạn, chọn
x = (1, 1) và y = (2, 2). Khi đó, ta thấy √ 2η = η(cid:107)x − y(cid:107)2, ∀η > 0. (cid:104)F (x) − F (y), x − y(cid:105) = 0 <
45
Mặt khác, ta lại có
(cid:107)F (x) − F (y)(cid:107) = (cid:107)A(x − y)(cid:107) ≤ 2(cid:107)x − y(cid:107).
Do đó, F là ánh xạ liên tục Lipschitz với L = 2.
Bây giờ, để ý rằng
(cid:104)F (x), y − x(cid:105) ≥ 0, ∀y ∈ R2 ⇔ F (x) = 0 ⇔ Ax = 0.
Do đó, ta nhận được
Sol(VIP(F, C)) = {x = (x1, x2) ∈ R2 : x1 = x2}.
Với phân tích ở trên, phương pháp chiếu gradient không áp dụng được cho
ví dụ này. Tuy nhiên, chúng ta có thể áp dụng phương pháp chiếu lai ghép (2.16) tìm một nghiệm xấp xỉ của bài toán. Ta lấy điểm ban đầu x0 = (2, 4). Khi đó, nghiệm cần tìm là
x∗ = PSol(VIP(F,C))(x0) = (3, 3).
Bây giờ, chọn tham số lặp
αk = 1 k + 2
thỏa mãn điều kiện hội tụ Định lí 2.11.
Với một số giá trị λ ∈ (0, 1/2), ta có bảng tính toán tìm nghiệm xấp xỉ
như dưới đây:
λ
1/100 TOL=(cid:107)xk − x∗(cid:107) 0.00991555542645 509
1/1000 0.00999783127775 4967
1/4 0.00887254509932 41
98/200 0.00991555542508 509
Bảng 2.3: Kết quả tính toán cho phương pháp (2.16) tương ứng với các giá trị λ thay đổi
988/2000 0.00999782970937 Số bước lặp k Sai số 10−2 10−2 10−2 10−2 10−2 4967
Kết quả trên cho thấy, khi tham số λ càng xa giá trị trung tâm của (0, 1/2)
thì số bước lặp tính toán cần thiết càng lớn.
46
Trong trường hợp hàm mục tiêu F là giả đơn điệu, ta có thể sử dụng phương pháp chiếu gradient tăng cường tìm nghiệm xấp xỉ của bài toán (2.1). Phương
pháp kiểu loại này [7] được giới thiệu bởi Korpelevich năm 1976 khi nghiên cứu về bài toán điểm yên ngựa cùng các bài toán liên quan.
Định lí 2.12. [4]
Cho C là tập con lồi đóng khác rỗng của Rn. Cho Cho F : C → Rn là ánh xạ giả đơn điệu tương ứng với tập nghiệm Sol(VIP(F, C)) (tức là, (cid:104)F (x), x − x∗(cid:105) ≥ 0, ∀x ∈ C, ∀x∗ ∈ Sol(VIP(F, C))) và L-liên tục Lipschitz. Giả sử 0 < τ < 1/L. Khi đó, dãy lặp {xk} xác định bởi
(2.17)
x0 ∈ C, yk = PC(xk − τ F (xk)), xk+1 = PC(xk − τ F (yk)), k ≥ 0,
hội tụ tới một nghiệm của bài toán (2.1) khi k → ∞.
Chứng minh. Định lí dược chứng minh thông qua một số bước sau.
Bước 1. Nếu x∗ ∈ Sol(VIP(F, C)) thì
∀k ≥ 0. (2.18) (cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 − (1 − τ 2L2)(cid:107)yk − xk(cid:107)2,
Trước hết, vì yk ∈ C nên ta có
∀k ≥ 0. (cid:104)F (x∗), yk − x∗(cid:105) ≥ 0,
Vì F là giả đơn điệu tương ứng với tập Sol(VIP(F, C)) nên suy ra
∀k ≥ 0. (cid:104)F (yk), yk − x∗(cid:105) ≥ 0,
Điều này dẫn đến
∀k ≥ 0, (cid:104)F (yk), x∗ − xk+1 + xk+1 − yk(cid:105) ≤ 0,
hay tương đương với
∀k ≥ 0. (2.19) (cid:104)F (yk), x∗ − xk+1(cid:105) ≤ (cid:104)F (yk), yk − xk+1(cid:105),
Áp dụng Mệnh đề 1.5 ta có đánh giá sau
(cid:104)xk+1 − yk,xk − τ F (yk) − yk(cid:105)
47
= (cid:104)xk+1 − yk, xk − τ F (xk) − yk(cid:105)
+ τ (cid:104)xk+1 − yk, F (xk) − F (yk)(cid:105)
= (cid:104)xk+1 − PC(xk − τ F (xk)), xk − τ F (xk) − PC(xk − τ F (xk))(cid:105)
+ τ (cid:104)xk+1 − yk, F (xk) − F (yk)(cid:105)
≤ τ (cid:104)xk+1 − yk, F (xk) − F (yk)(cid:105).
Đặt zk = xk − τ F (yk). Từ (2.19) và đánh giá trên ta có ước lượng
(cid:107)xk+1 − x∗(cid:107)2 = (cid:107)PC(zk) − x∗(cid:107)2 = (cid:107)PC(zk) − zk + zk − x∗(cid:107)2
= (cid:107)zk − x∗(cid:107)2 + (cid:107)zk − PC(zk)(cid:107)2 + 2(cid:104)PC(zk) − zk, zk − x∗(cid:105) ≤ (cid:107)zk − x∗(cid:107)2 − (cid:107)zk − PC(zk)(cid:107)2 = (cid:107)xk − τ F (yk) − x∗(cid:107)2 − (cid:107)xk − τ F (yk) − xk+1(cid:107)2 = (cid:107)xk − x∗ − τ F (yk)(cid:107)2 − (cid:107)xk − xk+1 − τ F (yk)(cid:107)2 = (cid:107)xk − x∗(cid:107)2 − 2τ (cid:104)xk − x∗, F (yk)(cid:105) + τ 2(cid:107)F (yk)(cid:107)2
− (cid:107)xk − xk+1(cid:107)2 + 2τ (cid:104)xk − xk+1, F (yk)(cid:105) − τ 2(cid:107)F (yk)(cid:107)2
= (cid:107)xk − x∗(cid:107)2 − (cid:107)xk − xk+1(cid:107)2 + 2τ (cid:104)x∗ − xk+1, F (yk)(cid:105) ≤ (cid:107)xk − x∗(cid:107)2 − (cid:107)xk − xk+1(cid:107)2 + 2τ (cid:104)yk − xk+1, F (yk)(cid:105) = (cid:107)xk − x∗(cid:107)2 − (cid:107)xk − yk + yk − xk+1(cid:107)2 + 2τ (cid:104)yk − xk+1, F (yk)(cid:105) = (cid:107)xk − x∗(cid:107)2 − (cid:107)xk − yk(cid:107)2 − (cid:107)yk − xk+1(cid:107)2
+ 2(cid:104)xk+1 − yk, xk − τ F (yk) − yk(cid:105) (cid:107)xk − x∗(cid:107)2 − (cid:107)xk − yk(cid:107)2 − (cid:107)yk − xk+1(cid:107)2 + τ (cid:104)xk+1 − yk, F (xk) − F (yk)(cid:105)
≤ (cid:107)xk − x∗(cid:107)2 − (cid:107)xk − yk(cid:107)2 − (cid:107)yk − xk+1(cid:107)2 ∀k ≥ 0. + 2τ L(cid:107)xk+1 − yk(cid:107)(cid:107)xk − yk(cid:107),
Từ đây ta có
(cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2
− (cid:107)xk − yk(cid:107)2 − (cid:107)yk − xk+1(cid:107)2 + 2τ L(cid:107)xk+1 − yk(cid:107)(cid:107)xk − yk(cid:107)
= (cid:107)xk − x∗(cid:107)2 − (1 − τ 2L2)(cid:107)xk − yk(cid:107)2 − [τ L(cid:107)xk − yk(cid:107) − (cid:107)xk+1 − yk(cid:107)]2
48
∀k ≥ 0. ≤ (cid:107)xk − x∗(cid:107)2 − (1 − τ 2L2)(cid:107)xk − yk(cid:107)2,
Bước 2. Chứng minh dãy {xk} bị chặn. Đặt ρ = 1 − τ 2L2. Vì 0 < τ < 1/L nên suy ra ρ ∈ (0, 1). Từ chứng minh
Bước 1, ta có
∀k ≥ 0. (cid:107)xk+1 − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2,
Điều này chứng tỏ rằng {xk} bị chặn. Hơn thế nữa, vì tính bị chặn của {xk} nên tồn tại một dãy con {xkj} của nó hội tụ. Giả sử
xkj → ¯x.
Ta có ¯x ∈ C vì C là tập đóng.
Bước 3. Chứng minh
¯x ∈ Sol(VIP(F, C)).
∞ (cid:88)
Từ đánh giá (2.18) ta suy ra
k=0
ρ (cid:107)xk − yk(cid:107) ≤ (cid:107)x0 − x∗(cid:107).
Vì ρ > 0 nên bất đẳng thức trên dẫn đến (cid:107)xk − yk(cid:107) → 0.
Mặt khác, vì xkj → ¯x nên ta cũng có
ykj → ¯x.
Từ cách xác định yk, tính liên tục của hàm F và phép chiếu PC, ta có
ykj ¯x = lim j→∞
PC(xkj − τ F (xkj)) = lim j→∞
= PC(¯x − τ F (¯x))
= PC(I − τ F )(¯x).
Đẳng thức trên chứng tỏ rằng ¯x là nghiệm của bài toán (2.1).
Bước 4. Chứng minh xk → ¯x. Sử dụng (2.18) với x∗ = ¯x ta suy ra dãy {(cid:107)xk − ¯x(cid:107)} là dãy đơn điệu giảm
và vì thế nó hội tụ. Vì
(cid:107)xkj − ¯x(cid:107) = 0 (cid:107)xk − ¯x(cid:107) = lim j→∞ lim k→∞
nên suy ra điều cần chứng minh.
49
Ví dụ 2.5. Xét bài toán nêu trong Ví dụ 2.3.
Chọn điểm ban đầu x0 = (10, 2), tham số τ = ρ ∈ (0, 1/2) và sử dụng
phương pháp (2.17), ta có bảng kết quả tính toán sau đây:
k k u(k) 1 u(k) 2 u(k) 1 u(k) 2
2 5.625000000 1.125000000 12 0.316763520 0.063352704
4 3.164062500 0.632812500 14 0.178179480 0.035635896
6 1.779785156 0.355957031 16 0.100225957 0.020045191
8 1.001129150 0.200225830 18 0.056377101 0.011275420
Bảng 2.4: Kết quả tính toán cho phương pháp (2.17) với τ = 1/4
10 0.563135147 0.112627029 20 0.031712119 0.006342423
Kết quả trên cho thấy phương pháp (2.17) hội tụ đến nghiệm chính xác
của bài toán chậm hơn khá nhiều so với phương pháp (2.14).
Ví dụ 2.6. Xét bài toán (2.1) với hàm mục tiêu F : C → R2 xác định bởi
F (x) = Ax
với A là ma trận vuông cấp hai có dạng
(cid:32) (cid:33) 0 1 A = −1 0
và miền ràng buộc C = R2. Khi đó, dễ thấy rằng
(cid:104)F (x)−F (y), x−y(cid:105) = (cid:104)A(x)−A(y), x−y(cid:105) = (cid:104)A(x−y), x−y(cid:105) = 0, ∀x, y ∈ C.
nên F là ánh xạ đơn điệu trên C và vì thế nó là giả đơn điệu trên C. Hơn thế
nữa, đẳng thức trên suy ra F không là ánh xạ đơn điệu mạnh trên C. Mặt
khác, ta lại có
(cid:107)F (x) − F (y)(cid:107) = (cid:107)A(x − y)(cid:107) = (cid:107)x − y(cid:107).
Do đó, F là ánh xạ liên tục Lipschitz với L = 1.
Dễ thấy rằng, với các giả thiết trên thì bài toán (2.1) có nghiệm duy nhất
x∗ = (0, 0) vì
(cid:104)F (x), y − x(cid:105) ≥ 0, ∀y ∈ R2 ⇔ F (x) = 0 ⇔ Ax = 0 ⇔ x = 0.
50
Ngoài ra, ta luôn có
∀x ∈ R2. (cid:104)F (x), x − x∗(cid:105) = (cid:104)Ax, x(cid:105) = 0,
Rõ ràng, phương pháp chiếu gradient không áp dụng được cho ví dụ này.
Tuy nhiên, chúng ta có thể áp dụng phương pháp chiếu tăng cường tìm một nghiệm xấp xỉ của bài toán. Với điểm ban đầu x0 = (1, 2), ta có bảng kết quả tính toán số sau đây:
τ
1/100 TOL=(cid:107)xk − x∗(cid:107) 0.00999959689087 108204
1/2 0.00911599960976 53
1/3 0.00951637762850 105
2/3 0.00887072093096 39
1/4 0.00993318320306 180
3/4 0.00906093894948 39
Bảng 2.5: Kết quả tính toán cho phương pháp (2.17) tương ứng với các giá trị τ thay đổi
99/100 0.00993318320306 Số bước lặp k Sai số 10−2 10−2 10−2 10−2 10−2 10−2 10−2 550
Kết quả trên cũng cho thấy tham số τ ảnh hưởng khá lớn đến sự hội tụ của phương pháp. Tốc độ hội tụ tốt khi tham số này gần giá trị trung tâm
của khoảng (0, 1) và hội tụ khá chậm khi tham số này gần giá trị 0.
51
KẾT LUẬN
Luận văn đã nghiên cứu và trình bày lại có hệ thống một số vấn đề cơ bản
sau đây:
Một là, trình bày lại những kết quả cơ bản của giải tích lồi và giải tích hàm trong không gian hữu hạn chiều ở Chương 1 nhằm phục vụ cho việc chi
tiết hóa các nội dung chính của luận văn ở Chương 2.
Hai là, trình bày mô hình bài toán bất đẳng thức biến phân (VIP) và mối
liên hệ với bài toán bất đẳng thức biến phân Minty (MVIP). Bên cạnh đó, chúng tôi cũng giới thiệu một số lớp bài toán liên quan như bài toán giải
phương trình (hệ phương trình), bài toán cực trị, bài toán điểm bất động với
các giải thích chi tiết.
Ba là, trình bày các kết quả về sự tồn tại nghiệm của bài toán nghiên cứu
dựa trên tính chất loại đơn điệu của hàm mục tiêu khi miền ràng buộc có hoặc không có tính chất compact.
Bốn là, trình bày phương pháp chiếu gradient, phương pháp chiếu lai ghép và phương pháp chiếu tăng cường để tìm nghiệm xấp xỉ của bài toán (VIP)
cùng các ví dụ số minh họa cụ thể.
Tài liệu tham khảo
[1] Ansari Q.H., Lalitha C.S, Mehta M. (2014), Generalized Convexity, Non-
smooth Variational Inequalities, and Nonsmooth Optimization, Springer.
[2] Bauschke H. H., Combettes P. L. (2010), Convex Analysis and Monotone
Operator Theory in Hilbert Spaces, Springer.
[3] Fan K.(1961), "A generalization of Tychonoffs fixed point theorem",
Math. Ann., 142, pp. 305-310.
[4] Facchinei F., Pang J-Sh. (2003), Finite Dimensional Variational Inequal-
ities and Complementarity Problems, Volume II, Springer.
[5] Goldstein A. A. (1964), "Convex programming in Hilbert space", Bull.
Am. Math. Soc., 70, pp. 709-710.
[6] Kinderlerhrer D., Stampacchia G. (1980), An introduction to variational
inequalities and their applications, Academic Press, NewYork.
[7] Korpelevich G.M. (1976), "The extragradient method for finding saddle
points and other problems",Ekon. Mat. Metody, 12, pp. 747–756.
[8] Thong D.V., Vinh N.T., Hieu D.V.
and shrinking projection methods for variational (2019), "Accelerated hybrid inequality prob-
lems",Optimization, 68 (5), pp. 981–998.
[9] Zeidler E. (1990), Nonlinear functional analysis and its applications,
II/B, Springer.