Luận văn Thạc sĩ Toán học: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

17
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: 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

ĐẠ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
iii 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ị 3 1.1. Một số vấn đề cơ bản về không gian Hilbert . . . . . . . . . . 3 1.2. Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3. Ánh xạ đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . 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 24 2.1. Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2. Phương pháp hướng gradient liên hợp . . . . . . . . . . . . . . 26 2.2.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . . . . 26 2.2.2 Sự hội tụ của phương pháp . . . . . . . . . . . . . . . 27 2.2.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . 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 . . . . . . . . . . . . . . . . . . . . 37 2.3.2 Sự hội tụ của phương pháp . . . . . . . . . . . . . . . 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
v 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 ∇f Gradient của hàm f ∇2 f Hessian của hàm f hx, yi Tích vô hướng của hai véctơ x và y kxk Chuẩn của véctơ x PC (x) Phép chiếu mêtric phần tử x lên tập C xn * 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
vi 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) . . . 36 2.4 Kết quả tính toán phương pháp (HCGM) với µ = 1 . . . . . . 43 2.5 Một số kết quả tính toán khác cho phương pháp (HCGM) . . 43
1 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: Tìm x∗ ∈ C sao cho: f (x∗ ) = min f (x), (0.1) 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à xk+1 = xk + αk dk , k = 0, 1, 2, ... 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.
3 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ố h., .i : H × H → R (x,y) 7→ hx,yi đượ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) hx, yi = hy, xi với mọi x, y ∈ H, ii) hx + y, zi = hx, zi + hy, zi với mọi x, y, z ∈ H, iii) hαx, yi = αhx, yi với mọi x, y ∈ H, α ∈ R, iv) hx, xi ≥ 0 với mọi x ∈ H và hx, xi = 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 hx, yi = x1 y1 + x2 y2 + ... + xn yn . 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 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à Z b |x(t)|2 dt < ∞ ∀x = x(t) ∈ L2 [a, b]. a Hàm số h., .i : L2 [a, b] × L2 [a, b]→R xác định bởi Z b hx, yi = x(t)y(t)dt ∀x = x(t), y = y(t) ∈ L2 [a, b], a 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ó |hx, yi|2 ≤ hx, xihy, yi, ∀x, y ∈ H. Chứng minh. Hiển nhiên y = 0 bất đẳng thức đúng. Giả sử y 6= 0 và với mọi λ ∈ R ta có hx + λy, x + λyi ≥ 0. Điều này dẫn đến hx, xi + 2λhx, yi + λ2 hy, yi ≥ 0. hx, yi Chọn λ = − và thay vào bất đẳng thức trên ta nhận được hy, yi |hx, yi|2 hx, xi − ≥ 0. hy, yi 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ố k.k : H → R xác định bởi p kxk = hx, xi 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ó kxk ≥ 0 và kxk = 0 ⇔ x = 0. Tiếp theo, với mọi x ∈ H và λ ∈ R ta thấy p p kλxk = hλx, λxi = |λ| hx, xi = |λ|kxk.
5 Cuối cùng, sử dụng bất đẳng thức Schwarz, với mọi x, y ∈ H ta có kx + yk2 = kxk2 + 2hx, yi + kyk2 ≤ kxk2 + 2kxkkyk + kyk2 = (kxk + kyk)2 . Suy ra kx + yk ≤ kxk + kyk. 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ó kx + yk2 + kx − yk2 = 2(kxk2 + kyk2 ), ∀x, y ∈ H. Chứng minh. Ta có kx + yk2 = kxk2 + 2hx, yi + kyk2 , ∀x, y ∈ H, và kx − yk2 = kxk2 − 2hx, yi + kyk2 , ∀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à kx + yk2 + kx − yk2 = 2(kxk2 + kyk2 ) ∀x, y ∈ H. thì trên H tồn tại một tích vô hướng sao cho hx, xi = kxk2 . Thật vậy, ta đặt 1 hx, yi = [kx + yk2 − kx − yk2 ] ∀x, y ∈ H. 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, hx, xi ≥ 0 với mọi x ∈ H và hx, xi = 0 ⇔ x = 0. ii) Hiển nhiên, hx, yi = hy, yi với mọi x, y ∈ H. iii) Từ quy tắc hình bình hành và cách xác định hx, yi ta có thể viết hx, yi dưới các dạng 1 hx, yi = [kx + yk2 − kxk2 − kyk2 ] (∗) 2
6 hoặc 1 hx, yi = [kxk2 + kyk2 − kx − yk2 ] (∗∗) 2 Để ý rằng 1 hx + y, zi = [k(x + y) + zk2 − k(x + y) − zk2 ] 4 1 = [k(x + y) + zk2 + k(x − y) + zk2 ] 4 1 − [k(x − y) + zk2 + k(x + y) − zk2 ] 4 1 1 = [kx + zk2 + kyk2 ] − [ky − zk2 + kxk2 ]. 2 2 Từ (*) và (**) ta có đánh giá 1 1 hx + y, zi = [kx + zk2 + kyk2 ] − [ky − zk2 + kxk2 ] 2 2 1 1 = [kx + zk2 − kxk2 − kzk2 ] + [kyk2 + kzk2 − ky − zk2 ] 2 2 = hx, zi + hy, zi iv) Cuối cùng, ta chứng minh hλx, yi = λhx, yi. Trước hết, với mỗi x, y ∈ H cố định, ta xét hàm số g(λ) = kλx + yk. Khi đó, ta có |g(λ1 ) − g(λ2 )| ≤ |λ1 − λ2 |kxk. 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 (λ) = hλx, yi 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) = hx, yi. 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 kxk = max |x(t)|, x = x(t) ∈ C[a, b]. 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 t−a là không gian Hilbert. Thật vậy, chọn x = x(t) = 1 và y = y(t) = với b−a mọi t ∈ [a, b]. Khi đó, ta có
t − a
kxk = 1 và kyk = max
= 1. a≤t≤b b − a