Luận án tiến sĩ: Tối ưu hóa đa trị - Điều kiện cần và biến phân

Hàm đa trị khác với hàm thông thường ở chỗ mỗi phần tử trong miền xác định được ánh xạ tới một tập hợp thay vì một điểm. Ánh xạ đa trị xuất hiện tự nhiên trong nhiều bài toán thực tế. Ví dụ trong tối ưu Pareto, mỗi quyết định có thể dẫn đến nhiều kết quả khác nhau. Tính nửa liên tục của ánh xạ đa trị đóng vai trò quan trọng trong phân tích. Các tính chất như tính đóng, tính lồi của ảnh cần được xem xét kỹ lưỡng.

Tham số biểu diễn các yếu tố bên ngoài ảnh hưởng đến bài toán. Khi tham số thay đổi, tập nghiệm và nghiệm hữu hiệu cũng biến đổi. Nghiên cứu độ nhạy nghiệm giúp hiểu được sự ổn định của lời giải. Điều này quan trọng trong ứng dụng thực tế khi dữ liệu có sai số. Phân tích tham số hóa là công cụ mạnh để nghiên cứu tính liên tục của nghiệm.

Bài toán tối ưu vector yêu cầu tối ưu đồng thời nhiều hàm mục tiêu. Nghiệm hữu hiệu hay nghiệm Pareto là khái niệm trung tâm. Một nghiệm được gọi là Pareto nếu không thể cải thiện một mục tiêu mà không làm xấu đi mục tiêu khác. Tập nghiệm Pareto thường là một tập đa trị. Điều này giải thích tại sao tối ưu đa trị là công cụ tự nhiên cho bài toán đa mục tiêu.

Điều kiện Fritz John là dạng tổng quát nhất của điều kiện cần tối ưu. Không yêu cầu điều kiện chính quy ràng buộc. Tồn tại các nhân tử không âm cho hàm mục tiêu và ràng buộc. Tổ hợp tuyến tính của gradient phải bằng không. Trong trường hợp đa trị, gradient được thay bằng đạo hàm suy rộng. Điều kiện này yếu hơn Kuhn-Tucker nhưng luôn thỏa mãn.

Điều kiện Kuhn-Tucker mạnh hơn Fritz John nhờ nhân tử hàm mục tiêu dương. Điều này đòi hỏi điều kiện chính quy ràng buộc được thỏa mãn. Các dạng điều kiện chính quy phổ biến là Mangasarian-Fromovitz và Slater. Với ràng buộc đẳng thức đơn trị, gradient các ràng buộc phải độc lập tuyến tính. Điều kiện bù yếu kết nối nhân tử Lagrange với ràng buộc tích cực.

Khi hàm mục tiêu là đa trị, khái niệm cực trị cần định nghĩa lại. Nghiệm hữu hiệu được sử dụng thay cho cực tiểu cổ điển. Đạo hàm Clarke và đạo hàm Mordukhovich là công cụ phân tích. Điều kiện cần được biểu diễn qua nón pháp tuyến và nón tiếp tuyến. Tính nửa liên tục của ánh xạ đa trị ảnh hưởng đến tính khả vi.

Ràng buộc bao hàm thức yêu cầu biến tối ưu thuộc ảnh của ánh xạ đa trị. Dạng tổng quát là x thuộc F(x,p) với p là tham số. Tập nghiệm phụ thuộc vào cả biến và tham số. Tính đóng và tính lồi của F ảnh hưởng đến tính chất nghiệm. Ràng buộc này bao hàm cả bất đẳng thức biến phân.

Với ràng buộc bao hàm thức, điều kiện Kuhn-Tucker được điều chỉnh. Nhân tử Lagrange liên quan đến nón pháp tuyến của tập ràng buộc. Đạo hàm cographe của ánh xạ đa trị xuất hiện trong biểu diễn. Điều kiện chính quy yêu cầu tính nửa liên tục và tính lồi. Tính compact địa phương của tập ràng buộc thường được giả thiết.

