Điều kiện KKT

Với bài toán $\underset{x}{min}{f}_0(x)$ có $m$ ràng buộc $f_i(x)\le 0$, đẳng thức $Ax=b$ và các hàm khả vi, KKT gồm , nhân tử không âm, điều kiện bù trừ ${\lambda }_i{f}_i(x)=0$ và điều kiện dừng của . Trong bài toán lồi, KKT đủ cho tối ưu. Để suy ra tính cần, phải có điều kiện phù hợp như .

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
• Tối ưu không ràng buộc và ràng buộc đẳng thứcToán cho AI

Giải thích kỹ thuật

Với $m$ ràng buộc bất đẳng thức, điều kiện dừng cộng một cho mỗi ràng buộc:

$\begin{array}{rl}& 0=\mathrm{\nabla }{f}_0(x)+{\lambda }_1\mathrm{\nabla }{f}_1(x)\\ & +\cdots +{\lambda }_m\mathrm{\nabla }{f}_m(x)+A^T\nu .\end{array}$

Viết gọn:

$0=\mathrm{\nabla }{f}_0(x)+\sum _{i=1}^m{\lambda }_i\mathrm{\nabla }{f}_i(x)+A^T\nu .$

Với các $f_i$ lồi khả vi và đẳng thức affine, nhân tử không âm làm lồi theo $x$. Điều kiện dừng cho biết $x$ cực tiểu Lagrangian. Khả thi và bù trừ đưa giá trị Lagrangian về $f_0(x)$. Vì vậy bằng 0 và nghiệm tối ưu.

là điều kiện đủ cho : Có điểm trong của miền chung, thỏa đẳng thức và thỏa chặt bất đẳng thức. Với điều kiện này và nghiệm đạt, KKT cũng cần. Trong bài không lồi, nghiệm KKT có thể không tối ưu toàn cục. Nguồn: Convex Optimization, §5.2.3 và §5.5.3.

Ví dụ

$min(x-2{)}^2$ với $x\le 1$ có $x^{\star }=1$, ${\lambda }^{\star }=2$. Dừng: $2(1-2)+2=0$. Bù trừ: $2(1-1)=0$.

Khi nào cần dùng?

Chứng nhận nghiệm ràng buộc và lập hệ Newton–KKT.

Câu hỏi ôn lại

${\lambda }_i=0$ có kéo theo $f_i(x)<0$ không?

Xem đáp án

Không. Bù trừ cho phép đồng thời ${\lambda }_i=0$ và $f_i(x)=0$. Chiều chắc chắn là $f_i(x)<0$ kéo theo ${\lambda }_i=0$.

Thuật ngữ liên quan

• Gradient
• Hàm lồi
• Hệ phương trình tuyến tính