Quy hoạch lồi (5) – Điều kiện Karush-Kuhn-Tucker (KKT)
Posted by Trần Quốc Long trên Tháng Hai 15, 2008
Đ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
:
:
.
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
- (Đ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
.
- (Đ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.
Trả lời