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

Learn & Enjoy …

Posts Tagged ‘cực đại’

« Những bài viết trước

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

Đăng bởi tqlong 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^*) 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.

Đăng trong Quy hoạch lồi, Quy hoạch phi tuyến | Tagged: , , , , , , , , , | Leave a Comment »

Quy hoạch lồi (1) – Bài toán và các khái niệm cơ bản

Đăng bởi tqlong on Tháng Hai 14, 2008

Định nghĩa (Quy hoạch toán học): Bài toán quy hoạch toán học (P) (mathematical programming) là bài toán tìm cực trị

\mathrm{Opt}(P)=\displaystyle \min_x\left\{f(x):\begin{array}{r} g(x)=(g_1(x),\ldots,g_m(x))^T\leq 0\\h(x)=(h_1(x),\ldots,h_k(x))=0\\ x\in X\end{array}\right\}~~(P) ,

trong đó

  1. f(x) gọi là hàm mục tiêu.
  2. g(x)=(g_1(x),\ldots,g_m(x))^T\leq 0 là các ràng buộc bất đẳng thức.
  3. h(x)=(h_1(x),\ldots,h_k(x))=0 là các ràng buộc đẳng thức.
  4. X\subset\mathrm{R}^n là miền xác định.
  5. x\in X thỏa mãn tất cả các ràng buộc gọi là nghiệm chấp nhận được (hoặc gọi tắt là nghiệm).
    Tập tất cả các nghiệm chấp nhận được, S_P, được gọi tắt là tập nghiệm.
    Khi tập nghiệm S_P\neq\emptyset, ta nói (P) thỏa được.
  6. Nếu f(x) bị chặn dưới trên tập nghiệm, ta nói (P) bị chặn.
  7. Giá trị tối ưu của hàm mục tiêu
    \mathrm{Opt}(P)=\displaystyle \inf_{x\in S_P}f(x) nếu (P) thỏa được.
    \mathrm{Opt}(P)=-\infty nếu (P) thỏa được nhưng không bị chặn.
    \mathrm{Opt}(P)=+\infty nếu (P) không thỏa được.
  8. Nghiệm tối ưu của (P) là nghiệm chấp nhận được x^* sao cho f(x^*)=\mathrm{Opt}(P). Bài toán quy hoạch (P) có nghiệm tối ưu gọi là bài toán giải được.

Nhận xét:

  1. Các ràng buộc dạng g(x)\leq f(x), g(x)=f(x) có thể biến thành g(x)-f(x)\leq 0, g(x)-f(x)=0.
  2. Ta cũng có thể phát biểu bài toán tìm cực đại với các khái niệm bị chặn, giá trị tối ưu thay đổi tương ứng.

Định nghĩa (Quy hoạch lồi): Bài toán quy hoạch toán học

\mathrm{Opt}(P) =\displaystyle \min_x\left\{f(x):\begin{array}{r} g(x)=(g_1(x),\ldots,g_m(x))^T\leq 0\\ x\in X\end{array}\right\}~~(P)

gọi là bài toán quy hoạch lồi (convex programming) nếu

  1. X\subset \mathrm{R}^n là tập lồi.
  2. f(x), g_1(x),\ldots,g_m(x) là các hàm lồi.
  3. Không có ràng buộc đẳng thức.

Nhận xét:

  1. Ta có thể đưa vào các ràng buộc đẳng thức, nhưng do tính lồi của hàm h_i(x), hàm này phải là hàm tuyến tính trên X, do đó các điều kiện này tương ứng với việc giới hạn tập nghiệm trên không gian affine con của \mathrm{R}^n, tức là không mất tính tổng quát, về mặt lý thuyết có thể giả sử không có ràng buộc đẳng thức.
  2. Trong thực hành, khi thiết kế thuật toán quy hoạch, không thể không tính đến các ràng buộc đẳng thức, khi đó thường người ta biến đổi thuật toán để nó hoạt động trên không gian affine tương ứng (sử dụng hệ cơ sở affine và các tọa độ trên hệ này).
  3. Vì g_i(x) lồi nên tập \{x:g_i(x)\leq 0\} lồi (xem bài điều kiện cực tiểu của hàm lồi). Như vậy tập nghiệm S_P là tập lồi vì nó là giao của các tập lồi.

Điều kiện Slater: Bài toán quy hoạch lồi (P) thỏa mãn điều kiện Slater (Slater conditions) nếu tồn tại \bar{x}\in X sao cho g_i(\bar{x})<0,\forall i. Tức là các ràng buộc đều thỏa mãn tại \bar{x} bằng bất đẳng thức thật sự.

Đăng trong Quy hoạch lồi, Quy hoạch phi tuyến | Tagged: , , , , , , , , , , | Leave a Comment »

« Những bài viết trước