CS Study Fun – Khoa học máy tính

Learn & Enjoy …

«
»

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 (P), với mỗi điểm x^*\in S_P, điều kiện KKT (KKT conditions) tương ứng của x^* là tồn tại \lambda^*\geq 0 sao cho

  1. (C1): \nabla f(x^*)+\displaystyle \sum_{i=1}^m\lambda_i\nabla g_i(x^*)\in N_X(x^*)
  2. (C2): \lambda_i^* g_i(x^*)=0,\forall i.

trong đó N_X(x^*) là nón trực giao với nón tâm T_X(x^*) của X tại x^*.

Đị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 (P)

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

Chứng minh (1): Xét hàm Lagrange L(x,\lambda^*). Hàm này là hàm lồi trên X và

\nabla L(x,\lambda^*)=\nabla f(x)+\displaystyle\sum_{i=1}^m\lambda_i^*\nabla g_i(x)

hơn nữa x^* thỏa mãn điều kiện (C1) nên x^* là cực tiểu của hàm L(x,\lambda^*):

L(x,\lambda^*)\geq L(x^*,\lambda^*),\forall x\in X.

Do x^* thỏa mãn điều kiện (C2) nên

L(x^*,\lambda^*)=f(x^*)\geq f(x^*)+\displaystyle \sum_{i=1}^m\lambda_i g_i(x^*)=L(x^*,\lambda),\forall \lambda\geq 0.

Như vậy, (x^*,\lambda^*) là điểm yên ngựa của hàm L(x,\lambda) trên tập X\times\{\lambda\geq 0\}. Suy ra, x^* là nghiệm tối ưu của bài toán quy hoạch (P).

Chứng minh (2):

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

“\Rightarrow“: Giả sử (P) là bài toán quy hoạch lồi thỏa mãn điều kiện Slater và x^*\in S_P là nghiệm tối ưu của (P). Suy ra, tồn tại \lambda^*\geq 0 sao cho (x^*,\lambda^*) là điểm yên ngựa của hàm L(x,\lambda) trên tập X\times\{\lambda\geq 0\}:

L(x,\lambda^*)\geq L(x^*,\lambda^*) \geq L(x^*,\lambda)

Xét hàm Lagrange L(x,\lambda^*). Hàm này là hàm lồi trên X và

\nabla L(x,\lambda^*)=\nabla f(x)+\displaystyle \sum_{i=1}^m\lambda_i^*\nabla g_i(x)

như vậy để L(x,\lambda^*) đạt cực tiểu tại x^* ta phải có

\nabla f(x^*)+\displaystyle \sum_{i=1}^m\lambda_i\nabla g_i(x^*)\in N_X(x^*).

Còn để hàm L(x^*,\lambda),\lambda\geq 0 đạt cực đại tại \lambda^*, do g_i(x^*)\leq 0,\forall i dễ thấy ta phải có

\lambda_i^*g_i(x^*)=0,\forall i.

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

Advertisements

This entry was posted on Tháng Hai 15, 2008 lúc 7:21 chiều and is filed under Quy hoạch lồi, Quy hoạch phi tuyến. Tagged: , , , , , , , , , . You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

Gravatar
WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com ( Đăng xuất /  Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ ( Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter ( Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook ( Đăng xuất /  Thay đổi )

w
Hủy bỏ

Connecting to %s

«
»
 
%d bloggers like this: