Luận án tiến sĩ: Phương pháp giải bài toán cân bằng trên tập điểm bất động

Bài toán cân bằng được xác định bởi song hàm f và tập C. Ký hiệu EP(C, f) biểu diễn bài toán cân bằng cơ bản. Mục tiêu tìm điểm x trong tập C thỏa mãn điều kiện cân bằng. Hàm lưỡng hàm f(x, y) mô tả mối quan hệ giữa các phần tử. Tập nghiệm S(C,f) chứa tất cả các điểm cân bằng. Bài toán tối ưu OP(Ω, f) là trường hợp đặc biệt. Bất đẳng thức biến phân VI(C, F) có liên hệ chặt chẽ. Điều kiện tồn tại nghiệm phụ thuộc vào tính chất của f và C.

Điểm bất động của ánh xạ T là điểm x thỏa mãn T(x) = x. Tập Fix(T) chứa tất cả điểm bất động của T. Ánh xạ không giãn bảo toàn khoảng cách giữa các điểm. Ánh xạ co làm giảm khoảng cách theo một tỷ lệ cố định. Định lý điểm bất động Banach là kết quả cổ điển. Không gian Hilbert cung cấp cấu trúc hình học thuận lợi. Tích vô hướng hx, yi định nghĩa góc và khoảng cách. Hình chiếu PrC(x) đóng vai trò quan trọng trong thuật toán.

Bài toán cân bằng trên tập điểm bất động FEP(C, f) kết hợp cả hai khái niệm. Tìm điểm vừa là điểm cân bằng vừa là điểm bất động. Tập ràng buộc C thường là tập điểm bất động của ánh xạ T. Bài toán cân bằng hai cấp BEP(C, f) là mở rộng quan trọng. Bài toán đối ngẫu EPd(C, f) cung cấp góc nhìn bổ sung. Điều kiện tồn tại nghiệm phức tạp hơn bài toán đơn lẻ. Phương pháp giải yêu cầu kỹ thuật tinh vi hơn.

Phương pháp chiếu song song xấp xỉ chia bài toán thành các bài toán con. Mỗi bài toán con được giải độc lập trên bộ xử lý riêng. Kết quả từ các bài toán con được kết hợp lại. Xấp xỉ giúp đơn giản hóa tính toán phức tạp. Hình chiếu PrC(x) được tính song song cho nhiều điểm. Thuật toán lặp cập nhật dần dần tiến tới nghiệm. Điều kiện dừng dựa trên sai số giữa các bước lặp. Tốc độ hội tụ phụ thuộc vào tham số thuật toán.

Phương pháp dưới đạo hàm song song xử lý hàm không trơn. Dưới vi phân ∂f(x) thay thế đạo hàm cổ điển. Tập dưới vi phân chứa nhiều phần tử trong trường hợp không khả vi. Dưới vi phân theo biến thứ hai ∂2f(x, x) xử lý hàm lưỡng hàm. Tính toán song song dưới vi phân tại nhiều điểm đồng thời. Thuật toán sử dụng thông tin từ dưới vi phân để cập nhật. Hội tụ được đảm bảo dưới điều kiện phù hợp. Phương pháp áp dụng cho bài toán cân bằng tổng quát.

Phương pháp chiếu đạo hàm tăng cường song song kết hợp nhiều kỹ thuật. Tăng cường đạo hàm cải thiện tính ổn định thuật toán. Chiếu song song tăng tốc độ tính toán đáng kể. Thuật toán xử lý đồng thời nhiều thành phần của bài toán. Định lý hội tụ đảm bảo thuật toán đạt nghiệm. Tính toán thực nghiệm xác nhận hiệu quả phương pháp. Số bước lặp Iter. giảm so với phương pháp cổ điển. Thời gian CPU-times cải thiện trong thực nghiệm.

Thuật toán dưới đạo hàm quán tính bắt đầu với điểm khởi tạo Start.point. Bước quán tính tạo điểm trung gian từ hai bước lặp gần nhất. Hệ số quán tính αk điều chỉnh theo số bước lặp. Dưới vi phân được tính tại điểm trung gian quán tính. Bước cập nhật sử dụng thông tin từ dưới vi phân. Hình chiếu đưa điểm mới về tập ràng buộc khả thi. Điều kiện dừng kiểm tra sai số giữa hai bước lặp liên tiếp. Thuật toán lặp cho đến khi đạt tiêu chuẩn hội tụ.

Định lý hội tụ đảm bảo dãy {xk} hội tụ mạnh tới nghiệm. Điều kiện trên hàm lưỡng hàm f bao gồm tính lồi giả đơn điệu. Điều kiện Lipschitz yếu hơn so với phương pháp cổ điển. Hệ số quán tính phải thỏa mãn điều kiện giới hạn. Bước nhảy λk được chọn phù hợp với tính chất bài toán. Không gian Hilbert cung cấp cấu trúc cần thiết cho chứng minh. Hội tụ yếu xk ⇀ x được thiết lập trước. Hội tụ mạnh xk → x là kết quả cuối cùng.

Nguyên lý bài toán phụ quán tính song song chia bài toán gốc thành các bài toán nhỏ. Mỗi bài toán phụ được giải với kỹ thuật quán tính riêng. Tính toán song song các bài toán phụ trên nhiều bộ xử lý. Kết quả từ các bài toán phụ được tổng hợp theo quy tắc nhất định. Quán tính áp dụng cho cả bài toán gốc và bài toán phụ. Phương pháp đặc biệt hiệu quả cho bài toán quy mô lớn. Tính toán thực nghiệm Test cho thấy hiệu suất vượt trội. Số bước lặp giảm đáng kể so với phương pháp không quán tính.

Không gian Hilbert H là không gian tuyến tính với tích vô hướng. Tích vô hướng thỏa mãn tính đối xứng và tuyến tính. Chuẩn được cảm sinh từ tích vô hướng: kxk = √hx, xi. Bất đẳng thức Cauchy-Schwarz: |hx, yi| ≤ kxk · kyk. Tính đầy đủ theo metric cảm sinh từ chuẩn. Mọi không gian con đóng là không gian Hilbert. Định lý biểu diễn Riesz liên hệ phiếm hàm và vectơ. Không gian khả ly có cơ sở trực chuẩn đếm được.

Hình chiếu PrC(x) là điểm gần x nhất trên tập đóng lồi C. Hình chiếu tồn tại duy nhất trong không gian Hilbert. Đặc trưng hình chiếu: hy - PrC(x), x - PrC(x)i ≤ 0 với mọi y ∈ C. Hình chiếu là ánh xạ không giãn: kPrC(x) - PrC(y)k ≤ kx - yk. Nón pháp tuyến NC(x) chứa các hướng vuông góc với C tại x. Điểm x là hình chiếu khi và chỉ khi x - x ∈ NC(x). Thuật toán chiếu gradient sử dụng hình chiếu lặp đi lặp lại. Hình chiếu song song tính toán nhiều điểm cùng lúc.

Ánh xạ không giãn T thỏa mãn kT(x) - T(y)k ≤ kx - yk. Ánh xạ co mạnh hơn với hằng số co k < 1. Điểm bất động của T là nghiệm của phương trình T(x) = x. Tập Fix(T) là tập đóng lồi trong không gian Hilbert. Định lý Browder-Göhde-Kirk đảm bảo tồn tại điểm bất động. Phương pháp lặp đơn giản: xk+1 = T(xk) hội tụ yếu. Phương pháp Krasnoselski: xk+1 = (1-α)xk + αT(xk) hội tụ mạnh. Ánh xạ không giãn xuất hiện trong nhiều bài toán ứng dụng.

Bất đẳng thức biến phân VI(C, F) tìm x* ∈ C thỏa mãn điều kiện. Điều kiện: hF(x*), y - x*i ≥ 0 với mọi y trong tập ràng buộc C. Tập C thường là tập đóng lồi trong không gian Hilbert. Ánh xạ F: H → H có thể là gradient của hàm mục tiêu. Bất đẳng thức biến phân đơn trị khi F ánh xạ mỗi điểm tới một điểm. Bất đẳng thức biến phân đa trị MVI(C, F) khi F ánh xạ tới tập hợp. Tập nghiệm Sol(C, F) có thể rỗng, đơn điểm hoặc nhiều điểm. Điều kiện tồn tại nghiệm phụ thuộc tính chất của F và C.

Bài toán cân bằng EP(C, f) với f(x, y) = hF(x), y - xi là VI(C, F). Mọi bất đẳng thức biến phân là bài toán cân bằng đặc biệt. Bài toán cân bằng tổng quát hơn với hàm lưỡng hàm bất kỳ. Hàm lưỡng hàm f không nhất thiết có dạng tuyến tính. Điều kiện đơn điệu của F tương ứng điều kiện giả đơn điệu của f. Phương pháp giải bài toán cân bằng áp dụng cho bất đẳng thức biến phân. Ngược lại không phải bài toán cân bằng nào cũng là VI. Nghiên cứu bài toán cân bằng bao trùm bất đẳng thức biến phân.

Phương pháp chiếu gradient cơ bản: xk+1 = PrC(xk - λF(xk)). Bước nhảy λ > 0 điều chỉnh tốc độ di chuyển. Hình chiếu PrC đưa điểm về tập ràng buộc khả thi C. Thuật toán lặp đơn giản và dễ thực hiện. Hội tụ đảm bảo khi F đơn điệu và Lipschitz liên tục. Phương pháp Extragradient sử dụng hai bước chiếu. Bước dự đoán: yk = PrC(xk - λF(xk)). Bước hiệu chỉnh: xk+1 = PrC(xk - λF(yk)). Phương pháp này hội tụ với điều kiện yếu hơn.

Các bài toán Test bao gồm bài toán cân bằng và bất đẳng thức biến phân. Không gian thử nghiệm từ R² đến R¹⁰⁰ với nhiều chiều khác nhau. Điểm khởi tạo Start.point được chọn ngẫu nhiên hoặc cố định. Tham số thuật toán được điều chỉnh cho từng loại bài toán. Tiêu chuẩn dừng dựa trên sai số tương đối giữa các bước lặp. Ngưỡng sai số thường chọn từ 10⁻⁴ đến 10⁻⁶. Mỗi bài toán được chạy nhiều lần với điểm khởi tạo khác nhau. Kết quả trung bình và độ lệch chuẩn được ghi nhận.

Số bước lặp Iter. của phương pháp quán tính giảm 30-50% so với cổ điển. Thời gian CPU-times của thuật toán song song nhanh hơn 2-4 lần. Phương pháp chiếu mở rộng ổn định hơn với điểm khởi tạo xa nghiệm. Thuật toán dưới đạo hàm xử lý tốt hàm không trơn. Phương pháp kết hợp quán tính và song song cho kết quả tốt nhất. Độ chính xác nghiệm đạt được tương đương các phương pháp khác. Bộ nhớ sử dụng tăng nhẹ do lưu thông tin bước lặp trước. Tổng thể hiệu quả tính toán cải thiện đáng kể.

Bài toán cân bằng Nash trong lý thuyết trò chơi được giải hiệu quả. Tối ưu hóa lưu lượng mạng sử dụng bất đẳng thức biến phân. Phân bổ tài nguyên trong kinh tế mô hình hóa bằng bài toán cân bằng. Xử lý ảnh và thị giác máy tính áp dụng phương pháp điểm bất động. Học máy sử dụng thuật toán tối ưu dựa trên chiếu gradient. Bài toán cân bằng hai cấp BEP(C, f) mô hình hóa quyết định phân cấp. Tích Đề-Các A×B biểu diễn không gian chiến lược nhiều người chơi. Phương pháp song song đặc biệt phù hợp với dữ liệu lớn.