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

Learn & Enjoy …

Thuật toán giảm tiềm năng (1) – Ý tưởng thiết kế và thuật toán

Posted by Trần Quốc Long on Tháng Ba 3, 2008

Thuật toán giảm tiềm năng (potential reduction algorithm) cũng là một trong các phương pháp điểm trong giải bài toán QHTT. Thuật toán này khắc phục điểm yếu của thuật toán giãn affine là bị “bẫy” khi gần chạm vào biên của đa diện lồi.

Ý tưởng thiết kế: Do “bước nhảy” \displaystyle d^* trong thuật toán giãn affine bị giới hạn khi nghiệm hiện tại \displaystyle x gần chạm đến biên của đa diện lồi, trong thuật toán giảm tiềm năng, người ta đưa thêm vào hàm mục tiêu các số hạng có tác dụng “phạt” khi \displaystyle x gần chạm đến biên của đa diện lồi. Như vậy, \displaystyle x sẽ được giữ càng cách xa biên của đa diện càng tốt nếu \displaystyle x chưa gần với nghiệm tối ưu.

Code trong Matlab của thuật toán giảm tiềm nă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 :-)

\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 giảm tiềm năng trong ví dụ trên

Xét bài toán QHTT ở dạng chuẩn tắc

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

Bài toán đối ngẫu là

\displaystyle \max \{\lambda^Tb:\lambda^TA+s^T=c^T,s\geq 0\}

trong đó ta đã thêm biến bù \displaystyle s\geq 0 (slack variable) để ràng buộc \displaystyle \lambda^TA\leq c^T trở thành ràng buộc đẳng thức. Như vậy, điều kiện để \displaystyle x hoặc \displaystyle \lambda^T tiến đến biên của đa diện là \displaystyle x\rightarrow 0\displaystyle s\rightarrow 0. Người ta xây dựng hàm tiềm năng của hai nghiệm như sau

\displaystyle G(x,s)=q\ln s^Tx-\sum_{j=1}^n\ln x_j-\sum_{j=1}^n\ln s_j

Trong đó có thể hiểu

  • \displaystyle s^Tx=(c^T-\lambda^TA)x=c^Tx-\lambda^Tb chính là khoảng cách đối ngẫu. Vì thế đại lượng \displaystyle q\ln s^Tx dùng để đo độ gần nghiệm tối ưu của \displaystyle x.
  • \displaystyle -\sum_{j=1}^n\ln x_j \rightarrow \infty khi một trong các \displaystyle x_j\rightarrow 0. Đây là đại lượng để phạt khi \displaystyle x_j\rightarrow 0.
  • Tương tự như vậy \displaystyle -\sum_{j=1}^n\ln s_j là đại lượng để phạt khi \displaystyle s_j\rightarrow 0.
  • Tham số \displaystyle q dùng để điều chỉnh tốc độ hội tụ của nghiệm (\displaystyle q lớn là ta muốn coi trọng hàm mục tiêu, \displaystyle q nhỏ là ta muốn coi trọng việc nghiệm cách xa biên của đa diện).

Cũng giống như thuật toán giãn affine, ta cũng tìm hướng \displaystyle d^* trong bài toán tối ưu

\displaystyle \min \{G(x+d,s):Ad=0,||X^{-1}d||^2\leq\beta<1\}

Đây là bài toán quy hoạch phi tuyến khó, ta có thể thay \displaystyle G(x+d,s) bằng xấp xỉ Taylor bậc 1 của nó

\displaystyle G(x+d,s)=\nabla_x G(x,s)^Td+o(||d||^2)

trong đó \displaystyle \nabla_x G(x,s) là gradient của \displaystyle G(x,s) theo biến \displaystyle x. Bài toán tối ưu trở thành

\displaystyle \min \{\nabla_x G(x,s)^Td:Ad=0,||X^{-1}d||^2\leq\beta<1\}

Để ý rằng đây chính là bài toán tối ưu mà ta xét trong thuật toán giãn affine, chỉ có điều ta thay \displaystyle c bằng \displaystyle \widehat{c}=\nabla_x G(x,s) với

\displaystyle \widehat{c}_i=\frac{\partial G(x,s)}{\partial x_i}=\frac{qs_i}{s^Tx}-\frac{1}{x_i}

Nghiệm của bài toán tối ưu trên là

\displaystyle d^*=-\beta X \frac{u}{||u||}

trong đó

\displaystyle u=X(\widehat{c}-A^T(AX^2A^T)^{-1}AX^2 \widehat{c}

\displaystyle =\left(I-XA^T(AX^2A^T)^{-1}AX\right)\left(\frac{q}{s^Tx}Xs-e\right)

với \displaystyle e=\left[\begin{array}{ccc}1&\ldots&1\end{array}\right]^T. Khi đó, giá trị hàm mục tiêu thay đổi một lượng bằng:

\displaystyle c^Td^*=-\beta||u||-O(\beta^2)

Thuật toán giảm tiềm năng hoạt động như sau: Tại mỗi bước, ta xét độ lớn của \displaystyle ||u||

  • Nếu \displaystyle ||u||\geq \gamma thì cập nhật \displaystyle x.
  • Nếu \displaystyle ||u||<\gamma thì cập nhật \displaystyle \lambda,s.

Thuật toán giảm tiềm năng:

Đầu vào (input):

  • Các ràng buộc và hàm mục tiêu \displaystyle A,b,c
  • Nghiệm chấp nhận được ban đầu của hai bài toán: \displaystyle x>0,\lambda,s>0.
  • Ngưỡng kiểm tra điều kiện tối ưu \displaystyle \epsilon.
  • Các tham số \displaystyle \beta,\gamma,q (thường chọn \displaystyle \beta<2/3,\gamma<0.5,q\geq n+\sqrt{n} để đảm bảo hội tụ đến nghiệm tối ưu).

Các bước lặp:

  1. Kiểm tra nếu \displaystyle s^Tx<\epsilon, 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 \bar{A}=(AX)^T(AX^2A^T)^{-1}AX
    \displaystyle u=(I-\bar{A})\left(\frac{q}{s^Tx}Xs-e\right)
    \displaystyle d^*=-\beta X \frac{u}{||u||}
  3. Nếu \displaystyle ||u||\geq \gamma cập nhật
    \displaystyle x\leftarrow x+d^*
  4. Nếu \displaystyle ||u||<\gamma cập nhật
    \displaystyle \lambda\leftarrow \lambda+(AX^2A)^{-1}AX\left(Xs-\frac{s^Tx}{q}e\right)
    \displaystyle s\leftarrow \frac{s^Tx}{q}X^{-1}(u+e)
  5. Quay lại bước 1.

Khởi tạo thuật toán: Ta cần khởi tạo thuật toán bằng các nghiệm \displaystyle x>0,\lambda,s>0, tương tự như việc khởi tạo thuật toán giãn affine, ta có thể thay bài toán gốc và đối ngẫu bằng các bài toán mới có thêm các ràng buộc và biến mới như sau:

Bài toán gốc trở thành

\displaystyle \min ~~c^Tx+M_1x_{n+1}

với ràng buộc

\displaystyle\begin{array}{rrrr}Ax&+(b-Ae)x_{n+1}&&=b\\ (e-c)^Tx&&+x_{n+2}&=M_2\end{array}
\displaystyle x_1,\ldots,x_{n+2}\geq 0

Bài toán đối ngẫu trở thành

\displaystyle \max ~~\lambda^Tb+\lambda_{m+1}M_2

với ràng buộc

\displaystyle \begin{array}{rrrr}\lambda^TA&+\lambda_{m+1}(e-c)^T&+s^T&=c^T\\ p^T(b-Ae)&&+s_{n+1}&=M_1\\ &\lambda_{m+1}&+s_{n+2}&=0\end{array}
\displaystyle s_1,\ldots,s_{n+2}\geq 0

với \displaystyle e>0. Khi đó có thể khởi tạo nghiệm ban đầu là

\displaystyle (x,x_{n+1},x_{n+2})=(e,1,M_2-(e-c)^Te)

\displaystyle (\lambda,\lambda_{m+1},s,s_{n+1},s_{n+2})=(0,-1,e,M_1,1)

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: