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

Learn & Enjoy …

Posts Tagged ‘định lý đảo’

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

Phân tích các phương pháp điểm trong (1) – Bài toán gốc và bài toán đối ngẫu

Đăng bởi tqlong on Tháng Ba 13, 2008

Ta đã biết, các phương pháp điểm trong chú trọng vào việc giải bài toán QHTT ở dạng chuẩn tắc

\displaystyle \mathrm{Opt}(P)=\min_x \{c^Tx: Ax=b, x\geq 0\} ~~(P)

và bài toán đối ngẫu

\displaystyle \mathrm{Opt}(D)=\max_{\lambda,s} \{\lambda^Tb: A^T\lambda+s=c, s\geq 0\}~~(D)

Ta sẽ xem xét mối quan hệ giữa nghiệm \displaystyle x và \displaystyle (\lambda,s) của hai bài toán này.
Định lý (điều kiện của nghiệm tối ưu): \displaystyle (x^*,\lambda^*,s^*) là nghiệm tối ưu của \displaystyle (P),(D) nếu và chỉ nếu các điều kiện sau đồng thời thỏa mãn

  1. \displaystyle Ax^* = b.
  2. \displaystyle A^T\lambda^* + s^* = c.
  3. \displaystyle (x^*)^Ts^* = 0.
  4. \displaystyle (x^*,s^*)\geq 0.

Lưu ý: Điều kiện (3) và (4) đồng nghĩa với \displaystyle x_i^*s_i^* = 0,\forall i=1,\ldots,n.
Chứng minh:
“\displaystyle \Leftarrow“: Giả sử các điều kiện trên đều được thỏa mãn tại \displaystyle (x^*,\lambda^*,s^*), ta có

\displaystyle 0 = (s^*)^Tx^* = (c-A^T\lambda^*)^Tx^*=c^Tx^*-(\lambda^*)^Tb

Tức là giá trị hàm mục tiêu của hai bài toán \displaystyle (P),(D) tại \displaystyle x^* và \displaystyle (\lambda^*,s^*) bằng nhau. Mặt khác nếu \displaystyle (x,\lambda,s) là nghiệm chấp nhận được bất kì của \displaystyle (P),(D) thì

\displaystyle c^Tx-\lambda^Tb=(c-A^T\lambda)^Tx= s^Tx\geq 0 do \displaystyle (x,s)\geq 0

tức là giá trị hàm mục tiêu của bài toán gốc luôn lớn hơn giá trị hàm mục tiêu của bài toán đối ngẫu. Vì thế \displaystyle (x^*,\lambda^*,s^*) là nghiệm tối ưu của hai bài toán \displaystyle (P),(D).
“\displaystyle \Rightarrow“: Giả sử \displaystyle (x^*,\lambda^*,s^*) là nghiệm tối ưu của hai bài toán \displaystyle (P),(D). Các điều kiện (1),(2),(4) đã được thỏa mãn, ta chỉ cần chứng minh điều kiện (3). Đặt

\displaystyle \mathrm{Opt}(P) = c^Tx^*

là giá trị tối ưu của bài toán gốc. Như vậy bất đẳng thức \displaystyle c^Tx\geq \mathrm{Opt}(P) là hệ quả của hệ bất đẳng thức

\displaystyle \begin{cases}Ax=b\\x\geq 0\end{cases}

Áp dụng định lý Farkas không thuần nhất, ta có, tồn tại \displaystyle \lambda và \displaystyle s\geq 0 sao cho

\displaystyle \begin{cases}A^T\lambda+s=c\\s\geq 0\\\lambda^Tb\geq \mathrm{Opt}(P)\end{cases}

Nghĩa là \displaystyle (\lambda,s) là nghiệm chấp nhận được của của bài toán đối ngẫu \displaystyle (D) mà

\displaystyle \lambda^T b\geq \mathrm{Opt}(P)\geq \mathrm{Opt}(D)\geq \lambda^T b

Suy ra

\displaystyle \lambda^T b = \mathrm{Opt}(P) = \mathrm{Opt}(D) = (\lambda^*)^T b = c^Tx^*
\displaystyle \Rightarrow (s^*)^Tx^*=c^Tx^*-(\lambda^*)^T b = 0

Nhận xét:

  1. Các điều kiện (1), (2), (3), (4) còn có thể được suy ra từ việc áp dụng điều kiện KKT vào bài toán gốc hoặc vào bài toán đối ngẫu.
  2. Ngoài việc thỏa mãn các ràng buộc của bài toán QHTT, điều kiện độ vênh ở các ràng buộc bất đẳng thức bù nhau \displaystyle x_is_i = 0,\forall i=1,\ldots,n là điều kiện cần và đủ của nghiệm tối ưu. Như vậy, với các nghiệm chấp nhận được chưa phải là nghiệm tối ưu ta có \displaystyle x^Ts > 0. Các điểm \displaystyle (x,\lambda,s) mà \displaystyle x_is_i>0,\forall i=1,\ldots,n gọi là các điểm trong.
  3. Các phương pháp điểm trong đều tìm cách giảm đại lượng \displaystyle x^Ts trong quá trình tìm kiếm nghiệm tối ưu. Tức là tìm cách xóa dần tính “không tối ưu” của nghiệm hiện tại.
  4. Chứng minh trên tương tự như chứng minh trong bài Bài toán đối ngẫu nên định lý về tính đối ngẫu của hai bài toán \displaystyle (P),(D) vẫn đúng.

Định lý (điều kiện để tập nghiệm tối ưu bị chặn): Giả sử cả hai bài toán \displaystyle (P),(D) đều thỏa được. Khi đó tập các nghiệm tối ưu của bài toán gốc \displaystyle (P):

\displaystyle \Omega_P = \{x:c^Tx=\mathrm{Opt}(P), Ax=b,x\geq 0,\}

là tập khác rỗng và bị chặn nếu và chỉ nếu bài toán đối ngẫu \displaystyle (D) có điểm trong. Tức là

\displaystyle \exists\lambda, s>0: A^T\lambda+s=c.

Lưu ý: Bài toán đối ngẫu của bài toán đối ngẫu là bài toán gốc nên điều kiện đủ để tập các nghiệm tối ưu của bài toán đối ngẫu \displaystyle (D) là tập khác rỗng và bị chặn là bài toán gốc \displaystyle (P) có điểm trong, tức là

\displaystyle \exists x>0: Ax=b.

Chứng minh:
“\displaystyle \Leftarrow “: Giả sử bài toán đối ngẫu có điểm trong \displaystyle (\lambda,s), xét điểm \displaystyle x_0 là một nghiệm chấp nhận được của bài toán gốc. Xét tập các nghiệm chấp nhận được có giá trị hàm mục tiêu không lớn hơn \displaystyle c^Tx_0:

\displaystyle T = \{x:Ax=b, x\geq 0, c^Tx\leq c^Tx_0\}

Để ý rằng \displaystyle \Omega_P = \{x\in T: c^Tx\leq c^Ty,\forall y\in T\} . Nói cách khác, tập các cực tiểu của \displaystyle c^Tx trên \displaystyle T chính là \displaystyle \Omega_P – tập các nghiệm tối ưu của bài toán \displaystyle (P).Ta có

\displaystyle x\in T\Rightarrow s^Tx = c^Tx-\lambda^Tb\leq c^Tx_0 - \lambda^Tb=s^Tx_0

Do \displaystyle s>0,x\geq 0 nên

\displaystyle x_is_i\leq s^Tx_0,\forall i=1,\ldots,n\displaystyle \Rightarrow x_i\leq \frac{s^Tx_0}{\displaystyle \min_i s_i}, \forall i=1,\ldots,n\displaystyle \Rightarrow \max_i x_i\leq \frac{s^Tx_0}{\displaystyle \min_i s_i}

