Điểm và miền khả thi

Điểm khả thi là một lựa chọn thỏa đồng thời mọi ràng buộc và thuộc miền xác định của các hàm. Miền khả thi là tập tất cả các điểm như vậy. Khả thi chỉ nói điểm hợp lệ, chưa nói điểm đó tối ưu.

Lĩnh vực: Tối ưu hóa

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Bài giảng dùng khái niệm này

• Giới thiệu tối ưu, tập lồi và hàm lồiToán cho AI
• Các bài toán tối ưu lồiToán cho AI
• Đối ngẫu LagrangeToán cho AI
• Tối ưu không ràng buộc và ràng buộc đẳng thứcToán cho AI
• Quy hoạch tuyến tính và quy hoạch độngToán cho AI

Giải thích kỹ thuật

Khả thi được kiểm trước tối ưu. Với bài có miền chung $D$, bất đẳng thức $f_i(x)\le 0$ và đẳng thức $h_j(x)=0$, miền khả thi là $D\cap \bigcap _i\{x:f_i(x)\le 0\}\cap \bigcap _j\{x:h_j(x)=0\}$. Chỉ cần một điều kiện sai là điểm không khả thi.

Miền khả thi rỗng làm bài toán vô nghiệm. Miền khác rỗng nhưng không đóng hoặc không bị chặn có thể khiến không đạt. Vì thế “tìm được một giá trị mục tiêu nhỏ” và “tìm được một nghiệm của bài toán” là hai phát biểu khác nhau. Nguồn: Convex Optimization, §4.1.

Ví dụ

Trong bài $min(x-2{)}^2$ với $x\le 1$, $x=0$ và $x=1$ đều khả thi, nhưng $x=2$ không khả thi dù cho giá trị mục tiêu bằng 0.

Khi nào cần dùng?

Kiểm tra một nghiệm trước khi so giá trị mục tiêu hoặc áp dụng .

Câu hỏi ôn lại

Một điểm có giá trị mục tiêu nhỏ nhưng vi phạm một ràng buộc có phải nghiệm khả thi không?

Xem đáp án

Không. Điểm phải thỏa tất cả ràng buộc.

Thuật ngữ liên quan

• Tập lồi
• Infimum
• Điều kiện KKT