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

Learn & Enjoy …

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

Posted by Trần Quốc Long 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\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^*\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\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)

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

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

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: