Quy hoạch lồi (5) – Điều kiện Karush-Kuhn-Tucker (KKT)

Điều kiện Karush-Kuhn-Tucker: Cho bài toán quy hoạch , với mỗi điểm , điều kiện KKT (KKT conditions) tương ứng của là tồn tại sao cho

1. :
2. : .

trong đó là nón trực giao với nón tâm của tại .

Định lý (điều kiện của nghiệm tối ưu của bài toán quy hoạch lồi): Cho bài toán quy hoạch lồi

1. (Điều kiện đủ) Nếu thỏa mãn điều kiện KKT thì là nghiệm tối ưu của bài toán quy hoạch .
2. (Điều kiện cần và đủ) Nếu là bài toán quy hoạch lồi thỏa mãn điều kiện Slater thì là nghiệm tối ưu của nếu và chỉ nếu thỏa mãn điều kiện KKT.

Chứng minh (1): Xét hàm Lagrange . Hàm này là hàm lồi trên và

hơn nữa thỏa mãn điều kiện nên là cực tiểu của hàm :

.

Do thỏa mãn điều kiện nên

.

Như vậy, là điểm yên ngựa của hàm trên tập . Suy ra, là nghiệm tối ưu của bài toán quy hoạch .

Chứng minh (2):

““: Hiển nhiên theo (1).

““: Giả sử là bài toán quy hoạch lồi thỏa mãn điều kiện Slater và là nghiệm tối ưu của . Suy ra, tồn tại sao cho là điểm yên ngựa của hàm trên tập :

Xét hàm Lagrange . Hàm này là hàm lồi trên và

như vậy để đạt cực tiểu tại ta phải có

.

Còn để hàm đạt cực đại tại , do dễ thấy ta phải có

.

Tức là phải thỏa mãn điều kiện KKT.

Advertisements