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

Learn & Enjoy …

Archive for the ‘Quy hoạch tuyến tính’ Category

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

Phân tích các phương pháp điểm trong (3) – Trung tuyến (central path)

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

Trong bài này, ta xem xét một khái niệm quan trọng mà các phương pháp điểm trong đều trực tiếp hoặc gián tiếp sử dụng. Đó là khái niệm trung tuyến (central path). Trên thực tế, việc “dò đường” trong các thuật toán dò đường và dò đường kết hợp đối ngẫu chính là việc hướng các nghiệm chấp nhận được (các điểm trong) đi theo trung tuyến này.

Định nghĩa (trung tuyến): Cặp \displaystyle (x_{\mu},s_{\mu}) là điểm thuộc trung tuyến nếu tồn tại \lambda_{\mu} sao cho \displaystyle (x_{\mu},\lambda_{\mu},s_{\mu}) là điểm trong của bài toán QHTT \displaystyle (P),(D) và

\displaystyle (x_{\mu})_i(s_{\mu})_i=\mu,\forall i=1,\ldots,n

với \displaystyle \mu>0.

Tập \displaystyle \mathcal{C}=\{(x_{\mu},s_{\mu}),\forall \mu>0\} gọi là trung tuyến của bài toán QHTT \displaystyle (P),(D).

Nhận xét:

  1. Các điểm \displaystyle (x,s) thuộc đường trung tuyến có tính chất
    \displaystyle x_1s_1 = x_2s_2=\ldots=x_ns_n=\mu=\frac{x^Ts}{n}.

    Nghĩa là khoảng cách đối ngẫu \displaystyle x^Ts được chia đều cho tất cả các biến \displaystyle x_i,s_i,i=1,\ldots,n. Đây chính là lý do tại sao \displaystyle \mathcal{C} được gọi là trung tuyến.
  2. Ta biết khi \displaystyle (x,\lambda,s) tiến dần đến nghiệm tối ưu\displaystyle (x^*,\lambda^*,s^*) thì khoảng cách đối ngẫu \displaystyle x^Ts\rightarrow 0. Nếu \displaystyle x^Ts không được chia đều cho các biến \displaystyle x_i,s_i thì sẽ có \displaystyle x_i,s_i nào đó gần bằng 0. Khi đó nghiệm \displaystyle (x,\lambda,s) ở gần với biên của tập nghiệm chấp nhận được. Kết quả là hướng thay đổi \displaystyle d không thể lớn được (trường hợp thuật toán giãn affine). Chính vì vậy, trong các phương pháp điểm trong, người ta có xu hướng giữ cho nghiệm \displaystyle (x,\lambda,s) ở gần trung tuyến \displaystyle \mathcal{C}.
  3. Ta đã biết, khi \displaystyle x_is_i=\mu,x_i>0,s_i>0,\forall i=1,\ldots,n thì \displaystyle (x,\lambda,s) là nghiệm của hệ phương trình
    \displaystyle \left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe\end{array}\right]=\left[\begin{array}{c}{0}\\{0}\\\mu e\end{array}\right]

    Các kết quả dưới đây sẽ cho thấy \displaystyle (x,s) xác định qua hệ phương trình này là duy nhất với mọi \displaystyle \mu>0 . Nghĩa là trung tuyến \displaystyle \mathcal{C} cũng được định nghĩa một cách duy nhất với mọi bài toán QHTT có chứa điểm trong.

Bổ đề 1: Nếu hai bài toán \displaystyle (P),(D) đều có điểm trong thì tập

\displaystyle \mathcal{F}_M=\{(x,s): x\geq 0,s\geq 0,\exists \lambda: Ax=b,A^T\lambda+s=c, x^Ts\leq M\}

bị chặn với mọi \displaystyle M\geq 0 .

Ý nghĩa: nếu tồn tại điểm trong thì khoảng cách đối ngẫu \displaystyle x^Ts bị chặn dẫn đến \displaystyle (x,s) bị chặn.

Chứng minh: Giả sử \displaystyle (x_I,\lambda_I,s_I) là một điểm trong, tức là

\displaystyle x_I>0, s_I>0, Ax_I=b,A^T\lambda_I+s_I=c.

Với mọi \displaystyle (x,s)\in \mathcal{F}_M, ta có

\displaystyle (x-x_I)^T(s-s_I) = -(x-x_I)^TA^T(\lambda-\lambda_I)=0

do \displaystyle s-s_I=-A^T(\lambda-\lambda_I) và \displaystyle (x-x_I)^TA^T=0. Suy ra

\displaystyle x^Ts_I+x_I^Ts=x^Ts+x_I^Ts_I\leq M+x_I^Ts_I=M'.

Vì \displaystyle x\geq 0,s\geq 0, x_I>0,s_I>0 nên

\displaystyle x_i\leq \frac{M'}{(s_I)_i}, s_i\leq \frac{M'}{(x_I)_i}, \forall i=1,\ldots, n

Nói cách khác, \displaystyle ||x||_{\infty},||s||_{\infty} bị chặn.

Bổ đề 2: Nếu hai bài toán \displaystyle (P),(D) đều có điểm trong và đặt

\displaystyle \mathcal{F}_M' = \{(x,s): x> 0,s> 0,\exists \lambda: Ax=b,A^T\lambda+s=c, f_{\mu}(x,s)\leq M\}

với \displaystyle f_{\mu}(x,s)=x^Ts-\mu\sum_{i=1}^n\ln(x_is_i) thì tồn tại \displaystyle M_l,M_u> 0 sao cho

\displaystyle M_l\leq x_i,s_i\leq M_u,\forall (x,s)\in \mathcal{F}_M',\forall i=1,\ldots,n

Lưu ý: Hàm \displaystyle f_{\mu}(x,s)=x^Ts-\mu\sum_{i=1}^n\ln(x_is_i) là một dạng hàm phân cách mà ta đã biết.

Chứng minh: Ta có

\displaystyle f_{\mu}(x,s)=\mu\left(\sum_{i=1}^n \frac{x_is_i}{\mu}-\ln \frac{x_is_i}{\mu}-1\right)+\mu(n-n\ln\mu)

Đặt \displaystyle g(t) = t - \ln t-1 thì

\displaystyle f_{\mu}(x,s)=\mu\sum_{i=1}^n g\left(\frac{x_is_i}{\mu}\right)+C

với \displaystyle C=\mu(n-n\ln\mu).

Dễ thấy các tính chất của \displaystyle g(t) là

  1. \displaystyle g(t) là hàm lồi chặt trong miền xác định \displaystyle t\in (0,\infty).
  2. \displaystyle g(t)\geq 0,\forall t>0 và \displaystyle g(t)=0\Leftrightarrow t=1.
  3. Khi \displaystyle t\rightarrow 0 hoặc \displaystyle t\rightarrow \infty thì \displaystyle g(t)\rightarrow \infty.

Vì thế ta có

\displaystyle g\left(\frac{x_is_i}{\mu}\right) \leq \frac{M-C}{\mu},\forall i=1,\ldots,n

Do tính chất 3 của \displaystyle g(t), phải tồn tại \displaystyle C_l,C_u> 0sao cho

\displaystyle C_l\leq x_is_i\leq C_u

\displaystyle \Rightarrow x^Ts=\sum_{i=1}^n x_is_i \leq nC_u

Theo bổ đề 1, tồn tại \displaystyle C'> 0 sao cho \displaystyle x_i\leq C', s_i\leq C', suy ra

\displaystyle x_iC'\geq x_is_i\geq C_l \Rightarrow x_i\geq \frac{C_l}{C'}

\displaystyle s_iC'\geq x_is_i\geq C_l \Rightarrow s_i\geq \frac{C_l}{C'}

Vậy nếu đặt \displaystyle M_l=\frac{C_l}{C'}, M_u=C' thì

\displaystyle M_l\leq x_i, s_i\leq M_u.

Định lý (tính duy nhất của \displaystyle (x_{\mu},s_{\mu})): Nếu bài toán QHTT \displaystyle (P),(D) tồn tại điểm trong và \displaystyle \mu>0 thì

  1. Hàm \displaystyle f_{\mu}(x,s) là hàm lồi chặt trên tập
    \displaystyle \mathcal{F}_I = \{(x,s): x> 0,s> 0,\exists \lambda: Ax=b,A^T\lambda+s=c\}.

    là tập các điểm trong của bài toán QHTT.

  2. Điểm trong \displaystyle (x_{\mu},\lambda_{\mu}, s_{\mu}) là nghiệm của hệ phương trình
    \displaystyle \left[\begin{array}{c}Ax-b\\A^T\lambda+s-c\\XSe\end{array}\right]=\left[\begin{array}{c}{0}\\{0}\\\mu e\end{array}\right]

    khi và chỉ khi \displaystyle (x_{\mu},s_{\mu}) chính là điểm cực tiểu của hàm \displaystyle f_{\mu}(x,s) trên \displaystyle \mathcal{F}_I. Vì thế \displaystyle (x_{\mu},s_{\mu}) xác định duy nhất.

Chứng minh (1): Với mọi \displaystyle (x,s)\in \mathcal{F}_I ta có

\displaystyle f_{\mu}(x,s)=x^Ts-\mu\sum_{i=1}^n\ln(x_is_i)
\displaystyle =x_I^Ts+x^Ts_I-x_I^Ts_I-\mu\sum_{i=1}^n\ln x_i-\mu\sum_{i=1}^n\ln s_i

với \displaystyle (x_I,s_I) là một điểm trong nào đó (theo bổ đề 1). Ta có \displaystyle -\ln x_i,-\ln s_i là các hàm lồi chặt. Hàm \displaystyle x_I^Ts+x^Ts_I là hàm tuyến tính theo \displaystyle (x,s) vì thế \displaystyle f_{\mu}(x,s) là hàm lồi chặt trên \displaystyle \mathcal{F}_I.

Chứng minh (2): Ta sẽ chứng minh \displaystyle f_{\mu}(x,s) có cực tiểu duy nhất trên \displaystyle \mathcal{F}_I. Thật vậy, theo bổ đề 2,

\displaystyle f_{\mu}(x,s)=\mu\sum_{i=1}^n g\left(\frac{x_is_i}{\mu}\right)+C\geq C

do \displaystyle g(t)\geq 0,\forall t>0, tức là \displaystyle f_{\mu}(x,s) bị chặn dưới trên \displaystyle \mathcal{F}_I .

Theo bổ đề 2, với mọi \displaystyle M>\inf_{(x,s)\in \mathcal{F}_I}f_{\mu}(x,s), tập

\displaystyle \mathcal{F}_M=\{(x,s)\in F_I:f_{\mu}(x,s)\leq M\}\displaystyle \subset \{(x,s)\in F_I:M_l\leq x_i,s_i\leq M_u\}=B

Ta thấy \displaystyle B là một tập con đóng và bị chặn (compact) của \displaystyle \mathcal{F}_I nên \displaystyle f_{\mu}(x,s) đạt cực tiểu trên \displaystyle B.  Do \displaystyle \mathcal{F}_M\subset B\subset \mathcal{F}_I, Ta có

\displaystyle \inf_{(x,s)\in \mathcal{F}_M}f_{\mu}(x,s)\geq \min_{(x,s)\in B}f_{\mu}(x,s)\geq\inf_{(x,s)\in \mathcal{F}_I}f_{\mu}(x,s)

Nhưng theo định nghĩa \displaystyle \inf_{(x,s)\in \mathcal{F}_M}f_{\mu}(x,s)=\inf_{(x,s)\in \mathcal{F}_I}f_{\mu}(x,s) suy ra \displaystyle \min_{(x,s)\in B}f_{\mu}(x,s)=\inf_{(x,s)\in \mathcal{F}_I}f_{\mu}(x,s). Vậy \displaystyle f_{\mu}(x,s) đạt cực tiểu trên \displaystyle \mathcal{F}_I. Cực tiểu này là duy nhất vì \displaystyle f_{\mu}(x,s) là hàm lồi chặt trên \displaystyle \mathcal{F}_I.

Bây giờ ta sẽ chứng minh điểm cực tiểu của \displaystyle f_{\mu}(x,s) chính là nghiệm \displaystyle (x_{\mu},s_{\mu}) của hệ phương trình trên bằng cách chỉ ra điều kiện KKT của bài toán quy hoạch lồi

\displaystyle \min f_{\mu}(x,s): x>0, s>0, Ax=b,A^T\lambda+s=c

chính là hệ phương trình này. Thật vậy, điều kiện KKT của \displaystyle f_{\mu}(x,s) là tồn tại \displaystyle \alpha\in \mathbb{R}^m ,\beta\in \mathbb{R}^n sao cho

\displaystyle \begin{cases}\nabla_x\left(f_{\mu}(x,s)-\alpha^T(Ax-b)-\beta^T(A^T\lambda+s-c)\right)=0\\ \nabla_{\lambda}\left(f_{\mu}(x,s)-\alpha^T(Ax-b)-\beta^T(A^T\lambda+s-c)\right)=0\\ \nabla_s\left(f_{\mu}(x,s)-\alpha^T(Ax-b)-\beta^T(A^T\lambda+s-c)\right)=0\end{cases}

\displaystyle \begin{cases} s-\mu X^{-1}e=A^T\alpha\\ -A\beta = 0\\ x-\mu S^{-1}e=\beta\end{cases}

Như vậy \displaystyle x-\mu S^{-1}e \in \mathrm{Null} A còn \displaystyle s-\mu X^{-1}e\in \mathrm{Im}A^T, suy ra

\displaystyle (s-\mu X^{-1}e)^T(x-\mu S^{-1}e)=0

do \displaystyle \mathrm{Im}A^T=(\mathrm{Null} A)^{\perp}. Thay \displaystyle x = Xe, s=Se, ta có

\displaystyle (Se-\mu X^{-1}e)^T(Xe-\mu S^{-1}e) =

\displaystyle = (Se-\mu X^{-1}e)^T(X^{1/2}S^{-1/2})(X^{-1/2}S^{1/2})(Xe-\mu S^{-1}e)

\displaystyle =((XS)^{1/2}e-\mu (XS)^{-1/2}e)^T((XS)^{1/2}e-\mu (XS)^{-1/2}e)

\displaystyle =||(XS)^{1/2}e-\mu (XS)^{-1/2}e||^2=0

Suy ra,

\displaystyle (XS)^{1/2}e-\mu (XS)^{-1/2}e=0,

nhân với \displaystyle (XS)^{1/2}, ta được

\displaystyle XSe=\mu e

Ngược lại, khi \displaystyle XSe=\mu e hay \displaystyle x_i s_i=\mu,\forall i = 1,\ldots,n thì ta có

\displaystyle g\left(\frac{x_is_i}{\mu}\right)=g(1)=0

suy ra \displaystyle f_{\mu}(x,s)=C tức là \displaystyle (x,s) là cực tiểu của \displaystyle f_{\mu}(x,s) trên\displaystyle \mathcal{F}_I.

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

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

Đăng bởi tqlong 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) là

  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 và \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) và \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 mà \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) là

\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) là đ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.

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

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