Tức là \displaystyle \forall x\in T, ||x||_{\infty} bị chặn. Như vậy \displaystyle T là tập khác rỗng (chứa \displaystyle x_0), đóng và bị chặn (compact). Vì thế hàm \displaystyle c^Tx đạt cực tiểu trên \displaystyle T và rõ ràng tập các cực tiểu này chính là \displaystyle \Omega_P. Nghĩa là \displaystyle \Omega_P khác rỗng và bị chặn.
“\displaystyle \Rightarrow“: Giả sử tập \displaystyle\Omega_P khác rỗng và bị chặn. Ta sẽ chứng minh tồn tại điểm trong \displaystyle (\lambda,s) thỏa mãn

\displaystyle \begin{cases}s>0\\A^T\lambda+s=c\end{cases}

Áp dụng định lý đảo tổng quát, ta có hệ bất phương trình trên có nghiệm tương đương với tính vô nghiệm của cả hai hệ bất phương trình sau

\displaystyle \mathcal{T}_1\begin{cases}\alpha\geq 0\\A\beta=0\\ \alpha+\beta=0\\ \displaystyle \sum_{i=1}^n\alpha_i>0\\ \displaystyle\sum_{i=1}^n\beta_ic_i\geq 0\end{cases} \displaystyle\mathcal{T}_2\begin{cases}\alpha\geq 0\\A\beta=0\\ \alpha+\beta=0\\ \displaystyle \sum_{i=1}^n\alpha_i=0\\ \displaystyle\sum_{i=1}^n\beta_ic_i>0\end{cases}

Hệ \displaystyle \mathcal{T}_2 rõ ràng vô nghiệm, còn hệ \displaystyle \mathcal{T}_1 thì tương đương với hệ

\displaystyle \mathcal{T}_1'\begin{cases}\beta\leq 0\\A\beta=0\\ \displaystyle \sum_{i=1}^n\beta_i<0\\c^T\beta\geq 0\end{cases}

Ta sẽ chứng minh khi \displaystyle \Omega_P khác rỗng và bị chặn thì \displaystyle\mathcal{T}_1' vô nghiệm. Thật vậy, giả sử có \displaystyle\beta thỏa mãn \displaystyle\mathcal{T}_1'. Suy ra, với mọi nghiệm tối ưu \displaystyle x\in\Omega_P, ta có \displaystyle x-t\beta\in\Omega_P với mọi \displaystyle t>0 vì

\displaystyle x-t\beta\geq 0 do \displaystyle \beta\leq 0
\displaystyle A(x-t\beta)=Ax-tA\beta=Ax=b
\displaystyle c^T(x-t\beta)=c^Tx-tc^T\beta\leq c^Tx

Mặt khác, \displaystyle \beta\neq 0 vì \displaystyle\sum_{i=1}^n\beta_i<0. Suy ra \displaystyle\Omega_P không bị chặn, mâu thuẫn. Vậy \displaystyle\mathcal{T}_1' vô nghiệm, hay tập nghiệm chấp nhận được của bài toán đối ngẫu chứa điểm trong \displaystyle (\lambda,s) nào đó.

Đăng trong Quy hoạch tuyến tính | Tagged: , , , , , | Leave a Comment »

Quy hoạch lồi (3) – Bài toán đối ngẫu Lagrange

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

Định nghĩa (hàm Lagrange): Cho bài toán quy hoạch

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

hàm Lagrange tương ứng của (P) là

L(x,\lambda)=f(x)+\displaystyle \sum_{i=1}^m\lambda_i g_i(x), (x,\lambda)\in X\times R.

Định nghĩa (bài toán đối ngẫu Lagrange): Cho bài toán quy hoạch (P) và hàm Lagrange L(x,\lambda) của nó. Nếu đặt

\underline{L}(\lambda)=\displaystyle \inf_{x\in X}L(x,\lambda)

thì bài toán đối ngẫu Lagrange của (P) là bài toán

\displaystyle \mathrm{Opt}(D)=\sup_{\lambda\geq 0} \underline{L}(\lambda)=\sup_{\lambda\geq 0}\inf_{x\in X}L(x,\lambda)~~(D).

Nhận xét:

  1. Hàm L(x,\lambda) được định nghĩa trên tập X\times R và không chịu ràng buộc g_i(x)\leq 0,\forall i.
  2. Hàm \underline{L}(\lambda) là hàm của \lambda vì ta lấy giá trị nhỏ nhất củaL(x,\lambda) trên toàn bộ x\in X.
  3. Khi \lambda\geq 0 ta có L(x,\lambda)\leq f(x), \forall x\in X.

Định lý (tính chất đối ngẫu của bài toán quy hoạch lồi):

  1. Với mọi \lambda\geq 0 ta có \underline{L}(\lambda)\leq\mathrm{Opt}(D) và vì thế
    \mathrm{Opt}(D)\leq \mathrm{Opt}(P)
  2. Nếu (P) là bài toán quy hoạch lồi, bị chặn (dưới) và thỏa mãn điều kiện Slater thì (D) giải được và giá trị tối ưu của hai bài toán (P),(D) bằng nhau:
    \mathrm{Opt}(D)= \mathrm{Opt}(P)

Chứng minh (1): Gọi S_P\subset X là tập các nghiệm chấp nhận được của (P), với mọi \lambda \geq 0, ta có

\underline{L}(\lambda)=\displaystyle \inf_{x\in X}L(x,\lambda)\leq \inf_{x\in S_P}L(x,\lambda)\leq \inf_{x\in S_P}f(x)=\mathrm{Opt}(P).

Suy ra

\mathrm{Opt}(D)=\displaystyle \sup_{\lambda\geq 0}\underline{L}(\lambda)\leq \mathrm{Opt}(P).

Chứng minh (2): Vì (P) bị chặn dưới nên có thể đặt \mathrm{Opt}(P) =\displaystyle\inf_{x\in S_P}f(x), ta có hệ bất phương trình

\begin{cases}f(x)<\mathrm{Opt}(P)\\x\in S_P\end{cases}

\Leftrightarrow \begin{cases}f(x)<\mathrm{Opt}(P)\\g_i(x)\leq 0,i=1,\ldots,m\\x\in X\end{cases}

vô nghiệm. Do X lồi, f,g_i,i=1,\ldots,m là các hàm lồi trên X, các ràng buộc thỏa mãn điều kiện Slater nên theo định lý đảo phải tồn tại \lambda^*\geq 0 sao cho

\displaystyle \inf_{x\in X}\left[f(x)+\sum_{i=1}^m\lambda_i^*g_i(x) \right] \geq \mathrm{Opt}(P).

tức là \mathrm{Opt}(P)\leq\underline{L}(\lambda^*)\leq \mathrm{Opt}(D). Theo (1), ta có

\underline{L}(\lambda^*)=\mathrm{Opt}(D)=\mathrm{Opt}(P).

Tức là (D) giải được.

Nhận xét:

  1. Kết quả về tính đối ngẫu ở bài toán quy hoạch lồi không cân xứng như bài toán quy hoạch tuyến tính, tuy nhiên trên thực tế, may mắn là điều kiện Slater thường được thỏa mãn nên khi ứng dụng người ta vẫn ngầm coi điều kiện này thỏa mãn và xây dựng bài toán đối ngẫu Lagrange để giải bài toán gốc.
  2. Thuật ngữ: (1) được gọi là tính đối ngẫu yếu (weak duality), (2) được gọi là tính đối ngẫu mạnh (strong duality) khi bài toán quy hoạch lồi bị chặn thỏa mãn điều kiện Slater.

Đă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