Thuật toán mới xấp xỉ liên kết quán tính để giải bài toán cực tiểu lồi

- Trong vài thập kỷ gần đây, nhiều thuật toán tối ưu đã được phát triển để giải quyết các vấn đề trong xử lý tín hiệu và hình ảnh, xem [1, 3], trong đó là vấn đề phục chế ảnh được mô hình hóa như sau:.
- THUẬT TOÁN MỚI XẤP XỈ LIÊN KẾT QUÁN TÍNH ĐỂ GIẢI BÀI TOÁN CỰC TIỂU LỒI.
- TÓM TẮT: Trong bài báo này, tôi đề xuất và chứng minh sự hội tụ của thuật toán xấp xỉ liên kết quán tính đề giải bài toán cực tiểu lồi, một bài toán thường áp dụng trong xử lý phục chế ảnh.
- Đây là một phương pháp mới để giải quyết bài toán này.
- So với các thuật toán khác, thuật toán này không cần thực hiện phép chiếu, mà chỉ sử dụng các bước lặp tính toán.
- Tôi đã chứng minh sự hội tụ mạnh của dãy lặp về điểm bất động chung của giao một họ các ánh xạ không giãn và của một ánh xạ co.
- Các bước chứng minh được tiến hành trên không gian Hilbert thực H.
- Tổng quát, vấn đề (1.2) là giải quyết bài toán cực tiểu lồi sau đây:.
- Cho ánh xạ: f 1.
- Bài toán (1.2) trở thành tìm:.
- thì bài toán (1.3) có nghiệm duy nhất.
- Hơn nữa, nghiệm x * của bài toán (1.3) được xác định thông qua điểm bất động của ánh xạ Proximity [3] như sau:.
- (1.4) Trong đó c là một hằng số không âm bất kỳ (xem tài liệu [3], trang 11), I là ma trận đơn vị cấp n , prox cf 2 là ánh xạ proximity từ không gian Hilbert H vào.
- Để tìm được nghiệm x * của bài toán (1.3), thuật toán FBSA (Forward- Backward Splitting Algorithm) [4] đã được đề xuất:.
- c n thỏa mãn 0 c n 2.
- x n sẽ hội tụ về nghiệm x * của bài toán (1.3)..
- Thực chất, các ánh xạ T n.
- là các ánh xạ không giãn vì ánh xạ proximity là không giãn, do đó sẽ không giãn với các trường hợp 0 c n 2.
- xuất thuật toán ngưỡng co lặp (FISTA:.
- Các tác giả đã chứng minh được sự hội tụ mạnh của dãy.
- Như vậy vấn đề cực tiểu lồi trong bài toán phục chế ảnh thực chất chính là tìm điểm bất động chung của một họ ánh xạ không giãn T n.
- Như ta đã biết, phương pháp lặp của Mann được đề xuất đầu tiên vào năm 1953 [6] là phương pháp nổi tiếng để tìm nghiệm xấp xỉ cho điểm bất động của ánh xạ không giãn T.
- Nhưng phương pháp của Mann chỉ cho kết quả hội tụ yếu, để thu được kết quả hội tụ mạnh, ta cần kết hợp với phương pháp xấp xỉ liên kết như sau [5, 11].
- H là một ánh xạ co và.
- Cách xây dựng dãy lặp là một tổ hợp lồi của ánh xạ không giãn T và ánh xạ co g cho ta kết quả hội tụ mạnh về điểm bất động chung của cả hai ánh xạ nói trên..
- Trong bài báo này, tôi đề xuất một thuật toán mới (thuật toán 2.1) là sự kết hợp giữa.
- phương xấp xỉ liên kết và kỹ thuật quán tính để tìm điểm bất động chung trên giao của một họ các ánh xạ không giãn và một ánh xạ co.
- Tôi chứng minh sự hội tụ mạnh của dãy lặp về nghiệm của bài toán, kết quả chứng minh trong không gian Hilbert thực.
- Cuối cùng, tôi đã áp dụng thuật toán 2.1 vào bài toán cực tiểu lồi thông qua cách xây dựng thuật toán 3.1..
- •Ánh xạ T H.
- ii, Ánh xạ co nếu T là liên tục Lipchitz với hệ số L và L <.
- iii, Ánh xạ không giãn nếu T là liên tục Lipchitz với L = 1.
- •Tập điểm bất động của ánh xạ T H.
- •Dãy các ánh xạ { T H n.
- Thuật toán và sự hội tụ.
- Thuật toán được xây dựng trên các giả thuyết sau:.
- H } là họ các ánh xạ không giãn..
- H : là ánh xạ co với hệ số k .
- Thuật toán 2.1:.
- Định lý 2.1 (về sự hội tụ của dãy lặp.
- x n trong thuật toán 2.1 hội tụ mạnh về nghiệm x.
- nếu các tham số trong thuật toán thỏa mãn điều kiện sau:.
- Để chứng minh sự hội tụ của dãy.
- Bổ đề 2.1 [10]: Cho x y H.
- 0,1 , ta có các tính chất sau:.
- Bổ đề 2.2 [8]: Cho.
- a n thỏa mãn : liminf ( n i 1 n i ) 0.
- thì ta có: lim n a n 0.
- Kết quả chứng minh sự hội tụ:.
- T n là họ các ánh xạ không giãn, theo tính chất của ánh xạ không giãn thì Fix T.
- là ánh xạ co, khi đó theo nguyên lý ánh xạ co Banach, tồn tại duy nhất điểm x * ∈Γ để x.
- Ta chứng minh.
- Từ (2.2) ta có:.
- Khi đó ta có:.
- Từ (2.1) và (C3) ta có: n n n 1 0.
- Theo quy nạp thì ta có:.
- (2.8) Từ bổ đề 2.1(i) và ta có.
- Bước 3 : Ta chỉ ra sự hội tụ của dãy.
- Ta áp dụng bổ đề 2.2 với.
- Từ (2.9) ta có bất đẳng thức sau : a n + 1.
- a n i của dãy.
- a n thỏa mãn liminf ( n i 1 n i ) 0.
- theo (C2) và (2.10) ta có.
- limsup 1 '.lim.
- Kết hợp điều này với (C1) ta có : lim i T w n i.
- Kết hợp (C1) và (C2) ta có : lim i.
- (2.12) Như vậy từ (2.11) và (2.12) ta có : z T z n i − n i.
- z n i j p của dãy.
- z n i j thỏa mãn.
- z n i j p hội tụ yếu về y H.
- Z của họ các ánh xạ.
- nên ta có.
- Như vậy, áp dụng bổ đề 2.2, dãy.
- a n hội tụ mạnh về 0 , hay x n → x * khi n.
- Định lý đã được chứng minh..
- Áp dụng thuật toán vào bài toán cực tiểu lồi.
- Bây giờ, ta áp dụng thuật toán 2.1 vào bài toán cực tiểu của tổng hai hàm lồi.
- n là một ánh xạ co..
- Thuật toán 3.1.
- x n trong thuật toán 3.1 hội tụ mạnh về nghiệm x.
- Để chứng minh định lý 3.1, trước hết ta có bổ đề sau:.
- Bổ đề 3.1 [7].
- H là ánh xạ không giãn thì I T − là nửa đóng tại 0 với.
- I là ánh xạ đồng nhất.
- hội tụ yếu về x trong không gian Hilbert H , và nếu dãy x T x n.
- n hội tụ mạnh về 0 thì x Fix T.
- Bổ đề 3.2 [2]: Cho hai hàm số:.
- Chứng minh định lý 3.2:.
- Khi đó ta có T n và T là các ánh xạ không giãn, và.
- u n hội tụ yếu về u thì tồn tại dãy con.
- u n hội tụ mạnh về u.
- Theo bổ đề 3.2, ta có.
- Do tính chất nửa đóng tại 0 của ánh xạ I T.
- ta có.
- Theo chứng minh của thuật toán 2.1, dãy.
- x n sẽ hội tụ mạnh về.
- Định lý được chứng minh..
- Kết luận : Bài báo đã đưa ra thuật toán mới cho việc tìm điểm bất động chung của một họ các ánh xạ không giãn và một ánh xạ co, áp dụng cho bài toán tìm cực tiểu lồi.
- Bài báo đã chứng minh sự hội tụ mạnh về nghiệm x * của dãy lặp được xây dựng trong thuật toán.
- Với cách xây dựng dãy lặp là sự kết hợp của phương pháp xấp xỉ liên kết và phương pháp quán tính, trong thuật toán đã không cần sử dụng phép chiếu, do đó hi vọng sẽ giảm nhẹ cho các bước tính toán trên máy tính

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt