ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM ——————————– PHẠM NGỌC THÁI BÀI TỐN TỐI ƯU KHƠNG TRƠN TRONG BÀI TOÁN NGƯỢC VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC Đà Nẵng - 2017 ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC SƯ PHẠM ——————————– PHẠM NGỌC THÁI BÀI TỐN TỐI ƯU KHƠNG TRƠN TRONG BÀI TỐN NGƯỢC VÀ ỨNG DỤNG Chun ngành: Tốn Giải tích Mã số: 60.46.01.02 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: TS Lê Hồng Trí Đà Nẵng - 2017 LỜI CAM ĐOAN Tơi cam đoan cơng trình nghiên cứu riêng Các số liệu, kết nêu luận văn trung thực chưa cơng bố cơng trình khác Tác giả PHẠM NGỌC THÁI LỜI CẢM ƠN Lời đầu tiên, tác giả xin gửi lời cảm ơn chân thành tới thầy giáo hướng dẫn, TS Lê Hồng Trí, người tận tình hướng dẫn tác giả suốt thời gian qua Với giúp đỡ thầy, tác giả hồn thành luận văn Tác giả xin gửi lời cảm ơn đến TS Phạm Quý Mười trao đổi, thảo luận góp ý thầy suốt q trình làm luận văn Tác giả trân trọng gửi lời cảm ơn đến tất quý thầy lãnh đạo Khoa Toán - Trường Đại học Sư phạm - Đại học Đà Nẵng q thầy giáo tận tình dạy bảo tác giả suốt thời gian học tập khóa học Đồng thời, tác giả xin gửi lời cảm ơn đến anh chị học viên lớp Giải tích K31 nhiệt tình giúp đỡ tác giả trình học tập Tác giả muốn gửi lời cảm ơn đến người bạn lớp, Nguyễn Thị Liêu Noa, hỗ trợ giúp đỡ tác giả, phần nghiệm số luận văn Tác giả PHẠM NGỌC THÁI MỤC LỤC MỞ ĐẦU CHƯƠNG KIẾN THỨC CƠ SỞ 1.1 KHÔNG GIAN HILBERT 1.2 HỆ TRỰC CHUẨN 1.3 TỐN TỬ TUYẾN TÍNH BỊ CHẶN VÀ TOÁN TỬ COMPACT 1.4 HÀM SỐ 13 1.5 DƯỚI VI PHÂN 15 CHƯƠNG BÀI TOÁN TỐI ƯU KHÔNG TRƠN VÀ CÁC GIẢI THUẬT 16 2.1 BÀI TOÁN 16 2.2 ĐIỀU KIỆN CÓ NGHIỆM VÀ ĐIỀU KIỆN CẦN CỦA NGHIỆM 16 2.3 GIẢI THUẬT GIẢM GRADIENT 19 2.3.1 Tốc độ hội tụ 20 2.3.2 Tiêu chuẩn lựa chọn stepsizes 25 2.3.3 Giải thuật giảm Gradient 26 2.4 GIẢI THUẬT CẢI TIẾN NESTEROV 27 CHƯƠNG ỨNG DỤNG VÀ VÍ DỤ 32 3.1 BÀI TOÁN 32 3.2 ÁP DỤNG CHỈNH HÓA THƯA 32 3.3 VÍ DỤ ÁP DỤNG 33 MỤC LỤC 3.3.1 Bài toán 33 3.3.2 Rời rạc toán 33 3.3.3 Áp dụng chỉnh hóa thưa 34 3.3.4 Minh họa nghiệm số hội tụ 35 KẾT LUẬN VÀ KIẾN NGHỊ 39 TÀI LIỆU THAM KHẢO 40 BẢNG KÍ HIỆU R x, y K x (X, ) Rn (X, X ) H x L2 C [a, b] L [X, Y ] A∗ KL X, Y R ∂f ∀x : Trường số thực : Tích vơ hướng x y : Chuẩn tốn tử K : Chuẩn x : Khơng gian tiền Hilbert X : Không gian tiền Hilbert n chiều : Không gian định chuẩn X : Không gian Hilbert : Chuẩn Ơclit : Không gian hàm liên tục [a,b] : Không gian gồm tất tốn tử tuyến tính bị chặn từ X vào Y : Toán tử liên hợp A : Tập {kl | k ∈ K, l ∈ L} : Không gian Hilbert thực : Tập mở rộng tập số thực R : Dưới vi phân hàm f : với x MỞ ĐẦU Lịch sử vấn đề lý chọn đề tài Hiện nay, mơ hình hóa vấn đề thực tiễn đặt nhiều lĩnh vực khoa học kỹ thuật thường dẫn đến nghiên cứu toán tối ưu khơng trơn (tức hàm mục tiêu khơng có đạo hàm) Điều thúc đẩy việc nghiên cứu tốn tối ưu khơng trơn, lĩnh vực quan tâm lớn có bước phát triển mạnh vài thập niên gần Trong lĩnh vực tốn ngược, phương pháp chỉnh hóa kiểu Tikhonov thường dẫn đến việc nghiên cứu toán tối ưu dạng: Θ (u) := F (u) + Φ (u) u∈H (1) Trong đó, F hàm khả vi liên tục Φ hàm nửa liên tục khơng khả vi Đây dạng tốn nghiên cứu nhóm tác giả Phạm Quý Mười, Đinh Nho Hào, Peter Maass Michael Pidcock đưa báo [10] Một vài trường hợp cụ thể toán nghiên cứu luận án tiến sĩ Phạm Quý Mười [11] Về giải thuật để giải Bài toán (1), phương pháp nghiên cứu nhiều giải thuật giảm Gradient giải thuật cải tiến Bên cạnh đó, Newtơn nửa trơn phương pháp tựa Newtơn nửa trơn sử dụng để tính tốn tốn ngược Với mong muốn nghiên cứu toán số giải thuật tìm nghiệm xấp xỉ tốn, tơi chọn đề tài “Bài tốn tối ưu khơng trơn toán ngược ứng dụng” Với đề tài này, dự định nghiên cứu tồn nghiệm toán, điều kiện cần cho nghiệm toán Đặc biệt, đề tài tập trung vào nghiên cứu áp dụng hai giải thuật bản: Giải thuật giảm Gradient giải thuật cải tiến Nesterov 2 Mục đích nghiên cứu Mục tiêu đề tài nghiên cứu, tìm hiểu Bài tốn tối ưu (1) thuật toán cho toán tối ưu Ứng dụng giải thuật cho số toán cụ thể Đối tượng phạm vi nghiên cứu Bài tốn tối ưu khơng trơn Θ (u) := F (u) + Φ (u) u∈H Các giải thuật cho Bài tốn tối ưu khơng trơn (1) + Giải thuật giảm Gradient, + Giải thuật cải tiến Nesterov Phương pháp nghiên cứu Với đề tài: “Bài tốn tối ưu khơng trơn tốn ngược ứng dụng” sử dụng phương pháp nghiên cứu sau: - Thu thập, tổng hợp tài liệu liên quan đến nội dung đề tài luận văn - Phân tích, nghiên cứu tài liệu thu thập để thực đề tài - Tham gia buổi seminar thầy hướng dẫn để trao đổi kết nghiên cứu Ý nghĩa khoa học thực tiễn Nội dung đề tài nghiên cứu cở sở lý thuyết giải thuật để giải tốn tối ưu khơng trơn tốn ngược Luận văn dùng làm tài liệu tham khảo cho sinh viên, học viên cao học có nhu cầu tìm hiểu tốn tối ưu khơng trơn tốn ngược Cấu trúc luận văn Luận văn “Bài toán tối ưu khơng trơn tốn ngược ứng dụng” trình bày theo cấu trúc sau: Mở đầu Chương I: Kiến thức sở Chúng nhắc lại số khái niệm, định nghĩa, định lí Giải tích hàm Các tính chất, định lí nêu không chứng minh Mặt khác, luận văn nhắc lại số tính chất hàm lồi, hàm coercive Các tính chất dùng chương Chương II: Bài toán tối ưu không trơn giải thuật Chương giới thiệu tốn tối ưu khơng trơn xuất chỉnh hóa tốn ngược Trước hết, luận văn nêu giả thiết cho toán, phát biểu chứng minh bổ đề, định lí điều kiện có nghiệm điều kiện cần nghiệm Nội dung chương giới thiệu giải thuật giảm Gradient giải thuật cải tiến Nesterov xem xét tốc độ hội tụ hai giải thuật Chương III: Ứng dụng ví dụ Áp dụng hai giải thuật giảm Gradient giải thuật cải tiến Nesterov nghiên cứu để tìm nghiệm xấp xỉ phương trình K (x) = y Áp dụng chỉnh hóa thưa để tìm nghiệm xấp xỉ phương trình vi phân cấp ví dụ minh họa 27 2.4 GIẢI THUẬT CẢI TIẾN NESTEROV Trong phần này, tác giả giới thiệu giải thuật cải tiến Nesterov, giải thuật cải tiến giải thuật Gradient Tốc độ hội tụ giải thuật biết đến tối ưu xem [4, 5, 6, 12] Giải thuật cải tiến Nesterov tác giả giới thiệu [10, 11] Sau đó, số tác giả [3, 9, 8] nghiên cứu mở rộng giải thuật cho toán tổng quát Algorithm 2.4.1 Giải thuật cải tiến Nesterov Input: Dự đoán ban đầu u0 ∈ domf (Φ) ; A0 = 0, v = u0 , µ ∈ (1, ∞), s0 ∈ [s, s] (0 < s ≤ L/µ ≤ s) Ψ0 (u) = 21 u − u0 1: for n = 0, 1, 2, 2: repeat √ n ns 3: an+1 ← 1+ 1+2A sn n n +an +1v 4: y n ← AnAun +a n +1 5: un+1 ← P 1n Φ y n − s1n F (y n ) s F (un+1 ) − F (y n ) > sn F (y n ) − F (un+1 ) , y n − un+1 then sn ← sn µ end if untill F (un+1 ) − F (y n ) ≤ sn F (y n ) − F (un+1 ) , y n − un+1 or sn ∈ / [s, s] An+1 ← An + an+1 v n+1 ← arg minu∈H Ψn+1 (u) với Ψn+1 (u) = Ψn (u) + an+1 (F (un+1 ) + F (un+1 ) , u − un+1 + Φ (u)) 12: Tính dự đốn ban đầu cho sn+1 13: end for Output: u = lim un 6: 7: 8: 9: 10: 11: if Bây giờ, chứng minh hội tụ tốc độ hội tụ Giải thuật 2.4.1 thông qua bổ đề định lí sau: Bổ đề 2.4.1 Cho Ψn (u) xác định bước 11 Giải thuật 2.4.1 Khi đó, v n = arg minu∈H Ψn (u) cho v n = PAn φ (z n ), (n > 0) đó: z o := uo z n := z n−1 − an F (un ) Chứng minh Bằng phương pháp quy nạp với Ψo (u) = Ψn (u) = u − u0 n + n u − u0 ta có: ak F (uk ) + F uk , u − uk ak Φ (u) + k=1 k=1 (2.18) 28 n = cn + u − u0 − ak F uk k=1 + An Φ (u) (2.19) cn số phụ thuộc vào n Từ định nghĩa toán tử proximal, ta có: n n ak F uk v = P An Φ u − (2.20) k=1 Bây giờ, ta định nghĩa biến z n với giá trị ban đầu z o := uo z n := z n−1 − an F (un ) Khi đó, ta có: v n = PAn Φ (z n ) Cuối cùng, để xét tốc độ hội tụ hàm mục tiêu Θ Giải thuật 2.4.1 ta cần bổ đề sau: Bổ đề 2.4.2 Các dãy {un } , {An } , {Ψn } sinh Giải thuật 2.4.1 thỏa mãn hệ thức sau: ∀n ≥ R1n : An Θ (un ) ≤ Ψ∗n ≡ Ψn (u) u R2n : Ψn (u) ≤ An Θ (u) + 2 u − u0 , ∀u ∈ H Chứng minh Ta chứng minh bổ đề phương pháp quy nạp Do điều kiện ban đầu Giải thuật 2.4.1, hai hệ thức tầm thường với n = Giả sử hệ thức R1n R2n với n ≥ Từ R2n , ∀n ∈ H ta có: Ψn+1 (u) ≤ An Θ (u) + 21 u − u0 +an+1 F un+1 + F un+1 , u − un+1 + Φ (u) ≤ (An + an+1 ) Θ (u) + 2 u − u0 , 29 Như R2n+1 Bây giờ, ta cần chứng minh R1n+1 Thật vây, từ công thức Ψn chứng minh Bổ đề 2.4.1, hàm Ψn hội tụ mạnh với tham số µ = Hơn nữa, R1n đúng, ∀u ∈ H, ta có: 1 u = v n ≥ An Θ (un ) + u − v n 2 := F un+1 + ξ với ξ ∈ ∂Φ un+1 , ta có: ψn (u) ≥ ψn∗ + Đặt: Θ un+1 (2.21) ∗ ψn+1 = ψn (u) + an+1 F un+1 + F un+1 , u − un+1 + Φ (u) u∈H (2.20) ≥ An Θ (un ) + u∈H u − + an+1 Θ un+1 + Θ un+1 , u − un+1 ≥ (An + an+1 ) Θ un+1 + An Θ un+1 , un − un+1 u∈H +an+1 Θ un+1 , u − un+1 + u − Step4 = An+1 Θ un+1 + Θ un+1 , An+1 y n − an+1 v n − An un+1 u∈H +an+1 Θ un+1 , u − un+1 + u − 2 = An+1 Θ un+1 + An+1 Θ un+1 , y n − un+1 u∈H +an+1 Θ un+1 , u − v n + u − Vì vậy, ta chứng minh bất đẳng thức ∗ ψn+1 n+1 ≥ An+1 Θ u n+1 + An+1 Θ u n n+1 ,y − u a2n+1 − Θ un+1 (2.22) Hơn nữa, un+1 cực tiểu Θsn (., y n ), ta chọn ξ ∈ ∂Φ un+1 cho: F (y n ) + sn un+1 − y n + ξ = ⇒ F un+1 +ξ = sn y n − un+1 +F un+1 −F (y n ) (2.23) Suy ra: Θ un+1 , y n − un+1 = sn y n − un+1 − F (y n ) − F un+1 , y n − un+1 30 (2.22) = sn Θ un+1 + 2sn F (y n ) − F un+1 , y n − un+1 − F (y n ) − F un+1 = sn Θ un+1 − F (y n ) − F un+1 , y n − un+1 + F (y n ) − F un+1 , y n − un+1 − s1n F (y n ) − F un+1 Điều kiện Bước Giải thuật 2.4.1 suy F (y n ) − F un+1 , y n − un+1 − sn F (y n ) − F un+1 ≥0 Θ un+1 , y n − un+1 ≥ Θ un+1 n s (2.24) Từ (2.21) (2.23), ta có: ∗ ψn+1 ≥ An+1 Θ un+1 + An+1 sn − a2n+1 Θ un+1 Cuối cùng, Bước Giải thuật 2.4.1, ta chọn an+1 từ phương trình An +an+1 sn − a2n+1 =0⇔ An+1 sn − a2n+1 = Vì vậy, R1n+1 là Bổ đề 2.4.3 Dãy dương {An } sinh Giải thuật 2.4.1 Bước thứ 12 với A0 = thỏa mãn A0 ≥ n2 , ∀n ≥ 0, 2C với C = µL Chứng minh Từ Bước thứ Giải thuật 2.4.1 (xem phương trình cuối chứng minh bổ đề trên), ta có: An+1 = sn (An+1 − An ) = sn 1/ − An/2 An+1 1/ + An/2 An+1 31 ≤ 2sn An+1 1/ − An/2 An+1 1/ Vì vậy, ta được: An ≥ √n 2C 2 ≤ 2CAn+1 hay A0 ≥ n2 2C , ∀n 1/ − An/2 , An+1 ≥ Định lí 2.4.4 Cho F lồi, F Φ thỏa mãn tính chất (1), (3) Giả định 2.2.1 Cho {un } sinh Giải thuật 2.4.1 u∗ cực tiểu Bài tốn (2.1) Khi đó, ∀n ≥ ∗ n Θ (u ) − Θ (u ) ≤ C u0 −u∗ n2 (C = L/µ) Chứng minh Từ Bổ đề 2.4.3, ∀n ≥ ta có: An Θ (un ) ≤ ψn∗ ≡ ψn (u) u ψn (u) ≤ An Θ (u) + 2 u − u0 , ∀u ∈ H, Lấy u := u∗ , cực tiểu Θ bất đẳng thức thứ hai, ta suy ∗ n Θ (u ) − Θ (u ) ≤ u∗ −u0 2An , ∀n ≥ Cuối cùng, áp dụng kết Bổ đề 2.4.4 ta có: A0 ≥ n2 2C , ∀n ≥ Ta suy n ∗ Θ (u ) − Θ (u ) ≤ C u0 −u∗ n2 (C = L/µ) 32 CHƯƠNG ỨNG DỤNG VÀ VÍ DỤ Chương này, luận văn áp dụng hai giải thuật giảm Gradient giải thuật cải tiến Nesterov nghiên cứu để tìm nghiệm xấp xỉ phương trình K (x) = y Áp dụng chỉnh hóa thưa để tìm nghiệm xấp xỉ phương trình vi phân cấp ví dụ minh họa 3.1 BÀI TỐN Tìm nghiệm phương trình: K (x) = y, (3.1) K : H → H tốn tử liên tục (tuyến tính phi tuyến) Hơn nữa, ta giả thiết liêu vế phải y xác mà có liệu xấp xỉ y δ y với y δ − y ≤ δ (3.2) Chúng ta giả sử Bài tốn (3.1) - (3.2) tốn đặt khơng chỉnh 3.2 ÁP DỤNG CHỈNH HÓA THƯA Trong nhiều trường hợp nghiệm xác x∗ (3.1) khơng biết thơng tin nghiệm biết trước Trong phần này, giả sử nghiệm xác x∗ có tính thưa Tính thưa định nghĩa sau: Nếu {ϕi }i∈∧ sở trực chuẩn không gian H u= (u, ϕi )ϕi , i∈∧ u gọi thưa có hữu hạn hệ số (u, ϕi ) khác khơng Áp dụng phương pháp chỉnh hóa thưa cho Bài toán (3.1) - (3.2) dẫn đến toán tối ưu 33 M inΘ (u) = F u, y δ + α |ui | i∈∧ đó, F u, y δ = 12 Ku − y δ , ui = (u, ϕi ) với {ϕi }i∈∧ sở trực chuẩn không gian Hilbert H Đây trường hợp đặc biệt Bài toán (3.1) với F (u) := F u, y δ Φ (u) = α |ui | i∈∧ Trường hợp này, [10] người ta chứng minh rằng: sgn (ui )max {|ui | − λ, 0} Pλφ (u) = i∈∧ 3.3 VÍ DỤ ÁP DỤNG 3.3.1 Bài tốn Cho f ∈ L2 (0, 1) , tìm ϕ (s) ∈ L2 (0, 1) cho g (x, s)ϕ (s) ds = f (s) (3.3) Đặt Kϕ = g (x, s)ϕ (s) ds, ta có: K : L2 (0, 1) → L2 (0, 1) toán tử compact 3.3.2 Rời rạc toán Ta chia đoạn [0,1] thành n đoạn điểm = xo < x1 < x2 < < xn = độ dài đoạn h = n1 Áp dụng quy tắc hình thang để tính gần tích phân Khi Kϕ xấp xỉ sau: Kϕ = g(x, s)ϕ(s)ds ≈h g(x, x0 )ϕ(x0 ) n−1 + i=1 g(x, xi )ϕ(xi ) + 12 g(x, xn )ϕ(xn ) 34 Đặt ϕi = ϕ(xi ), fi = f (xi ), i = 0, n cho x nhận giá trị x0 , x1 , , x Khi đó, ta có hệ xấp xỉ:  n n−1    g(x, xi )ϕj + 21 g(x, xn )ϕn = f (x0 ) h g(x, x )ϕ +  0   j=1       h g(x, x )ϕ + n−1 g(x, x )ϕ + g(x, x )ϕ = f (x ) i j 0 n n j=1        n−1     g(x, xi )ϕj + 21 g(x, xn )ϕn = f (xn ) h g(x, x )ϕ + 0  j=1 Ta viết dạng ma trận:   ϕ0  ϕ1   K   =  ϕn   f0 f1   fn (3.4) hay Kϕ = f Trong K ma trận hệ số phương trình 3.3.3 Áp dụng chỉnh hóa thưa Để minh họa tính hiệu phương pháp chỉnh hóa thưa xem xét hoạt động giải thuật chương ta chọn nghiệm xác hàm g phương trình (3.2) sau: g(x, s) = x2 s + x, s, s ∈ 0, s ∈ / v = s = 3, 3, 3 Khi đó, liệu xác f (x) là: f (x) = Kϕ = x s + x sds = 2 x s ds + = xsds x(14x+54) 162 Áp dụng phương pháp chỉnh hóa thưa cho Bài tốn (3.3) dẫn đến toán cực tiểu Θ(v) := F (v) + αΦ (v) v∈Rn+1 (3.5) 35 n với F (¯ v ) = K v¯ − fi vΦ(¯ v) = |¯ vi |, i=1 đó, fi = f (xi ) liệu xấp xỉ f (Chúng ta lấy giữ liệu xấp xỉ với liệu xác) 3.3.4 Minh họa nghiệm số hội tụ Áp dụng giải thuật giảm Gradient giải thuật cải tiến Nesterov cho Bài toán (3.5) Khi đó, ta có chương trình Matlab sau đây: a) Chương trình Matlab giải thuật giảm Gradient n=100; h=(b-a)/n; p=a:h:b; N=size(p,2); A=zeros(N,N); F=zeros(N,1); gf = @(x, s)x2 ∗ s3 + s ∗ x3 ; f f = @(x)x2 ∗ (7 ∗ x + 5)/35; for i=1:N for j=1:N A(i,j)=gf(p(i),p(j)); end F(i)=ff(p(i)); end A=A*h; A(:,1)=A(:,1)/2; A(:,end)=A(:,end)/2; f=@(x) (A*x-F)’*(A*x-F); gradf=@(x) 2*A’*(A*x-F); eta = 1e-4; alpha = eta*ones(N,1); q=0.5; s1=1e-5;s2=1e5; maxiter=300; x0 = ones(N,1); solution1=[x0]; objfcn1=f(x0); objfcnt1 = objfcn1 + alpha’*abs(x0); gradfcn1 =gradf(x0); 36 for i = 1:maxiter obj1=[obj1 objfcnt1]; ok=1; while ok stemp = x0 - sn*gradfcn1; x1 = sign(stemp).*max(abs(stemp)-sn*alpha,0); objfcn2=f(x1); objfcnt2 = objfcn2 + alpha’*abs(x1); DL=objfcn1+gradfcn1’*(x1-x0)+(x1-x0)’*(x1-x0)/(2*sn); DL = DL + alpha’*abs(x1); if objf cnt2 > DL&(sn >= s1)&(sn = s1)&(sn