ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ HỒNG XUYÊN
PHƯƠNG PHÁP HƯỚNG GRADIENT LIÊN HỢP CHO BÀI TOÁN TỐI ƯU LỒI TRÊN TẬP ĐIỂM BẤT ĐỘNG CỦA ÁNH XẠ KHÔNG GIÃN
Chuyên ngành: Toán ứng dụng
Mã số: 8460112
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Nguyễn Song Hà
Thái Nguyên - 2020
ii
LỜI CẢM ƠN
Luận văn này được hoàn thành tại Khoa Toán - Tin, Trường Đại học Khoa học, Đại học Thái Nguyên dưới sự hướng dẫn hết sức tận tình của Thầy giáo,
Tiến sĩ Nguyễn Song Hà. Tôi xin bày tỏ lòng kính trọng và lòng biết ơn sâu sắc nhất tới Thầy, người đã luôn theo sát, hướng dẫn, chỉ bảo cho tôi trong
suốt quá trình từ khi lựa chọn đề tài cho đến khi thực hiện và hoàn thiện luận
văn. Qua đây, tôi cũng xin được gửi lời cảm ơn đến các Thầy, Cô giáo thuộc Khoa Toán - Tin, 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, tôi xin gửi lời cảm ơn tới Ban giám hiệu, tập thể các Thầy, Cô giáo của trường Trung học
phổ thông Lương Thế Vinh nơi tôi đang công tác, đã động viên và tạo điều kiện cho tôi trong suốt thời gian học tập cũng như thực hiện đề tài.
Tác giả
Nguyễn Thị Hồng Xuyên
Mục lục
Trang bìa phụ i
Lời cảm ơn ii
Mục lục iii
Danh mục ký hiệu và chữ viết tắt v
Danh sách bảng vi
Mở đầu 1
Chương 1. Kiến thức chuẩn bị
1.1. Một số vấn đề cơ bản về không gian Hilbert . . . . . . . . . . 3 3
1.2. Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Ánh xạ đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . 9 15
1.4. Ánh xạ không giãn và điểm bất động . . . . . . . . . . . . . . 17
Chương 2. Phương pháp hướng gradient liên hợp cho một lớp
bài toán tối ưu lồi 2.1. Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 24 24
2.2. Phương pháp hướng gradient liên hợp . . . . . . . . . . . . . . 2.2.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . . . . 26 26
2.2.2 Sự hội tụ của phương pháp . . . . . . . . . . . . . . . 2.2.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . 27 34
2.3. Phương pháp hướng gradient liên hợp lai ghép . . . . . . . . . 37
2.3.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . . . . Sự hội tụ của phương pháp . . . . . . . . . . . . . . . 2.3.2 37 37
iv
2.3.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . 43
Kết luận chung và đề nghị 44
Tài liệu tham khảo 45
Danh mục ký hiệu và chữ viết tắt
H Không gian Hilbert thực H
Rn Không gian thực n chiều
Gradient của hàm f
∇f ∇2f Hessian của hàm f
(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
Phép chiếu mêtric phần tử x lên tập C PC(x)
xn (cid:42) x Dãy {xn} hội tụ yếu đến x
xn → x Dãy {xn} hội tụ mạnh đến x
(CGM) Phương pháp hướng gradient liên hợp
(HCGM) Phương pháp hướng gradient liên hợp lai ghép
Danh sách bảng
2.1 Kết quả tính toán phương pháp (CGM) với µ = 1 . . . . . . . 36
2.2 Kết quả tính toán phương pháp (CGM) với µ = 1/100 . . . . 36
2.3 Một số kết quả tính toán khác cho phương pháp (CGM) . . . 2.4 Kết quả tính toán phương pháp (HCGM) với µ = 1 . . . . . . 36 43
2.5 Một số kết quả tính toán khác cho phương pháp (HCGM) . . 43
Mở đầu
Nhiều mô hình bài toán lí thuyết và thực tiễn có thể quy về mô hình bài
toán tối ưu có dạng:
f (x), (0.1) Tìm x∗ ∈ C sao cho: f (x∗) = min x∈C
trong đó, C là tập con khác rỗng của không gian Hilbert thực H và f : C → R là hàm số xác định trên C.
Việc vận dụng lí thuyết bài toán trên vào thực tiễn đòi hỏi phải có những
phương pháp hoặc thuật toán giải số hữu hiệu. Đó là một trong những hướng nghiên cứu quan trọng và dành được sự quan tâm sâu sắc của nhiều nhà
toán học trên thế giới. Việc đề xuất các phương pháp mới hoặc cải tiến hiệu quả của nhiều phương pháp đã có giải bài toán (0.1) vẫn đang là một chủ đề
nghiên cứu cấp thiết và mang tính thời sự. Cho đến nay, người ta đã thiết
lập được nhiều kĩ thuật tìm nghiệm xấp xỉ của bài toán (0.1). Chẳng hạn, phương pháp lặp điển hình giải bài toán (0.1) là phương pháp chiếu gradient. Trường hợp đặc biệt H = Rn, phương pháp giải bài toán (0.1) có lịch sử lâu đời và có nhiều nghiên cứu mở rộng như phương pháp Newton, phương pháp
tựa Newton, phương pháp đường dốc nhất hay phương pháp gradient liên hợp . . . Các phương pháp này có cấu trúc chung là
k = 0, 1, 2, ... xk+1 = xk + αkdk,
trong đó, xk là nghiệm xấp xỉ thứ k, αk là kích thước bước lặp và dk là hướng tìm kiếm.
Mục đích chính của luận văn này là trình bày lại có hệ thống về một số phương pháp hướng gradient liên hợp tìm nghiệm xấp xỉ cho một lớp bài toán
tối ưu lồi trên không gian Hilbert thực. Cụ thể, lớp bài toán đó là "Bài toán tối ưu trên tập điểm bất động của một ánh xạ không giãn". Nội dung này
được tham khảo từ các nghiên cứu của Iiduka và cộng sự công bố năm 2009.
2
Với mục tiêu như vậy, ngoài lời 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, chúng tôi dành để hệ thống lại những
kiến thức cơ bản về giải tích lồi, toán tử đơn điệu, ánh xạ không giãn và điểm bất động nhằm phục vụ cho việc cụ thể hóa nội dung chính ở chương sau của
luận văn. Chương 2 dùng để trình bày hai phương pháp hướng gradient liên hợp giải bài toán nêu trên cùng các ví dụ số minh họa.
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 bốn phần: Mục 1.1 dành để nhắc lại một vài khái niệm và tính chất về không gian Hilbert thực H. Mục 1.2 trình bày vài vấn
đề cần thiết về tập lồi và hàm lồi. Một số nội dung về toán tử loại đơn điệu được đề cập đến trong Mục 1.3. Cuối cùng, Mục 1.4 dùng để giới thiệu về lớp
ánh xạ không giãn, phép chiếu mêtric lên một tập đóng lồi trong không gian Hilbert cùng những tính chất cốt yếu.
1.1. Một số vấn đề cơ bản về không gian Hilbert
Định nghĩa 1.1. Cho H là một không gian véctơ thực. Hàm số
(x,y)
(cid:104)., .(cid:105) : H × H → (cid:55)→ R (cid:104)x,y(cid:105)
được gọi là tích vô hướng của hai véctơ x và y nếu các điều kiện sau được
thỏa mãn: i) (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105) với mọi x, y ∈ H,
ii) (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105) với mọi x, y, z ∈ H, iii) (cid:104)αx, y(cid:105) = α(cid:104)x, y(cid:105) với mọi x, y ∈ H, α ∈ R, iv) (cid:104)x, x(cid:105) ≥ 0 với mọi x ∈ H và (cid:104)x, x(cid:105) = 0 ⇔ x = 0.
Không gian véctơ thực H với một tích vô hướng xác định như trên được
gọi là không gian tiền Hilbert.
Ví dụ 1.1. Trong không gian hữu hạn chiều Rn, 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.
Không gian Rn cùng với tích vô hướng xác định như trên là một không gian tiền Hilbert.
4
a
Ví dụ 1.2. Xét L2[a, b] là không gian các hàm số thực bình phương khả tích trên [a, b] ⊂ R, tức là (cid:90) b |x(t)|2dt < ∞ ∀x = x(t) ∈ L2[a, b].
Hàm số (cid:104)., .(cid:105) : L2[a, b] × L2[a, b]→R xác định bởi
a
(cid:90) b (cid:104)x, y(cid:105) = x(t)y(t)dt ∀x = x(t), y = y(t) ∈ L2[a, b],
là một tích vô hướng trên L2[a, b] và L2[a, b] là một không gian tiền Hilbert.
Mệnh đề 1.1. (Bất đẳng thức Schwarz)
Trong không gian tiền Hilbert H ta luôn có
|(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105)(cid:104)y, y(cid:105), ∀x, y ∈ H.
Chứng minh. Hiển nhiên y = 0 bất đẳng thức đúng. Giả sử y (cid:54)= 0 và với mọi λ ∈ R ta có
(cid:104)x + λy, x + λy(cid:105) ≥ 0.
Điều này dẫn đến
(cid:104)x, x(cid:105) + 2λ(cid:104)x, y(cid:105) + λ2(cid:104)y, y(cid:105) ≥ 0.
và thay vào bất đẳng thức trên ta nhận được Chọn λ = − (cid:104)x, y(cid:105) (cid:104)y, y(cid:105)
(cid:104)x, x(cid:105) − ≥ 0. |(cid:104)x, y(cid:105)|2 (cid:104)y, y(cid:105)
Từ đây suy ra điều cần chứng minh.
Mệnh đề 1.2. Cho H là một không gian tiền Hilbert. Hàm số (cid:107).(cid:107) : H → R xác định bởi
(cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) x ∈ H, (1.1)
là một chuẩn trên H và chuẩn này gọi là chuẩn sinh ra bởi tích vô hướng.
Chứng minh. Hiển nhiên, từ (1.1) và điều kiện iv) trong định nghĩa tích vô hướng, ta có (cid:107)x(cid:107) ≥ 0 và (cid:107)x(cid:107) = 0 ⇔ x = 0.
Tiếp theo, với mọi x ∈ H và λ ∈ R ta thấy
(cid:107)λx(cid:107) = (cid:112)(cid:104)λx, λx(cid:105) = |λ|(cid:112)(cid:104)x, x(cid:105) = |λ|(cid:107)x(cid:107).
5
Cuối cùng, sử dụng bất đẳng thức Schwarz, với mọi x, y ∈ H ta có
(cid:107)x + y(cid:107)2 = (cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105) + (cid:107)y(cid:107)2 ≤ (cid:107)x(cid:107)2 + 2(cid:107)x(cid:107)(cid:107)y(cid:107) + (cid:107)y(cid:107)2
= ((cid:107)x(cid:107) + (cid:107)y(cid:107))2.
Suy ra (cid:107)x + y(cid:107) ≤ (cid:107)x(cid:107) + (cid:107)y(cid:107).
Mệnh đề 1.3. (Quy tắc hình bình hành)
Trong không gian tiền Hilbert H ta luôn có
(cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 2((cid:107)x(cid:107)2 + (cid:107)y(cid:107)2), ∀x, y ∈ H.
Chứng minh. Ta có
(cid:107)x + y(cid:107)2 = (cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105) + (cid:107)y(cid:107)2, ∀x, y ∈ H,
và
(cid:107)x − y(cid:107)2 = (cid:107)x(cid:107)2 − 2(cid:104)x, y(cid:105) + (cid:107)y(cid:107)2, ∀x, y ∈ H.
Cộng hai vế các đẳng thức trên ta có điều cần chứng minh.
Định nghĩa 1.2. Không gian tiền Hilbert H đầy đủ với chuẩn xác định bởi
(1.1) được gọi là một không gian Hilbert.
Nhận xét 1.1. [1]
Cho H là một không gian định chuẩn thực. Nếu quy tắc hình bình hành
bảo đảm đối với chuẩn, tức là
(cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 2((cid:107)x(cid:107)2 + (cid:107)y(cid:107)2) ∀x, y ∈ H.
thì trên H tồn tại một tích vô hướng sao cho (cid:104)x, x(cid:105) = (cid:107)x(cid:107)2. Thật vậy, ta đặt
[(cid:107)x + y(cid:107)2 − (cid:107)x − y(cid:107)2] ∀x, y ∈ H. (cid:104)x, y(cid:105) = 1 4
Ta sẽ chứng minh hàm số trên là một tích vô hướng trên H.
i) Hiển nhiên, (cid:104)x, x(cid:105) ≥ 0 với mọi x ∈ H và (cid:104)x, x(cid:105) = 0 ⇔ x = 0. ii) Hiển nhiên, (cid:104)x, y(cid:105) = (cid:104)y, y(cid:105) với mọi x, y ∈ H.
iii) Từ quy tắc hình bình hành và cách xác định (cid:104)x, y(cid:105) ta có thể viết (cid:104)x, y(cid:105)
dưới các dạng
[(cid:107)x + y(cid:107)2 − (cid:107)x(cid:107)2 − (cid:107)y(cid:107)2] (∗) (cid:104)x, y(cid:105) = 1 2
6
hoặc
(cid:104)x, y(cid:105) = [(cid:107)x(cid:107)2 + (cid:107)y(cid:107)2 − (cid:107)x − y(cid:107)2] (∗∗) 1 2
Để ý rằng
[(cid:107)(x + y) + z(cid:107)2 − (cid:107)(x + y) − z(cid:107)2] (cid:104)x + y, z(cid:105) =
[(cid:107)(x + y) + z(cid:107)2 + (cid:107)(x − y) + z(cid:107)2] = 1 4 1 4
− [(cid:107)(x − y) + z(cid:107)2 + (cid:107)(x + y) − z(cid:107)2]
1 4 [(cid:107)x + z(cid:107)2 + (cid:107)y(cid:107)2] − = [(cid:107)y − z(cid:107)2 + (cid:107)x(cid:107)2]. 1 2 1 2
Từ (*) và (**) ta có đánh giá
(cid:104)x + y, z(cid:105) = [(cid:107)x + z(cid:107)2 + (cid:107)y(cid:107)2] − [(cid:107)y − z(cid:107)2 + (cid:107)x(cid:107)2] 1 2
= [(cid:107)x + z(cid:107)2 − (cid:107)x(cid:107)2 − (cid:107)z(cid:107)2] + [(cid:107)y(cid:107)2 + (cid:107)z(cid:107)2 − (cid:107)y − z(cid:107)2] 1 2 1 2 1 2
= (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105)
iv) Cuối cùng, ta chứng minh (cid:104)λx, y(cid:105) = λ(cid:104)x, y(cid:105). Trước hết, với mỗi x, y ∈ H
cố định, ta xét hàm số g(λ) = (cid:107)λx + y(cid:107). Khi đó, ta có
|g(λ1) − g(λ2)| ≤ |λ1 − λ2|(cid:107)x(cid:107).
Bất đẳng thức trên suy ra g là hàm liên tục theo λ và vì thế hàm số
f (λ) = (cid:104)λx, y(cid:105)
cũng liên tục theo λ. Hơn nữa, theo chứng minh trên ta có f là hàm cộng
tính. Do đó, f là hàm tuyến tính. Tức là, f (λ) = Cλ với C là hằng số nào đó. Mặt khác, để ý rằng C = f (1) = (cid:104)x, y(cid:105). Từ đây ta có điều cần chứng minh.
Như vậy, một không gian Hilbert là không gian định chuẩn có chuẩn thỏa
mãn quy tắc hình bình hành.
Ví dụ 1.3. [2]
Các không gian lp, Lp[a, b] (1 ≤ p < ∞) là không gian Hilbert khi và chỉ
khi p = 2.
Ví dụ 1.4. Xét không gian C[a, b] với chuẩn
|x(t)|, x = x(t) ∈ C[a, b]. (cid:107)x(cid:107) = max a≤t≤b
7
Chuẩn này không thỏa mãn quy tắc hình bình hành và vì thế C[a, b] không
là không gian Hilbert. Thật vậy, chọn x = x(t) = 1 và y = y(t) = với t − a b − a mọi t ∈ [a, b]. Khi đó, ta có
= 1. (cid:107)x(cid:107) = 1 và (cid:107)y(cid:107) = max a≤t≤b t − a b − a (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
Mặt khác, ta lại có
= 2 1 + (cid:107)x + y(cid:107) = max a≤t≤b = max a≤t≤b t − a b − a t + b − 2a b − a (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
và
= 1. 1 − = max a≤t≤b (cid:107)x − y(cid:107) = max a≤t≤b t − a b − a b − t b − a (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
Do đó, ta nhận được
(cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 5.
Tuy nhiên
2 (cid:0)(cid:107)x(cid:107)2 + (cid:107)y(cid:107)2(cid:1) = 4.
Mệnh đề 1.4. Trong không gian Hilbert H, ta luôn có
(cid:107)x(cid:107)2 + 2(cid:104)y, x(cid:105) ≤ (cid:107)x + y(cid:107)2 ≤ (cid:107)x(cid:107)2 + 2(cid:104)y, x + y(cid:105),
với mọi x, y ∈ H.
Chứng minh. Với mọi x, y ∈ H ta có
(cid:107)x + y(cid:107)2 = (cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105) + (cid:107)y(cid:107)2.
Do đó, ta nhận được
(cid:107)x + y(cid:107)2 ≥ (cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105).
Mặt khác, ta lại có
(cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105) + (cid:107)y(cid:107)2 ≤ (cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105) + 2(cid:107)y(cid:107)2 = (cid:107)x(cid:107)2 + 2(cid:104)y, x + y(cid:105)
nên suy ra
(cid:107)x + y(cid:107)2 ≤ (cid:107)x(cid:107)2 + 2(cid:104)y, x + y(cid:105).
Ta có điều cần chứng minh.
8
Mệnh đề 1.5. Trong không gian Hilbert H, ta luôn có
(cid:107)λx + (1 − λ)y(cid:107)2 + λ(1 − λ)(cid:107)x − y(cid:107)2 = λ(cid:107)x(cid:107)2 + (1 − λ)(cid:107)y(cid:107)2
với mọi x, y ∈ H và λ ∈ R.
Chứng minh. Ta có
(cid:107)λx + (1 − λ)y(cid:107)2 = λ2(cid:107)x(cid:107)2 + (1 − λ)2(cid:107)y(cid:107)2 + 2λ(1 − λ)(cid:104)x, y(cid:105), λ(1 − λ)(cid:107)x − y(cid:107)2 = λ(1 − λ)(cid:107)x(cid:107)2 + λ(1 − λ)(cid:107)y(cid:107)2 − 2λ(1 − λ)(cid:104)x, y(cid:105)
Cộng hai vế các đẳng thức trên ta có điều cần chứng minh.
Định nghĩa 1.3. Dãy {xn} các phần tử trong không gian Hilbert H được gọi là
(i) hội tụ mạnh đến x ∈ H khi n tiến ra +∞ nếu
(cid:107)xn − x(cid:107) = 0, lim n→+∞
và kí hiệu là xn → x.
(ii) hội tụ yếu đến x ∈ H khi n tiến ra +∞ nếu
∀y ∈ H, (cid:104)xn, y(cid:105) = (cid:104)x, y(cid:105), lim n→+∞
và kí hiệu là xn (cid:42) x.
Nhận xét 1.2. Một dãy hội tụ mạnh là hội tụ yếu. Tuy nhiên, khẳng định ngược lại nói chung không đúng. Chẳng hạn, dãy {en} (hệ trực chuẩn) trong không gian l2 là một dãy có tính chất như vậy.
Mệnh đề 1.6. Trong không gian Hilbert H nếu các điều kiện sau bảo đảm xn (cid:42) x và (cid:107)xn(cid:107) → (cid:107)x(cid:107) thì xn → x. Chứng minh. Với mọi n ∈ N ta có
(cid:107)xn − x(cid:107)2 = (cid:107)xn(cid:107)2 + (cid:107)x(cid:107)2 − 2(cid:104)xn, x(cid:105).
Từ giả thiết suy ra
(cid:107)xn(cid:107)2 → (cid:107)x(cid:107)2 và (cid:104)xn, x(cid:105) → (cid:107)x(cid:107)2.
Do đó, ta nhận được
(cid:107)xn − x(cid:107)2 → 0.
Hay suy ra xn → x.
9
Để thuận tiện cho việc trình bày những nội dung tiếp theo, kể từ đây ta luôn kí hiệu H là không gian Hilbert thực với tích vô hướng (cid:104)., .(cid:105) và chuẩn
sinh bởi tích vô hướng này là (cid:107).(cid:107) nếu không nói gì thêm.
1.2. Tập lồi và hàm lồi
Định nghĩa 1.4. Tập C ⊆ H đượ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 ⊆ H 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.5. Các nửa không gian đóng, các hình cầu đóng trong H dưới đây là các tập lồi
∆ := {x ∈ H : (cid:104)a, x(cid:105) ≤ α},
B[x0, r] := {x ∈ H : (cid:107)x − x0(cid:107) ≤ r},
trong đó a, x0 ∈ H là các phần tử cố định, α và r > 0 là các số thực.
Một vài tính chất cơ bản về tập lồi được phát biểu trong mệnh đề sau đây.
Mệnh đề 1.7. Trong không gian Hilbert H, ta luôn có
(i) Giao của một họ tùy ý các tập lồi là lồi.
(ii) Tổng của hai tập lồi là lồi.
(iii) Tích Descartes của hai tập lồi là tập lồi.
(iv) Nếu C là tập lồi thì αC cũng là tập lồi với mọi số thực α.
(iv) Ả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.
m (cid:88)
Định nghĩa 1.5. Véctơ x ∈ H được gọi là tổ hợp lồi của các véctơ xi ∈ H
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.
10
Mệnh đề 1.8. Cho C ⊆ H 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
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.6. Cho C ⊆ H là tập lồi khác rỗng. Hàm f : C → R được gọi là hàm lồi 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).
11
Nhận xét 1.3. Nếu f là một hàm lồi thì giá trị của nó tại một tổ hợp lồi nào đó của hai điểm bất kỳ x, y không lớn hơn giá trị nhận được khi lấy cùng
tổ hợp lồi như thế của hai giá trị f (x), f (y).
Về mặt hình học, đồ thị của hàm lồi không khi nào nằm cao hơn dây cung
nối hai điểm bất kỳ của nó. Tập các điểm nằm về phía trên đồ thị của một hàm lồi, còn gọi là tập trên đồ thị của f , kí hiệu và xác định bởi
epi(f ) := {(x, r) ∈ H × R : f (x) ≤ r}
luôn là một tập lồi.
Ví dụ 1.6. Hàm chuẩn (cid:107) · (cid:107) : H → R là một hàm lồi. Thật vậy, ta luôn có
(cid:107)λx + (1 − λ)y(cid:107) ≤ λ(cid:107)x(cid:107) + (1 − λ)(cid:107)y(cid:107) ∀x, y ∈ H, ∀λ ∈ [0, 1].
Ví dụ 1.7. [3, 5]
Hàm f : H → R xác định bởi
(cid:104)x, Q(x)(cid:105) + (cid:104)b, x(cid:105) x ∈ H, f (x) = 1 2
là hàm lồi, trong đó Q : H → H là ánh xạ tuyến tính bị chặn, tự liên hợp (tức là, (cid:104)x, Q(y)(cid:105) = (cid:104)Q(y), x(cid:105) với mọi x, y ∈ H) thỏa mãn
(cid:104)x, Q(x)(cid:105) ≥ α(cid:107)x(cid:107)2,
với α > 0 nào đó và b ∈ H cố định.
Nhận xét 1.4. Cho C ⊂ H là tập lồi khác rỗng và f : C → R là hàm lồi. Khi đó, mọi điểm cực tiểu địa phương của f đều là điểm cực tiểu toàn cục
của nó. Hơn nữa, nếu f là hàm lồi chặt, tức là
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x (cid:54)= y ∈ C, ∀λ ∈ [0, 1]
thì điểm cực tiểu nếu có của hàm f là duy nhất.
Thật vậy, giả sử x là điểm cực tiểu địa phương của f . Tức là, tồn tại ε > 0
sao cho
f (x) ≤ f (y) ∀y ∈ C mà (cid:107)y − x(cid:107) < ε.
Nếu x không là điểm cực tiểu toàn cục của f thì tồn tại z ∈ C, z (cid:54)= x sao cho f (z) < f (x). Đặt u = λz + (1 − λ)x, λ ∈ [0, 1]. Do C lồi nên u ∈ C và
(cid:107)u − x(cid:107) = λ(cid:107)z − x(cid:107) < ε,
12
với λ đủ nhỏ. Mặt khác, vì f lồi nên ta lại có
f (u) ≤ λf (z) + (1 − λ)f (x) = f (x) + λ(f (z) − f (x)) < f (x).
Mâu thuẫn. Do đó, x là điểm cực tiểu toàn cục.
Tiếp theo, giả sử f là hàm lồi chặt và x (cid:54)= y ∈ C là hai điểm cực tiểu của
∈ C vì tính lồi của tập C và hiển nhiên hàm f . Để ý rằng x + y 2 (cid:19) (cid:19) f (x) ≤ f , f (y) ≤ f . (cid:18)x + y 2 (cid:18)x + y 2
Mặt khác, từ tính lồi chặt của f ta lại có
(cid:19) f < f (x) + f (y). (cid:18)x + y 2 1 2 1 2
Từ các bất đẳng thức trên suy ra
(cid:19) (cid:19) f < f (x) + f (y) ≤ f . (cid:18)x + y 2 1 2 1 2 (cid:18)x + y 2
Mâu thuẫn. Vì thế, ta phải có x = y hay điểm cực tiểu nếu có của hàm f là
duy nhất.
Định nghĩa 1.7. Cho f : C → R là hàm lồi trên C ⊆ H. (i) Phần tử x∗ ∈ H đượ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∗ ∈ H : 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.8. Cho f : R → R xác định bởi
f (x) = x2 + |x − 1|.
Khi đó, dưới vi phân của hàm f là
∂f (x) = nếu x = 1,
{2x − 1} nếu x < 1, {[1, 3]} {2x + 1} nếu x > 1.
13
Định nghĩa 1.8. Cho f : C → R là hàm xác định trên C ⊆ H. 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 điểm 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 điểm x ∈ C.
Nhận xét 1.5. [2] Nếu f : C → R khả vi Fréchet tại x ∈ C thì nó cũng khả vi Gâteaux. Khẳng định ngược lại nói chung không đúng.
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.9. [2]
Cho f : H → R là hàm lồi. Khi đó, ta có các khẳng định sau:
G(x) = x∗ và f khả dưới vi phân
(i) Nếu f khả vi Gâteaux tại x ∈ H 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 ∈ H 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 (x).
f
14
Mệnh đề 1.10. [2]
Cho C là tập con lồi mở khác rỗng của H. Cho f : H → R là hàm khả vi
Gâteaux (Fréchet) trên H. Khi đó, ta có các khẳng định sau:
(i) f là hàm lồi trên C khi và chỉ khi
f (y) ≥ f (x) + (cid:104)∇f (x), y − x(cid:105), ∀x, y ∈ C.
(ii) f là hàm lồi chặt trên C khi và chỉ khi
f (y) > f (x) + (cid:104)∇f (x), y − x(cid:105), ∀x (cid:54)= y ∈ C.
Chứng minh. (i) Trước hết, giả sử rằng
f (y) ≥ f (x) + (cid:104)∇f (x), y − x(cid:105), ∀x, y ∈ C.
Ta đặt z = αx + (1 − α)y ∈ C với α ∈ [0, 1]. Từ giả thiết trên suy ra
f (x) ≥ f (z) + (cid:104)∇f (z), x − z(cid:105),
f (y) ≥ f (z) + (cid:104)∇f (z), y − z(cid:105).
Nhân bất đẳng thức thứ nhất với α, bất đẳng thức thứ hai với 1 − α, sau đó
cộng hai bất thức này lại ta nhận được αf (x) + (1 − α)f (y) ≥ f (z). Do đó, ∀x, y ∈ C và α ∈ [0, 1] ta có
f (αx + (1 − α)y) ≤ αf (x) + (1 − α)f (y).
Vì thế f là hàm lồi trên C.
Ngược lại, giả sử f là hàm lồi trên C. Với x (cid:54)= z tùy ý trong C và α ∈ (0, 1]
ta xét hàm số
g(α) = f (x + α(z − x)) − f (x) α
Ta có g là ánh xạ đơn điệu theo α trên (0, 1]. Thật vậy, giả sử 0 < a < b ≤ 1, ta đặt
0 < λ = < 1, w = x + b(z − x). a b
Vì f lồi nên
f (x + λ(w − x)) ≤ λf (w) + (1 − λ)f (x)
hay tương đương với
≤ f (w) − f (x). f (x + λ(w − x)) − f (x) λ
15
(cid:17) x + f − f (x) Từ đây dẫn đến (cid:16) a b ≤ f (x + b(z − x)) − f (x).
([x + b(z − x)] − x) a b
Từ bất đẳng thức trên dẫn đến
g(a) ≤ g(b).
Do đó, ta nhận được
g(α) ≤ g(1) = f (z) − f (x). (cid:104)∇f (x), z − x(cid:105) = lim α→0
(ii) Chứng minh tương tự (sử dụng tính lồi chặt của hàm f , ta sẽ chỉ ra
được g là ánh xạ đơn điệu chặt theo α).
1.3. Ánh xạ đơn điệu
Trong phần này, chúng tôi sẽ nhắc lại một vài khái niệm và tính chất cơ
bản về ánh xạ (toán tử) loại đơn điệu.
Định nghĩa 1.9. Cho C ⊆ H là tập con khác rỗng và F : C → H 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.2)
(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.3)
(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.4)
Nhận xét 1.6. 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.
16
Ví dụ 1.9. Cho C = R. Ánh xạ F : R → R xác định bởi F (x) = 2x là ánh xạ 2-đơ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.
nếu x < 0, Ánh xạ F : R → R xác định bởi 1 F (x) = x2 + 1 nếu x ≥ 0,
là ánh xạ đơn điệu trên R nhưng không đơn điệu chặt.
1 + x2 nếu x ≥ 0, Ánh xạ F : R → R xác định bởi F (x) = 1 − x2 nếu x ≤ 0,
là ánh xạ đơn điệu chặt trên R nhưng không đơn điệu mạnh.
Tiếp theo, ta có tính lồi của một hàm f khả vi Gâteaux (Fréchet) có thể
đặc trưng bởi tính đơn điệu của ∇f như dưới đây.
Mệnh đề 1.11. [3]
Cho C ⊆ H là tập con lồi khác rỗng và f : C → R là hàm khả vi Gâteaux (Fréchet) liên tục. Khi đó, hàm f là lồi khi và chỉ khi gradient ∇f là ánh xạ đơn điệu.
Chứng minh. Giả sử f là hàm lồi. Từ 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.
Đổ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).
17
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.
Chú ý 1.1. Trong không gian hữu hạn chiều Rn, hàm khả vi đến cấp hai f : Rn → R là lồi khi và chỉ ma trận Hessian ∇2f (x) (ma trận các đạo hàm riêng cấp hai) là nửa xác định dương, tức là
(cid:104)v, ∇2f (x)v(cid:105) ≥ 0, ∀v ∈ Rn.
1.4. Ánh xạ không giãn và điểm bất động
Định nghĩa 1.10. Cho F : H → H là ánh xạ xác định trên H. Á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 ∈ H. (1.5)
Nếu (1.5) đúng với L = 1 thì ánh xạ F được gọi là ánh xạ không giãn còn nếu (1.5) đúng với 0 ≤ L < 1 thì ánh xạ F được gọi là ánh xạ co.
18
Ví dụ 1.10. Xét ánh xạ F : R2 → R2 xác định bởi
F (x) = A(x), ∀x = (u, v) ∈ R2,
trong đó A là ma trận vuông có dạng
(cid:32) (cid:33) a 0 A = , a ∈ R. 0 a
Khi đó, với mọi x, y ∈ R2, ta có
(cid:107)F (x) − F (y)(cid:107) = (cid:107)A(x) − A(y)(cid:107) = (cid:107)A(x − y)(cid:107) = |a|(cid:107)x − y(cid:107).
Do đó, F là ánh xạ |a|-liên tục Lipschitz. Hơn nữa, ta thấy rằng:
(i) Nếu |a| < 1 thì F là ánh xạ co.
(ii) Nếu |a| = 1 thì F là ánh xạ không giãn.
(iii) Nếu |a| > 1 thì F không phải là ánh xạ co, không giãn.
Định nghĩa 1.11. Cho C là một tập con khác rỗng của H và T : 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
T nếu T (x) = x. Tập tất các điểm bất động của ánh xạ T được kí hiệu là Fix(T ), tức là
Fix(T ) = {x ∈ C : T (x) = x}.
Tính chất điểm bất động của ánh xạ không giãn được phát biểu trong
mệnh đề sau.
Mệnh đề 1.12. Cho C là một tập con đóng lồi khác rỗng của H. Khi đó, tập Fix(T ) của ánh xạ không giãn T : C → C là tập đóng lồi.
Chứng minh. Trước hết, dễ thấy rằng ánh xạ không giãn T là một ánh xạ liên tục trên C.
Giả sử {xn} là một dãy các phần tử trong tập Fix(T ) và xn → x ∈ H. Hiển nhiên, x ∈ C vì C là tập đóng. Do T là ánh xạ liên tục nên T (xn) → T (x). Mặt khác, vì T (xn) = xn nên ta cũng có T (xn) → x. Điều này dẫn đến x = T (x) hay x ∈ Fix(T ). Do đó, Fix(T ) là tập đóng. Tiếp theo, lấy tùy ý x, y ∈ Fix(T ), λ ∈ (0, 1) và đặt
z = λx + (1 − λ)y.
19
Khi đó, ta có z ∈ C vì tính lồi của C. Áp dụng Mệnh đề 1.5 ta có ước lượng
(cid:107)T (z) − z(cid:107)2 = (cid:107)T (z) − (λx + (1 − λ)y)(cid:107)2
= (cid:107)λ[T (z) − x] + (1 − λ)[T (z) − y](cid:107)2 = (cid:107)λ[T (z) − T (x)] + (1 − λ)[T (z) − T (y)](cid:107)2 = λ(cid:107)T (z) − T (x)(cid:107)2 + (1 − λ)(cid:107)T (z) − T (y)(cid:107)2
− λ(1 − λ)(cid:107)T (x) − T (y)(cid:107)2 ≤ λ(cid:107)z − x(cid:107)2 + (1 − λ)(cid:107)z − y(cid:107)2 − λ(1 − λ)(cid:107)T (x) − T (y)(cid:107)2 = λ(cid:107)z − x(cid:107)2 + (1 − λ)(cid:107)z − y(cid:107)2
− λ(1 − λ)(cid:107)x − y(cid:107)2
= (cid:107)λ(z − x) + (1 − λ)(z − y)(cid:107)2 = (cid:107)z − z(cid:107)2 = 0.
Do đó, T (z) = z hay z ∈ Fix(T ). Vì thế, Fix(T ) là tập lồi.
Mệnh đề 1.13. [2]
Cho C là tập con lồi đóng khác rỗng của H. Khi đó, với mỗi x ∈ H tồn
tại duy nhất một điểm y ∈ C thỏa mãn
(cid:107)x − y(cid:107) = d(x, C),
(cid:107)x − z(cid:107). với d(x, C) = 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,
20
(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 Hilbert H. Do đó, tồn tại giới hạn của dãy trên và giả sử rằng
yn → y.
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.
Chú ý 1.2. Điểm y ∈ C trong Mệnh đề 1.13 còn được gọi là xấp xỉ tốt nhất của x ∈ H bởi C.
Định nghĩa 1.12. Cho C là tập con lồi đóng khác rỗng của H. Ánh xạ PC : H → C xác định bởi (cid:26) (cid:27) y ∈ C : (cid:107)x − y(cid:107) = d(x, C) ∀x ∈ H PC(x) =
được gọi là phép chiếu mêtric từ H lên C.
Ví dụ 1.11. [2]
Giả sử C := {x ∈ Rn : (cid:104)x, u(cid:105) ≤ ζ} là nửa không gian đóng trong Rn với
ζ ∈ 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.
21
nếu (cid:104)x, u(cid:105) ≤ ζ, 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) = x + u nếu (cid:104)x, u(cid:105) > ζ. ζ − (cid:104)x, u(cid:105) (cid:107)u(cid:107)2
Ví dụ 1.12. [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 đề 1.14. [2]
Cho C ⊆ H 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.13, 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
22
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 H. 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 ∈ H.
Chứng minh. Với mọi x, y ∈ H, từ Mệnh đề 1.14 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.
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).
Ta có điều cần chứng minh.
Mệnh đề dưới đây là một trong những chìa khóa quan trọng sẽ được sử dụng để chứng minh sự hội tụ của các thuật toán đề cập đến ở chương sau.
Mệnh đề 1.15. [3]
Cho T : H → H là ánh xạ không giãn và f : H → R là hàm khả vi Fréchet liên tục. Giả sử ∇f : H → H là ánh xạ α-đơn điệu mạnh, L-liên tục Lipschitz và µ ∈ (0, 2α/L2). Ta định nghĩa ánh xạ T λ : H → H như sau
T λ(x) := T (x − µλ∇f (x)), x ∈ H, λ ∈ [0, 1].
Khi đó, với mọi x, y ∈ H ta có
(cid:107)T λ(x) − T λ(y)(cid:107) ≤ (1 − λτ )(cid:107)x − y(cid:107),
ở đây, τ := 1 − (cid:112)1 − µ(2α − µL2) ∈ (0, 1].
23
Chứng minh. Với mọi x, y ∈ H ta có
(cid:107)(µ∇f (x) − x) − (µ∇f (y) − y)(cid:107)2 = (cid:107)µ(∇f (x) − ∇f (y)) − (x − y)(cid:107)2
= µ2(cid:107)∇f (x) − ∇f (y)(cid:107)2
− 2µ(cid:104)∇f (x) − ∇f (y), x − y(cid:105) + (cid:107)x − y(cid:107)2.
Từ tính α-đơn điệu mạnh, L-liên tục Lipschitz của ∇f ta nhận được
(cid:107)(µ∇f (x) − x) − (µ∇f (y) − y)(cid:107)2 ≤ µ2L2(cid:107)x − y(cid:107)2 − 2µα(cid:107)x − y(cid:107)2 + (cid:107)x − y(cid:107)2
= (1 − µ(2α − µL2))(cid:107)x − y(cid:107)2.
Do đó, ta nhận được
(cid:107)(µ∇f (x) − x) − (µ∇f (y) − y)(cid:107) ≤ (cid:112)1 − µ(2α − µL2)(cid:107)x − y(cid:107) ∀x, y ∈ H.
Mặt khác, để ý rằng
(cid:107)T λ(x) − T λ(y)(cid:107) = (cid:107)T (x − µλ∇f (x)) − T (y − µλ∇f (y))(cid:107)
≤ (cid:107)(x − µλ∇f (x)) − (y − µλ∇f (y))(cid:107)
= (cid:107)(x − y) − µλ(∇f (x) − ∇f (y))(cid:107)
= (cid:107)(1 − λ)(x − y) + λ[(x − y) − µ(∇f (x) − ∇f (y))](cid:107)
≤ (1 − λ)(cid:107)x − y(cid:107) + λ(cid:107)(x − y) − µ(∇f (x) − ∇f (y))(cid:107)
= (1 − λ)(cid:107)x − y(cid:107) + λ(cid:107)(µ∇f (x) − x) − (µ∇f (y) − y)(cid:107) ≤ (1 − λ)(cid:107)x − y(cid:107) + λ(cid:112)1 − µ(2α − µL2)(cid:107)x − y(cid:107) = (1 − λ(1 − (cid:112)1 − µ(2α − µL2)))(cid:107)x − y(cid:107) = (1 − λτ )(cid:107)x − y(cid:107) ∀x, y ∈ H.
Ta có điều cần chứng minh.
Chương 2
Phương pháp hướng gradient liên
hợp cho một lớp bài toán tối ưu lồi
Trong chương này chúng tôi trình bày hai phương pháp tìm nghiệm xấp xỉ
của bài toán tối ưu lồi trên tập điểm bất động của một ánh xạ không giãn do Iiduka cùng các cộng sự đưa ra năm 2009. Cấu trúc của chương được chia
thành ba phần: Mục 2.1 dành để giới thiệu mô hình bài toán nghiên cứu.
Mục 2.2 và Mục 2.3 dùng để trình bày chi tiết phương pháp, sự hội tụ cùng các ví dụ số minh họa cụ thể tương ứng cho các phương pháp hướng gradient
liên hợp và phương pháp hướng gradient liên hợp lai ghép.
2.1. Mô hình bài toán
Cho H là không gian Hilbert thực. Giả sử rằng:
A1) f : H → R là hàm khả vi (Fréchet) liên tục;
A2) ∇f : H → H là toán tử α-đơn điệu mạnh và L-liên tục Lipschitz;
A3) T : H → H là ánh xạ không giãn với Fix(T ) (cid:54)= ∅.
Xét bài toán (OP) tìm x∗ ∈ Fix(T ) sao cho:
x∈Fix(T )
f (x). (2.1) f (x∗) = min
Ta có kết quả sau đây về sự tồn tại nghiệm của bài toán (2.1).
Mệnh đề 2.1. [2, 5]
Nếu các giả thiết A1), A2) và A3) bảo đảm thì bài toán cực trị (2.1) có
duy nhất nghiệm.
Chứng minh. Kí hiệu C = Fix(T ). Khi đó, theo Mệnh đề 1.12 và A3), ta có C là tập con đóng lồi khác rỗng. Mặt khác, từ A2), các Mệnh đề 1.10 và Mệnh
25
đề 1.11 suy ra x∗ ∈ C là nghiệm của bài toán (2.1) khi và chỉ khi x∗ ∈ C nghiệm đúng bất đẳng thức biến phân
∀y ∈ C. (2.2) (cid:104)∇f (x∗), y − x∗(cid:105) ≥ 0,
Hơn nữa, (2.2) có thể viết tương đương thành
∀y ∈ C, (cid:104)x∗, y − x∗(cid:105) ≥ (cid:104)(I − µ∇f )(x∗), y − x∗(cid:105),
ở đây, µ là hằng số dương cố định nào đó thuộc (0, 2η/L2). Do đó, từ Mệnh đề 1.14, (hoặc có thể xem Mệnh đề 2.5, [5]) x∗ ∈ C thỏa mãn (2.2) nếu và chỉ nếu
(2.3) x∗ = PC(I − µ∇f )(x∗).
Để ý rằng, từ tính chất của phép chiếu PC, với mọi u, v ∈ C ta lại có
(cid:107)PC(I − µ∇f )(u) − PC(I − µ∇f )(v)(cid:107)2
≤ (cid:107)(I − µ∇f )(u) − (I − µ∇f )(v)(cid:107)2 = (cid:107)(u − v) − µ[∇f (u) − ∇f (v)](cid:107)2 = (cid:107)u − v(cid:107)2 − 2µ(cid:104)u − v, ∇f (u) − ∇f (v)(cid:105)
+ µ2(cid:107)∇f (u) − ∇f (v)(cid:107)2.
Sử dụng A2) ta nhận được
(cid:107)PC(I − µ∇f )(u) − PC(I − µ∇f )(v)(cid:107) ≤ β(cid:107)(u − v)(cid:107), trong đó β = (cid:112)1 − 2µη + L2µ2 ∈ (0, 1) với mọi µ ∈ (0, 2η/L2). Do đó, PC(I − µ∇f ) là ánh xạ co. Vì thế, nguyên lí ánh xạ co Banach bảo đảm sự tồn tại của x∗ thỏa mãn (2.3) hay nói cách khác bài toán (2.1) có nghiệm.
Cuối cùng, giả sử bài toán có hai nghiệm x∗ và y∗. Khi đó, từ điều kiện
(2.2) ta có đánh giá
(cid:104)∇f (x∗), y∗ − x∗(cid:105) ≥ 0
và
(cid:104)∇f (y∗), x∗ − y∗(cid:105) ≥ 0.
Cộng hai vế các bất đẳng thức trên và sử dụng A2) ta nhận được
η(cid:107)x∗ − y∗(cid:107)2 ≤ (cid:104)∇f (x∗) − ∇f (y∗), x∗ − y∗(cid:105) ≤ 0.
Điều này suy ra x∗ = y∗.
26
Dưới đây là một ví dụ về lớp hàm lồi thỏa mãn các điều kiện A1), A2) và
A3) nêu trên.
Ví dụ 2.1. Cho b ∈ H và Q : H → H là toán tử tuyến tính bị chặn, tự liên hợp và bức (tức là, tồn tại số thực dương α sao cho (cid:104)x, Q(x)(cid:105) ≥ α(cid:107)x(cid:107)2 với mọi x ∈ H). Ta xác định hàm toàn phương f : H → R như sau:
(cid:104)x, Q(x)(cid:105) + (cid:104)b, x(cid:105), ∀x ∈ H. f (x) := 1 2
Khi đó, ∇f (x) = Q(x) + b là α-đơn điệu mạnh và L-liên tục Lipschitz với
. (cid:104)x, Q(x)(cid:105) (cid:107)x(cid:107)2 L = (cid:107)Q(cid:107) := sup x(cid:54)=0
(Nếu H := Rn là không gian hữu hạn chiều thì Q trùng với ma trận xác định dương (ma trận xác định ánh xạ tuyến tính Q). Khi đó, với mỗi x ∈ Rn ta có ma trận Hessian ∇2f = Q và
λmin(cid:107)x(cid:107)2 ≤ (cid:104)x, Q(x)(cid:105) ≤ λmax(cid:107)x(cid:107)2,
ở đây, λmin và λmax tương ứng là các giá trị riêng nhỏ nhất và lớn nhất của Q. Do đó, ta có α = λmin và L = (cid:107)Q(cid:107) = λmax).
2.2. Phương pháp hướng gradient liên hợp
2.2.1 Mô tả phương pháp
Cho f : H → R và T : H → H thỏa mãn các giả thiết A1), A2) và A3). Giả sử số thực dương µ, dãy số thực αn ∈ (0, 1] và βn ∈ [0, ∞) thỏa mãn các điều kiện sau:
B1) µ ∈ (0, 2α/L2)
∞ (cid:88)
αn = 0; B2) lim n→∞
n=1
∞ (cid:88)
B3) αn = ∞;
n=1
B4) | αn+1 − αn |< ∞;
27
≤ σ với mọi n ∈ N với một σ ≥ 1 nào đó; B5)
βn = 0; αn αn+1 B6) lim n→∞
Khi đó, để tìm nghiệm xấp xỉ của bài toán (2.1) ta có thể thực hiện theo thủ
tục lặp (viết tắt là (CGM)) như sau:
• Bước 1. Lấy µ > 0 thỏa mãn B1). Chọn x1 ∈ H và α1 ∈ (0, 1] tùy ý.
Chúng ta tính
d1 := −∇f (x1)
và gán n := 1.
• Bước 2. Với xn ∈ H, dn ∈ H, chọn αn ∈ (0, 1] thỏa mãn B2)-B5) và xác
định xn+1 ∈ H bởi
xn+1 := T (xn + µαndn).
• Bước 3. Chọn βn+1 ∈ [0, ∞) thỏa mãn B6) và cập nhật hướng tìm kiếm
mới như sau
dn+1 := −∇f (xn+1) + βn+1dn
.
• Bước 4. Đặt n := n + 1 và thực hiện Bước 2.
2.2.2 Sự hội tụ của phương pháp
Sự hội tụ của phương pháp hướng gradient liên hợp đề cập đến ở trên được
phát biểu và chứng minh thông qua định lí sau.
Định lí 2.1. [2]
Cho f : H → R và T : H → H thỏa mãn các giả thiết A1), A2) và A3). Cho µ, αn ∈ (0, 1] và βn ∈ [0, ∞) lần lượt thỏa mãn các điều kiện từ B1) đến B6). Khi đó, nếu {∇f (xn)} bị chặn thì dãy lặp {xn} xác định bởi thủ tục lặp (CGM) trong Mục 2.2.1 nêu trên thỏa mãn:
(i) {xn} và {dn} bị chặn;
(cid:107)xn+1 − T (xn)(cid:107) = 0; (ii) lim n→∞
(cid:107)xn − T (xn)(cid:107) = 0; (iii) lim n→∞ (cid:107)xn+1 − xn(cid:107) = 0 và lim n→∞
28
(iv) {xn} hội tụ mạnh đến nghiệm duy nhất của bài toán (2.1).
Chứng minh. (i) Từ điều kiện B6) suy ra tồn tại m1 ∈ N sao cho
, βn ≤ ∀n ≥ m1. 1 2
Vì {∇f (xn)} bị chặn nên
{(cid:107)∇f (xn)(cid:107)} < ∞, K1 := sup n∈N
và
K2 := max{K1, (cid:107)dm1(cid:107)}
hoàn toàn xác định.
Ta có ước lượng sau
(cid:107)dm1(cid:107) = (cid:107) − ∇f (xm1+1) + βm1+1dm1(cid:107)
≤ (cid:107) − ∇f (xm1+1)(cid:107) + βm1+1(cid:107)dm1(cid:107)
≤ K1 + (cid:107)dm1(cid:107)
≤ K2 + (cid:107)dm1(cid:107). 1 2 1 2
Do đó, ta có đánh giá
(cid:107)dm1(cid:107) ≤ 2K2.
Mặt khác, ta lại có
(cid:107)dn+1(cid:107) = (cid:107) − ∇f (xn+1) + βn+1dn(cid:107)
≤ (cid:107) − ∇f (xn+1)(cid:107) + βn+1(cid:107)dn(cid:107)
(cid:107)dn(cid:107) ≤ K1 +
≤ K2 + (cid:107)dn(cid:107) ∀n ≥ m1. 1 2 1 2
Bây giờ, giả sử rằng (cid:107)dn(cid:107) ≤ 2K2, ∀n ≥ m1. Khi đó, kết hợp với bất đẳng thức trên ta có
(cid:107)dn+1(cid:107) ≤ 2K2, ∀n ≥ m1.
Theo nguyên lí quy nạp suy ra
(cid:107)dn(cid:107) ≤ 2K2, ∀n ≥ m1,
29
và vì vậy {dn} bị chặn.
Tiếp theo, lấy tùy ý x∗ ∈ Fix(T ) là nghiệm của (2.1). Ta đặt
{(cid:107)βn+1dn − ∇f (x∗)(cid:107)} < ∞, K3 := sup n∈N
và
K := max{K3, (cid:107)∇f (x∗)(cid:107)}.
Áp dụng Mệnh đề 1.15 ta nhận được
(cid:107)xn+1 − x∗(cid:107) = (cid:107)T (xn + µαndn) − x∗(cid:107)
= (cid:107)T (xn + µαndn) − T (x∗)(cid:107)
≤ (cid:107)xn + µαndn − x∗(cid:107)
= (cid:107)xn + µαn(−∇f (xn) + βndn−1) − x∗(cid:107)
= (cid:107)[xn − µαn∇f (xn)] − [x∗ − µαn∇f (x∗)]
+ µαn[βndn−1 − ∇f (x∗)](cid:107)
≤ (cid:107)[xn − µαn∇f (xn)] − [x∗ − µαn∇f (x∗)](cid:107)
+ µαn(cid:107)βndn−1 − ∇f (x∗)(cid:107)
≤ (1 − τ αn)(cid:107)xn − x∗(cid:107) + τ αn µK τ (cid:26) (cid:27) ≤ max , (cid:107)xn − x∗(cid:107), µK τ
trong đó, τ := 1 − (cid:112)1 − µ(2α − µL2) ∈ (0, 1]. Do đó, bằng quy nạp ta có
(cid:26) (cid:27) , ∀n ∈ N, (cid:107)xn − x∗(cid:107) ≤ max (cid:107)x1 − x∗(cid:107), µK τ
và vì vậy {xn} bị chặn.
(ii) Từ tính không giãn của T ta có ước lượng sau
n→∞
n→∞
0 ≤ lim sup (cid:107)xn+1 − T (xn)(cid:107) = lim sup (cid:107)T (xn + µαndn) − T (xn)(cid:107)
n→∞ ≤ µ lim sup
≤ lim sup (cid:107)µαndn(cid:107)
n→∞
αn(cid:107)dn(cid:107).
Kết hợp với kết luận (i) và điều kiện B2) suy ra
(cid:107)xn+1 − T (xn)(cid:107) = 0. lim n→∞
30
(iii) Ta đặt
{|(cid:104)zn − zn−1, ∇f (xn−1)(cid:105)|},
M2 = {|(cid:104)zn − zn−1, dn−1(cid:105)|}, sup n≥2
M2 = {|(cid:104)zn − zn−1, dn−2(cid:105)|}, zn = xn + µαndn, n ∈ N, M1 = sup n≥2 1 τ σ τ sup n≥3
M = max{M1, M2, M3}.
Khi đó, ta có ước lượng sau đây
(cid:107)xn+1 − xn(cid:107)2 = (cid:107)T (xn + µαndn) − T (xn−1 + µαn−1dn−1)(cid:107)2
≤ (cid:107)[xn + µαndn] − [xn−1 + µαn−1dn−1](cid:107)2 = (cid:107)[xn + µαn(−∇f (xn) + βndn−1)] − [xn−1 + µαn−1dn−1](cid:107)2 = (cid:107)[xn − µαn∇f (xn)] + µαnβndn−1 − [xn−1 + µαn−1dn−1](cid:107)2 = (cid:107)[xn − µαn∇f (xn)] − [xn−1 − µαn∇f (xn−1)] + µ[αnβndn−1 − αn∇f (xn−1) − αn−1dn−1](cid:107)2 ≤ (cid:107)[xn − µαn∇f (xn)] − [xn−1 − µαn∇f (xn−1)](cid:107)2
+ 2µ(cid:104)αnβndn−1 − αn∇f (xn−1) − αn−1dn−1, zn − zn−1(cid:105)
≤ (1 − τ αn)2(cid:107)xn − xn−1(cid:107)2
+ 2µ(cid:104)αnβndn−1 − αn∇f (xn−1) − αn−1dn−1, zn − zn−1(cid:105)
≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2
+ 2µ(cid:104)αnβndn−1 − αn∇f (xn−1)
− αn−1(−∇f (xn−1) + βn−1dn−2), zn − zn−1(cid:105)
≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2
+ 2µ(αn−1 − αn)(cid:104)∇f (xn−1), zn − zn−1(cid:105)
+ 2µαnβn(cid:104)dn−1, zn − zn−1(cid:105)
+ 2µαn−1βn−1(cid:104)−dn−2, zn − zn−1(cid:105)
≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2 + 2µM |αn−1 − αn|
+ 2µM τ αnβn
31
+ 2µM αn−1βn−1 τ σ
≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2
+ 2µM |αn−1 − αn| + 2µM τ αnβn + 2µM τ βn−1, ∀n ≥ 3.
Từ B6) suy ra với mỗi ε > 0, tồn tại n1 ∈ N sao cho
, βn ≤ ∀n ≥ n1. ε 4
Khi đó, với mọi n ≥ n1 + 1 ta có
(cid:107)xn+1 − xn(cid:107)2 ≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2
+ 2µM |αn−1 − αn|
+ 2µM ε(1 − (1 − τ αn)).
Từ đó quy nạp ta nhận được
(cid:107)xm+n+1 − xm+n(cid:107)2 ≤ (1 − τ αn+m)(cid:107)xm+n − xm+n−1(cid:107)2
+ 2µM |αm+n − αm+n−1|
+ µM ε(1 − (1 − τ αm+n))
n+m−1 (cid:89)
≤ · · ·
k=m
n+m−1 (cid:88)
≤ (1 − τ αk+1)(cid:107)xm+1 − xm(cid:107)2
+ 2µM |αk+1 − αk|
k=m (cid:32)
n+m−1 (cid:89)
(cid:33)
k=m
+ µM ε 1 − (1 − τ αk+1)
∞ (cid:89)
Điều kiện B2, B3) suy ra
k=m
(1 − τ αk+1) → 0.
n+m−1 (cid:88)
Do đó, ta có
k=m
|αk+1 − αk| + µM ε. lim sup n→∞ (cid:107)xm+n+1 − xm+n(cid:107)2 ≤ 2µM lim sup n→∞
32
Kết hợp với B4) ta có
(cid:107)xm+n+1 − xm+n(cid:107)2 lim sup n→∞
(cid:107)xn+1 − xn(cid:107)2 = lim sup n→∞ ≤ µM ε.
Vì ε > 0 bé tùy ý nên suy ra
(cid:107)xn+1 − xn(cid:107) = 0. lim n→∞
Ngoài ra, từ ước lượng
(cid:107)xn − T (xn)(cid:107) ≤ (cid:107)xn − xn+1(cid:107) + (cid:107)xn+1 − T (xn)(cid:107)
ta nhận được
(cid:107)xn − T (xn)(cid:107) = 0. lim n→∞
(iv) Trước hết, ta sẽ chứng minh
(2.4) (cid:104)x∗ − xn, ∇f (x∗)(cid:105) ≤ 0. lim sup n→∞
Lấy {xnk} là dãy con của dãy {xn} thỏa mãn
(cid:104)x∗ − xnk, ∇f (x∗)(cid:105). (cid:104)x∗ − xn, ∇f (x∗)(cid:105) = lim k→∞ lim sup n→∞
} của nó hội tụ yếu trong H.
Vì {xnk} cũng bị chặn nên tồn tại dãy con {xnkj Giả sử rằng
, w(cid:105) = (cid:104)ˆx, w(cid:105), ˆx ∈ H. (cid:104)xnkj lim j→∞
Để ý rằng, nếu ˆx (cid:54)= T (ˆx) thì
− T (ˆx)(cid:107) (cid:107)xnkj (cid:107)xnkj lim inf j→∞ − ˆx(cid:107) < lim inf j→∞
) − T (ˆx)(cid:107) (cid:107)xnkj − T (xnkj ) + T (xnkj = lim inf j→∞
) − T (ˆx)(cid:107)] [(cid:107)xnkj − T (xnkj )(cid:107) + (cid:107)T (xnkj ≤ lim inf j→∞
) − T (ˆx)(cid:107) (cid:107)T (xnkj = lim inf j→∞
− ˆx(cid:107), (cid:107)xnkj ≤ lim inf j→∞
mâu thuẫn. Do đó, ta phải có ˆx = T (ˆx). Mặt khác, vì x∗ là nghiệm của bài toán (2.1) nên ta có
(cid:104)∇f (x∗), ˆx − x∗(cid:105) ≥ 0.
33
Từ đó suy ra
(cid:104)x∗ − xnk, ∇f (x∗)(cid:105) (cid:104)x∗ − xn, ∇f (x∗)(cid:105) = lim k→∞ lim sup n→∞
j→∞
≤ lim sup , ∇f (x∗)(cid:105) (cid:104)x∗ − xnkj
= (cid:104)x∗ − ˆx, ∇f (x∗)(cid:105) ≤ 0.
Điều kiện B6) và tính bị chặn của các dãy {zn}, {dn} bảo đảm rằng
βn(cid:104)zn − x∗, dn−1(cid:105) ≤ 0. lim sup n→∞
Điều kiện B2) dẫn đến với mọi ε > 0 đều tồn tại số m0 ∈ N sao cho
, (cid:104)dn, −∇f (x∗)(cid:105) ≤
, µ2αn τ (cid:104)x∗ − xn, ∇f (x∗)(cid:105) ≤
, (cid:104)zn − x∗, dn−1(cid:105) ≤ µ τ µβn τ ε 6 ε 6 ε 6
với mọi n ≥ m0.
Cuối cùng, ta có ước lượng sau
(cid:107)xn+1 − x∗(cid:107)2 = (cid:107)T (xn + µαndn) − T (x∗)(cid:107)2
≤ (cid:107)xn + µαndn − x∗(cid:107)2 = (cid:107)xn + µαn(−∇f (xn) + βndn−1) − x∗(cid:107)2 = (cid:107)[xn − µαn∇f (xn)] − [x∗ − µαn∇f (xn)]
+ µαnβndn−1 − µαn∇f (xn)(cid:107)2
≤ (1 − τ αn)(cid:107)xn − x∗(cid:107)2
+ 2αn(cid:104)(xn + µαndn) − x∗, µβndn−1 − µ∇f (xn)(cid:105)
(cid:19)
(cid:104)zn − x∗, dn−1(cid:105) + 2τ αn ≤ (1 − τ αn)(cid:107)xn − x∗(cid:107)2 (cid:18)µβn τ (cid:17) + 2τ αn (cid:104)x∗ − xn, ∇f (x∗)(cid:105)
(cid:19) . (cid:104)dn, −∇f (x∗)(cid:105) + 2τ αn (cid:16)µ τ (cid:18)µ2αn τ
34
Kết hợp với đánh giá phía trên ta nhận được
(cid:107)xn+1 − x∗(cid:107)2 ≤ (1 − τ αn)(cid:107)xn − x∗(cid:107)2 + τ αnε, ∀n ≥ m0.
Bằng quy nạp, ∀n ≥ m0, ta có
n (cid:89)
n (cid:89)
(cid:32) (cid:33)
k=m0
k=m0
1 − . (cid:107)xn+1 − x∗(cid:107)2 ≤ (1 − τ αk) (1 − τ αk)(cid:107)xm0 − x∗(cid:107)2 + ε
Từ B3) suy ra
(cid:107)xn+1 − x∗(cid:107)2 ≤ ε. lim sup n→∞
Do ε > 0 bé tùy ý nên ta nhận được
(cid:107)xn+1 − x∗(cid:107)2 ≤ 0. lim sup n→∞
Điều này suy ra
(cid:107)xn+1 − x∗(cid:107)2 = 0.
lim n→∞ Hay nói cách khác dãy {xn} hội tụ mạnh đến nghiệm x∗.
2.2.3 Ví dụ minh họa
Trong phần này, chúng tôi xét H là không gian hữu hạn chiều Rn có 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 tương ứng sinh bởi tích vô hướng trên là
1 + x2 x2
2 + . . . + x2 n.
(cid:113) (cid:107)x(cid:107) =
Cho b = (b1, b2, ..., bn) ∈ Rn và Q : Rn → Rn là toán tử tuyến tính bị chặn, tự liên hợp và bức với hệ số α xác định bởi một ma trận vuông thực cỡ n × n
xác định dương.
Ta xác định hàm toàn phương f : Rn → R như sau:
f (x) := (cid:104)x, Q(x)(cid:105) + (cid:104)b, x(cid:105), ∀x ∈ Rn. 1 2
Khi đó, ∇f (x) = Q(x) + b là λmin-đơn điệu mạnh và λmax-liên tục Lipschitz với λmin và λmax lần lượt là giá trị riêng nhỏ nhất và lớn nhất của Q.
35
n (cid:92)
i=1
Cho C = Ci với
i = 1, 2, ..., n, Ci = {x = (x1, x2, ..., xn) ∈ Rn : (cid:104)ei, xi(cid:105) ≥ 0, },
ở đây, ei ∈ Rn có các tọa độ đều bằng 0 trừ ra tọa độ thứ i bằng 1. Để ý rằng, PCi là các ánh xạ không giãn và
Ci = Fix(PCi).
i=1
Ta đặt (cid:32) n (cid:33) (cid:88) , ∀x ∈ Rn. T (x) = PCi(x) 1 n
n (cid:92)
Khi đó, T là ánh xạ không giãn và hiển nhiên Fix(T ) (cid:54)= ∅. Hơn nữa, ta thấy
i=1
Fix(T ) = C := Ci.
Xét bài toán (OP) tìm x∗ ∈ C sao cho:
f (x). (2.5) f (x∗) = min x∈C
Ví dụ 2.2. Xét mô hình bài toán (2.5) với các thông tin như sau:
(cid:32) (cid:33) 1 0 n = 2, Q = , b = (1, 2) 0 1
và T = (PC1 + PC2) với 1 2
C1 = {x = (x1, x2) ∈ R2 : x1 ≤ 0}, C2 = {x = (x1, x2) ∈ R2 : x2 ≤ 0}.
Trong trường hợp này ta có f (x) := (cid:104)x, x(cid:105)+(cid:104)b, x(cid:105), ∀x ∈ Rn và ∇f (x) = x+b 1 2 là 1-đơn điệu mạnh và 1-liên tục Lipschitz. Ngoài ra, ta cũng thấy
Fix(T ) = {x = (x1, x2) ∈ R2 : x1 ≤ 0, x2 ≤ 0} = R2 −.
Dễ thấy x∗ = (−1, −2) là nghiệm duy nhất của bài toán (2.5). Chọn các tham số thỏa mãn điều kiện Định lí 2.1 như sau
1 √ , αn = βn = (n + 1)2 , µ ∈ (0, 2). 1 n + 1
36
2 ) như dưới đây:
1 , u(k)
Với điểm ban đầu x0 = (3, 4), áp dụng thuật toán nêu trong Mục 2.2.1, ta nhận được bảng kết quả tính toán số cho nghiệm xấp xỉ thứ k là xk = (u(k)
k k u(k) 1 u(k) 2
2 u(k) 1 0.085786437 u(k) 2 -0.242640687 -0.999883737 -1.999768714 20
4 -0.946666102 -1.896827181 -0.999998013 -1.999996048 40
6 -0.986447733 -1.973043702 -0.999999906 -1.999999813 60
8 -0.994757726 -1.989571298 -0.999999992 -1.999999985 80
Bảng 2.1: Kết quả tính toán phương pháp (CGM) với µ = 1
10 -0.997651003 -1.995327029 100 -0.999999999 -1.999999998
Với giá trị tham số µ = 1/100 ta nhận được
u(k) 1 u(k) 2 u(k) 1 u(k) 2
-0.432398958 -0.866916036
-0.855383818 -1.711307302
-0.998085387 -1.996177919
-0.999999997 -1.999999995
Bảng 2.2: Kết quả tính toán phương pháp (CGM) với µ = 1/100
k k 100 -0.125221845 -0.253708106 103 200 -0.194683834 -0.392372871 104 300 -0.244249719 -0.491319677 105 500 -0.316691531 -0.635932970 106 800 -0.393018940 -0.788302955 107 -0.999999999 -1.999999999
Ngoài ra, tính toán với một số giá trị µ khác ta có
µ u(k) 1 u(k) 2
1/1000 -0.464619251 -0.929409024
199/100 k 105 50 -0.999999999 -1.999999999
Bảng 2.3: Một số kết quả tính toán khác cho phương pháp (CGM)
20 1999/1000 -0.999999998 -1.999999998
Kết quả trên 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ụ khá chậm khi tham số này gần giá trị 0 và khá
tốt khi tham số này thuộc [1, 2).
37
2.3. Phương pháp hướng gradient liên hợp lai ghép
2.3.1 Mô tả phương pháp
Cho f : H → R và T : H → H thỏa mãn các giả thiết A1), A2) và A3). Cho µ, αn ∈ (0, 1] và βn ∈ [0, ∞) lần lượt thỏa mãn các điều kiện từ B1) đến B6). Khi đó, để tìm nghiệm xấp xỉ của bài toán (2.1) ta có thể thực hiện theo thủ tục lặp (viết tắt là (HCGM)) như sau:
• Bước 1. Lấy µ > 0 thỏa mãn B1). Chọn x1 ∈ H và α1 ∈ (0, 1] tùy ý.
Chúng ta tính
d1 := −∇f (x1)
và gán n := 1.
• Bước 2. Với xn ∈ H, dn ∈ H, chọn αn ∈ (0, 1] thỏa mãn B2)-B5) và xác
định xn+1 ∈ H bởi
xn+1 := T (xn) + µαndn.
• Bước 3. Chọn βn+1 ∈ [0, ∞) thỏa mãn B6) và cập nhật hướng tìm kiếm
mới như sau
dn+1 := −∇f (T (xn+1)) + βn+1dn
.
• Bước 4. Đặt n := n + 1 và thực hiện Bước 2.
2.3.2 Sự hội tụ của phương pháp
Sự hội tụ của phương pháp hướng gradient liên hợp lai ghép đề cập đến ở
trên được phát biểu và chứng minh thông qua định lí sau.
Định lí 2.2. [3]
Cho f : H → R và T : H → H thỏa mãn các giả thiết A1), A2) và A3). Cho µ, αn ∈ (0, 1] và βn ∈ [0, ∞) lần lượt thỏa mãn các điều kiện từ B1) đến B6). Khi đó, nếu {dn} bị chặn thì dãy lặp {xn} xác định bởi thủ tục lặp (HCGM) trong Mục 2.2.1 nêu trên thỏa mãn:
(i) {xn}, {T (xn)} và {∇f (xn)} bị chặn;
(cid:107)xn+1 − T (xn)(cid:107) = 0; (ii) lim n→∞
38
(cid:107)xn+1 − xn(cid:107) = 0; (iii) lim n→∞
(iv) {xn} hội tụ mạnh đến nghiệm duy nhất của bài toán (2.1).
Chứng minh. (i) Lấy tùy ý x∗ ∈ Fix(T ) là nghiệm của (2.1). Ta đặt
{(cid:107)βn+1dn − ∇f (T (x∗))(cid:107)} < ∞, K1 := sup n∈N
và
K := max{K1, (cid:107)∇f (x∗)(cid:107)}.
Áp dụng Mệnh đề 1.15 ta nhận được
(cid:107)xn+1 − x∗(cid:107) = (cid:107)T (xn) + µαndn − x∗(cid:107)
= (cid:107)T (xn) + µαn(−∇f (T (xn)) + βndn−1) − T (x∗)(cid:107)
= (cid:107)[T (xn) − µαn∇f (T (xn))] − [T (x∗) − µαn∇f (T (x∗))]
+ µαn[βndn−1 − ∇f (T (x∗))(cid:107)
= (cid:107)[T (xn) − µαn∇f (T (xn))] − [T (x∗) − µαn∇f (T (x∗))](cid:107)
+ µαn(cid:107)βndn−1 − ∇f (T (x∗))(cid:107)
≤ (1 − τ αn)(cid:107)T (xn) − T (x∗)(cid:107) + µαn(cid:107)βndn−1 − ∇f (T (x∗))(cid:107)
≤ (1 − τ αn)(cid:107)xn − x∗(cid:107) + µαn(cid:107)βndn−1 − ∇f (T (x∗))(cid:107)
≤ (1 − τ αn)(cid:107)xn − x∗(cid:107) + µαnK
}, = (1 − τ αn)(cid:107)xn − x∗(cid:107) + τ αn ≤ max{(cid:107)xn − x∗(cid:107), µK τ
µK τ trong đó, τ := 1 − (cid:112)1 − µ(2α − µL2) ∈ (0, 1]. Bằng quy nạp, suy ra
}. (cid:107)xn+1 − x∗(cid:107) ≤ max{(cid:107)x1 − x∗(cid:107), µK τ
Do đó, dãy {xn} bị chặn. Mặt khác, vì T là ánh xạ không giãn và ∇f (x) là L-liên tục Lipschitz nên {T (xn)} và {∇f (xn)} cũng là các dãy bị chặn.
(ii) Từ B2) và tính bị chặn của {dn} suy ra
n→∞
n→∞
(cid:107)xn+1 − T (xn)(cid:107) = lim sup (cid:107)µαndn(cid:107) = µ lim sup αn(cid:107)dn(cid:107) ≤ 0. lim sup n→∞
Do đó, ta có
(cid:107)xn+1 − T (xn)(cid:107) = 0. lim n→∞
39
(iii) Ta đặt
{|(cid:104)xn+1xn, ∇f (T (xn−1))(cid:105)|},
M2 := {|(cid:104)xn+1xn, dn−1(cid:105)|}, sup n≥2
M3 := {|(cid:104)xn+1xn, dn−2(cid:105)|}, M1 := sup n≥2 1 τ σ τ sup n≥3
M := max{M1, M2, M3}.
Ta có ước lượng sau
(cid:107)xn+1 − xn(cid:107)2 = (cid:107)T (xn) + µαndn − T (xn−1) − µαn−1dn−1(cid:107)2
= (cid:107)T (xn) + µαn(−∇f (T (xn)) + βndn−1)
− [T (xn−1) − µαn∇f (T (xn−1))] − µαn∇f (T (xn−1)) − µαn−1dn−1(cid:107)2
= (cid:107)[T (xn) − µαn∇f (T (xn))] − [T (xn−1) − µαn∇f (T (xn−1))]
+ µ[αnβndn−1 − αn∇f (T (xn−1)) − αn−1dn−1](cid:107)2
≤ (cid:107)[T (xn) − µαn∇f (T (xn))] − [T (xn−1) − µαn∇f (T (xn−1))](cid:107)2 + 2µ(cid:104)αnβndn−1 − αn∇f (T (xn−1)) − αn−1dn−1, xn+1 − xn(cid:105)
≤ (1 − τ αn)2(cid:107)T (xn) − T (xn−1)(cid:107)2
+ 2µ(cid:104)αnβndn−1 − αn∇f (T (xn−1)) − αn−1dn−1, xn+1 − xn(cid:105)
≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2
+ 2µ(cid:104)αnβndn−1 − αn∇f (T (xn−1))
− αn−1(−∇f (T (xn−1)) + βn−1dn−2), xn+1 − xn(cid:105)
≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2
+ 2µ(αn−1 − αn)(cid:104)∇f (T (xn−1)), xn+1 − xn(cid:105)
+ 2µαnβn(cid:104)dn−1, xn+1 − xn(cid:105)
+ 2µαn−1βn−1(cid:104)−dn−2, xn+1 − xn(cid:105)
≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2 + 2µ|αn−1 − αn|M
+ 2µαnβnM τ
+ 2µαnβn−1M τ, ∀n ≥ 3.
40
Từ B6) suy ra với mỗi ε > 0, tồn tại n1 ∈ N sao cho
, βn ≤ ∀n ≥ n1. ε 4
Khi đó, với mọi n ≥ n1 + 1 ta có
(cid:107)xn+1 − xn(cid:107)2 ≤ (1 − τ αn)(cid:107)xn − xn−1(cid:107)2 + 2µ|αn−1 − αn|M + µM ε(1 − (1 − τ αn)).
Khi đó, với mọi n, m ≥ n1 ta có đánh giá
(cid:107)xm+n+1 − xm+n(cid:107)2 ≤ (1 − τ αm+n)(cid:107)xm+n − xm+n−1(cid:107)2
+ 2µM |αm+n − αm+n−1|
+ µM ε(1 − (1 − τ αm+n))
n+m−1 (cid:89)
≤ · · ·
k=m
n+m−1 (cid:88)
≤ (1 − τ αk+1)(cid:107)xm+1 − xm(cid:107)2
+ 2µM |αk+1 − αk|
k=m (cid:32)
n+m−1 (cid:89)
(cid:33)
k=m
+ µM ε 1 − (1 − τ αk+1)
∞ (cid:89)
Điều kiện B2, B3) suy ra
k=m
(1 − τ αk+1) → 0.
n+m−1 (cid:88)
Do đó, ta có
k=m
|αk+1 − αk| + µM ε. lim sup n→∞ (cid:107)xm+n+1 − xm+n(cid:107)2 ≤ 2µM lim sup n→∞
Kết hợp với B4) ta có
(cid:107)xm+n+1 − xm+n(cid:107)2 lim sup n→∞
(cid:107)xn+1 − xn(cid:107)2 = lim sup n→∞ ≤ µM ε.
Vì ε > 0 bé tùy ý nên suy ra
(cid:107)xn+1 − xn(cid:107) = 0. lim n→∞
41
Ngoài ra, từ ước lượng
(cid:107)xn − T (xn)(cid:107) ≤ (cid:107)xn − xn+1(cid:107) + (cid:107)xn+1 − T (xn)(cid:107)
ta nhận được
(cid:107)xn − T (xn)(cid:107) = 0. lim n→∞
(iv) Trước hết, ta sẽ chứng minh
(2.6) (cid:104)x∗ − xn, ∇f (x∗)(cid:105) ≤ 0. lim sup n→∞
Lấy {xnk} là dãy con của dãy {xn} thỏa mãn
(cid:104)x∗ − xnk, ∇f (x∗)(cid:105). (cid:104)x∗ − xn, ∇f (x∗)(cid:105) = lim k→∞ lim sup n→∞
} của nó hội tụ yếu trong H.
Vì {xnk} cũng bị chặn nên tồn tại dãy con {xnkj Giả sử rằng
, w(cid:105) = (cid:104)ˆx, w(cid:105), ˆx ∈ H. (cid:104)xnkj lim j→∞
Để ý rằng, nếu ˆx (cid:54)= T (ˆx) thì
− T (ˆx)(cid:107) (cid:107)xnkj (cid:107)xnkj − ˆx(cid:107) < lim inf j→∞ lim inf j→∞
) − T (ˆx)(cid:107) ) + T (xnkj − T (xnkj (cid:107)xnkj = lim inf j→∞
) − T (ˆx)(cid:107)] )(cid:107) + (cid:107)T (xnkj − T (xnkj [(cid:107)xnkj ≤ lim inf j→∞
) − T (ˆx)(cid:107) (cid:107)T (xnkj = lim inf j→∞
− ˆx(cid:107), (cid:107)xnkj ≤ lim inf j→∞
mâu thuẫn. Do đó, ta phải có ˆx = T (ˆx). Mặt khác, vì x∗ là nghiệm của bài toán (2.1) nên ta có
(cid:104)∇f (x∗), ˆx − x∗(cid:105) ≥ 0.
Từ đó suy ra
(cid:104)x∗ − xnk, ∇f (x∗)(cid:105) (cid:104)x∗ − xn, ∇f (x∗)(cid:105) = lim k→∞ lim sup n→∞
j→∞
≤ lim sup , ∇f (x∗)(cid:105) (cid:104)x∗ − xnkj
= (cid:104)x∗ − ˆx, ∇f (x∗)(cid:105) ≤ 0.
42
Điều kiện B6) và tính bị chặn của các dãy {xn}, {dn} bảo đảm rằng
βn(cid:104)xn+1 − x∗, dn−1(cid:105) ≤ 0. lim sup n→∞
Điều kiện B2) dẫn đến với mọi ε > 0 đều tồn tại số m0 ∈ N sao cho
, (cid:104)x∗ − xn, ∇f (x∗)(cid:105) ≤
, (cid:104)xn+1 − x∗, dn−1(cid:105) ≤ µ τ µβn τ ε 4 ε 4
với mọi n ≥ m0.
Cuối cùng, ta có ước lượng sau
(cid:107)xn+1 − x∗(cid:107)2 = (cid:107)T (xn) + µαndn − T (x∗)(cid:107)2
= (cid:107)T (xn) + µαn(−∇f (T (xn)) + βndn−1) − T (x∗)(cid:107)2 = (cid:107)[T (xn) − µαn∇f (T (xn))] − [T (x∗) − µαn∇f (T (x∗))]
+ [µαnβndn−1 − µαn∇f (T (x∗))](cid:107)2
≤ (cid:107)[T (xn) − µαn∇f (T (xn))] − [T (x∗) − µαn∇f (T (x∗))](cid:107)2
+ 2µαn(cid:104)βndn−1 − ∇f (T (x∗)), xn+1 − x∗(cid:105)
≤ (1 − τ αn)2(cid:107)T (xn) − T (x∗)(cid:107)2
+ 2µαn(cid:104)βndn−1 − ∇f (T (x∗)), xn+1 − x∗(cid:105)
(cid:19)
+ 2τ αn (cid:104)dn−1, xn+1 − x∗(cid:105) + (cid:104)∇ − f (T (x∗)), xn+1 − x∗(cid:105) ≤ (1 − τ αn)(cid:107)xn − x∗(cid:107)2 (cid:18)µβn τ
Kết hợp với đánh giá phía trên ta nhận được
(cid:107)xn+1 − x∗(cid:107)2 ≤ (1 − τ αn)(cid:107)xn − x∗(cid:107)2 + τ αnε, ∀n ≥ m0.
Bằng quy nạp, ∀n ≥ m0, ta có
n (cid:89)
n (cid:89)
(cid:32) (cid:33)
k=m0
k=m0
1 − . (cid:107)xn+1 − x∗(cid:107)2 ≤ (1 − τ αk) (1 − τ αk)(cid:107)xm0 − x∗(cid:107)2 + ε
Từ B3) suy ra
(cid:107)xn+1 − x∗(cid:107)2 ≤ ε. lim sup n→∞
43
Do ε > 0 bé tùy ý nên ta nhận được
(cid:107)xn+1 − x∗(cid:107)2 ≤ 0. lim sup n→∞
Điều này suy ra
(cid:107)xn+1 − x∗(cid:107)2 = 0.
lim n→∞ Hay nói cách khác dãy {xn} hội tụ mạnh đến nghiệm x∗.
2.3.3 Ví dụ minh họa
Ví dụ 2.3. Ta xét bài toán (2.3) với các giả thiết và kí hiệu đã trình bày
trong Ví dụ 2.2 ở Mục 2.2.3.
Với cùng điểm ban đầu x0 = (3, 4), áp dụng thuật toán được nêu trong Mục 2.3.1, ta nhận được bảng kết quả tính toán số cho nghiệm xấp xỉ thứ k là xk = (u(k)
1 , u(k) 2 ) như dưới đây: u(k) u(k) 2 1
k k u(k) 1 u(k) 2
2 -1.328427124 -2.242640687 12 -1.005061468 -2.006493080
4 -1.201330418 -2.256976912 14 1.002664477 -2.003418112
6 -1.059289567 -2.076057612 16 -1.001476606 -2.001894257
8 -1.022950752 -2.029442258 18 -1.000852498 -2.001093623
Bảng 2.4: Kết quả tính toán phương pháp (HCGM) với µ = 1
10 -1.010283950 -2.013192715 20 -1.000508997 -2.000652965
Tính toán với một số giá trị µ khác ta có bảng tính toán sau
µ k u(k) 1 u(k) 2
1
1/100 -0.998091979 -1.996191042
1/1000 -0.464769669 -0.929722856
199/100 100 -1.000000003 -2.000000004 105 105 50 -1.000000000 -2.000000000
Bảng 2.5: Một số kết quả tính toán khác cho phương pháp (HCGM)
1999/1000 20 -1.000000003 -2.000000003
Tương quan kết quả tính toán trên với Ví dụ 2.2, ta thấy ảnh hưởng của
tham số µ tới tốc độ hội tụ của hai phương pháp khá tương đồng.
44
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 một số kiến thức cơ bản về giải tích hàm, giải tích lồi trong không gian Hilbert thực ở 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 tối ưu trên tập điểm bất động của một
ánh xạ không giãn trong không gian Hilbert thực.
Ba là, trình bày chi tiết phương pháp, sự hội tụ cùng các ví dụ số minh họa
cụ thể tương ứng cho các phương pháp hướng gradient liên hợp và phương
pháp hướng gradient liên hợp lai ghép.
Tài liệu tham khảo
Tiếng Việt
[1] Hoàng Tụy (2003), Hàm thực và Giải tích hàm (Giải tích hiện đại), Nhà
xuất bản Đại học Quốc gia Hà Nội.
Tiếng Anh
[2] Bauschke H. H., Combettes P. L. (2010), Convex Analysis and Monotone
Operator Theory in Hilbert Spaces, Springer.
[3] Iiduka H. (2009), "Hybrid conjugate gradient method for a convex opti-
mization problem over the fixed point set of a nonexpansive mapping", J. Optim. Theory Appl., 140, pp. 463-475.
[4] Iiduka H., Yamada I. (2009), "A use of conjugate gradient direction for the convex optimization problem over the fixed point set of a nonexpan-
sive mapping", SIAM J. Optim., 19, pp. 1881-1893.
[5] Yamada I. (2001), "The hybrid steepest descent method for the varia- tional inequality problem over the intersection of fixed point sets of non-
expansive mappings", Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, Chapter 8, pp. 473-504.
![Luận văn Thạc sĩ: Tổng hợp và đánh giá hoạt tính chống ung thư của hợp chất lai chứa khung tetrahydro-β-carboline và imidazo[1,5-a]pyridine](https://cdn.tailieu.vn/images/document/thumbnail/2025/20250807/kimphuong1001/135x160/50321754536913.jpg)
