Dự thảo Tóm tắt Luận án Tiến sĩ Toán học: Một số phương pháp kết hợp giải hệ phương trình toán tử

ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN<br /> <br /> ĐẶNG VĂN HIẾU<br /> <br /> MỘT SỐ PHƯƠNG PHÁP KẾT HỢP<br /> GIẢI HỆ PHƯƠNG TRÌNH TOÁN TỬ<br /> <br /> Chuyên ngành: Toán ứng dụng<br /> Mã số: 62460112<br /> DỰ THẢO TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC<br /> <br /> Hà Nội - 2016<br /> <br /> Công trình được hoàn thành tại: Trường Đại học Khoa học Tự nhiên - Đại<br /> học Quốc gia Hà Nội<br /> <br /> Người hướng dẫn khoa học:<br /> GS. TSKH. Phạm Kỳ Anh<br /> <br /> Phản biện 1: ............................................<br /> Phản biện 2: ............................................<br /> Phản biện 3: ............................................<br /> <br /> Luận án sẽ được bảo vệ trước Hội đồng cấp Đại học Quốc gia chấm luận<br /> án tiến sĩ họp tại.............................................. vào hồi<br /> <br /> giờ<br /> <br /> năm<br /> <br /> Có thể tìm thấy luận án tại:<br /> - Thư viện Quốc gia Việt Nam<br /> - Trung tâm thông tin - Thư viện, Đại học Quốc gia Hà Nội<br /> <br /> ngày<br /> <br /> tháng<br /> <br /> MỞ ĐẦU<br /> Nhiều bài toán trong khoa học và kĩ thuật như bài toán khôi phục ảnh, bài toán xử lý tín hiệu, bài toán<br /> tối ưu, bài toán cân bằng v.v. dẫn tới giải bài toán chấp nhận lồi sau đây.<br /> Bài toán 0.1 (CFP - Convex Feasibility Problem). Cho Ci , i = 1, . . . , N là các tập con lồi đóng khác rỗng của<br /> không gian Hilbert H hoặc Banach X. Bài toán CFP được phát biểu như sau:<br /> Tìm điểm x ∗ sao cho x ∗ ∈ C :=<br /> <br /> N<br /> <br /> Ci .<br /> <br /> (1)<br /> <br /> i =1<br /> <br /> Dạng đơn giản nhất của bài toán CFP là tìm điểm chung của các tập lồi cho trước (dạng hiển). Khi<br /> đó, kĩ thuật phổ biến giải bài toán CFP là sử dụng phép chiếu lên các tập lồi. Một số phương pháp điển<br /> hình như phương pháp chiếu lặp tuần tự (xoay vòng), phương pháp chiếu lặp đồng thời (song song)<br /> hoặc phương pháp lặp khối. Tuy nhiên trong thực tế hầu hết các tập Ci được cho dưới dạng ẩn, tức<br /> chúng là nghiệm của các bài toán nào đó. Một ví dụ điển hình trong xử lý ảnh, chúng ta cần khôi phục<br /> hình ảnh ban đầu x từ các quan sát f i (chẳng hạn, hình chiếu hoặc các đại lượng vật lý khác liên quan<br /> tới ảnh x). Điều này có thể đưa về giải một hệ phương trình toán tử có dạng Fi ( x ) = f i , i = 1, . . . , N, khi<br /> đó Ci được cho dưới dạng ẩn là nghiệm của phương trình Fi ( x ) = f i .<br /> Trong luận án này, chúng tôi nghiên cứu bài toán chấp nhận lồi dạng tổng quát (GCFP - Generalized<br /> Convex Feasibility Problem). Bài toán GCFP được phát biểu như sau:<br /> Bài toán 0.2 (GCFP - Generalized Convex Feasibility Problem). Cho N bài toán P1 , P2 , . . . , P N trong không<br /> gian Hilbert H hoặc Banach X và các tập Ci trong Bài toán CFP (1) cho dưới dạng ẩn là tập nghiệm của N bài<br /> toán tương ứng Pi , i = 1, . . . , N. Bài toán GCFP cho N bài toán này là:<br /> Tìm điểm x ∗ là nghiệm chung của các bài toán P1 , P2 , . . . , P N .<br /> <br /> (2)<br /> <br /> Sau đây là một số dạng cơ bản của bài toán GCFP được nghiên cứu trong luận án này.<br /> 1. Giải hệ phương trình toán tử (SOE):<br /> Ai ( x ) := Fi ( x ) − f i = 0, x ∈ X, i = 1, 2 . . . , N,<br /> <br /> (3)<br /> <br /> trong đó Fi : X → Y là toán tử, f i ∈ Y và X, Y là các không gian Hilbert hoặc Banach. Khi đó, Pi là bài<br /> toán giải phương trình toán tử Ai ( x ) := Fi ( x ) − f i = 0 và Ci là tập nghiệm tương ứng của nó.<br /> 2. Tìm điểm bất động chung của một họ toán tử (CFPP): Cho C là một tập con lồi đóng và khác rỗng<br /> trong không gian Hilbert H hoặc Banach X và Si : C → C, i = 1, . . . , N là một họ hữu hạn các ánh xạ.<br /> Bài toán CFPP cho họ ánh xạ Si , i = 1, . . . , N là tìm x ∗ ∈ C sao cho:<br /> x ∗ ∈ F :=<br /> <br /> N<br /> <br /> F ( Si ) .<br /> <br /> (4)<br /> <br /> i =1<br /> <br /> Bài toán CFPP là trường hợp riêng của bài toán GCFP với Pi là bài toán tìm điểm bất động của ánh xạ<br /> Si và Ci = F (Si ) là tập điểm bất động của Si .<br /> 3. Nghiệm chung của các bất đẳng thức biến phân (CSVIP): Cho Ai : C → X, i = 1, . . . , N là các toán<br /> tử. Bài toán CSVIP cho họ các toán tử Ai , i = 1, . . . , N trên C là tìm x ∗ ∈ C sao cho:<br /> Ai ( x ∗ ), x − x ∗ ≥ 0, ∀ x ∈ C, i = 1, . . . , N.<br /> 1<br /> <br /> (5)<br /> <br /> Bài toán CSVIP là một dạng bài toán GCFP với Ci = V I ( Ai , C ) là tập nghiệm của bất đẳng thức biến<br /> phân cho toán tử Ai trên tập C.<br /> 4. Nghiệm chung của các bài toán cân bằng (CSEP): Cho f i : C × C → ℜ, i = 1, . . . , N là các song hàm.<br /> Bài toán CSEP cho họ các song hàm f i , i = 1, . . . , N trên C là tìm x ∗ ∈ C sao cho:<br /> f i ( x ∗ , y) ≥ 0, ∀y ∈ C, i = 1, . . . , N.<br /> <br /> (6)<br /> <br /> Bài toán CSEP cũng là một dạng của bài toán GCFP với Ci = EP( f i , C ) là tập nghiệm của bài toán cân<br /> bằng cho song hàm f i trên tập C.<br /> Ngoài các bài toán tìm nghiệm chung nêu trên, trong thực tế còn có nhiều bài toán dạng GCFP khác<br /> như: Bài toán tìm nghiệm chung hỗn hợp (tức là tìm nghiệm chung của nhiều họ bài toán với nhau) hoặc<br /> các bài toán tổng quát hơn, gọi là các bài toán tách, bao gồm bài toán chấp nhận tách, bài toán biến phân<br /> tách và bài toán cân bằng tách.<br /> Trong hai thập niên gần đây, các bài toán dạng GCFP (3) − (6) được quan tâm và nghiên cứu rộng<br /> rãi bởi nhiều nhà toán học. Phần lớn các thuật toán giải chúng là tuần tự (xoay vòng). Ý tưởng chung là<br /> sử dụng một thuật toán đã biết để xấp xỉ nghiệm tại mỗi bước cho một bài toán con và việc này được<br /> lặp một cách luân phiên xoay vòng qua các bài toán thành phần của hệ ban đầu. Đối với hệ phương<br /> trình toán tử SOE (3), nếu không đặt điều kiện gì thêm lên toán tử Fi thì bài toán giải hệ phương trình<br /> Ai ( x ) := Fi ( x ) − f i = 0, i = 1, . . . , N là đặt không chỉnh theo nghĩa nó không có lời giải duy nhất với<br /> mọi vế phải f i ∈ X (X ∗ ) hoặc lời giải không phụ thuộc liên tục vào dữ liệu ban đầu ( Fi , f i ). Do tính không<br /> ổn định của bài toán đặt không chỉnh nên ta cần chiến lược hiệu chỉnh bài toán. Ý tưởng của phương<br /> pháp hiệu chỉnh là thay bài toán ban đầu bằng một họ các bài toán đặt chỉnh mà nghiệm của chúng hội<br /> tụ về nghiệm của bài toán ban đầu khi tham số hiệu chỉnh dần tới 0. Hai phương pháp hiệu chỉnh phổ<br /> biến được sử dụng cho các bài toán đặt không chỉnh là: Phương pháp hiệu chỉnh Tikhonov và Phương pháp<br /> hiệu chỉnh Lavrentiev. Ngoài phương pháp hiệu chỉnh, các phương pháp chỉnh lặp cũng được sử dụng để<br /> giải các bài toán đặt không chỉnh. Ý tưởng của các phương pháp chỉnh lặp là kết hợp các phép lặp đã<br /> biết với kĩ thuật hiệu chỉnh. Một số phương pháp chỉnh lặp điển hình được kể đến như phương pháp<br /> chỉnh lặp bậc không và bậc một, phương pháp chiếu-lặp hiệu chỉnh (iterative-projection regularization<br /> method), phương pháp hàm phạt (penalty method), phương pháp giảm dư (residual method), phương<br /> pháp tựa nghiệm (quasi-solution method).<br /> Hệ phương trình SOE (3) có thể được thiết lập một cách tương đương với bài toán CFPP (4) cho họ<br /> hữu hạn các ánh xạ Ti , i = 1, . . . , N với Ti = x − Ai ( x ). Hai phương pháp lặp phổ biến cho bài toán FPP<br /> (Fixed Point Problem) được sử dụng trong luận án này là phương pháp lặp Mann và phương pháp lặp<br /> Halpern. Dựa trên hai phương pháp cơ bản này, chúng ta có thể thiết kế các thuật toán khác nhau cho<br /> bài toán CFPP (4), chẳng hạn, để giải bài toán CFPP (4) cho một họ các ánh xạ không giãn tương đối<br /> Ti : C → C, i = 1, . . . , N trong không gian Banach, năm 2011, Liu sử dụng thuật toán lặp Halpern và đề<br /> xuất phương pháp lai ghép tuần tự như sau: Chọn x0 ∈ C và<br /> <br />  y = J −1 (α Jx + (1 − α ) JT<br />  n<br /> n 0<br /> n<br /> <br /> n (mod) N x n ),<br /> <br /> <br /> <br />  C = {v ∈ C : φ(v, y ) ≤ α φ(v, x ) + (1 − α )φ(v, x )} ,<br /> n<br /> n<br /> n<br /> n<br /> n<br /> 0<br />  Q = {v ∈ C : Jx − Jx , x − v ≥ 0} ,<br />  n<br /> n n<br /> 0<br /> <br /> <br /> <br /> <br />  x<br /> n +1 = Π Cn ∩ Q n x0 , n ≥ 0,<br /> 2<br /> <br /> (7)<br /> <br /> trong đó J : X → X ∗ là ánh xạ đối ngẫu chuẩn tắc và ΠC là phép chiếu tổng quát lên tập C trong không<br /> gian Banach X.<br /> Bài toán bất đẳng thức biến phân (VIP - Variational Inequality Problem) là một trường hợp đặc biệt<br /> của bài toán cân bằng (EP - Equilibrium Problem). Phương pháp chiếu đơn giản nhất cho bài toán VIP<br /> là phương pháp chiếu đạo hàm (GM - Gradient Method), ở đó chỉ cần tìm một phép chiếu lên tập ràng<br /> buộc. Tuy nhiên, sự hội tụ (hội tụ yếu) của phương pháp này đòi hỏi toán tử là đơn điệu mạnh (hoặc đơn<br /> điệu mạnh ngược). Để vượt qua khó khăn đó, năm 1976, Korpelevich đã đề xuất phương pháp chiếu<br /> đạo hàm tăng cường (EGM - Extragradient Method) khi nghiên cứu bài toán điểm yên ngựa. Phương<br /> pháp EGM được thiết kế như sau:<br /> <br />  y = P ( x − λ A( x )),<br /> n<br /> n<br /> n<br /> C n<br />  x<br /> n +1 = PC ( x n − λn A ( y n )),<br /> <br /> (8)<br /> <br /> trong đó A : H → H là một toán tử và PC là phép chiếu metric lên C. Sự hội tụ của phương pháp EGM<br /> chỉ đòi hỏi tính liên tục Lipschitz và tính đơn điệu (hoặc giả đơn điệu) của toán tử A.<br /> Phương pháp điểm gần kề (PPM) cho bài toán EP bao gồm việc giải một bài toán cân bằng hiệu<br /> chỉnh (REP - Regularization Equilibrium Problem) trên mỗi bước lặp, nghĩa là, biết xn , xấp xỉ tiếp theo<br /> f<br /> <br /> f<br /> <br /> xn+1 = Tr ( xn ), trong đó r > 0 là tham số và Tr là giải thức của song hàm f xác định bởi<br /> f<br /> <br /> Tr ( x ) =<br /> <br /> u ∈ H : f (u, y) +<br /> <br /> 1<br /> y − u, u − x ≥ 0,<br /> r<br /> <br /> ∀y ∈ C , x ∈ H.<br /> <br /> (9)<br /> <br /> f<br /> <br /> Nếu f đơn điệu thì giải thức Tr là đơn điệu mạnh, không giãn và đơn trị. Nếu f là song hàm thuộc lớp<br /> f<br /> <br /> đơn điệu tổng quát hơn, chẳng hạn, giả đơn điệu thì Tr , nói chung, là không đơn trị, không đơn điệu<br /> mạnh. Do đó, phương pháp PPM không thể áp dụng trong trường hợp này. Năm 2008, Quoc và các cộng<br /> sự đã mở rộng phương pháp EGM cho các bài toán EP. Phương pháp EGM cho bài toán EP bao gồm<br /> việc giải hai bài toán tối ưu sau đây<br /> <br />  y = arg min{λ f ( x , y) + 1 || x − y||2 : y ∈ C },<br /> n<br /> n<br /> n<br /> n<br /> 2<br /> 1<br />  x<br /> = arg min{λ f (y , y) + || x − y||2 : y ∈ C }.<br /> n +1<br /> <br /> n<br /> <br /> n<br /> <br /> 2<br /> <br /> (10)<br /> <br /> n<br /> <br /> Ưu điểm của của phương pháp EGM là có thể sử dụng cho lớp các song hàm giả đơn điệu và hai bài<br /> toán tối ưu trên mỗi bước lặp có thể được giải dễ dàng hơn phương pháp PPM trong nhiều trường hợp.<br /> Trong những năm gần đây, cả hai phương pháp PPM và EGM được nghiên cứu sâu rộng bởi các nhà<br /> toán học trong và ngoài nước cả về lý thuyết và thuật toán<br /> Cùng với các bài toán tìm nghiệm chung, bài toán tìm nghiệm chung hỗn hợp cũng được quan tâm<br /> và nghiên cứu. Trong nhiều lĩnh vực của toán học ứng dụng như bài toán tối ưu đa mục tiêu, bài toán<br /> cân bằng Nash-Cournot trong kinh tế, hoặc bài toán tối ưu mà miền ràng buộc được biểu diễn dưới<br /> dạng giao của một họ hữu hạn các tập điểm bất động dẫn tới bài toán tìm nghiệm chung của hai hay<br /> nhiều hơn các bài toán EP, VIP hoặc FPP trong cùng một không gian hoặc hai không gian khác nhau<br /> (qua một ánh xạ tuyến tính). Dựa trên các phương pháp đã biết cho từng bài toán thành phần, các tác<br /> giả đã thiết kế chúng theo một trật tự nhất định và thu được thuật toán cho bài toán tìm nghiệm chung<br /> hỗn hợp. Chẳng hạn, để tìm nghiệm chung của bài toán CSEP cho các song hàm f i , i = 1, . . . , M, bài<br /> toán CSVIP cho các toán tử A j , j = 1, . . . , N và bài toán CFPP cho các ánh xạ không giãn Sk , k = 1, 2, . . .<br /> trong không gian Hilbert H, năm 2010, Saeidi đã sử dụng phương pháp điểm gần kề (PPM), phép chiếu<br /> 3<br /> <br />