Tối ưu hóa đa tiêu chí

Tối ưu hóa đa tiêu chí (còn gọi là quy hoạch đa tiêu chí, tiếng Anh: multi-objective optimization, multi-criteria optimization) — là một nhánh của tối ưu hóa toán học, nghiên cứu các bài toán tối ưu hóa đồng thời theo hai hay nhiều hàm mục tiêu (tiêu chí), thường mâu thuẫn với nhau. Về mặt hình thức, bài toán được phát biểu là bài toán cực tiểu hóa hàm mục tiêu dạng vector trên tập các nghiệm chấp nhận được.

Định nghĩa và thuật ngữ

Bài toán tối ưu hóa đa tiêu chí ở dạng tổng quát được viết như sau: $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ trong đó $S\subseteq {\mathbb{ℝ}}^n$ — tập nghiệm chấp nhận được khác rỗng, còn $f_i:S\to \mathbb{ℝ}$ — các hàm mục tiêu ($k\ge 2$). Vector $f(x)=(f_1(x),\dots ,f_k(x))$ được gọi là vector mục tiêu.

Khác với tối ưu hóa vô hướng, trong bài toán đa tiêu chí thường không tồn tại một nghiệm duy nhất cải thiện đồng thời tất cả các tiêu chí. Do đó, khái niệm tối ưu cổ điển được tổng quát hóa bằng cách sử dụng khái niệm tối ưu theo Pareto.

• Nghiệm Pareto (nghiệm tối ưu theo Pareto hay nghiệm hiệu quả): nghiệm chấp nhận được $x^{*}\in S$, mà không tồn tại nghiệm nào khác $x\in S$ thỏa mãn $f_i(x)\le f_i(x^{*})$ với mọi $i=1,\dots ,k$, và đồng thời $f_j(x)<f_j(x^{*})$ với ít nhất một chỉ số $j$. Nói cách khác, một nghiệm là tối ưu theo Pareto nếu không thể cải thiện giá trị của bất kỳ tiêu chí nào mà không làm xấu đi ít nhất một tiêu chí khác.
• Mặt trận Pareto (hay tập Pareto): tập hợp tất cả các vector mục tiêu tương ứng với các nghiệm tối ưu theo Pareto.
• Nghiệm tối ưu yếu theo Pareto: nghiệm $x^{*}\in S$, mà không tồn tại nghiệm nào khác $x\in S$ thỏa mãn $f_i(x)<f_i(x^{*})$ với mọi $i$.

Các tính chất và định lý quan trọng

• Định lý về tổng có trọng số: Trong các bài toán lồi (khi tất cả các hàm $f_i(x)$ và tập $S$ đều lồi), mọi nghiệm tối ưu theo Pareto $x^{*}$ đều là nghiệm của bài toán vô hướng cực tiểu hóa tổng có trọng số của các tiêu chí $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ với một bộ trọng số không âm nào đó $w_i\ge 0$. Tuy nhiên, trong các bài toán không lồi, phương pháp này có thể không tìm được một số phần của mặt trận Pareto.

• Điều kiện tối ưu Karush–Kuhn–Tucker (KKT): Các điều kiện tối ưu cần thiết cho các bài toán trơn được tổng quát hóa sang trường hợp đa tiêu chí. Tại điểm tối ưu theo Pareto tồn tại một bộ hệ số nhân (trọng số) không âm khác không, mà các gradient của các hàm mục tiêu và các ràng buộc tích cực phụ thuộc tuyến tính.

• Tính chất của tập nghiệm: Mặt trận Pareto có một số đặc trưng định tính quan trọng. Biên của nó được giới hạn bởi điểm lý tưởng (được tạo thành từ các giá trị cực tiểu theo từng phần tử của tất cả các tiêu chí) và điểm nadir (từ các giá trị cực đại theo từng phần tử trên mặt trận).

Ví dụ

• Bài toán tuyến tính: Cực tiểu hóa $f_1(x)=-x_1$ và $f_2(x)=-x_2$ với ràng buộc $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Ở đây việc cải thiện một tiêu chí (ví dụ, tăng $x_1$) tất yếu dẫn đến sự suy giảm tiêu chí kia (giảm $x_2$). Tập các nghiệm tối ưu theo Pareto là một đoạn thẳng $x_1+x_2=1$.
• Bài toán không lồi: Cực tiểu hóa $f_1(x)=x^2$ và $f_2(x)=(x-2{)}^2$ trên đoạn $[0,2]$. Mặt trận Pareto là không lồi. Phương pháp tổng có trọng số với các trọng số dương sẽ không thể tìm được các nghiệm bên trong đoạn này (ví dụ, tại điểm $x=1$), vì tổ hợp tuyến tính của các tiêu chí chỉ đạt cực tiểu tại các điểm biên $x=0$ hoặc $x=2$.

Các khái niệm liên quan và ứng dụng

Tối ưu hóa đa tiêu chí gắn chặt với lý thuyết ra quyết định đa tiêu chí (MCDM), nghiên cứu việc lựa chọn phương án tốt nhất có tính đến sở thích của người ra quyết định. Các phương pháp chính để chuyển bài toán đa tiêu chí thành bài toán vô hướng (vô hướng hóa) bao gồm:

• Phương pháp tổng có trọng số.
• Phương pháp ràng buộc $\epsilon$: Tối ưu hóa một tiêu chí, còn các tiêu chí còn lại được chuyển thành các ràng buộc dạng $f_i(x)\le {\epsilon }_i$. Phương pháp này có khả năng tìm nghiệm trên các phần không lồi của mặt trận.

Tối ưu hóa đa tiêu chí được ứng dụng rộng rãi trong thiết kế kỹ thuật, kinh tế (ví dụ, tối ưu hóa danh mục đầu tư), quản lý và sinh thái học.

Xem thêm

• Tối ưu theo Pareto
• Tối ưu hóa vector
• Lý thuyết ra quyết định
• Hệ thống hỗ trợ ra quyết định
• Nghiên cứu vận trù