Hàm đối ngẫu Lagrange

Hàm đối ngẫu $g(\lambda ,\nu )$ là của theo biến gốc khi giữ các nhân tử cố định. Mỗi bộ nhân tử khả thi cho một cận dưới của bài cực tiểu, vì vậy bài đối ngẫu tìm bộ nhân tử cho cận dưới lớn nhất.

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

• Đối ngẫu LagrangeToán cho AI

Giải thích kỹ thuật

Lấy theo biến gốc trước. Hàm $g(\lambda ,\nu )=\underset{x\in D}{inf}L(x,\lambda ,\nu )$ giữ các điều kiện miền xác định nhưng bỏ các ràng buộc đã đưa vào . Nếu infimum không hữu hạn, $g=-\mathrm{\infty }$ vẫn là một cận đúng nhưng không giúp nhiều.

$g$ luôn lõm theo các nhân tử vì nó là của một họ hàm affine theo $(\lambda ,\nu )$. Tính lõm này đúng ngay cả khi bài gốc không lồi. Bài đối ngẫu cực đại $g$ trên $\lambda \ge 0$. Nguồn: Convex Optimization, §5.1.2–5.1.3.

Ví dụ

Với $L=(x-2{)}^2+\lambda (x-1)$, lấy theo x cho $g(\lambda )=\lambda -\frac{{\lambda }^2}{4}$, $\lambda \ge 0$.

Khi nào cần dùng?

Chứng nhận cận dưới và đo khoảng cách tới tối ưu.

Câu hỏi ôn lại

Vì sao bài đối ngẫu cực đại g thay vì cực tiểu g?

Xem đáp án

Vì mọi giá trị g đều là cận dưới, cận lớn hơn sẽ gần giá trị tối ưu của bài gốc hơn.

Thuật ngữ liên quan

• Lagrangian
• Đối ngẫu mạnh và khoảng cách đối ngẫu
• Điều kiện Slater