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 on 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^*)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

\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^*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 Slaterx^*\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

\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.

Gửi phản hồ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:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: