Mở đầu 1. Tính cấp thiết của đề tài Bài toán chấp nhận lồi có một vai trò rất quan trọng của toán học, đặc biệt là Toán ứng dụng. Bài toán này đã được nghiên cứu từ những năm 30 của thế kỷ trước bởi các nhà toán hoc nổi tiếng nhu J. Bài toán chấp nhận lỗi (Convex feasibility problem) là bài toán tìm một điểm trong giao của một số hữu hạn, hoặc vô hạn các tập lồi đóng trong một không gian nào đó.
Về mặt toán học, bài toán này được phát biểu như sau: Tìm z” € Œ := f/*¡Œ;, (CFP) trong đó C; là các tập lồi đóng. Một ví dụ điển hình của bài toán này là tìm nghiệm của một hệ phương trình, hoặc bất phương trình tuyến tính. Trong vài thập kỷ qua, bài toán chấp nhận lồi được nhiều người nghiên cứu khi các tập lồi thành phần được cho dưới dạng an như là tập nghiệm của các bài toán khác, ví dụ như bài toán tối ưu, bất đắng thức biến phân, điểm bất động, hay tổng quát hơn là bài toán cân bằng được định nghĩa bởi bất đẳng thức Nikaido-Isoda-Ky Fan. Các công trình nghiên cứu về vấn đề này đáng chú ý là |8, 17, 18, 39, 42, 78, 80, 81, 84].
Sau đây, chúng tôi giới thiệu hai bài toán quan trọng sẽ được đề cập trong bản luận án này đó là bài toán điểm bất động (ñxed point problem) va bai to4n can bang (equilibrium problem) trong khong gian Hilbert thuc. Bai toán điểm bất động là một bài toán quan trọng của toán học, do phạm vi ứng dụng hết sức rộng rãi của nó. Các định lý điểm bất động Brouwer, phát triển lên ánh xạ đa trị bởi Kakutani nói về sự tồn tại điểm bất động đã có từ những năm đầu của thế kỷ 20, tuy nhiên cho đến nay thuật toán hữu hiệu để tìm điểm bất động này vẫn chưa có. Để thu được các thuật toán hiệu quả tìm điểm bất động của một toán tử, ngoài tính chất liên tục như trong các định lý Brouwer và Kakutani người ta thường phải giả thiết về tính liên tục Lipschitz cho ánh xạ, trong đó nguyên lý ánh xạ co Banach là một kết quả cơ bản cho phép xây dựng các thuật toán lặp hiệu quả cho lớp bài toán điểm bất động của ánh xạ co.
Tính chất co này sau đó được giảm nhẹ bằng các tính chất giả co, không giãn, tiệm cận không giãn, tựa không giãn v. Một lớp bài toán khác được đề cập trong luận án này là bài toán cân bằng. Thuật ngữ cân bằng được sử dụng lần đầu tiên trong bài bao [62] của L. Oettli vào năm 1992 và hiện nay được sử dụng rộng rãi.
Trong bản luận án này, bài toán cân bằng được định nghĩa như sau: ìm z” CC: ƒ(z”,) > 0 Vụ € C. EP(C, f) O dé C la mot tập lồi đóng khác rỗng trong một không gian Hilbert thực H và ƒ : Œ x Œ — I. Thông thường người ta giả thiết ƒ(z,#) > 0 với mọi z € Œ, điều kiện này được gọi là điều kiện cân bằng, xuất phát từ các bài toán trong lý thuyết trò chơi. Bất đẳng thức trong bài toán EP(C, f) được dùng lần đầu tiên năm 1955 bởi H.
Isoda [67] trong một mô hình của bài toán trò chơi lồi. Fan goi EP(C, ƒ) là bất đẳng thức minimax và thiết lập một định lý về sự tồn tại nghiệm của bài toán EP(Œ, ƒ) trong không gian Ởclít hữu hạn chiều khi C mét tap 16i compact va f(z,-) tua 16i trén Œ (xem [33]). Mặc dù có dạng rất đơn giản, nhưng bai toán cân bằng EP(Œ, ƒ) bao hàm nhiều lớp bài toán quan trọng. Trong |62] các tác giả đã chỉ ra rằng các bài toán tối ưu, bất đắng thức biến phân, điểm bất động Kakutani là những trường hợp riêng của bài toán EP(C,f) và đã đề xuất một thuật toán hàm phạt Lagrange giải bài toán này.
Oettli đã chứng minh được bài toán EP(C, f) còn bao hàm các bài toán điểm yên ngựa và mô hình cân bằng Nash trong trò chơi không hợp tác (xem [19]), đồng thời thiết lập một số điều kiện tồn tại nghiệm cho bài toán này dưới những giả thiết về tính đơn điệu của song hàm ƒ. Một số trường hợp riêng quan trọng khác như bài toán tối ưu ngược, tối ưu véctd v. có thể tham khảo trong các sách chuyên khao [14, 48). Bài toán cân bằng đã thu hút sự nghiên cứu của nhiều nhà khoa học trong và ngoài nước, về cả mặt định tính, định lượng và ứng dụng.
Đối với khía cạnh định tính, nhiều kết quả quan trọng đã đạt được về sự tồn tại nghiệm, cấu trúc tập nghiệm, tính ổn định, cận sai số v. Về mặt định lượng và ứng dụng, nhiều phương pháp giải theo một số tiếp cận khác nhau đã được đề xuất và áp dụng vào các mô hình cân bằng trong kinh tế, kỹ thuật (xem, chẳng hạn [8, 15, 27, 30, 39, 48, 70| và các trích dẫn trong đó). Trong những năm gần đây, một số tác giả quan tâm đến bài toán tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động [2, 3, 8, 17, 18, 39, 42, 78, 80, 81, 84| với những giả thiết khác nhau đặt lên bài toán cân bằng và ánh xạ xác định điểm bất động. Bài toán tìm nghiệm chung này thuộc lớp bài toán chấp nhận lồi khi các tập nghiệm của bài toán này là lồi.
Cần nói thêm rằng về lý thuyết, bài toán cân bằng với những giả thiết nhất định có thể quy về bài toán điểm bất động và ngược lại. Tuy nhiên cách xét riêng từng bài toán cho phép sử dụng được các tính chất riêng của chúng. Đối với bài toán cân bằng, thường có giả thiết về một tính chất đơn điệu và một tính chất lồi nào đó cho song hàm, trong khi với bài toán điểm bất động, người ta phải dùng đến một tính chất co, hoặc không giãn suy rộng nào đó. Về quan hệ giữa các tính chất của song hàm cân bằng và tính chất co, không giãn, c-không giãn của ánh xạ gần kề xây dựng từ bài toán cân bằng có thể xem [CTI].
Một cách tiếp cận để tìm nghiệm của bài toán chấp nhận lồi này là kết hợp các phương pháp giải bài toán cân bằng, chẳng hạn như phương pháp điểm gần kề, phương pháp hiệu chỉnh Tikhonov, phương pháp đạo ham tăng cường, phương pháp chiếu đạo hàm v.với các phép lặp giải bài toán tìm điểm bất động, ví dụ như các phương pháp lặp Mann [27], phương pháp lặp Harpen [13], phương pháp lặp Ishikawa |44| v. Các nhà nghiên cứu đã xây dựng được một số thuật toán lặp hội tụ yếu hoặc mạnh để tìm nghiệm cho bài toán này trong trường hợp song hàm ƒ thỏa mãn điều kiện đơn điệu hoặc đơn điệu suy rộng kết hợp với tính chất không giãn hoặc không giãn suy rộng của ánh xạ điểm bất động, xem chẳng hạn |8, 41, 57, 59, 83, 89] và các tài liệu tham khảo trong các công trình này. Nhằm nâng cao tính hiệu quả của các phương pháp giải đã có và mở rộng phạm vi ứng dụng, người ta đang quan tâm đến vấn đề cải tiến các phương pháp giải đã có và xây dựng các thuật toán mới bằng cách giảm nhẹ các điều kiện đặt lên bài toán cân bằng hoặc/và bài toán điểm bất động. Trong luận ấn này chúng tôi nghiên cứu một số thuật toán mới giải bài toán tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động, đồng thời áp dụng vào một mô hình cân bằng cung-cầu Walras với cung, cầu được cho dưới dạng ấn như là nghiệm của các bài toán tối ưu.
Muc tiéu va nhiém vu nghién ctfu cua dé tal Mục tiêu và nhiêm vụ chính của luận án là tập trung nghiên cứu các vấn đề sau: i) Nghiên cứu các tính chất đơn điệu của ánh xạ gần kề cho bài toán bat dang thức biến phân đa trị (một trường hợp riêng quan trong của bài toán cân bằng) và mở rộng ra một số lớp bài toán cân bằng có tính đơn điệu; ii) Xây dựng một số thuật toán mới để tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động, khi song hàm cân bằng là lồi hoặc tựa lồi theo biến thứ hai, đồng thời chỉ có tính chất đơn điệu suy rộng, thậm chí không đơn điệu, còn ánh xạ cần tìm điểm bất động là ánh xạ lai ghép (hybrid) đối xứng tổng quát, tựa không giãn, hoặc tiệm cận không giãn; iii) Nghiên cứu một mô hình cân bằng cung-cầu Walras với cung, cầu được cho ấn như là nghiệm của các bài toán tối ưu lồi và đưa ra thuật toán để giải mô hình. Mô hình này có thể coi như bài toán chấp nhận lồi (CF 'P) với mm = 1, có đặc điểm bài toán cân bằng ở đây là một bài toán bù, nhưng ánh xạ giá lại được cho dưới dạng ấn thông qua các nghiệm tối ưu của hai bài toán quy hoạch lồi. Đối tượng nghiên cứu và phạm vi nghiên cứu Với các mục đích đặt ra như trên, luận án có đôi tượng nghiên cứu và phạm vi nghiên cứu như sau: 11 a. Déi tudng nghién cttu i) Ánh xạ gần kề cho bài toán bất đẳng thức biến phân đa trị và bài toán cân bằng; ii) Bài toán tìm nghiệm chung của bài toán cân bằng và bài toán điểm ` Z ` tA `.
Z «2 bất động có cẫu trúc; iii) Mô hình cân bằng cung-cầu Walras. Phạm vỉ nghiên cứu i) Nghiên cứu các tính chất đơn điệu của ánh xạ gần kề cho ánh đa trị và áp dụng vào bài toán bất đẳng thức biến phân đa trị và bài toán cân bằng; ii) Xây dựng các thuật toán tìm nghiệm chung của các bài toán điểm bất động và bài toán cân bằng với kỹ thuật kết hợp giữa thuật toán lặp Ishikawa với các thuật toán điểm gần kề, thuật toán đạo hàm tăng cường (extragradient) không sử dụng hoặc có sử dụng kỹ thuật tìm kiếm theo tia hay thuật toán chiếu trong trường hợp: ánh xạ của bài toán điểm bất động là ánh xạ lai ghép đối xứng tổng quát, còn song hàm cân bằng là lồi theo biến thứ hai. Hoặc ánh xạ của bài toán điểm bất động là ánh xạ tiệm cận không giãn, còn song hàm của bài toán cân bằng là tựa lồi theo biến thứ hai; iii) Xây dựng mô hình cân bằng cung cầu Walras với cung và cầu được cho dưới dạng an như là các tập nghiệm của các bài toán quy hoạch toán học, đồng thời đề xuất thuật toán tìm điểm cân bằng của mô hình.