Luận án tiến sĩ Toán học: Một số phương pháp giải bài toán chấp nhận tách suy rộng liên quan đến bài toán cân bằng

Chia sẻ: Trần Văn Ha | Ngày: | Loại File: PDF | Số trang:91

Thêm vào BST

Báo xấu

40
lượt xem 4
download

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

Luận án đã thu được kết quả sau: Đề xuất được một thuật toán chiếu kết hợp phép lặp MannKrasnoselskii giải bài toán chấp nhận tách liên quan đến bài toán cân bằng và bài toán tối ưu. Chúng tôi thu được sự hội tụ cho thuật toán, cụ thể là chúng tôi đã chỉ ra với các giả thiết thông thường thì thuật toán hội tụ khi bài toán có nghiệm và nếu bài toán không có nghiệm thì thuật toán có thể không hội tụ.

Chủ đề:

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

Lưu

Nội dung Text: Luận án tiến sĩ Toán học: Một số phương pháp giải bài toán chấp nhận tách suy rộng liên quan đến bài toán cân bằng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM NGUYỄN THỊ THANH HUYỀN MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CHẤP NHẬN TÁCH SUY RỘNG LIÊN QUAN ĐẾN BÀI TOÁN CÂN BẰNG LUẬN ÁN TIẾN SĨ TOÁN HỌC THÁI NGUYÊN–2020
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM NGUYỄN THỊ THANH HUYỀN MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CHẤP NHẬN TÁCH SUY RỘNG LIÊN QUAN ĐẾN BÀI TOÁN CÂN BẰNG Chuyên ngành: Toán Giải tích Mã số: 946 01 02 Người hướng dẫn khoa học: GS. TSKH. LÊ DŨNG MƯU THÁI NGUYÊN–2020
i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi, được hoàn thành dưới sự hướng dẫn của GS. TSKH. Lê Dũng Mưu. Các kết quả viết chung với tác giả khác đã được sự nhất trí của đồng tác giả khi đưa vào luận án. Các kết quả nêu trong luận án là những kết quả mới và chưa từng được ai công bố trong các công trình nào khác. Tác giả Nguyễn Thị Thanh Huyền
ii LỜI CẢM ƠN Lời đầu tiên, tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy tôi GS. TSKH. Lê Dũng Mưu. Thầy đã tận tình hướng dẫn tôi từ khi tôi làm luận văn thạc sĩ và bây giờ là luận án tiến sĩ. Thầy đã tận tình chỉ dạy tôi phương pháp nghiên cứu, cách phát hiện và giải quyết vấn đề, đồng thời Thầy luôn động viên, khích lệ để tôi hoàn thành luận án này. Từ tận đáy lòng, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới Thầy của tôi. Tôi xin được trân trọng gửi lời cảm ơn tới Ban Giám hiệu Trường Đại học Sư phạm, Ban Chủ nhiệm Khoa Toán, cùng các thầy, các cô tham gia giảng dạy, tạo điều kiện thuận lợi để tôi học tập và nghiên cứu. Đồng thời tôi cũng chân thành cảm ơn các anh chị em nghiên cứu sinh, bạn bè đồng nghiệp tại xêmina nghiên cứu sinh khoa Toán Trường Đại học Sư phạm đã động viên, trao đổi và đóng góp những ý kiến quý báu cho tôi trong suốt quá trình học tập, nghiên cứu và hoàn thành luận án. Tôi xin cảm ơn Ban giám hiệu trường Đại học Khoa học, Đại học Thái Nguyên đã cho tôi cơ hội được đi học tập và nghiên cứu. Tôi xin cảm ơn Ban chủ nhiệm khoa Toán - Tin và các thầy cô Khoa Toán - Tin, đã tạo mọi điều kiện thu xếp công việc thuận lợi cho tôi trong suốt thời gian tôi đi làm nghiên cứu sinh. Tôi xin gửi lời cảm ơn sâu sắc tới các thầy, các anh chị và các bạn trong nhóm xêmina liên cơ quan Đại học Khoa học Tự nhiên, Đại học Bách Khoa Hà Nội, Viện Toán học, Đại học Thăng Long. Xêmina đã tạo cho tôi động lực trong nghiên cứu khoa học và sự gắn bó với môi trường nghiên cứu. Đặc biệt, tôi xin gửi lời cảm ơn chân thành tới GS. TSKH. Phạm Kỳ Anh. Thầy đã luôn động viên tôi, tạo điều kiện cho tôi báo cáo và chỉ dạy tôi nhiều kiến thức hữu ích. Tôi cũng xin gửi lời cảm ơn sâu sắc tới TS. Lê Hải Yến, người đã luôn quan tâm, chỉ bảo tôi trên con đường khoa học. Cuối cùng, tôi muốn bày tỏ lòng biết ơn sâu sắc tới những người thân
iii trong gia đình, đặc biệt là bố mẹ hai bên, chồng và các con. Những người đã luôn động viên, chia sẻ mọi khó khăn cùng tôi suốt những năm tháng qua để tôi có thể hoàn thành luận án này. Tác giả Nguyễn Thị Thanh Huyền
iv Mục lục Lời cam đoan i Lời cảm ơn iii Mục lục iii Bảng ký hiệu v Bảng chữ viết tắt viii Mở đầu 1 Chương 1 Một số kiến thức chuẩn bị 12 1.1. Các khái niệm và kết quả cơ bản . . . . . . . . . . . . . 12 1.2. Bài toán cân bằng và một số bài toán liên quan . . . . . 18 1.3. Bài toán chấp nhận tách . . . . . . . . . . . . . . . . . . 21 1.4. Một số phương pháp lặp cơ bản tìm điểm bất động . . . 22 1.5. Các kết quả bổ trợ . . . . . . . . . . . . . . . . . . . . . 23 1.6. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Chương 2 Thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii giải bài toán chấp nhận tách 26 2.1. Mô tả bài toán và sự hội tụ . . . . . . . . . . . . . . . . 26 2.2. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . 40 2.3. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
v Chương 3 Thuật toán dưới đạo hàm giải bài toán chấp nhận tách phi tuyến và ứng dụng cho mô hình cân bằng Nash có ràng buộc 44 3.1. Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . 45 3.2. Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . 46 3.3. Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . 60 3.4. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Kết luận 69 Tài liệu tham khảo 72
vi
vii Bảng ký hiệu R tập các số thực R++ tập các số thực dương Rn không gian véctơ Euclid thực n−chiều hx, yi tích vô hướng của hai véctơ x và y kxk chuẩn Euclid của véctơ x trong không gian Rn xn → x Dãy {xn } hội tụ mạnh tới x PC (x) Phép chiếu của điểm x lên tập C PC (x) = argminy∈C ky − xk NC (x) Nón pháp tuyến ngoài của tập lồi C tại x ∂f (x) Dưới vi phân của hàm f tại x ∂ ǫ f (x) ǫ-dưới vi phân của hàm f tại x ∂2 f (x, x) Dưới vi phân theo biến thứ hai của song hàm f (x, .) tại x ∂2ǫ f (x, x) ǫ-dưới vi phân theo biến thứ hai của song hàm f tại x argminC f Tập các điểm cực tiểu của hàm f trên tập C proxλg Ánh xạ gần kề của hàm lồi g với tham số λ > 0 AT ma trận chuyển vị của ma trận A EP (C, f ) Bài toán cân bằng của song hàm f trên tập C S(C, f ) Tập nghiệm của bài toán cân bằng song hàm f trên tập C ∅ Tập rỗng ✷ Kết thúc chứng minh
viii Bảng chữ viết tắt (CFP) Bài toán chấp nhận lồi (EP) Bài toán cân bằng (SEO) Bài toán chấp nhận tách với C là tập nghiệm của bài toán EP và Q là tập nghiệm của bài toán tối ưu (SFP) Bài toán chấp nhận tách (NSEP) Bài toán chấp nhận tách phi tuyến
1 Mở đầu Một trong những lớp bài toán quan trọng thu hút được sự quan tâm nghiên cứu của nhiều nhà khoa học trong nước cũng như trên thế giới đó là bài toán cân bằng. Thuật ngữ cân bằng được sử dụng rộng rãi trong nhiều ngữ cảnh khoa học và kĩ thuật. Trong Vật lý, trạng thái cân bằng của một hệ, theo thuật ngữ cơ học cổ điển, xảy ra khi hợp lực tác động lên hệ bằng không và trạng thái này được duy trì trong một khoảng thời gian dài. Trong Hóa học, vấn đề cân bằng cũng được đề cập trong các phản ứng hóa học. Trong Sinh học, cân bằng sinh thái là trạng thái ổn định tự nhiên của hệ sinh thái, hướng tới sự thích nghi cao nhất với điều kiện sống, trạng thái này thường xảy ra khi tương quan lực lượng giữa con mồi và thú săn mồi trong hệ sinh thái đó có tỉ lệ tương đồng với nhau. Trong kinh tế, sự cân bằng xảy ra, ví dụ như khi lượng cung bằng lượng cầu. Trạng thái cân bằng là trạng thái mà con người và vạn vật đều có xu hướng tiến đến. Bài toán cân bằng, còn được gọi là bất đẳng thức Ky Fan, được nghiên cứu trong luận án này có thể phát biểu một cách đơn giản như sau: Cho C là một tập lồi, đóng, khác rỗng trong không gian Rn và f : C × C → R là một song hàm thỏa mãn f (x, x) = 0, với mọi x ∈ C (song hàm có tính chất này thường được gọi là song hàm cân bằng). Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. EP(C, f ) Bất đẳng thức trên được H. Nikaido và K. Isoda [81] sử dụng lần đầu tiên vào năm 1955 trong khi nghiên cứu trò chơi không hợp tác. Năm 1972, Ky Fan [62] gọi là bất đẳng thức minimax và ông đã đưa ra các
2 kết quả về sự tồn tại nghiệm của bài toán này. Thuật ngữ bài toán cân bằng được sử dụng lần đầu tiên bởi L.D. Muu và W. Oettli [77] năm 1992. Bài toán cân bằng bao hàm nhiều lớp bài toán quen thuộc như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động Kakutani, bài toán cân bằng Nash trong lý thuyết trò chơi không hợp tác, bài toán cân bằng véctơ, bài toán cân bằng tập... Các bài toán này, một số được trình bày bởi L.D. Muu và W. Oettli [77], sau đó được E. Blum và W. Oettli giới thiệu thêm trong công trình [21] năm 1994, gần đây được giới thiệu khá đầy đủ trong cuốn sách chuyên khảo của G. Bigi và các cộng sự [26]. Ngoài ra, bài toán cân bằng còn được mở rộng sang các bài toán cân bằng véctơ, bài toán cân bằng tập bởi nhiều tác giả trong các tài liệu [42, 49, 70, 73, 87] và cuốn chuyên khảo [55]. Trong vài chục năm trở lại đây, bài toán cân bằng được nghiên cứu cả về tính chất định tính và phương pháp giải. Về tính chất định tính, sự tồn tại nghiệm của bài toán cân bằng được khảo sát trong các công trình [23, 24, 25, 41, 52, 53, 57] và các tài liệu tham khảo trong đó. Sự ổn định nghiệm, cấu trúc của tập nghiệm được nghiên cứu trong các tài liệu [11, 12, 13, 76]. Hướng nghiên cứu về phương pháp giải có thể nói là được quan tâm nhiều hơn, chẳng hạn trong [6, 7, 8, 9, 16, 35, 38, 39, 40, 41, 52, 53, 57, 63, 64, 65, 78, 79, 83, 88, 89, 92]. Dễ thấy rằng nếu ta định nghĩa ánh xạ S bằng cách, với mỗi x ∈ C, đặt S(x) := argmin{f (x, y) : y ∈ C} thì từ điều kiện f (x, x) = 0 với mọi x ∈ C, ta có mọi điểm bất động của ánh xạ S đều là nghiệm của bài toán cân bằng. Ngược lại với các giả thiết thông thường là f (x, .) lồi, khả dưới vi phân, thỏa mãn một tính chất chính quy nào đó, thì mọi điểm bất động của ánh xạ S đều là nghiệm của bài toán cân bằng. Qua đây ta thấy việc tìm nghiệm của bài toán cân bằng có thể quy về việc tìm điểm bất động. Tuy nhiên việc tìm điểm bất động của một ánh xạ, ngay trong trường hợp điểm bất
3 động theo định lý Brouwer đã có từ hơn một thế kỷ, nhưng cho đến nay vẫn chưa có thuật toán hiệu quả cho bài toán này. Hơn nữa, như đã nêu, bài toán cân bằng bao hàm nhiều bài toán quan trọng, khó giải như là những trường hợp riêng, nên không hy vọng có một thuật toán hiệu quả để giải bài toán cân bằng tổng quát. Vì thế người ta đã nghiên cứu các phương pháp giải bài toán cân bằng với những giả thiết nhất định. Các giả thiết này có thể là một tính chất đơn điệu nào đó như tính giả đơn điệu, đơn điệu, đơn điệu chặt, đơn điệu mạnh và tính lồi, khả dưới vi phân theo biến thứ hai của song hàm f . Một số tiếp cận về phương pháp giải bài toán cân bằng với các giả thiết nêu trên có thể được kể đến như sau: • Phương pháp điểm bất động cho ánh xạ co [71, 79], hoặc không giãn, không giãn suy rộng [10, 15] dựa trên nguyên lý bài toán phụ. Nguyên lý bài toán phụ cho bài toán cân bằng EP(C,f) liên quan đến bài toán cân bằng dưới đây, kí hiệu là EP(C, fα ) Tìm x ∈ C : fα (x, y) := f (x, y) + αM (x, y) ≥ 0, ∀y ∈ C, trong đó α > 0, và M (được gọi là hàm khoảng cách Bregman) có tính chất (M1) Xác định trên toàn không gian, hàm M (x, .) lồi mạnh, khả vi và ∇M (x, x) = 0 với mọi x ∈ C. Nguyên lý bài toán phụ được G. Cohen [32, 33] đề xuất lần đầu tiên cho bài toán tối ưu và bài toán bất đẳng thức biến phân lần lượt vào các năm 1980 và 1988. Đến năm 2003, nguyên lý này đã được mở rộng cho bài toán cân bằng bởi G. Mastroeni [71]. Nếu ký hiệu s(x) là nghiệm duy nhất của bài toán tối ưu lồi miny∈C fα (x, y), thì với các giả thiết về tính đơn điệu mạnh, hoặc giả đơn điệu mạnh, cộng thêm tính chất kiểu Lipschitz của song hàm f , thì s là ánh xạ co, khi tham số α được chọn thích hợp (phụ thuộc vào hệ số đơn điệu (giả đơn điệu) mạnh và hằng số Lipschitz
4 của f [41, 79]). Trong trường hợp f là đơn điệu mạnh ngược, còn gọi là tự bức (co-coercive), thì s là ánh xạ không giãn [10], còn khi f là giả đơn điệu thì trong [15] các tác giả đã xây dựng một s ánh xạ tựa không giãn (quasinonexpansive) có tập điểm bất động trùng với tập nghiệm của bài toán cân bằng. Bên cạnh các ánh xạ nghiệm dựa trên tập nghiệm của các bài toán quy hoạch lồi đã nêu ở trên, một ánh xạ khác, được gọi là ánh xạ Combettes, dựa trên phương pháp hiệu chỉnh gần kề, được định nghĩa bởi R(x) := {y ∈ C : f (x, y) + rhx − x0 , y − xi ≥ 0 ∀y ∈ C}. P.L. Combettes [34] đã chỉ ra, khi f đơn điệu và có thêm một vài tính chất liên tục thông thường, thì với mọi r > 0, ánh xạ R xác định khắp nơi, không giãn và tập điểm bất động của ánh xạ này trùng với tập nghiệm của bài toán cân bằng EP(C, f ). Chú ý rằng ánh xạ R này được xác định qua việc giải một bài toán cân bằng đơn điệu mạnh, trong khi ánh xạ nghiệm s nói trên được xác định bằng việc giải một bài toán quy hoạch lồi mạnh. • Phương pháp hàm đánh giá (gap function). Ý tưởng chính của phương pháp hàm đánh giá là chuyển việc giải bài toán cân bằng về bài toán tối ưu. Hai loại hàm đánh giá cơ bản là hàm đánh giá Auslender và hàm đánh giá Fukushima được định nghĩa lần lượt như sau [72]: gA (x) = − min{f (x, y) : y ∈ C} gF (x) = − min{f (x, y) + αM (x, y) : y ∈ C}, trong đó α > 0 và song hàm M có tính chất (M1). Như đã biết, x ∈ C, gA (x) = 0, hoặc gF (x) = 0 khi và chỉ khi x là nghiệm của bài toán EP(C, f ). Chú ý rằng bài toán quy hoạch lồi xác định gA (x) có thể không tồn tại nghiệm, và nếu có nghiệm thì nghiệm có thể
5 không duy nhất. Tuy nhiên bài toán xác định gF (x), do M (x, .) lồi mạnh, nên luôn tồn tại duy nhất nghiệm. Ngoài các hàm đánh giá ở trên người ta còn dùng hàm đánh giá cho bài toán cân bằng Minty sau (còn được gọi là bài toán đối ngẫu) [83]: tìm x∗ ∈ C : f (y, x∗ ) ≤ 0, ∀y ∈ C. M EP (C, f ) Các hàm đánh giá không ràng buộc (D-gap function) cũng được sử dụng để thu được các bài toán tối ưu không ràng buộc tương đương với bài toán cân bằng. Các phương pháp của quy hoạch toán học, như phương pháp hướng giảm, đã được dùng để cực tiểu hàm đánh giá, qua đó thu được nghiệm của bài toán cân bằng, xem chẳng hạn G. Mastroeni [71], và T.D. Quoc [83] và tài liệu trích dẫn ở đó. • Phương pháp hiệu chỉnh Tikhonov và phương pháp điểm gần kề. Các phương pháp này nhằm mục đích chuyển việc giải bài toán đặt không chỉnh, ví dụ các bài toán không duy nhất nghiệm, và/hoặc nghiệm không phụ thuộc liên tục vào các dữ kiện ban đầu về việc giải các bài toán đặt chỉnh. Để bảo đảm tính duy nhất nghiệm, người ta thường dùng một song hàm hiệu chỉnh và một tham số hiệu chỉnh để xây dựng bài toán phụ có duy nhất nghiệm phụ thuộc tham số hiệu chỉnh, và nghiệm duy nhất này sẽ hội tụ đến một nghiệm của bài toán ban đầu, khi tham số hiệu chỉnh tiến tới giá trị nhất định. Các phương pháp hiệu chỉnh này đã được sử dụng một cách hiệu quả cho bài toán tối ưu, bất đẳng thức biến phân, phương trình toán tử, bao hàm thức đơn điệu (xem [85, 93]) và gần đây cho bài toán cân bằng đơn điệu [75], giả đơn điệu [38, 66]. Trong phương pháp hiệu chỉnh Tikhonov bài toán hiệu chỉnh, với hàm hiệu chỉnh khoảng cách, được cho như sau: fT (x, y) := f (x, y) + ǫhx − xg , y − xi, trong đó ǫ > 0 là tham số hiệu chỉnh, còn xg đóng vai trò như lời giải dự đoán. Trong phương pháp điểm gần kề, điểm dự đoán xg
6 thay đổi ở mỗi bước lặp k và hàm hiệu chỉnh có dạng fP (x, y) := f (x, y) + chx − xk , y − xi, với c > 0. Với giả thiết f đơn điệu trên C, thì fT và fP đơn điệu mạnh trên C. Do đó, với các giả thiết thông thường về tính liên tục của song hàm, bài toán cân bằng hiệu chỉnh EP(C, fT ) và EP(C, fP ) có duy nhất nghiệm phụ thuộc vào các tham số hiệu chỉnh và hội tụ đến một nghiệm của bài toán ban đầu khi ǫ tiến dần đến 0, đối với hiệu chỉnh Tikhonov, còn đối với hiệu chỉnh điểm gần kề thì c tiến về một số hữu hạn. Chú ý rằng chỉ với giả thiết giả đơn điệu thì nghiệm của các bài toán hiệu chỉnh có thể không duy nhất. Tuy nhiên các kết quả trong [38, 66] đã chỉ ra rằng bất kỳ một quỹ đạo nghiệm nào của các bài toán hiệu chỉnh cũng hội tụ về một nghiệm của bài toán ban đầu, hơn nữa các tác giả ở đây đã đưa ra các thuật toán để tìm nghiệm đó dựa trên kỹ thuật của tối ưu hai cấp (bilevel optimization). • Phương pháp đạo hàm và đạo hàm tăng cường (extragradient method). Phương pháp đạo hàm cơ bản cho bài toán cân bằng có thể không hội tụ, ngay cả khi song hàm f là đơn điệu. Do đó, năm 1997, S. Flam và A. Antipin [45] đã dùng phương pháp đạo hàm tăng cường với hàm khoảng cách Bregman cho bài toán cân bằng với tập chấp nhận được là tập lồi compac trong không gian Rn. Năm 2011, N. Langenberg [67] mở rộng kết quả của Flam và Antipin, xét tập chấp nhận được là không bị chặn. Sau đó, nhiều tác giả đã dùng phương pháp đạo hàm tăng cường giải bài toán cân bằng với các giả thiết khác nhau đặt lên song hàm f . Trong phương pháp đạo hàm tăng cường [84], ở mỗi bước lặp k, phải giải hai bài toán tối ưu α xk = argmin{f (xk , y) + ky − xk k2 : y ∈ C}; 2 α xk+1 = argmin{f (xk , y) + ky − xk k2 : y ∈ C}. 2
7 Với các giả thiết thông thường, dãy điểm lặp xác định như trên sẽ hội tụ về một nghiệm của bài toán EP(C, f ). Trong trường hợp bài toán bất đẳng thức biến phân, các bài toán tối ưu này trở về bài toán tìm hình chiếu. Đối với bài toán cân bằng có tính chất mạnh hơn đơn điệu, như đơn điệu mạnh, giả đơn điệu mạnh, đơn điệu mạnh ngược, para-đơn điệu (paramonotone), thì chỉ cần dùng phương pháp đạo hàm cơ bản [51, 88] là thuật toán hội tụ. Một số thuật toán dựa trên phương pháp đạo hàm cơ bản và đạo hàm tăng cường cũng đã được đề xuất để bảo đảm sự hội tụ mạnh và nâng cao sự hiệu quả của thuật toán, người ta đã thay phép chiếu thứ hai lên tập ràng buộc bằng việc chiếu lên một siêu phẳng, hoặc tách riêng song hàm f bằng tổng của hai hoặc nhiều song hàm v.v... Các thuật toán này có thể xem trong các luận án Tiến sĩ của Bùi Văn Định [2], Trịnh Ngọc Hải [3], Phạm Gia Hưng [4]. Một bài toán khác liên quan nhiều đến luận án này là bài toán chấp nhận tách (Split feasibility problem). Bài toán chấp nhận tách được Y. Censor và T. Elfving [28] giới thiệu lần đầu tiên vào năm 1994 cho mô hình bài toán ngược. Sau đó được C. Byrne [27] ứng dụng vào năm 2002 cho bài toán phục hồi và tái tạo hình ảnh y tế. Gần đây, bài toán này còn được Y. Censor [29] ứng dụng trong mô hình điều khiển cường độ xạ trị trong điều trị ung thư. Trong không gian hữu hạn chiều, bài toán chấp nhận tách có thể mô tả như sau: Cho C và Q là các tập lồi khác rỗng trong không gian Rn và Rm tương ứng, và A : Rn → Rm là toán tử tuyến tính (được gọi là toán tử chuyển). Bài toán chấp nhận tách được phát biểu: Tìm x ∈ C sao cho Ax ∈ Q. (SFP). Trong trường hợp hai không gian là trùng nhau và A là toán tử đồng nhất, thì bài toán chấp nhận tách trở về bài toán chấp nhận lồi (convex feasibility problem) là tìm x ∈ C ∩ D. Kí hiệu Γ là tập nghiệm của bài
8 toán chấp nhận tách (SFP), Γ = {x ∈ C : Ax ∈ Q} = C ∩ A−1 Q, thì do C, Q là các tập lồi đóng, nên Γ là tập lồi, đóng và là giao của hai tập lồi đóng C và A−1 Q. Như vậy bài toán chấp nhận tách có thể xem như một trường hợp đặc biệt của bài toán chấp nhận lồi. Trong những năm gần đây, việc giải bài toán chấp nhận tách được nhiều tác giả quan tâm nghiên cứu, đặc biệt là trong trường hợp C và/hoặc Q được cho dưới dạng ẩn như là tập nghiệm của các bài toán nào đó, ví dụ tập điểm bất động của ánh xạ không giãn hoặc ánh xạ không giãn suy rộng, tập nghiệm của bài toán tối ưu lồi, bài toán bất đẳng thức biến phân, và tổng quát hơn là tập nghiệm của bài toán cân bằng. Trong những trường hợp này, bài toán sẽ gọi là bài toán chấp nhận tách suy rộng (generalized split feasibility problem). Bài toán chấp nhận tách cũng đã được nhiều người nghiên cứu (xem, chẳng hạn luận án Tiến sĩ của Trần Việt Anh và tài liệu tham khảo ở đó). Có hai cách tiếp cận cơ bản để giải bài toán chấp nhận tách. Cách tiếp cận thứ nhất dựa trên các phương pháp chiếu (lần lượt hoặc song song). Cách tiếp cận thứ hai là dựa trên ý tưởng chuyển bài toán chấp nhận tách về bài toán tối ưu. Các thuật toán chiếu lấy ý tưởng từ các phương pháp chiếu của C.J. Karzmark và của V. Neumann (xem [27, 28, 97]). Để giải bài toán chấp nhận tách trong không gian hữu hạn chiều, C. Byrne [27] đề xuất thuật toán chiếu CQ như sau: với k ≥ 0 xk+1 = PC (xk + γAT (PQ − I)Axk ), trong đó C, Q lần lượt là hai tập lồi đóng khác rỗng trong không gian Rn và Rm , A là ma trận thực m × n, L là giá trị riêng lớn nhất của ma trận AT A và γ ∈ (0, L2 ). Sau đó, có nhiều tác giả đã nghiên cứu bài toán chấp nhận tách bằng cách mở rộng bài toán chấp nhận tách trong không gian vô hạn chiều,
9 hoặc cải tiến cho độ dài bước γ hoặc mở rộng tập C và tập Q. Giải bài toán chấp nhận tách bằng phương pháp chiếu với C và/hoặc Q là tập nghiệm của bài toán bất đẳng thức biến phân hay tập điểm bất động của ánh xạ không giãn có thể xem luận án Tiến sĩ của Trần Việt Anh [1] và các tài liệu tham khảo ở đó. Việc giải bài toán chấp nhận tách dựa trên ý tưởng chuyển về bài toán tối ưu dựa trên ý tưởng của A. Moudafi và B.S. Thakur [74] năm 2013 bằng cách chứng minh bài toán tối ưu lồi 1 min{ k(I − PQ )(Ax)k2 , ∀λ > 0} x∈C 2λ tương đương với bài toán chấp nhận tách: Tìm x ∈ C sao cho Ax ∈ Q. Do đó, các phương pháp của quy hoạch toán học có thể áp dụng để giải bài toán chấp nhận tách. Cần phải nói thêm rằng các thuật toán đã có chỉ áp dụng cho trường hợp A là toán tử tuyến tính, lý do chính là các thuật toán dựa trên phương pháp chiếu đòi hỏi phải tính được hoặc toán tử chuyển vị A∗ hoặc toán tử nghịch đảo A−1 , trong khi đó với phương pháp dựa trên 1 bài toán tối ưu, thì hàm mục tiêu 2λ k(I − PQ )(Ax)k2 chỉ lồi và khả vi khi A là tuyến tính. Do tính khả vi của hàm mục tiêu nên bài toán cực tiểu hàm này tương đương với bài toán bất đẳng thức biến phân đơn điệu. Trong bài báo [68], Z. Li và các cộng sự đã xét bài toán chấp nhận tách với toán tử A là phi tuyến với C và Q đều là giao của một số hữu hạn tập lồi. Tuy nhiên, các tác giả phải giả thiết tính lồi của hàm 1 p(x) := kPQ (F (x)) − F (x)k2 2 để thuật toán đưa ra hội tụ. Một vấn đề được đặt ra là nghiên cứu thuật toán giải bài toán chấp nhận tách với toán tử chuyển không phải là tuyến tính và với C và/hoặc
10 Q không được cho tường minh, mà là tập nghiệm của các bài toán khác, chẳng hạn là tập nghiệm của bài toán cân bằng, hoặc các trường hợp riêng của nó. Trong luận án, chúng tôi xét bài toán chấp nhận tách cho hai trường hợp: Trường hợp đầu tiên, chúng tôi xét bài toán chấp nhận tách với C là tập nghiệm của bài toán cân bằng và Q là tập nghiệm của bài toán quy hoạch lồi. Đối với bài toán này chúng tôi đề xuất một thuật toán chiếu một lần giải bài toán cân bằng kết hợp với phương pháp chiếu giải bài toán quy hoạch lồi bằng cách sử dụng ánh xạ gần kề của hàm mục tiêu. Sự hội tụ của thuật toán đã được chứng minh khi bài toán cân bằng với song hàm cân bằng là para-đơn điệu. Một mô hình cân bằng sản xuất điện với chi phí môi trường thấp nhất được đưa ra minh họa cho thuật toán chúng tôi đề ra. Bài toán chấp nhận tách thứ hai được xét trong luận án là bài toán trong đó toán tử chuyển không nhất thiết là tuyến tính mà là một phép biến đổi được cho bởi các hàm số tựa tuyến tính. Thuật toán đề xuất dựa trên phương pháp tối ưu cho bài toán tựa lồi, sử dụng dưới đạo hàm Clarke và đã chứng minh được sự hội tụ. Mô hình cân bằng Nash với ràng buộc chung nảy sinh trong thực tế đã được mô tả dưới bài toán chấp nhận tách xét ở đây và đã thử nghiệm trên máy tính. Các kết quả tính toán được so sánh với một thuật toán đã có. Bản luận án, ngoài phần mở đầu, kết luận, danh mục các công trình đã công bố của tác giả có liên quan đến luận án và danh mục tài liệu tham khảo, luận án gồm 3 chương. Các kết quả chính được trình bày trong các Chương 2 và 3. Chương 1 trình bày các kiến thức bổ trợ, nhắc lại các kết quả về phép chiếu mêtric, tập lồi, hàm lồi, hàm tựa lồi, song hàm đơn điệu, bài toán cân bằng và một số bài toán liên quan, bài toán chấp nhận tách, một số phương pháp lặp cơ bản tìm điểm bất động và các bổ đề dùng để chứng minh cho các kết quả chính ở các chương sau.