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 (3) – Trung tuyến (central path)

Posted by Trần Quốc Long trên 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.

This entry was posted on Tháng Tư 3, 2008 lúc 8:45 chiều and is filed under Quy hoạch tuyến tính. Thẻ: , , , . You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, hoặc trackback from your own site.

Bình luận về bài viết này

«
»