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

Learn & Enjoy …

Archive for Tháng Ba, 2008

« 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 »

Thuật toán dò đường và thuật toán dò đường kết hợp đối ngẫu

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

Thay vì tối ưu hóa hàm tiềm năng, trong thuật toán dò đường (primal path following), người ta giải bài toán tối ưu sau

\displaystyle \min B_{\mu}(x) = c^Tx-\mu\sum_{j=1}^n \ln x_j, Ax=b

Để ý rằng ta đã loại bỏ ràng buộc \displaystyle x\geq 0 vì \displaystyle -\ln x_j\rightarrow \infty khi\displaystyle x_j\rightarrow 0 và hàm \displaystyle \ln(x) chỉ có nghĩa khi \displaystyle x>0. Vì thế ta cũng định nghĩa \displaystyle B_{\mu}(x)=\infty khi có \displaystyle j nào đó mà \displaystyle x_j\leq 0. Hàm \displaystyle B_{\mu}(x) còn được gọi là hàm phân cách (barrier function) (do đại lượng \displaystyle -\mu\sum_{j=1}^n \ln x_j phân cách \displaystyle x và biên của đa diện lồi). Đây là bài toán tối ưu phi tuyến khó, người ta thay \displaystyle B_{\mu}(x+d) bằng xấp xỉ Taylor bậc 2

\displaystyle B_{\mu}(x+d)=B_{\mu}(x)+(c^T-\mu e^TX^{-1})d+\frac{1}{2}\mu d^TX^{-2}d

và chuyển bài toán tối ưu thành

\displaystyle \min (c^T-\mu e^TX^{-1})d+\frac{1}{2}\mu d^TX^{-2}d với ràng buộc \displaystyle Ad = 0

Hàm Lagrange tương ứng là

\displaystyle L(d,\lambda)=(c^T-\mu e^TX^{-1})d+\frac{1}{2}\mu d^TX^{-2}d-\lambda^TAd

Đạo hàm theo \displaystyle d,\lambda và gán bằng 0, ta có \displaystyle d,\lambda là nghiệm của hệ phương trình tuyến tính:

\displaystyle \left[\begin{array}{cc}\mu X^{-2}&-A^T\\A&0\end{array}\right] \left[\begin{array}{r}d\\ \lambda\end{array}\right]= \left[\begin{array}{c}\mu X^{-1}e-c\\{0}\end{array}\right]

với \displaystyle e=\left[\begin{array}{ccc}1&\ldots&1\end{array}\right]^T. Như vậy ta có thuật toán dò đường (gốc) như sau:

Đầu vào (input):

  • Các ràng buộc và hàm mục tiêu \displaystyle A,b,c.
  • Nghiệm ban đầu của bài toán gốc và đối ngẫu: \displaystyle x>0,\lambda,s>0.
  • Ngưỡng kiểm tra điều kiện tối ưu \displaystyle \epsilon>0.
  • Các tham số \displaystyle \beta,\alpha,\mu (thường chọn \displaystyle \beta=1/4,\alpha=1-\frac{\sqrt{\beta}-\beta}{\sqrt{\beta}+n},\mu=4\sqrt{||c||^2+M^2} để đảm bảo hội tụ)

Thuật toán dò đường (gốc):

  1. Kiểm tra điều kiện tối ưu \displaystyle s^Tx<\epsilon, nếu đúng thì dừng và thông báo nghiệm \displaystyle x.
  2. Tính các đại lượng
    \displaystyle X=\mathrm{diag}(x_1,\ldots,x_n)
    \displaystyle \mu\leftarrow \alpha\mu
  3. Giải hệ phương trình
    \displaystyle \left[\begin{array}{cc}\mu X^{-2}&-A^T\\A&0\end{array}\right] \left[\begin{array}{r}d\\ \lambda\end{array}\right]= \left[\begin{array}{c}\mu X^{-1}e-c\\{0}\end{array}\right]

    để tìm \displaystyle d, \lambda.

  4. Cập nhật nghiệm
    \displaystyle x\leftarrow x+d
    \displaystyle s\leftarrow c-A^T\lambda
  5. Quay lại bước 1.

Ví dụ:

\displaystyle \min~ -x_1-x_2
\displaystyle \begin{array}{rrr}-x_1&+2x_2&\leq 8\\2x_1&+x_2&\leq 9\\3x_1&-x_2&\leq 6\\x_1,x_2&&\geq 0\end{array}

Quá trình chạy thuật toán dò đường trong ví dụ trên

Một cải tiến quan trọng của thuật toán dò đường là thuật toán dò đường kết hợp đối ngẫu (primal-dual path following). Trong thuật toán này nghiệm của cả hai bài toán gốc và đối ngẫu đều được biến đổi để tối ưu hóa hai mục tiêu: (1) giá trị hàm mục tiêu và (2) giữ cho \displaystyle x và \displaystyle s cách xa biên nếu chưa tới gần nghiệm tối ưu. Như vậy ta đồng thời giải hai bài toán tối ưu:

\displaystyle \min B_{\mu}(x) = c^Tx-\mu\sum_{j=1}^n \ln x_j, Ax=b

\displaystyle \max B_{\mu}^D(\lambda,s) = \lambda^Tb+\mu\sum_{j=1}^n \ln s_j, \lambda^TA+s=c

Giải bài toán tối ưu này dẫn đến hướng cập nhật \displaystyle d_x,d_{\lambda},d_s là nghiệm của hệ phương trình tuyến tính

\displaystyle \left[\begin{array}{ccc}A&0&0\\ 0&A^T&I\\S&0&X\end{array}\right] \left[\begin{array}{r}d_x\\d_{\lambda}\\d_s\end{array}\right]= -\left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe-\mu e\end{array}\right]

với \displaystyle e=\left[\begin{array}{ccc}1&\ldots&1\end{array}\right]^T. Người ta giải điều kiện tối ưu KKT bằng phương pháp Newton nên các hướng này còn được gọi là các hướng Newton. Như vậy ta có thuật toán dò đường (kết hợp đối ngẫu) như sau:

Đầu vào (input):

  • Các ràng buộc và hàm mục tiêu \displaystyle A,b,c.
  • Nghiệm ban đầu của bài toán gốc và đối ngẫu: \displaystyle x>0,\lambda,s>0.
  • Ngưỡng kiểm tra điều kiện tối ưu \displaystyle \epsilon>0.

Thuật toán dò đường (kết hợp đối ngẫu):

  1. Kiểm tra điều kiện tối ưu \displaystyle s^Tx<\epsilon, nếu đúng thì dừng và thông báo nghiệm \displaystyle x.
  2. Tính các đại lượng
    \displaystyle X=\mathrm{diag}(x_1,\ldots,x_n)
    \displaystyle S=\mathrm{diag}(s_1,\ldots,s_n)
    \displaystyle \mu\leftarrow \rho\frac{s^Tx}{n},0<\rho<1
  3. Giải hệ phương trình
    \displaystyle \left[\begin{array}{ccc}A&0&0\\ 0&A^T&I\\S&0&X\end{array}\right] \left[\begin{array}{r}d_x\\d_{\lambda}\\d_s\end{array}\right]= -\left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe-\mu e\end{array}\right]

    để tìm \displaystyle d_x, d_{\lambda},d_s.

  4. Cập nhật nghiệm
    \displaystyle x\leftarrow x+\beta_Pd_x
    \displaystyle \lambda\leftarrow \lambda+\beta_Dd_{\lambda}
    \displaystyle s\leftarrow s+\beta_Dd_s

    với

    \displaystyle \beta_P=\min \left\{1,\alpha \min_{i,d_x^i<0}\frac{x_i}{d_x^i} \right\}
    \displaystyle \beta_D=\min \left\{1,\alpha \min_{i,d_s^i<0}\frac{s_i}{d_s^i} \right\}
    \displaystyle 0<\alpha<1
  5. Quay lại bước 1.

 

Quá trình chạy thuật toán dò đường (kết hợp đối ngẫu) trong ví dụ trên

Code trong Matlab của cả hai thuật toán dò đường, cùng với code chạy thuật toán trên ví dụ ta đã xét ở loạt bài về Phương pháp đơn hình, download ở đây :-)

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

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