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 (2) – Giải điều kiện tối ưu bằng phương pháp Newton

Posted by Trần Quốc Long on Tháng Tư 2, 2008

Ta biết, điều kiện tối ưu của hai bài toán gốc và đối ngẫu \displaystyle (P),(D)

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

Nếu đặt \displaystyle z=\left[\begin{array}{ccc}x&\lambda&s\end{array}\right]^T\displaystyle F(z):\mathbb{R}^{2n+m}\rightarrow \mathbb{R}^{2n+m}

\displaystyle F(z) = \left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe\end{array}\right]

với \displaystyle X=\mathrm{diag}(x), S=\mathrm{diag}(s)\displaystyle e=\left[\begin{array}{ccc}1&\ldots&1\end{array}\right]^T, thì nghiệm tối ưu của bài toán QHTT chính là nghiệm của hệ phương trình

\displaystyle F(z)=F(x,\lambda,s)=0

với điều kiện \displaystyle x,s\geq 0.

Phương pháp Newton tìm nghiệm của hệ phương trình: Giả sử \displaystyle F:\mathbb{R}^n\rightarrow \mathbb{R}^n. Ta cần tìm nghiệm của hệ phương trình

\displaystyle F(x)=(f_1(x),\ldots,f_n(x))=0

Để tìm nghiệm của phương trình này, ta xuất phát từ một điểm \displaystyle x\displaystyle F(x)\neq 0 và điều chỉnh \displaystyle x để \displaystyle F(x) tiến gần đến \displaystyle {0} hơn. Xấp xỉ \displaystyle F(x) bằng chuỗi Taylor bậc 1, ta có

\displaystyle F(x+d)\approx F(x)+\mathbb{J}F(x) d

với \displaystyle \mathbb{J}F(x) là ma trận Jacobian của \displaystyle F(x)

\displaystyle \mathbb{J}F(x) = \left[\begin{array}{ccc}\frac{\partial f_1}{\partial x_1}&\ldots&\frac{\partial f_1}{\partial x_n}\\ \vdots &\ldots&\vdots\\ \frac{\partial f_n}{\partial x_1}&\ldots&\frac{\partial f_n}{\partial x_n}\end{array}\right].

Thay \displaystyle F(x+d)\approx 0, ta có

\displaystyle F(x)+\mathbb{J}F(x) d = 0  hay

\displaystyle d = [\mathbb{J}F(x)]^{-1}(-F(x))

Việc điều chỉnh \displaystyle x theo hướng \displaystyle d như trên gọi là phương pháp Newton giải hệ phương trình. Hướng \displaystyle d còn gọi là hướng Newton.

Áp dụng phương pháp Newton giải điều kiện tối ưu: Ta cần giải hệ phương trình

\displaystyle F(z)=F(x,\lambda,s)=0

Ma trận Jacobian của \displaystyle F(z)

\displaystyle \mathbb{J}F(z)=\left[\begin{array}{ccc}\mathbb{J}_xF(z)&\mathbb{J}_{\lambda}F(z)&\mathbb{J}_sF(z)\end{array}\right].

trong đó

\displaystyle \mathbb{J}_xF(z)=\nabla_x \left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe\end{array}\right] = \left[\begin{array}{c}A\\{0}\\S\end{array}\right],

\displaystyle \mathbb{J}_{\lambda}F(z)=\nabla_{\lambda} \left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe\end{array}\right] = \left[\begin{array}{c}{0}\\A^T\\{0}\end{array}\right],

\displaystyle \mathbb{J}_sF(z)=\nabla_s \left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe\end{array}\right] = \left[\begin{array}{c}{0}\\I\\X\end{array}\right].

Vậy

\displaystyle \mathbb{J}F(z)=\left[\begin{array}{ccc}A&0&0\\{0}&A^T&I\\S&0&X\end{array}\right].

Như vậy, xuất phát từ một điểm \displaystyle z=(x,\lambda,s), hướng Newton là nghiệm của hệ phương trình

\displaystyle \mathbb{J}F(z) d=-F(z)

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

Nhận xét:

  1. Ta đã thấy một phương trình tương tự trong thuật toán dò đường. Phương trình này chỉ khác phương trình trên là thay vì \displaystyle XSe ta có \displaystyle XSe-\mu e với \displaystyle \mu>0. Nghĩa là trong thuật toán dò đường kết hợp đối ngẫu, người ta muốn tìm nghiệm của hệ phương trình
    \displaystyle F(x,\lambda,s) = \left[\begin{array}{c}{0}\\{0}\\\mu e\end{array}\right].

    tức là thay điều kiện \displaystyle x_i^* s_i^*= 0 bằng điều kiện\displaystyle x_i s_i = \mu. Đại lượng \displaystyle \mu vì thế còn gọi là độ giãn biên (barrier parameter) vì khi \displaystyle \mu=0 ta có nghiệm \displaystyle (x,\lambda,s) của phương trình trên nằm trên biên của đa diện lồi còn khi \displaystyle \mu>0 thì \displaystyle (x,\lambda,s)điểm trong của hai bài toán \displaystyle (P),(D). Mấu chốt của thuật toán dò đường kết hợp đối ngẫu là khi \displaystyle \mu\rightarrow 0, nghiệm \displaystyle (x_{\mu},\lambda_{\mu},s_{\mu}) của phương trình trên tiệm cận nghiệm tối ưu \displaystyle (x^*,\lambda^*,s^*) của bài toán QHTT. Hơn nữa, do \displaystyle x>0,s>0 nên \displaystyle \mathbb{J}F(z) khả nghịch (khi \displaystyle A có các dòng (các ràng buộc) độc lập tuyến tính).

  2. Để ý rằng nếu điểm xuất phát \displaystyle (x,\lambda,s) nằm trong tập nghiệm chấp được thì \displaystyle Ax=b,A^T\lambda+s=c, hướng Newton \displaystyle d sẽ là nghiệm của hệ phương trình
    \displaystyle \mathbb{J}F(z)d=\left[\begin{array}{ccc}A&0&0\\{0}&A^T&I\\S&0&X\end{array}\right]\left[\begin{array}{c}d_x\\d_{\lambda}\\d_s\end{array}\right]=-\left[\begin{array}{c}{0}\\{0}\\XSe-\mu e\end{array}\right]

    Vì thế \displaystyle A(x+d_x)=Ax+Ad_x=b, \displaystyle A^T(\lambda+d_{\lambda})+(s+d_s)=c. Tức là \displaystyle (x+d_x,\lambda+d_{\lambda},s+d_s) cũng là nghiệm chấp nhận được.
  3. Một số phương pháp điểm trong không yêu cầu điểm xuất phát là nghiệm chấp nhận được, khi đó người ta thay hệ phương trình bằng hệ
    \displaystyle \mathbb{J}F(z)d=-\left[\begin{array}{c}r_P\\r_D\\XSe-\mu e\end{array}\right]

    rồi cho \displaystyle r_P\rightarrow 0, r_D\rightarrow 0, \mu\rightarrow 0^+.

  4. Phương pháp Newton tìm nghiệm của hệ phương trình là cốt lõi của hầu hết các phương pháp tối ưu hóa hàm nhiều biến có ràng buộc với độ phức tạp đa thức (polynomial complexity), đặc biệt là ở các phương pháp điểm trong giải bài toán quy hoạch tuyến tính, quy hoạch lồi, quy hoạch phi tuyến.

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: