zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Thạc sĩ - Tiến sĩ - Cao học

Phương pháp đối ngẫu trong bài toán biến phân khôi phục tín hiệu

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

Báo xấu

61
lượt xem 3
download

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

Luận văn được trình bày thành 3 chương. Chương 1 trình bày những kiến thức cơ bản về giải tích lồi, toán tử proximity và thuật toán tách tiến lùi. Chương 2 trình bày phương pháp đối ngẫu trong các bài toán biến phân khôi phục tín hiệu. Chương 3 trình bày những ứng dụng của phương pháp đối ngẫu trong các bài toán khôi phục tín hiệu.

Chủ đề:

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

Lưu

Nội dung Text: Phương pháp đối ngẫu trong bài toán biến phân khôi phục tín hiệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐỖ KHẮC HUẤN PHƯƠNG PHÁP ĐỐI NGẪU TRONG BÀI TOÁN BIẾN PHÂN KHÔI PHỤC TÍN HIỆU LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐỖ KHẮC HUẤN PHƯƠNG PHÁP ĐỐI NGẪU TRONG BÀI TOÁN BIẾN PHÂN KHÔI PHỤC TÍN HIỆU Chuyên ngành: Toán học tính toán Mã số: 60.46.30 LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: GS.TSKH. ĐINH DŨNG Hà Nội - 2011
Mục lục Lời cảm ơn iii Giới thiệu 1 1 Các kiến thức chuẩn bị 7 1.1 Các công cụ giải tích lồi . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 Hàm nửa liên tục dưới . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.4 Vi phân mạnh, vi phân yếu . . . . . . . . . . . . . . . . . . . . 9 1.1.5 Hàm liên hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.6 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.7 Toán tử không giãn chặt . . . . . . . . . . . . . . . . . . . . . 12 1.2 Thuật toán tách tiến lùi . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.1 Toán tử proximity . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.2 Các ví dụ về toán tử proximity . . . . . . . . . . . . . . . . . . 14 1.2.3 Thuật toán tách tiến lùi . . . . . . . . . . . . . . . . . . . . . . 18 2 Phương pháp đối ngẫu trong các bài toán biến phân khôi phục tín hiệu 21 2.1 Đối ngẫu Fenchel- Moreau- Rockafellar . . . . . . . . . . . . . . . . . . 21 2.2 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 Sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3 Ứng dụng trong các bài toán khôi phục tín hiệu 31 3.1 Xấp xỉ tốt nhất chấp nhận được . . . . . . . . . . . . . . . . . . . . . 31 i
MỤC LỤC 3.2 Xấp xỉ tốt nhất mềm chấp nhận được . . . . . . . . . . . . . . . . . . . 37 3.3 Khử nhiễu theo từ điển . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4 Khử nhiễu với các hàm giá . . . . . . . . . . . . . . . . . . . . . . . . 47 Kết luận 53 Bảng ký hiệu 54 Tài liệu tham khảo 55 Chỉ dẫn 59 ii
Lời cảm ơn Đầu tiên, tác giả xin được gửi lời cảm ơn sâu sắc đến người thầy, người hướng dẫn khoa học của mình, GS.TSKH. Đinh Dũng, người đã đưa ra đề tài, luôn quan tâm và tận tình hướng dẫn trong suốt quá trình nghiên cứu của tác giả. Đồng thời tác giả cũng chân thành cảm ơn các thầy cô trong khoa Toán - Cơ - Tin học, phòng Sau đại học, Ban giám hiệu Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, đã tận tình giảng dạy, hướng dẫn trong thời gian học tập tại trường, đã tạo mọi điều kiện cho tác giả về tài liệu và thủ tục hành chính để tác giả hoàn thành bản luận văn này. Tác giả cũng chân thành cảm ơn Ban giám hiệu, tổ Toán trường THPT Sơn Tây đã tạo mọi điều kiện thuận lợi nhất để tác giả có thế hoàn thành khóa học. Tác giả cũng gửi lời cảm ơn đến bạn bè, đặc biệt là bạn bè trong nhóm Toán học tính toán 08-10, đã động viên và cổ vũ rất nhiều trong suốt thời gian vừa qua. Do thời gian và trình độ còn hạn chế, chắc chắn bản luận văn không thể tránh khỏi những thiếu sót, tác giả rất mong nhận được những ý kiến đóng góp quý báu của các thầy cô và bạn bè đồng nghiệp, tác giả xin chân thành cảm ơn! Hà Nội, tháng 02 năm 2011 Học viên Đỗ Khắc Huấn iii
Giới thiệu Trong tối ưu lồi, lí thuyết đối ngẫu nhiều lúc có thể dẫn đến các phương pháp giải bài toán đối ngẫu đơn giản và hiệu quả hơn là việc giải trực tiếp bài toán ban đầu. Trong luận văn này, chúng ta áp dụng phương pháp đối ngẫu cho các bài toán biến phân phức hợp nảy sinh trong khôi phục tín hiệu. Những bài toán này không dễ giải với các phương pháp trực tiếp, nhưng thông qua việc áp dụng phương pháp đối ngẫu Fenchel - Moreau - Rockafellar có thể giải chúng bằng thuật toán tách tiến lùi [18]. Chúng ta sẽ trình bày một thuật toán được đề xuất trong [14], nó đồng thời xây dựng được một dãy hội tụ yếu đến nghiệm của bài toán đối ngẫu và một dãy hội tụ mạnh đến nghiệm của bài toán ban đầu. Trải qua nhiều năm, một số cấu trúc đã được hình thành nhằm hợp nhất các phương pháp giải tích và các phương pháp giải số đối với các bài toán khôi phục tín hiệu. Từ năm 1978 Yonla [40] đã chỉ ra rằng một số bài toán khôi phục tín hiệu có một đặc điểm chung là đều chứa một cấu trúc hình học đơn giản và có thể qui được về dạng bài toán tối ưu trong một không gian Hilbert H như sau: tìm một tín hiệu x trong một không gian véctơ con đóng C trong H, sao cho khoảng cách từ x tới tín hiệu z là nhỏ nhất, biết rằng ảnh của x lên một không gian véctơ con đóng V là r. Điều này dẫn đến giải bài toán biến phân 1 minimize kx − zk2 , (1) x∈C 2 PV x=r trong đó PV kí hiệu là phép chiếu lên V . Các bài toán khôi phục tín hiệu trong không gian Hilbert đã được nghiên cứu bởi nhiều tác giả khác nhau. Chẳng hạn, năm 1965, Levi [26] đã nghiên cứu bài toán cực tiểu hóa tín hiệu x, có giải tần hữu hạn và có năng lượng nhỏ nhất thông qua N phép đo tuyến tính. Trong không gian Hilbert H = L2 (R), 1
Giới thiệu bài toán biến phân này có dạng 1 minimize kxk2 , (2) x∈C 2 hx|s1 i=ρ1 .. . hx|sN i=ρN trong đó C là không gian con của không gian các tín hiệu có giải tần bị chặn, (si )1≤i≤N ∈ HN là các tín hiệu đo, và (ρi )1≤i≤N ∈ RN là các phép đo. Trong [33], Potter và Arun đã nhận xét rằng: với một tập con lồi đóng C Bài toán (2) xuất hiện trong nhiều bài toán khác nhau, từ việc đánh giá phổ [3, 36], chụp cắt lớp [27] đến các bài toán ngược [4]. Họ đã dùng phương pháp đối ngẫu để giải nó, dẫn đến thuật toán. Mệnh đề 0.0.1. [33, Định lí 1 và 3] Đặt r = (ρi )1≤i≤N và L : H → RN : x 7→ N ksi k2 ≤ 1 và r nằm trong tập các điểm P (hx | si i)1≤i≤N , cho γ ∈]0, 2[ . Giả sử rằng i=1 trong tương đối của L(C). Đặt ω0 ∈ RN và (∀n ∈ N) ωn+1 = ωn + γ(r − LPC L∗ ωn ), (3) N trong đó L∗ : RN → H : (vi )1≤i≤N 7→ P vi si là toán tử liên hợp của L. Khi đó dãy i=1 (ωn )n∈N hội tụ đến một điểm ω sao cho LPC L∗ ω = r và PC L∗ ω là nghiệm của Bài toán (2). Phương pháp đối ngẫu đóng một vai trò trọng tâm trong lí thuyết tối ưu hóa hàm lồi [21, 31, 35, 41] và nó đã được sử dụng một cách rộng rãi với những mục đích khác nhau trong các bài toán khôi phục tín hiệu, chúng ta có thể tìm thấy điều này trong các bài báo [3, 5, 8, 10, 18, 20, 22, 23, 24, 25, 39]. Những khía cạnh khác của lí thuyết đối ngẫu trong xử lí ảnh đã được nghiên cứu trong [6]. Dạng đối ngẫu thích hợp nhất đối với các bài toán biến phân khôi phục tín hiệu là đối ngẫu Fenchel-Moreau-Rockafellar, có liên quan đến việc cực tiểu hóa bài toán ban đầu với việc cực tiểu hóa bài toán đối ngẫu với các hàm liên hợp và toán tử liên hợp với các hàm và toán tử trong bài toán ban đầu. Nhìn chung, phương pháp đối ngẫu đã mở rộng các lớp bài toán ban đầu. Hơn nữa, việc giải bài toán đối ngẫu còn có thể giúp ta tìm được nghiệm của bài toán ban đầu từ bất kì nghiệm đối ngẫu nào. Với các giả thiết như Mệnh đề 0.0.1 Bài toán (2) sẽ rất khó giải, nhưng nếu C đơn giản, bài toán đối ngẫu có thể giải được một cách hiệu quả và nghiệm của bài toán ban đầu có thể được khôi phục dễ dàng. Nguyên lí 2
Giới thiệu đối ngẫu này cũng được áp dụng trong các bài toán khôi phục tín hiệu khác. Chẳng hạn, nó có thể áp dụng cho bài toán biến phân có nhiễu 1 2 minimize g(Lx) + kx − zk , (4) x∈H 2 trong đó z là một tín hiệu quan sát được nhưng bị nhiễu của một tín hiệu lí tưởng, L là một toán tử tuyến tính bị chặn từ H vào một không gian Hilbert G và g : G →]−∞, +∞] là một hàm lồi chính thường nửa liên tục dưới. Một hướng phát triển nổi tiếng là thuật toán biến phân toàn phần giải số bài toán khôi phục ảnh có nhiễu được đưa ra trong [8] và được hoàn chỉnh trong [9]. Mục đích chính của bản luận văn là trình bày phương pháp đối ngẫu để giải các Bài toán (1) và (2), cải tiến các thuật toán hiện có, chuẩn hóa các kĩ thuật đối ngẫu trong các bài toán khôi phục tín hiệu và mở rộng những ứng dụng to lớn của chúng. Các kết quả này đã được công bố chủ yếu trong bài báo [14] và một phần trong bài báo [18]. Điều cần nhấn mạnh là các lớp bài toán biến phân mà chúng ta nghiên cứu phải thỏa mãn các yêu cầu sau đây: (a) Chúng bao trùm các bài toán cực tiểu ở trên. (b) Chúng không dễ giải trực tiếp nhưng lại thích hợp cho phương pháp đối ngẫu Fenchel-Moreau- Rockafellar, phương pháp có thể giải được một cách chắc chắn theo nghĩa xây dựng một thuật toán khả thi, thuật toán này tạo ra hai dãy lặp: một dãy hội tụ yếu đến nghiệm của bài toán đối ngẫu và một dãy hội tụ mạnh đến nghiệm của bài toán ban đầu. Các thuật toán này không chứa các chương trình con, những chương trình không đảm bảo hội tụ sau một số hữu hạn bước lặp, điều đó có thể làm khuyếch đại sai số sau mỗi bước lặp. (c) Các thuật toán này cho phép xây dựng nghiệm của bài toán ban đầu từ một nghiệm bất kì của bài toán đối ngẫu. Bài toán 0.0.2. (Bài toán ban đầu) Cho H và G là các không gian Hilbert thực, z ∈ H, r ∈ G, cho f : H →] − ∞, +∞] và g : G →] − ∞, +∞] là các hàm lồi nửa liên tục dưới và cho L : H → G là một toán tử tuyến tính khác không, bị chặn sao cho điều kiện r ∈ sri (L(dom f ) − dom g) (5) 3
Giới thiệu được thỏa mãn. Bài toán là 1 2 minimize f (x) + g(Lx − r) + kx − zk . (6) x∈H 2 Trước hết, chúng ta có một số bình luận về bài toán này. Liên quan đến Điều kiện (a), khi f = 0 thì Bài toán (6) trở thành Bài toán (4). Nếu cho f và g tương ứng là các hàm chỉ (xem (1.5) ) của các tập con lồi đóng C ⊂ H và D ⊂ G thì Bài toán (6) được qui về bài toán xấp xỉ tốt nhất 1 minimize kx − zk2 . (7) x∈C 2 Lx−r∈D Nếu trong phương trình trên ta chọn C là một không gian véctơ con đóng của H và D = {0} thì Bài toán (1) tương ứng với trường hợp H = G và L = PV , trong khi đó Bài toán (2) sẽ ứng với trường hợp G = RN , L : H → RN : x 7→ (hx | si i)1≤i≤N , r = (ρi )1≤i≤N và z = 0. Như trong Chương 3 sẽ trình bày thì Bài toán 0.0.2 là sự mở rộng của các bài toán khôi phục tín hiệu. Liên quan đến Điều kiện (b), một câu hỏi tự nhiên được đặt ra là Bài toán (6) có thể giải được theo các thuật toán đã có hay không ? Chúng ta hãy đặt h : H →] − ∞, +∞] : x 7→ f (x) + g(Lx − r). (8) Do tính chất của các hàm f và g mà ta giả thiết ở trên thì h cũng là một hàm lồi chính thường nửa liên tục dưới. Do đó toán tử proximity của h (ta sẽ định nghĩa ở phần sau) 1 2 proxh : x 7→ argmin h(y) + kx − yk y∈H 2 tồn tại và duy nhất. Từ đó Bài toán 0.0.2 có nghiệm duy nhất, và nghiệm đó được viết dưới dạng x = proxh z. (9) Thật khó tính ra một cách cụ thể toán tử proximity của một hàm hợp h như trên, do đó một trong các phương pháp được sử dụng là tách biểu thức trong Bài toán (6) để xây dựng proxh z. Bài toán (6) được viết lại dưới dạng minimize {f1 (x) + f2 (x)} , (10) x∈H trong đó 1 f1 : x 7→ f (x) + kx − zk2 và f2 : x 7→ g(Lx − r) (11) 2 4
Giới thiệu là các hàm lồi nửa liên tục dưới từ H vào ] − ∞, +∞]. Để giải quyết Bài toán (10) chúng ta có thể sử dụng thuật toán tách tiến lùi được trình bày trong [18] theo lược đồ sau:  x = ∇f2 (xn ) + a2,n  1  n+ 2 (12) xn+1 = xn + λn proxγn f1 xn − γn xn+ 1 + a1,n − xn ,   2 trong đó yêu cầu hàm f2 khả vi Lipschitz trên H; λn > 0; γn > 0 và a1,n , a2,n tương ứng là các mô phỏng sai số của các toán tử proximity của f1 và gradient của f2 . Các kết quả cụ thể về sự hội tụ của dãy lặp (xn )n∈N trong thuật toán trên sẽ được trình bày kĩ hơn trong Định lí 1.2.21. Khi hàm f2 không thỏa mãn điều kiện khả vi Lipschitz trên H thì ta có thể giải Bài toán (10) bằng cách sử dụng thuật toán Douglas-Rachford [16].  xn+ 1 = proxγf2 xn + a2,n   2 (13) xn+1 = xn + λn proxγf1 (2xn+ 1 − xn ) + a1,n − xn+ 1 ,   2 2 trong đó λn > 0, γ > 0 và a1,n , a2,n tương ứng là mô phỏng sai số của các toán tử proximity của f1 và f2 (xem [16, Định lí 20], các kết quả hội tụ chính xác và các ứng dụng của nó có thể tham khảo thêm trong [12]). Tuy nhiên phương pháp này yêu cầu toán tử proximity của hàm hợp f2 trong Phương trình (11) phải được tính toán cụ thể với sai số xác định. Trong trường hợp tổng quát điều này rất khó thực hiện được, như trong Ví dụ 1.2.6 toán tử proxf2 được tính thông qua toán tử proxg với giả thiết nghiêm ngặt L ◦ L∗ = κId, trong đó κ > 0. Với yêu cầu khắt khe như vậy thì thật khó áp dụng phương pháp này cho Bài toán 0.0.2 và nhiều bài toán quan trọng khác khác. Trong [2] có trình bày một phương pháp thích hợp cho các bài toán 1 2 minimize h1 (x) + h2 (x) + kx − zk , (14) x∈H 2 trong đó h1 và h2 là các hàm lồi nửa liên tục dưới từ H vào ] − ∞, +∞] sao cho dom h1 ∩dom h2 6= ∅. Bài toán (14) trùng với Bài toán (6) khi h1 = f và h2 = g(Lx−r). Để giải Bài toán (14) chúng ta có thể sử dụng thuật toán Dykstra-thuật toán tương tự 5
Giới thiệu được trình bày trong [2] như sau:      Khởi tạo    y 0 = z       q0 = 0            p0 = 0   For n = 0, 1 · · · (15)     xn = proxh2 (yn + qn )       qn+1 = yn + qn − xn            yn+1 = proxh1 (xn + pn )     n+1 = xn + pn − yn+1 p Thuật toán này yêu cầu các toán tử proximity của các hàm h1 và h2 được tính toán ở dạng hiển. Cũng giống như thuật toán Douglas-Rachford thì yêu cầu nãy cũng rất khó thực hiện với những hàm hợp f2 . Như vậy những kĩ thuật tách hiện có thật khó áp dụng với Bài toán 0.0.2. Chính vì lẽ đó, chúng ta sẽ xây dựng một đối ngẫu Frechel-Moreau-Rockafellar, thông qua đối ngẫu này để giải Bài toán 0.0.2, trong đó chúng ta có thể ước lượng được các toán tử proxf và proxg với sai số xác định. Luận văn được trình bày thành 3 chương như sau: • Chương 1 trình bày những kiến thức cơ bản về giải tích lồi, toán tử proximity và thuật toán tách tiến lùi. • Chương 2 trình bày phương pháp đối ngẫu trong các bài toán biến phân khôi phục tín hiệu. • Chương 3 trình bày những ứng dụng của phương pháp đối ngẫu trong các bài toán khôi phục tín hiệu. 6
Chương 1 Các kiến thức chuẩn bị 1.1 Các công cụ giải tích lồi Luận văn sử dụng các kiến thức về giải tích lồi. Để tiện cho việc xem xét các bài toán trong các chương tiếp theo, chúng tôi sẽ trình bày các khái niệm dưới đây trong các không gian Hilbert thực, chi tiết độc giả có thể tham khảo trong cuốn sách [41]. 1.1.1 Tập lồi Cho H và G là các không gian Hilbert thực. Với x, y ∈ H ta kí hiệu [x, y] := {(1 − λ)x + λy | λ ∈ [0, 1]} , [x, y[:= {(1 − λ)x + λy | λ ∈ [0, 1[} , và ]x, y[:= {(1 − λ)x + λy | λ ∈]0, 1[} tương ứng gọi là đoạn thẳng đóng, nửa đoạn thẳng đóng và đoạn thẳng mở. Một tập con C khác rỗng của H được gọi là lồi nếu [x, y] ⊂ C với mọi x, y ∈ C và bao nón của C là [ coneC = {λx | x ∈ C}. (1.1) λ>0 Nếu C là một tập lồi đóng, hình chiếu của một điểm x ∈ H lên C là một điểm duy nhất PC x ∈ C sao cho PC x = argminkξ − xk. Ta kí hiệu intC là các điểm trong của ξ∈C C, spanC là bao tuyến tính của C, spanC là bao đóng của spanC. Nhân của C kí hiệu là coreC = {x ∈ C | cone(C − x) = H}, miền trong tương đối mạnh của C là sriC = {x ∈ C|cone(C − x) = span(C − x)} ; (1.2) 7
Chương 1. Các kiến thức chuẩn bị và miền trong tương đối của C là riC = {x ∈ C|cone(C − x) = span(C − x)}. Ta có intC ⊂ coreC ⊂ sriC ⊂ riC ⊂ C. (1.3) Miền trong tương đối mạnh là sự mở rộng của khái niệm miền trong tương đối. Sự mở rộng này đặc biệt quan trọng trong giải tích lồi với các tập không có miền trong tương đối trong các không gian vô hạn chiều. 1.1.2 Hàm lồi Kí hiệu R = R ∪ {−∞, +∞}, với mỗi hàm f : H → R và số λ ∈ R, dom f := {x ∈ H | f (x) < +∞}, epi f := {(x, t) ∈ H × R | f (x) ≤ t} và epis f := {(x, t)|f (x) < t} tương ứng được gọi là miền hữu dụng, trên đồ thị và trên đồ thị chặt của f . Hàm f được gọi là chính thường nếu dom f 6= ∅ và f (x) > −∞, với mọi x ∈ H. Hàm f được gọi là lồi nếu ∀x, y ∈ H, x 6= y, ∀λ ∈]0, 1[: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y). (1.4) Nếu đẳng thức trên đúng với ” < ” thay vì ” ≤ ” khi đó ta nói rằng hàm f là lồi chặt . Tương tự như vậy ta nói rằng hàm f là lõm (lõm chặt) nếu hàm −f là lồi (lồi chặt) Định lý 1.1.1. [41, Định lí 2.1.1] Cho f : H → R. Các mệnh đề dưới đây là tương đương (i) f là lồi (lồi chặt); (ii) hàm ϕx,y : R → R, ϕx,y (t) := f ((1 − t)x + ty) là lồi (lồi chặt) với mọi x, y ∈ H(x 6= y); (iii) dom f là tập lồi và ∀x, y ∈ dom f, ∀λ ∈]0, 1[: f (λx + (1 − λ)y ≤ λf (x) + (1 − λ)f (y)) ( đánh giá trên sẽ trở nên chặt khi x 6= y) (iv) ∀n ∈ N, ∀ x1 , · · · , xn ∈ H, ∀λ1 , · · · , λn ∈]0, 1[, λ1 + · · · + λn = 1 : f (λ1 x1 + · · · + λn xn ) ≤ λ1 f (x1 ) + · · · + λn f (xn ) (đánh giá trên sẽ trở nên chặt khi x1 , · · · , xn không bằng nhau); 8
Chương 1. Các kiến thức chuẩn bị (v) epif là một tập con lồi của H × R; (vi) epis f là một tập con lồi chặt của H × R. Một số ví dụ đơn giản về hàm lồi Cho C là một tập con lồi đóng khác rỗng của H. Hàm chỉ tiêu của C là  0, nếu x ∈ C,  ιC : x 7→ (1.5) +∞, nếu x ∈/ C.  hàm khoảng cách của C là dC : H → [0, +∞[: x 7→ inf kx − yk, (1.6) y∈C hàm giá của C là σC : H →] − ∞, +∞] : u 7→ suphx|yi. (1.7) x∈C 1.1.3 Hàm nửa liên tục dưới Định nghĩa 1.1.2. Một hàm số f : C 7→ R được gọi là nửa liên tục dưới tại một điểm x0 ∈ C nếu lim f (x) ≥ f (x0 ) ∀x ∈ C, x→x0 hay nói cách khác: với mỗi > 0 có một số δ > 0 sao cho x ∈ C, kx − x0 k ≤ δ thì f (x) > f (x0 ) − . Hàm f được gọi là nửa liên tục dưới trên C nếu nó là nửa liên tục dưới tại mọi điểm x ∈ C. Định lý 1.1.3. Một hàm lồi trên C là nửa liên tục dưới trên C khi và chỉ khi với mỗi số thực µ, tập mức {x ∈ C | f (x) ≤ µ} là đóng. 1.1.4 Vi phân mạnh, vi phân yếu Cho Ω là một tập mở khác rỗng trong H, hàm F : Ω → G được gọi là khả vi theo nghĩa Fréchet ( khả vi mạnh ) tại x0 ∈ Ω nếu: ∀h ∈ H (khk
Chương 1. Các kiến thức chuẩn bị trong đó A ∈ L(H, G) là không gian các toán tử tuyến tính liên tục từ H vào G và kω(x0 , h)k → 0 khi h → θ, Ah được gọi là vi phân mạnh của F tại x0 và được kí hiệu khk là dF (x0 , h). Do đó ta có dF (x0 , h) = Ah. Toán tử A được gọi là đạo hàm Fréchet của F tại x0 , kí hiệu là F 0 (x0 ). Vi phân yếu của F tại x0 là biểu thức d F (x0 + th) − F (x0 ) dFw (x0 , h) := F (x0 + th) |t=0 = lim ∀h ∈ H, h cố định . dt t→0 t Nếu dFw (x0 , h) = Bh, B ∈ L(H, G) thì B được gọi là đạo hàm yếu ( theo nghĩa Gateaux) của F tại điểm x0 và được kí hiệu là Fw0 . Do đó ta cũng có Fw0 (x0 )h = Bh. Nếu F khả vi mạnh tại x0 thì F khả vi yếu tại x0 và Fw0 (x0 ) = F 0 (x0 ). Nếu phiếm hàm f : H → R khả vi tại mọi x thì f (x + th) − f (x) f 0 (x)h = lim = ∇f (x).h, t→0 t và f 0 ∈ L (X , R) = H∗ , ở đây H∗ là phiếm hàm tuyến tính liên tục trên H. Định lý 1.1.4. [41, Định lí 2.1.11] Cho D ⊂ (H, k · k) là một tập mở, lồi khác rỗng, f : D → R là một phiếm hàm khả vi theo nghĩa Gateaux trên D. Khi đó các mệnh đề sau là tương đương (i) f là lồi; (ii) ∀x, y ∈ D : hy − x | ∇f (x)i ≤ f (y) − f (x); (iii) ∀x, y ∈ D : hy − x | ∇f (y) − ∇f (x)i ≥ 0; (iv) ∀x ∈ D, ∀u ∈ X : ∇2 f (x)(u, u) ≥ 0 ( khi f là khả vi hai lần theo nghĩa Gateaux trên D). 1.1.5 Hàm liên hợp Kí hiệu Γ0 (H) là lớp các hàm lồi chính thường nửa liên tục dưới từ H vào ] − ∞, +∞]. Cho ϕ ∈ Γ0 (H), hàm liên hợp của ϕ là hàm ϕ∗ ∈ Γ0 (H) xác định bởi (∀u ∈ H) ϕ∗ (u) = sup {hx|ui − ϕ(x)} . (1.8) x∈H 10
Chương 1. Các kiến thức chuẩn bị Định lý 1.1.5. [41, Định lí 2.3.1] Cho f, g : H → R, khi đó (i) Bất đẳng thức Young- Fenchel dưới đây là đúng: ∀x ∈ H, ∀u ∈ H : f (x) + f ∗ (x∗ ) ≥ hx | ui, (ii) Nếu f ≤ g thì g ∗ ≤ f ∗ , (iii) Nếu g(x) = f (x + x0 ) với x ∈ H, thì g ∗ (x∗ ) = f ∗ (x∗ ) − hx0 | x∗ i với mỗi x∗ ∈ H. Định lí Fenchel - Moreau phát biểu rằng ϕ∗∗ = ϕ. Chẳng hạn, hàm liên hợp của hàm chỉ tiêu của một tập lồi đóng khác rỗng của C, tức là hàm ιC là hàm giá của C, tức là ι∗C = σC : u 7→ suphx|ui. (1.9) x∈C Ngược lại σC∗ = ι∗∗ C = ιC . (1.10) Bổ đề 1.1.6. [7, Bổ đề 2.2] Cho C là một tập con lồi đóng khác rỗng của H, φ : R →] − ∞, +∞] là một hàm chẵn và tăng trên [0, +∞[, đặt ϕ = φ ◦ dC . Khi đó ϕ∗ = σC + φ∗ ◦ k · k. 1.1.6 Dưới vi phân Dưới vi phân của ϕ ∈ Γ0 (H) là toán tử đa trị ∂ϕ : H → 2H : x 7→ {u ∈ H|(∀y ∈ H)hy − x | ui + ϕ(x) ≤ ϕ(y)} , (1.11) hoặc tương đương ∂ϕ(x) = {u ∈ H | ϕ(x) + ϕ∗ (u) = hx | ui} . (1.12) Ta có (∀(x, u) ∈ H × H) u ∈ ∂ϕ(x) ⇔ x ∈ ∂ϕ∗ (u). (1.13) Theo Định luật Fermat ta có (∀x ∈ H) x ∈ Argmin ϕ = {x ∈ dom ϕ | (∀y ∈ H) ϕ(x) ≤ ϕ(y)} ⇔ 0 ∈ ∂ϕ(x). (1.14) Hơn nữa, nếu ϕ khả vi theo nghĩa Gateaux tại x thì ∂ϕ(x) = {∇ϕ(x)} . (1.15) 11
Chương 1. Các kiến thức chuẩn bị Bổ đề 1.1.7. [41, Định lí 2.8.3] Cho ϕ ∈ Γ0 (H), ψ ∈ Γ0 (G), và M ∈ B(H, G) sao cho 0 ∈ sri (M (dom ϕ) − dom ψ) . Khi đó ∂(ϕ + ψ ◦ M ) = ∂ϕ + M ∗ ◦ (∂ψ) ◦ M. 1.1.7 Toán tử không giãn chặt Một toán tử T : H → H được gọi là toán tử không giãn nếu ∀(x, y) ∈ H2 kT x − T yk ≤ kx − yk. (1.16) Một toán tử T : H → H là không giãn chặt nếu nó thỏa mãn một trong các điều kiện sau: (i) (∀(x, y) ∈ H2 ) kT x − T yk2 ≤ hT x − T y | x − yi, (ii) (∀(x, y) ∈ H2 ) kT x − T yk ≤ kx − yk2 − k (Id − T ) x − (Id − T ) yk2 . Có thể dễ dàng suy ra ngay rằng một toán tử không giãn chặt thì cũng là một toán tử không giãn. 1.2 Thuật toán tách tiến lùi Như trong phần Giới thiệu đã đề cập, Bài toán (10) có thể giải được nhờ thuật toán tách tiến lùi. Trong mục này chúng ta sẽ trình bày các tính chất cơ bản của bài toán (10), sự hội tụ của thuật toán tách tiến lùi. Công cụ chính mà chúng ta sẽ sử dụng là toán tử proximity, toán tử đã được giới thiệu bởi Moreau trong những năm 1960. 1.2.1 Toán tử proximity Bao Moreau của một hàm ϕ ∈ Γ0 (H) là hàm lồi liên tục 1 2 e : H → R : x 7→ min ϕ(y) + kx − yk . ϕ (1.17) y∈H 2 12
Chương 1. Các kiến thức chuẩn bị kx − yk2 Với mỗi x ∈ H, hàm y 7→ ϕ(y) + đạt giá trị nhỏ nhất tại duy nhất một điểm, 2 điểm đó được kí hiệu là proxϕ x. Toán tử proximity ϕ được định nghĩa bởi 1 2 proxϕ : H → H : x 7→ argmin ϕ(y) + kx − yk (1.18) y∈H 2 và được đặc trưng bởi hệ thức (∀ (x, p) ∈ H × H) p = proxϕ x ⇔ x − p ∈ ∂ϕ(p). (1.19) Bổ đề 1.2.1. [30] Cho ϕ ∈ Γ0 (H). Các mệnh đề dưới đây là đúng (i) (∀x ∈ H) (∀y ∈ H) k proxϕ x − proxϕ yk2 ≤ hx − y | proxϕ x − proxϕ yi. (ii) (∀x ∈ H) (∀y ∈ H) k proxϕ x − proxϕ yk ≤ kx − yk. k·k (iii) ϕ f∗ = e+ϕ . 2 f∗ khả vi theo nghĩa Fréchet và ∇ϕ (iv) ϕ f∗ = proxϕ = Id − proxϕ∗ . kx − ωk Bổ đề 1.2.2. Cho ψ ∈ Γ0 (H), và đặt ϕ : x 7→ ψ(x) + . Khi đó 2 kωk ϕ∗ : u 7→ ψ f∗ (u + ω) − . 2 Chứng minh. Theo định nghĩa hàm liên hợp ta có ϕ∗ (u) = sup {hx | ui − ϕ(x)} x∈H 1 2 = sup hx | ui − ψ(x) − kx − ωk x∈H 2 1 2 = − inf ψ(x) + kx − ωk − hx | ui x∈H 2 1 2 2 = − inf ψ(x) + kxk − 2hx | ωi + kωk − hx | ui x∈H 2 1 2 1 2 = − inf ψ(x) + kxk − hx | u + ωi + kωk x∈H 2 2 1 2 2 1 2 1 2 = − inf ψ(x) + kxk − 2hx | u + ωi + ku + ωk − ku + ωk + kωk x∈H 2 2 2 1 1 = − inf ψ(x) + kx − (u + ω)k2 − kuk2 − hu | ωi x∈H 2 2 1 2 1 2 = kuk + hu | ωi − inf ψ(x) + kx − (u + ω)k 2 x∈H 2 1 1 = ku + ωk2 − kωk2 − ψ(u e + ω). 2 2 13
Chương 1. Các kiến thức chuẩn bị Mặt khác theo Bổ đề 1.2.1(iii) ta có ψ(u f∗ (u + ω) = 1 ku + ωk2 e + ω) + ψ 2 nên ta có f∗ (u + ω) − 1 kωk2 . ϕ∗ (u) = ψ 2 Bổ đề 1.2.3. [18, Bổ đề 2.10] Cho ϕ ∈ Γ0 (H), x ∈ H và γ ∈]0, +∞[. Khi đó x = proxγϕ x + γ proxγ −1 ϕ∗ (γ −1 x). 1.2.2 Các ví dụ về toán tử proximity Ví dụ 1.2.4. Cho C là một tập con lồi đóng khác rỗng của H. Khi đó các mệnh đề dưới đây là đúng. (i) Nếu ϕ = ιC thì proxϕ = PC [30, Ví dụ 3.d]. (ii) Nếu ϕ = σC thì proxϕ = Id − PC [18, Ví dụ 2.17]. d2C (iii) [18, Ví dụ 2.14] Nếu ϕ = thì (2α) (∀x ∈ H) proxϕ x = x + (1 − α)−1 (PC x − x). k · k2 − d2C (iv) [18, Bổ đề 2.7] Đặt ϕ = . Khi đó 2α proxϕ x = x − α−1 PC α(α + 1)− 1 . (∀x ∈ H) k · k2 Ví dụ 1.2.5. [18, Bổ đề 2.7] Cho ψ ∈ Γ0 (H) và đặt ϕ = − ψ. e Khi đó 2 ϕ ∈ Γ0 (H) và x (∀x ∈ H) proxϕ x = x − prox ψ ( ). 2 2 Ví dụ 1.2.6. [16, Mệnh đề 11] Cho G là một không gian Hilbert thực, ψ ∈ Γ0 (H), M ∈ B(H, G) và ϕ = ψ ◦ M. Giả sử rằng M ◦ M ∗ = κId với κ ∈]0, +∞[. Khi đó ϕ ∈ Γ0 (H) và 1 proxϕ = Id + M ∗ ◦ proxκψ −Id ◦ M. (1.20) κ 14
Chương 1. Các kiến thức chuẩn bị Ví dụ 1.2.7. [11, Mệnh đề 2.10 và Nhận xét 3.2 (ii)] Đặt X ϕ : H →] − ∞, +∞] : x 7→ φκ (hx | oκ i) , (1.21) κ∈K trong đó : (i) ∅ = 6 K ⊂ N; (ii) (ok )k∈K là một cơ sở trực truẩn của H; (iii) (φk )k∈K là các hàm trong Γ0 (R); (iv) Hoặc K là hữu hạn hoặc tồn tại một tập con L của K sao cho : (a) K\L là hữu hạn; (b) (∀k ∈ L) φk ≥ φk (0) = 0. Khi đó ϕ ∈ Γ0 (H) và X (∀x ∈ H) proxϕ x = proxφk hx | ok i ok . (1.22) k∈K Ví dụ 1.2.8. [7, Mệnh đề 2.1] Cho C là một tập con lồi đóng khác rỗng của H, và φ ∈ Γ0 (H) là một hàm chẵn, đặt ϕ = φ ◦ dC . Khi đó ϕ ∈ Γ0 (H). Hơn nữa, proxϕ = PC nếu φ = ι{0} + η với η ∈ R, ngoài ra prox∗φ dC (x)  x + (PC x − x), nếu dC (x) > max ∂φ(0);  dC (x)     (∀x ∈ H) proxϕ x = PC x, nếu x ∈ / C và dC (x) ≤ max ∂φ(0);     nếu x ∈ C.  x, (1.23) Nhận xét 1.2.9. Nếu trong Ví dụ 1.2.8 ta cho C = {0} và ψ 6= ι{0} + η(η ∈ R). Khi đó dC (x) = kxk và PC x = 0, hơn nữa sử dụng Bổ đề 1.2.1(iv) ta được proxφ∗ = Id−proxφ . Do đó proxφ∗ dC (x) Id − proxφ (kxk) x+ (PC x − x) = x + (−x) dC (x) kxk kxk − proxφ kxk =x+ (−x) kxk proxφ kxk =x+ 1− (−x) kxk proxφ kxk = x. kxk 15

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.26: Bộ 320 Luận Văn Thạc Sĩ Y Học

320 tài liệu

1253 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.