Luận án tiến sĩ: Phương pháp giải bài toán cân bằng và bất đẳng thức biến phân hai cấp

Bài toán cân bằng hai cấp BEP(g, F, C) được định nghĩa trên không gian Hilbert H. Cho C là tập lồi đóng khác rỗng. Ánh xạ F và song hàm g thỏa mãn các điều kiện đơn điệu. Bài toán cấp trên tìm điểm x* thuộc tập nghiệm của bài toán cấp dưới. Bài toán cấp dưới là bài toán bất đẳng thức biến phân VI(F, C). Tập nghiệm ký hiệu là Ω. Điều kiện tồn tại nghiệm yêu cầu tính đơn điệu mạnh hoặc giả đơn điệu của các ánh xạ.

Bất đẳng thức biến phân VI(F, C) là trường hợp đặc biệt của bài toán cân bằng. Tìm x* thuộc C sao cho ⟨F(x*), y - x*⟩ ≥ 0 với mọi y thuộc C. Bài toán hai cấp mở rộng bằng cách thêm ràng buộc cấp trên. Nghiệm phải thỏa mãn đồng thời hai điều kiện: thuộc tập nghiệm cấp dưới và cực tiểu hóa hàm mục tiêu cấp trên. Cấu trúc này phức tạp hơn bài toán một cấp thông thường.

Bài toán hai cấp xuất hiện trong thiết kế mạng lưới giao thông. Cấp trên là nhà quản lý tối ưu hóa cơ sở hạ tầng. Cấp dưới là người dùng chọn lộ trình tối ưu. Cân bằng Nash trong lý thuyết trò chơi cũng dẫn đến bài toán hai cấp. Ứng dụng khác bao gồm quản lý tài nguyên và lập kế hoạch sản xuất. Tính hai cấp phản ánh cấu trúc phân cấp trong ra quyết định thực tế.

Hình chiếu P_C(x) là điểm gần x nhất trong C. Với tập lồi đóng, hình chiếu tồn tại duy nhất. Bất đẳng thức đặc trưng: ⟨x - P_C(x), y - P_C(x)⟩ ≤ 0 với mọi y thuộc C. Hình chiếu là ánh xạ không giãn: ||P_C(x) - P_C(y)|| ≤ ||x - y||. Tính chất này đảm bảo tính ổn định của thuật toán chiếu. Hình chiếu lên các tập đơn giản (hình cầu, đa diện) tính được hiệu quả.

Thuật toán chiếu gradient giải VI(F, C) bằng lặp x_{k+1} = P_C(x_k - α_k F(x_k)). Độ dài bước α_k cố định hoặc thay đổi theo quy tắc Armijo. Điều kiện hội tụ: F đơn điệu mạnh và Lipschitz liên tục. Hội tụ mạnh đạt tốc độ tuyến tính với α_k thích hợp. Thuật toán đơn giản nhưng hiệu quả với bài toán có cấu trúc đặc biệt. Mở rộng cho bài toán hai cấp cần điều chỉnh thêm.

Thuật toán điểm gần kề giải bài toán cân bằng EP(f, C). Phép lặp: x_{k+1} = argmin{f(x_k, y) + (1/2λ_k)||y - x_k||² : y ∈ C}. Tham số λ_k điều chỉnh độ gần với điểm hiện tại. Phương pháp này hội tụ yếu với điều kiện đơn điệu giả trên f. Ưu điểm là không cần tính Lipschitz. Nhược điểm là phải giải bài toán phụ mỗi bước lặp. Kết hợp với chiếu dưới đạo hàm cải thiện hiệu quả.

Dưới vi phân chéo ∂²g(x, x) của song hàm g theo biến thứ hai tại x. Với g lồi theo biến thứ hai, ∂²g(x, x) là tập lồi đóng. Tính chất đơn điệu: nếu g đơn điệu mạnh thì ∂²g đơn điệu mạnh. Dưới vi phân chéo khác với gradient thông thường. Sử dụng trong thuật toán khi gradient không tồn tại. Tính toán dựa vào định nghĩa hoặc công thức đặc biệt cho hàm cụ thể.

Thuật toán bắt đầu với x_0 tùy ý trong C. Mỗi bước lặp tính y_k = P_C(x_k - α_k F(x_k)). Chọn d_k thuộc ∂²g(y_k, y_k). Tính z_k = P_C(y_k - β_k d_k). Cập nhật x_{k+1} dựa trên z_k và điều kiện Armijo. Tham số α_k, β_k điều chỉnh theo quy tắc giảm. Thuật toán dừng khi ||x_{k+1} - x_k|| nhỏ hơn sai số cho phép. Độ phức tạp mỗi bước phụ thuộc vào tính toán hình chiếu.

Định lý hội tụ mạnh yêu cầu F và G đơn điệu mạnh. Hằng số Lipschitz của F và G phải bị chặn. Dãy {α_k} và {β_k} thỏa mãn điều kiện tổng và tổng bình phương. Tập nghiệm Ω khác rỗng và bị chặn. Với các điều kiện này, dãy {x_k} hội tụ mạnh đến nghiệm x* thuộc Ω. Tốc độ hội tụ là tuyến tính hoặc siêu tuyến tính tùy chọn tham số. Chứng minh dựa trên bổ đề điểm bất động và ước lượng sai số.

Bài toán VIEP tìm x* thuộc Sol(f, C) thỏa ⟨F(x*), y - x*⟩ ≥ 0 với mọi y thuộc Sol(f, C). Sol(f, C) là tập nghiệm của bài toán cân bằng EP(f, C). Cấp dưới là bài toán cân bằng với song hàm f. Cấp trên là bất đẳng thức biến phân với toán tử F. Tập nghiệm Sol(F, f, C) là giao của hai tập nghiệm. Điều kiện tồn tại: f và F đơn điệu, C compact hoặc bị chặn.

Bài toán EVIP tìm x* thuộc S(F, C) thỏa g(x*, y) ≥ 0 với mọi y thuộc S(F, C). S(F, C) là tập nghiệm của VI(F, C). Thuật toán lặp: tính y_k giải xấp xỉ VI(F, C). Chọn d_k thuộc ∂²g(y_k, y_k). Chiếu z_k = P_C(y_k - β_k d_k). Cập nhật x_{k+1} theo quy tắc kết hợp. Hội tụ mạnh với điều kiện F và g đơn điệu mạnh. Tốc độ hội tụ phụ thuộc vào độ chính xác giải bài toán cấp dưới.

Thực nghiệm số với các bài toán test trong R^n. So sánh số bước lặp và thời gian CPU. VIEP hội tụ nhanh hơn khi f đơn giản hơn F. EVIP hiệu quả hơn khi VI(F, C) dễ giải. Độ chính xác cuối cùng tương đương với cả hai phương pháp. Chọn phương pháp phù hợp phụ thuộc cấu trúc bài toán cụ thể. Kết hợp hai phương pháp có thể cải thiện hiệu quả tổng thể.

Ánh xạ F: H → H đơn điệu khi ⟨F(x) - F(y), x - y⟩ ≥ 0. Đơn điệu mạnh với hằng số μ > 0 khi ⟨F(x) - F(y), x - y⟩ ≥ μ||x - y||². Giả đơn điệu là dạng yếu hơn của đơn điệu. Đơn điệu cực đại khi đồ thị là tập đơn điệu cực đại. Tính chất đơn điệu bảo toàn qua tổng và tích vô hướng dương. Ánh xạ đơn điệu mạnh có nghịch đảo Lipschitz liên tục.

Điểm bất động x* của T thỏa T(x*) = x*. Định lý Banach: ánh xạ co trên không gian đầy đủ có điểm bất động duy nhất. Phương pháp lặp Picard: x_{k+1} = T(x_k) hội tụ đến điểm bất động. Bài toán VI(F, C) tương đương với điểm bất động của T(x) = P_C(x - αF(x)). Tốc độ hội tụ tuyến tính với hằng số co k. Phương pháp này là cơ sở cho nhiều thuật toán giải bài toán hai cấp.

Ánh xạ không giãn T thỏa ||T(x) - T(y)|| ≤ ||x - y||. Hình chiếu P_C là ánh xạ không giãn. Điểm bất động tồn tại nhưng không nhất thiết duy nhất. Hội tụ yếu đạt được với phương pháp Krasnoselski-Mann. Hội tụ mạnh yêu cầu điều kiện bổ sung như tính demiclosed. Ánh xạ không giãn xuất hiện trong bài toán điểm bất động trên tập nghiệm VIFIX. Tốc độ hội tụ yếu chậm hơn hội tụ mạnh.

Bài toán test 1: VI(F, C) với F(x) = Ax + b, C là hình cầu đơn vị. Bài toán test 2: EP(f, C) với f song tuyến tính, C là đơn hình. Bài toán test 3: BVI(F, G, C) với F, G đơn điệu mạnh. Bài toán test 4: VIEP với chiều không gian n = 100. Tham số đơn điệu mạnh μ thay đổi từ 0.1 đến 1.0. Điểm khởi đầu x_0 chọn ngẫu nhiên trong C. Tiêu chuẩn dừng: ||x_{k+1} - x_k|| < 10^{-6}.

Thuật toán chiếu dưới đạo hàm hội tụ trong 50-200 bước lặp. Thời gian CPU từ 0.1s đến 5s tùy chiều không gian. Độ chính xác đạt 10^{-6} đến 10^{-8}. Tốc độ hội tụ nhanh hơn khi μ lớn (đơn điệu mạnh hơn). Chọn α_k giảm chậm cải thiện ổn định. Phương pháp điểm gần kề cần 2-3 lần nhiều bước lặp hơn. Kết quả phù hợp với ước lượng lý thuyết về tốc độ hội tụ tuyến tính.

Áp dụng cho bài toán định tuyến giao thông với 20 nút. Cấp dưới là cân bằng Wardrop của người dùng. Cấp trên là tối ưu hóa luồng của nhà quản lý. Thuật toán tìm được nghiệm trong 150 bước lặp. Thời gian tính toán 2.3 giây trên CPU Intel i5. Nghiệm giảm tổng thời gian di chuyển 15% so với không tối ưu. Kết quả cho thấy tính khả thi trong ứng dụng thực tế quy mô trung bình.