Bài toán cân bằng Nash có thể biểu diễn qua ràng buộc bao hàm thức. Mỗi người chơi tối ưu hóa trên tập phụ thuộc vào quyết định của người khác. Điểm yên ngựa cũng là trường hợp đặc biệt. Bài toán cân bằng giao thông sử dụng ràng buộc dạng này. Tính tồn tại và duy nhất nghiệm là câu hỏi quan trọng.

Bài toán cổ điển tìm x trong tập lồi đóng K sao cho (f(x), y-x) ≥ 0 với mọi y trong K. Điều kiện này tương đương với x là điểm cực tiểu của hàm khả vi trên K. Tính đơn điệu của f đảm bảo tính duy nhất nghiệm. Phương pháp điểm bất động thường được dùng để chứng minh tồn tại. Ứng dụng trong cơ học, vật lý và kinh tế rất phong phú.

Dạng suy rộng cho phép tập K phụ thuộc vào nghiệm x. Bài toán tìm x thuộc K(x) sao cho (f(x), y-x) ≥ 0 với mọi y trong K(x). Tính chất điểm bất động xuất hiện qua K(x). Điều kiện tồn tại nghiệm phức tạp hơn do tính tự tham chiếu. Ánh xạ K cần có tính nửa liên tục và giá trị lồi.

Giả bất đẳng thức biến phân thay điều kiện cho mọi y bằng điều kiện yếu hơn. Tồn tại y sao cho bất đẳng thức không thỏa mãn. Dạng này tổng quát hóa cả bất đẳng thức biến phân và bài toán bù. Định lý tồn tại sử dụng kỹ thuật KKM và điểm bất động. Giả thiết đơn điệu có thể được giảm nhẹ đáng kể.

Định lý điểm bất động Brouwer và Kakutani là công cụ cơ bản. Bài toán được chuyển về tìm điểm bất động của ánh xạ phù hợp. Tính liên tục của ánh xạ cần được kiểm chứng cẩn thận. Với ánh xạ đa trị, tính nửa liên tục trên và giá trị lồi là cần thiết. Tính compact của miền xác định thường không thể thiếu.

Bổ đề Knaster-Kuratowski-Mazurkiewicz là công cụ mạnh trong giải tích lồi. Từ KKM suy ra nhiều định lý điểm bất động và minimax. Ứng dụng vào bất đẳng thức biến phân thông qua ánh xạ KKM phù hợp. Tính đóng của các tập trong họ KKM là giả thiết quan trọng. Kỹ thuật này hiệu quả với bài toán không có tính đơn điệu.

Điều kiện coercive đảm bảo nghiệm nằm trong tập compact. Dạng thông dụng là (f(x),x) tiến đến vô cùng khi ||x|| lớn. Tính đơn điệu mạnh của f đảm bảo nghiệm duy nhất. Đơn điệu đều cho phép ước lượng tốc độ hội tụ của thuật toán. Kết hợp coercive và đơn điệu cho kết quả tồn tại duy nhất mạnh.

Ánh xạ nghiệm gán mỗi tham số với tập nghiệm tương ứng. Nửa liên tục trên nghĩa là đồ thị đóng trong tô pô tích. Nửa liên tục dưới yêu cầu ảnh của lân cận chứa lân cận của ảnh. Tính compact của tập nghiệm giúp chứng minh nửa liên tục trên. Điều kiện đơn điệu đều hỗ trợ nửa liên tục dưới.

Bài toán bù tìm x sao cho x ≥ 0, f(x) ≥ 0 và x^T f(x) = 0. Giả bài toán bù thay điều kiện bằng điều kiện quasi. Đây là trường hợp đặc biệt của giả bất đẳng thức biến phân. Phân tích ổn định giúp hiểu sự thay đổi điểm cân bằng. Ứng dụng trong lý thuyết trò chơi và kinh tế cân bằng.

Mô hình Wardrop mô tả phân bố lưu lượng trên mạng giao thông. Nguyên lý cân bằng: tất cả đường đi được sử dụng có chi phí bằng nhau và nhỏ nhất. Điều này dẫn đến bất đẳng thức biến phân với hàm chi phí. Tham số là ma trận nhu cầu giao thông. Phân tích độ nhạy cho biết ảnh hưởng của thay đổi nhu cầu đến lưu lượng cân bằng.