ĐẠ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 c 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 c 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. Một số vấn đề cơ bản về không gian Hilbert . Tập lồi và hàm lồi . Ánh xạ đơn điệu . Ánh xạ không giãn và điểm bất động . 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. Mô hình bài toán . Phương pháp hướng gradient liên hợp .1 Mô tả phương pháp .2 Sự hội tụ của phương pháp .3 Ví dụ minh họa . Phương pháp hướng gradient liên hợp lai ghép .1 Mô tả phương pháp .2 Sự hội tụ của phương pháp .3 Ví dụ minh họa . 43 Kết luận chung và đề nghị 44 Tài liệu tham khảo 45 c 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 c vi Danh sách bảng 2.1 Kết quả tính toán phương pháp (CGM) với µ = 1 .2 Kết quả tính toán phương pháp (CGM) với µ = 1/100 .3 Một số kết quả tính toán khác cho phương pháp (CGM) .4 Kết quả tính toán phương pháp (HCGM) với µ = 1 .5 Một số kết quả tính toán khác cho phương pháp (HCGM) . 43 c 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. 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. c 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. c 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.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. 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. Một số vấn đề cơ bản về không gian Hilbert Định nghĩa 1. Cho H là một không gian véctơ thực.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. 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 + . 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.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. (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. 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. Cho H là một không gian tiền Hilbert.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. 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. c 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. 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. 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. [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 c 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 ].
Tổng quan nghiên cứu
Trong lĩnh vực toán ứng dụng, bài toán tối ưu lồi trên không gian Hilbert thực là một chủ đề nghiên cứu quan trọng với nhiều ứng dụng trong khoa học và kỹ thuật. Theo ước tính, việc tìm nghiệm xấp xỉ 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 có ý nghĩa thiết thực trong việc giải quyết các bài toán phức tạp trong không gian vô hạn chiều. Luận văn tập trung nghiên cứu phương pháp hướng gradient liên hợp cho lớp bài toán này, với mục tiêu xây dựng và phân tích các thuật toán có tính hội tụ mạnh và hiệu quả tính toán cao.
Phạm vi nghiên cứu được giới hạn trong không gian Hilbert thực, tập trung vào 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, với giả thiết hàm mục tiêu khả vi Fréchet liên tục, gradient α-đơn điệu mạnh và Lipschitz liên tục. Thời gian nghiên cứu là năm 2020 tại Trường Đại học Khoa học, Đại học Thái Nguyên. Ý nghĩa của nghiên cứu được thể hiện qua việc cung cấp các phương pháp giải số mới, có thể áp dụng trong các lĩnh vực như tối ưu hóa, học máy, và các bài toán điều khiển.
Cơ sở lý thuyết và phương pháp nghiên cứu
Khung lý thuyết áp dụng
Luận văn dựa trên nền tảng lý thuyết giải tích lồi và không gian Hilbert thực. Hai lý thuyết chính được áp dụng là:
-
Lý thuyết không gian Hilbert thực: Không gian Hilbert là không gian véctơ thực có tích vô hướng và chuẩn sinh ra bởi tích vô hướng, thỏa mãn quy tắc hình bình hành. Các tính chất như hội tụ mạnh, hội tụ yếu, phép chiếu mêtric lên tập lồi đóng, và ánh xạ không giãn được sử dụng làm cơ sở cho việc xây dựng thuật toán.
-
Lý thuyết hàm lồi và ánh xạ đơn điệu: Hàm lồi có tính chất điểm cực tiểu địa phương là điểm cực tiểu toàn cục, và gradient của hàm lồi là ánh xạ đơn điệu. Ánh xạ α-đơn điệu mạnh và Lipschitz liên tục của gradient được sử dụng để đảm bảo tính hội tụ của thuật toán.
Các khái niệm chính bao gồm: tập lồi, hàm lồi, ánh xạ không giãn, điểm bất động, phép chiếu mêtric, đạo hàm Fréchet và Gâteaux, ánh xạ α-đơn điệu mạnh, và phương pháp hướng gradient liên hợp.
Phương pháp nghiên cứu
Nguồn dữ liệu nghiên cứu chủ yếu là các tài liệu học thuật, bài báo khoa học và các công trình nghiên cứu liên quan đến tối ưu hóa lồi và không gian Hilbert. Phương pháp nghiên cứu bao gồm:
-
Phân tích lý thuyết: Hệ thống hóa các kiến thức cơ bản về không gian Hilbert, hàm lồi, ánh xạ không giãn và điểm bất động để xây dựng mô hình bài toán tối ưu.
-
Phát triển thuật toán: Trình bày chi tiết hai phương pháp hướng gradient liên hợp (CGM) và phương pháp hướng gradient liên hợp lai ghép (HCGM) cho bài toán tối ưu lồi trên tập điểm bất động.
-
Phân tích hội tụ: Chứng minh tính hội tụ mạnh của các thuật toán dựa trên các điều kiện về tham số và tính chất của hàm mục tiêu.
-
Thí nghiệm số: Thực hiện các ví dụ minh họa trên không gian hữu hạn chiều Rn với các tham số khác nhau để đánh giá tốc độ hội tụ và ảnh hưởng của tham số bước lặp µ.
Thời gian nghiên cứu kéo dài trong năm 2020, với các bước thực hiện từ tổng hợp lý thuyết, phát triển thuật toán đến kiểm chứng qua ví dụ số.
Kết quả nghiên cứu và thảo luận
Những phát hiện chính
-
Sự tồn tại và duy nhất nghiệm bài toán tối ưu lồi trên tập điểm bất động: Dưới các giả thiết hàm khả vi Fréchet liên tục, gradient α-đơn điệu mạnh và ánh xạ không giãn có tập điểm bất động không rỗng, bài toán tối ưu có nghiệm duy nhất. Điều này được chứng minh thông qua bất đẳng thức biến phân và tính chất co của ánh xạ chiếu mêtric.
-
Hiệu quả của phương pháp hướng gradient liên hợp (CGM): Thuật toán CGM với tham số bước lặp µ trong khoảng (0, 2α/L²) hội tụ mạnh đến nghiệm duy nhất. Ví dụ số cho thấy với µ = 1, thuật toán hội tụ nhanh hơn so với µ = 1/100 hoặc µ = 1/1000, minh chứng qua các giá trị xấp xỉ nghiệm tại các bước lặp k.
-
Phương pháp hướng gradient liên hợp lai ghép (HCGM): Thuật toán HCGM cũng hội tụ mạnh đến nghiệm duy nhất với điều kiện tương tự. Kết quả tính toán cho thấy tốc độ hội tụ của HCGM tương đương với CGM khi thay đổi tham số µ, cho thấy tính ổn định và hiệu quả của phương pháp.
-
Ảnh hưởng của tham số bước lặp µ: Cả hai phương pháp đều bị ảnh hưởng rõ rệt bởi giá trị µ. Khi µ gần 0, tốc độ hội tụ chậm; khi µ thuộc khoảng [1, 2), tốc độ hội tụ được cải thiện đáng kể. Điều này được minh họa qua bảng kết quả tính toán số với các giá trị µ khác nhau.
Thảo luận kết quả
Nguyên nhân của sự hội tụ mạnh và hiệu quả của các phương pháp là do sự kết hợp giữa tính α-đơn điệu mạnh và Lipschitz liên tục của gradient hàm mục tiêu, cùng với tính không giãn của ánh xạ chiếu mêtric. So sánh với các nghiên cứu trước đây, phương pháp hướng gradient liên hợp được cải tiến để áp dụng cho bài toán tối ưu trên tập điểm bất động, mở rộng phạm vi ứng dụng trong không gian Hilbert thực.
Dữ liệu có thể được trình bày qua biểu đồ thể hiện sự giảm dần của chuẩn sai số kx_n - x* k theo số bước lặp, hoặc bảng so sánh tốc độ hội tụ với các giá trị tham số µ khác nhau. Điều này giúp minh họa trực quan ảnh hưởng của tham số và hiệu quả của thuật toán.
Đề xuất và khuyến nghị
-
Tối ưu hóa tham số bước lặp µ: Khuyến nghị lựa chọn µ trong khoảng [1, 2) để đảm bảo tốc độ hội tụ nhanh và ổn định. Chủ thể thực hiện là các nhà nghiên cứu và kỹ sư phát triển thuật toán tối ưu.
-
Áp dụng phương pháp cho các bài toán thực tế: Đề xuất sử dụng phương pháp hướng gradient liên hợp trong các bài toán tối ưu hóa trong học máy, xử lý ảnh, và điều khiển tự động, nhằm tận dụng tính hội tụ mạnh và hiệu quả tính toán.
-
Phát triển thuật toán lai ghép nâng cao: Khuyến khích nghiên cứu tiếp tục cải tiến phương pháp HCGM bằng cách kết hợp với các kỹ thuật tối ưu khác để tăng tốc độ hội tụ và khả năng xử lý bài toán phức tạp hơn.
-
Xây dựng phần mềm hỗ trợ: Đề xuất phát triển các thư viện phần mềm triển khai các thuật toán này, giúp cộng đồng nghiên cứu và ứng dụng dễ dàng tiếp cận và sử dụng.
Các giải pháp trên nên được thực hiện trong vòng 1-2 năm tới, với sự phối hợp giữa các viện nghiên cứu, trường đại học và doanh nghiệp công nghệ.
Đối tượng nên tham khảo luận văn
-
Sinh viên và nghiên cứu sinh ngành Toán ứng dụng: Giúp hiểu sâu về lý thuyết không gian Hilbert, hàm lồi và các phương pháp tối ưu hóa hiện đại.
-
Giảng viên và nhà nghiên cứu trong lĩnh vực tối ưu hóa: Cung cấp cơ sở lý thuyết và thuật toán mới để phát triển nghiên cứu và giảng dạy.
-
Kỹ sư phát triển thuật toán trong công nghiệp: Áp dụng các phương pháp tối ưu hóa lồi cho các bài toán thực tế trong kỹ thuật, tài chính, và công nghệ thông tin.
-
Chuyên gia trong lĩnh vực học máy và trí tuệ nhân tạo: Sử dụng các thuật toán tối ưu hóa gradient liên hợp để cải thiện hiệu suất mô hình và thuật toán học.
Mỗi nhóm đối tượng có thể áp dụng kiến thức và thuật toán trong các use case cụ thể như thiết kế hệ thống điều khiển, tối ưu hóa mô hình dự báo, hoặc phát triển phần mềm tối ưu.
Câu hỏi thường gặp
-
Phương pháp hướng gradient liên hợp là gì?
Phương pháp này là thuật toán lặp nhằm tìm nghiệm xấp xỉ của bài toán tối ưu lồi bằng cách kết hợp hướng gradient và các hướng liên hợp, giúp tăng tốc độ hội tụ so với phương pháp gradient đơn thuần. -
Tại sao cần ánh xạ không giãn trong bài toán?
Ánh xạ không giãn đảm bảo tính liên tục và ổn định của phép chiếu lên tập điểm bất động, từ đó giúp thuật toán hội tụ mạnh đến nghiệm duy nhất. -
Làm thế nào để chọn tham số bước lặp µ?
Theo nghiên cứu, µ nên nằm trong khoảng (0, 2α/L²), với α và L là các hằng số liên quan đến tính đơn điệu và Lipschitz của gradient. Thực nghiệm cho thấy µ trong [1, 2) cho tốc độ hội tụ tốt nhất. -
Phương pháp hướng gradient liên hợp lai ghép khác gì so với CGM?
Phương pháp lai ghép (HCGM) kết hợp thêm các thành phần điều chỉnh trong bước lặp nhằm cải thiện tính ổn định và tốc độ hội tụ, đặc biệt hiệu quả khi gradient bị nhiễu hoặc không chính xác. -
Có thể áp dụng các phương pháp này cho không gian vô hạn chiều không?
Có, nghiên cứu được xây dựng trên không gian Hilbert thực, bao gồm cả không gian vô hạn chiều, miễn là các giả thiết về hàm mục tiêu và ánh xạ không giãn được thỏa mãn.
Kết luận
- Trình bày hệ thống kiến thức cơ bản về không gian Hilbert, hàm lồi và ánh xạ không giãn làm nền tảng cho nghiên cứu.
- Xây dựng và phân tích hai phương pháp hướng gradient liên hợp (CGM) và lai ghép (HCGM) cho bài toán tối ưu lồi trên tập điểm bất động.
- Chứng minh tính hội tụ mạnh của các thuật toán dưới các điều kiện giả thiết cụ thể.
- Thực hiện các ví dụ số minh họa cho thấy ảnh hưởng của tham số bước lặp và hiệu quả của thuật toán.
- Đề xuất các hướng phát triển và ứng dụng trong thực tế, đồng thời khuyến nghị các nhóm đối tượng nghiên cứu và ứng dụng tham khảo.
Tiếp theo, nghiên cứu có thể mở rộng bằng cách phát triển các thuật toán tối ưu hóa lai ghép nâng cao và ứng dụng trong các lĩnh vực công nghiệp. Độc giả và nhà nghiên cứu được khuyến khích áp dụng và phát triển các phương pháp này trong công việc của mình.