Điều kiện Karush–Kuhn–Tucker

Phát biểu

Xét bài toán $\min f(x)$ với ràng buộc $g_i(x) \le 0\ (i=1,\dots,m)$ và $h_j(x)=0\ (j=1,\dots,p)$, trong đó $f, g_i, h_j$ khả vi. Nếu $x^*$ là cực tiểu địa phương thỏa mãn một điều kiện chính quy ràng buộc, thì tồn tại các nhân tử $\mu_i \ge 0$, $\lambda_j$ sao cho: (tính dừng) $\nabla f(x^*) + \sum_i \mu_i \nabla g_i(x^*) + \sum_j \lambda_j \nabla h_j(x^*) = 0$; (khả thi gốc) $g_i(x^*)\le 0,\ h_j(x^*)=0$; (khả thi đối ngẫu) $\mu_i \ge 0$; (độ lệch bù) $\mu_i g_i(x^*) = 0$ với mọi $i$. Với bài toán lồi, các điều kiện này còn là điều kiện đủ cho cực tiểu toàn cục.

Vì sao đúng?

Tại điểm tối ưu có ràng buộc, ta không thể cải thiện hàm mục tiêu bằng bất kỳ dịch chuyển khả thi nhỏ nào. Tính dừng nói rằng gradient của $f$ bị triệt tiêu chính xác bởi tổ hợp không âm của gradient các ràng buộc đang chặt — điểm đó bị 'ghim' vào biên miền khả thi bởi các lực (nhân tử) chỉ đẩy vào trong. Độ lệch bù nói rằng một ràng buộc chỉ sinh lực ($\mu_i>0$) khi nó thực sự chặt ($g_i(x^*)=0$); ràng buộc còn dư không đóng góp gì.

Chủ đề chứa định lý này

Định lý liên quan

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.