Luận án tiến sĩ: Phương pháp chiếu mở rộng giải bài toán cân bằng hai cấp

Bài toán cân bằng hai cấp là dạng toán tối ưu đặc biệt với cấu trúc phân tầng. Cấp trên tối ưu hóa mục tiêu riêng với ràng buộc phụ thuộc cấp dưới. Cấp dưới giải bài toán cân bằng độc lập tạo tập nghiệm. Tập ràng buộc của cấp trên chính là tập nghiệm cấp dưới. Cấu trúc này phản ánh nhiều tình huống thực tế trong kinh tế và kỹ thuật. Bài toán bất đẳng thức biến phân hai cấp là trường hợp đặc biệt quan trọng. Song hàm cân bằng mô tả quan hệ giữa các biến quyết định.

Phương pháp chiếu là nền tảng để giải bài toán cân bằng. Phép chiếu ánh xạ điểm bất kỳ về tập ràng buộc gần nhất. Tính chất toán tử đơn điệu đảm bảo sự tồn tại nghiệm. Hội tụ mạnh cho phép xác định nghiệm chính xác qua các bước lặp. Thuật toán chiếu mở rộng cải thiện tốc độ hội tụ đáng kể. Kỹ thuật xấp xỉ giảm độ phức tạp tính toán trong mỗi bước lặp.

Mô hình cân bằng kinh tế Nash-Cournot mô tả cạnh tranh giữa các công ty. Bài toán tối ưu hai cấp xuất hiện trong thiết kế mạng viễn thông. Hệ thống CDMA sử dụng bài toán cân bằng để phân bổ tài nguyên. Các phương pháp chiếu giải quyết hiệu quả các bài toán quy mô lớn. Kết quả số minh họa cho thấy hiệu suất vượt trội so với phương pháp cổ điển.

Dưới vi phân là tập hợp các véc tơ tuyến tính xấp xỉ hàm từ dưới. Dưới đạo hàm xấp xỉ mở rộng khái niệm này với độ chính xác có kiểm soát. Tính toán dưới vi phân đơn giản hơn nhiều so với đạo hàm cổ điển. Khoảng cách Hausdorff đo độ gần giữa các tập dưới vi phân. Điều kiện tăng trưởng đảm bảo dưới đạo hàm bị chặn.

Hình chiếu chính xác lên tập ràng buộc thường tốn kém về tính toán. Chiếu xấp xỉ cho phép sai số nhỏ có kiểm soát trong mỗi bước. Nón pháp tuyến xấp xỉ ngoài mô tả tập ràng buộc cục bộ. Thuật toán điều chỉnh tham số xấp xỉ theo tiến trình hội tụ. Độ phức tạp tính toán giảm đáng kể với chiếu xấp xỉ.

Hội tụ mạnh đảm bảo dãy lặp tiến về nghiệm theo chuẩn. Điều kiện đơn điệu mạnh của toán tử là yếu tố then chốt. Bổ đề điểm bất động cung cấp công cụ chứng minh chính. Tham số bước lặp phải thỏa mãn điều kiện tổng vô hạn. Kết quả hội tụ áp dụng cho lớp rộng các bài toán cân bằng.

Quán tính mượn ý tưởng từ cơ học cổ điển về động lượng. Mỗi bước lặp kết hợp vị trí hiện tại và xu hướng chuyển động. Tham số quán tính thường chọn trong khoảng từ 0 đến 1. Giá trị lớn tăng tốc độ nhưng có thể giảm ổn định. Điều chỉnh thích nghi tham số cải thiện hiệu suất tổng thể.

Gradient tăng cường kết hợp đạo hàm và thông tin bổ sung. Kỹ thuật này giảm dao động trong quá trình hội tụ. Bước lặp được tính toán dựa trên gradient hiệu chỉnh. Điều kiện Armijo đảm bảo giảm đủ giá trị hàm mục tiêu. Phương pháp này ổn định hơn gradient descent cổ điển.

Mô hình Nash-Cournot mô tả cạnh tranh về sản lượng giữa các công ty. Mỗi công ty chọn sản lượng tối đa hóa lợi nhuận riêng. Giá thị trường phụ thuộc vào tổng sản lượng của tất cả công ty. Điểm cân bằng Nash là trạng thái không công ty nào muốn thay đổi. Thuật toán đạo hàm tăng cường tìm cân bằng hiệu quả. Kết quả số cho thấy hội tụ nhanh với ít bước lặp.

Hàm DC là hiệu của hai hàm lồi trên không gian Hilbert. Mọi hàm khả vi liên tục đều biểu diễn được dưới dạng DC. Tập DC chứa nhiều lớp hàm quan trọng trong ứng dụng. Dưới vi phân DC kết hợp dưới vi phân của hai thành phần lồi. Tuyến tính hóa DC tại một điểm tạo xấp xỉ affine.

Bài toán phụ DC thu được bằng tuyến tính hóa thành phần lồi thứ hai. Nghiệm bài toán phụ tính toán dễ hơn nhiều so với bài toán gốc. Tham số chính quy hóa đảm bảo bài toán phụ có nghiệm duy nhất. Điều kiện tối ưu của bài toán phụ cho công thức lặp. Kỹ thuật này áp dụng rộng rãi trong tối ưu phi lồi.

Sai số giữa điểm lặp và nghiệm giảm theo quy luật xác định. Tốc độ hội tụ tuyến tính với hằng số co phụ thuộc tham số. Ước lượng sai số tiên nghiệm giúp chọn tham số phù hợp. Điều kiện dừng dựa trên sai số giữa hai bước lặp liên tiếp. Kết quả số xác nhận các ước lượng lý thuyết về hội tụ. Số chiều bài toán ảnh hưởng đến thời gian tính toán nhưng không làm mất hội tụ.

Tập ràng buộc đóng đảm bảo giới hạn của dãy trong tập vẫn thuộc tập. Tính lồi cho phép áp dụng các kỹ thuật tối ưu lồi mạnh mẽ. Compact yếu trong không gian Hilbert vô hạn chiều rất quan trọng. Giao của các tập lồi đóng vẫn là tập lồi đóng. Phép chiếu lên tập lồi đóng luôn xác định duy nhất.

Song hàm cân bằng là hàm hai biến mô tả quan hệ giữa các lựa chọn. Điều kiện cân bằng yêu cầu hàm không âm tại điểm cân bằng. Nửa liên tục dưới theo biến thứ nhất đảm bảo tính đóng tập mức. Lồi theo biến thứ hai cho phép sử dụng công cụ giải tích lồi. Điều kiện Lipschitz kiểm soát tốc độ thay đổi của song hàm.

Định lý Ky Fan là kết quả cơ bản cho bài toán cân bằng. Điều kiện coercive đảm bảo nghiệm nằm trong tập compact. Định lý điểm bất động Brouwer áp dụng cho ánh xạ liên tục. Nguyên lý Ekeland cho nghiệm xấp xỉ với sai số kiểm soát. Kết hợp các điều kiện trên cho sự tồn tại nghiệm chính xác.

Bài toán kiểm tra được thiết kế với nghiệm biết trước để đánh giá chính xác. Số chiều thay đổi từ 2 đến 1000 để kiểm tra khả năng mở rộng. Song hàm cân bằng bao gồm dạng tuyến tính, bậc hai và phi tuyến. Tập ràng buộc có dạng hình hộp, simplex hoặc giao của nhiều tập. Tham số Lipschitz và đơn điệu thay đổi để kiểm tra độ bền vững.

Đồ thị sai số theo số bước lặp cho thấy xu hướng giảm rõ ràng. Tốc độ hội tụ tuyến tính được xác nhận qua độ dốc đường log. Thuật toán quán tính giảm số bước lặp trung bình 30-50 phần trăm. Phương pháp DC ổn định hơn khi song hàm không đơn điệu. Sai số cuối cùng đạt dưới ngưỡng cho phép trong tất cả thử nghiệm.

Thời gian CPU tăng tuyến tính hoặc bậc hai theo số chiều bài toán. Phương pháp chiếu xấp xỉ nhanh hơn chiếu chính xác 2-5 lần. Bộ nhớ sử dụng tối ưu nhờ cấu trúc dữ liệu hiệu quả. Thuật toán song song hóa được trên nhiều lõi xử lý. Kết quả cho thấy khả năng giải bài toán quy mô lớn trong thực tế.