Lagrangian

Lagrangian cộng mục tiêu với các ràng buộc đã nhân bởi các nhân tử. Với quy ước $f_i(x)\le 0$, nhân tử bất đẳng thức ${\lambda }_i$ phải không âm, còn nhân tử đẳng thức không bị dấ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

• Các bài toán tối ưu lồiToán cho AI
• Đối ngẫu LagrangeToá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

Vai trò của quy ước dấu. Với bài cực tiểu $f_0(x)$ có $m$ bất đẳng thức $f_i(x)\le 0$ và $p$ đẳng thức $h_j(x)=0$, mỗi ràng buộc góp một số hạng vào Lagrangian:

$$L(x,\lambda ,\nu )=f_0(x)+{\lambda }_1{f}_1(x)+\cdots +{\lambda }_m{f}_m(x)+{\nu }_1{h}_1(x)+\cdots +{\nu }_p{h}_p(x).$$

Viết gọn:

$$L=f_0+\sum _{i=1}^m{\lambda }_i{f}_i+\sum _{j=1}^p{\nu }_j{h}_j.$$

$i$ chạy qua các bất đẳng thức, $j$ chạy qua các đẳng thức. Tổng của nhóm rỗng bằng 0. Các nhân tử ${\lambda }_i\ge 0$, còn ${\nu }_j\in \mathbb{R}$. Tại , $L\le f_0$. Nếu viết bất đẳng thức theo chiều ngược, quy ước dấu của nhân tử cũng phải đổi.

Lagrangian không tự biến điểm cực tiểu theo $x$ thành nghiệm khả thi. Nó là công cụ tạo cận và điều kiện dừng. vẫn phải được kiểm riêng. Nguồn: Convex Optimization, §5.1.1.

Ví dụ

Với $min(x-2{)}^2$, $x\le 1$: $L(x,\lambda )=(x-2{)}^2+\lambda (x-1)$, $\lambda \ge 0$.

Khi nào cần dùng?

Tạo cận dưới, lập và phân tích độ nhạy.

Câu hỏi ôn lại

Vì sao nhân tử của $x-1\le 0$ không được âm?

Xem đáp án

Vì tại , $\lambda (x-1)$ chỉ chắc chắn không dương khi $\lambda \ge 0$. Đó là bước giữ cận dưới.

Thuật ngữ liên quan

• Điểm và miền khả thi
• Hàm đối ngẫu Lagrange
• Điều kiện KKT