Nới lỏng bài toán

Nới lỏng mở rộng hoặc bỏ bớt điều kiện để tạo một bài dễ hơn. Với bài cực tiểu và cùng hàm mục tiêu, giá trị của bài nới lỏng là cận dưới. Tuy nhiên, nghiệm của bài nới lỏng chưa chắc hợp lệ cho bài gốc.

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

• Các bài toán tối ưu lồiToán cho AI

Giải thích kỹ thuật

Chiều của cận phụ thuộc min hay max. Nếu $C\subseteq \tilde{C}$, thì với bài min, $\underset{x\in \tilde{C}}{inf}f(x)\le \underset{x\in C}{inf}f(x)$. Với bài max, chiều đảo lại. Đây là quan hệ , không cần hai bài đều lồi.

Nới lỏng thường đi cùng một phép thu hồi nghiệm: Làm tròn, chiếu hoặc một quy tắc gần đúng khác. Giá trị nới lỏng cho cận. Giá trị của ứng viên khả thi cho cận phía còn lại. Chỉ khi hai cận gặp nhau mới có chứng nhận tối ưu. Nguồn: Convex Optimization, §4.1 và các ví dụ về nới lỏng trong §5.1.2.

Ví dụ

Thay $x\in \{0,1\}$ bằng $0\le x\le 1$ cho phép thêm các giá trị như $x=0$,4.

Khi nào cần dùng?

Tạo cận tối ưu và thiết kế thuật toán xấp xỉ cho bài rời rạc hoặc khó.

Câu hỏi ôn lại

Nghiệm tối ưu của bài nới lỏng có luôn là nghiệm của bài gốc không?

Xem đáp án

Không. Phải kiểm lại các ràng buộc đã được nới.

Thuật ngữ liên quan

• Điểm và miền khả thi
• Infimum
• Đối ngẫu mạnh và khoảng cách đối ngẫu