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

Learn & Enjoy …

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

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

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: