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

Learn & Enjoy …

Tập lồi (7) – Cấu trúc của đa diện lồi

Posted by Trần Quốc Long on Tháng Hai 14, 2008

Định nghĩa (đa diện lồi): Tập P=\{x\in \mathbb{R}^n :Ax\leq b\} gọi là đa diện lồi (polyhedra) trong \mathbb{R}^n.

Nhận xét:

  1. Đa diện lồi là tập đóng, lồi.
  2. \mathbb{R}^n cũng là đa diện lồi khi ta chọn A=0, b\geq 0.
  3. Các ràng buộc của bài toán quy hoạch tuyến tính tạo nên đa diện lồi.

Định lý (cấu trúc của đa diện lồi): Đa diện lồi P=\{x\in \mathbb{R}^n :Ax\leq b\} luôn có thể biểu diễn dưới dạng

P=P^*+L

trong đó P^* là tập đóng lồi không chứa đường thẳng, L=\mathrm{Null}A là không gian con của \mathbb{R}^n.

Lưu ý: Nhắc lại khái niệm trong đại số tuyến tính:

  1. \mathrm{Null}A=\{x:Ax=0\} (nhân của ma trận, còn kí hiệu là \mathrm{Ker}A).
  2. \mathrm{Im}A=\{y:y=Ax\} (không gian con tạo bởi các cột của A).
  3. Tính chất: \mathrm{Im}A^T=(\mathrm{Null}A)^\perp.

Chứng minh: Ta sẽ chứng minh theo thứ tự sau

  1. Nếu x\in P, đường thẳng \{x(t):x+th, x\in P,t\in \mathbb{R},h\neq 0\}\subset P nếu và chỉ nếu h\in\mathrm{Null}A.
  2. Đặt P^*=P\cap\mathrm{Im}A^T=\{x\in \mathrm{Im}A^T,Ax\leq b\} thì P=P^*+\mathrm{Null}AP^* không chứa đường thẳng.

Chứng minh (1): Nếu h\in\mathrm{Null}A, ta có A^T(x+th)=A^Tx\leq b,\forall t\in\mathbb{R}.

Ngược lại, nếu A(x+th)\leq b,\forall t, tức là a_i^T(x+th)\leq b_i,\forall i,t (a_i là dòng thứ i của A). Xét 2 trường hợp:

  • a_i^Th>0, rõ ràng khi t\rightarrow \infty ta sẽ có a_i^T(x+th)>b_i.
  • a_i^Th<0 thì khi t\rightarrow -\infty ta cũng có a_i^T(x+th)>b_i.

Vậy chỉ còn khả năng a_i^Th=0,\forall i, tức là h\in\mathrm{Null}A.

Chứng minh (2): Rõ ràng P^*\subset P nên P^*+\mathrm{Null}A\subset P theo (1). Ngược lại, nếu x\in P, chiếu x xuống \mathrm{Im}A^T, ta có

x=y+z, y\in \mathrm{Im}A^T, z\in\mathrm{Null}A

Ta thấy y=x-z nên y\in P theo (1), như vậy y\in P\cap\mathrm{Im}A^T=P^*, suy ra x\in P^*+\mathrm{Null}A. Tức là P\subset P^*+\mathrm{Null}A. Kết luận P=P^*+\mathrm{Null}A.

Để thấy P^* không chứa đường thẳng, để ý rằng P^*\subset P nên mọi đường thẳng trong P^* cũng là đường thẳng trong P, nghĩa là hướng của đường thẳng này nằm trong \mathrm{Null} A, vô lý vì P^* nằm trong không gian trực giao với \mathrm{Null} A.

Nhận xét:

  1. Ta thấy P^* là đa diện lồi trong không gian con của \mathbb{R}^n nên nó cũng là đa diện lồi trong \mathbb{R}^n (ngoài điều kiện Ax\leq b ta thêm vào các điều kiện a_i^Tx\leq 0,-a_i^Tx\leq 0,\forall i).
  2. P không chứa đường thằng nếu và chỉ nếu \mathrm{Null}A=\{0\}.

Định lý (cấu trúc của đa diện lồi có điểm cực biên): Nếu P=\{x\in \mathbb{R}^n :Ax\leq b\} là đa diện lồi không chứa đường thẳng thì P có thể biểu diễn dưới dạng

P=\mathrm{Conv}V+\mathrm{Cone}R

trong đó V=\mathrm{Ext}P hữu hạn, R là tập hữu hạn các véctơ và \mathrm{Cone}R=\{r:Ar\leq 0\}.

Chứng minh: Ta sẽ chứng minh theo thứ tự sau

  1. Nếu r\neq 0 sao cho tồn tại x\in P:x+tr\in P,\forall t>0 thì Ar\leq 0.
  2. Hơn nữa, với r như vậy, với mọi y\in P, y+tr\in P,\forall t>0.
  3. P=\mathrm{ConvExt}P+\{r:Ar\leq 0\}.
  4. Tập V=\mathrm{Ext}P hữu hạn.
  5. Tập \{r:Ar\leq 0\} là tập tất cả các tổ hợp nón của một tập hữu hạn véctơ R=\{r_1,\ldots,r_k\}.

Chứng minh (1): Ta có A(x+tr)\leq b,\forall t>0, tức là a_i^T(x+tr)\leq b_i,\forall i, t>0. Nếu a_i^Tr>0 thì khi t\rightarrow \infty, ta sẽ có a_i^T(x+tr)>b_i. Như vậy, ta phải có a_i^Tr\leq 0,\forall i, tức là Ar\leq 0.

Chứng minh (2):Ar\leq 0, với mọi y\in P, t>0, ta có A(y+tr)\leq Ay\leq b, tức là toàn bộ tia \{y(t)=y+tr,t>0\} \subset P.

Chứng minh (3): Rõ ràng \mathrm{ConvExt}P\subset P nên \mathrm{ConvExt}P+\{r:Ar\leq 0\}\subset P theo (2). Ngược lại, nếu x\in P, ta sẽ chứng minh x\in\mathrm{ConvExt}P+\{r:Ar\leq 0\} bằng quy nạp theo n=\dim P.

Cơ sở: với n=0 tức là P=\{x\} định lý đúng.

Quy nạp: giả sử định lý đúng với n<k, ta sẽ chứng minh định lý cũng đúng với n=k. Thật vậy, chọn một véctơ r\neq 0, r\in\{r:Ar\leq 0\}. Vì P không chứa đường thẳng nên Ar\neq 0 (do \mathrm{Null}A=\{0\} theo định lý trên). Đồng thời, tia \{x(t)=x-tr, t>0\} phải thoát ra khỏi A ở một điểm x^*\in\partial P nào đó, nếu không P sẽ chứa toàn bộ đường thẳng \{x(t)=x+tr,t\in \mathrm{R}\}. Xét siêu phẳng \Pi=\{x:f^Tx=a\} đỡ Px^*, đặt Q=\Pi\cap P. Rõ ràng Q cũng là đa diện lồi, không chứa đường thẳng, theo giả thiết quy nạp điểm x^* phải thuộc vào tập \mathrm{ConvExt}Q+\{r:Ar\leq 0,f^Tr=0\} (do ta thêm một điều kiện f^Tx=a vào đa diện lồi). Rõ ràng

\mathrm{ConvExt}Q\subset\mathrm{ConvExt}P

\{r:Ar\leq 0,f^Tr=0\}\subset\{r:Ar\leq 0\}

tức là x^*\in \mathrm{ConvExt}Q+\{r:Ar\leq 0,f^Tr=0\}\subset\mathrm{ConvExt}P+\{r:Ar\leq 0\}. Suy ra x=x^*+tr \in\mathrm{ConvExt}P+\{r:Ar\leq 0\}.

Chứng minh (4): Kết luận (4) là hệ quả của bổ đề sau đây

Bổ đề (điều kiện cực biên của đa diện lồi): Nếu x là điểm cực biên của P, trong các ràng buộc được kích hoạt tại x, phải có n ràng buộc độc lập tuyến tính, tức là có

a_{i_1}^Tx=b_{i_1},\ldots,a_{i_n}^Tx=b_{i_n}(a_{i_1},\ldots,a_{i_n}) độc lập tuyến tính.

Chứng minh: Thật vậy, giả sử ngược lại, chỉ có k<n ràng buộc độc lập tuyến tính. Như vậy, tồn tại véctơ h\neq 0 sao cho h trực giao với tất cả a_{i_j} của các ràng buộc được kích hoạt tại x. Xét điểm x(\epsilon)=x+\epsilon h, \epsilon\in \mathbb{R} . Rõ ràng, các ràng buộc được kích hoạt tại x vẫn được kích hoạt tại x(\epsilon), ngoài ra, với |\epsilon|>0 đủ nhỏ, các ràng buộc không được kích hoạt tại x vẫn được thỏa mãn tại x(\epsilon), như vậy x+\epsilon h,x-\epsilon h\in P với |\epsilon|>0 đủ nhỏ, tức là x không phải là điểm cực biên, mâu thuẫn.

Do số lượng các bộ n ràng buộc trong m ràng buộc (m là số dòng của ma trận A) là \mathrm{C}_n^m hữu hạn nên số điểm cực biên, |\mathrm{Ext}P|, cũng là hữu hạn.

Chứng minh (5): Để chứng minh kết luận (5) ta cũng dùng cách quy nạp như chứng minh (3), tuy nhiên, ta không chọn siêu phẳng đỡ bất kì mà chọn siêu phẳng \Pi_i tạo bởi một điều kiện a_i^Tx\leq b_i bị kích hoạt tại x^* (tại x^*\in\partial P phải có điều kiện được kích hoạt, nếu không nó phải nằm trong \mathrm{rint}P). Theo giả thiết quy nạp,

x^* \in \mathrm{Conv}Ext(\Pi_i\cap P)+\mathrm{Cone}R_i

với R_i là tập hữu hạn. Như vậy

x=x^*+th\in\mathrm{Conv}\mathrm{Ext}(\Pi_i\cap P)+\mathrm{Cone}(R_i\cup\{r\}).

Do số ràng buộc, m, là hữu hạn nên nếu ta đặt R=\displaystyle\cup_{i=1}^m  R_i\cup\{r\}, thì

x\in\mathrm{Conv}\mathrm{Ext}P+\mathrm{Cone}R.

Nhận xét:

  1. Qua hai định lý trên, tổng hợp lại, ta luôn có khẳng định sau: Đa diện lồi P=\{x:Ax\leq b\} luôn có thể viết dưới dạng
    P=\mathrm{Conv}V+\mathrm{Cone}R=\left\{\displaystyle \sum_{i=1}^I\lambda_i v_i+\sum_{j=1}^J\mu_j r_j\right\} (*)

    trong đó \lambda_i,\mu_j\geq 0, \displaystyle \sum_{i=1}^I\lambda_i=1I, J hữu hạn.

  2. Có thể chứng minh mọi tập có dạng (*) đều là đa diện lồi.
  3. Nếu coi biểu diễn \{x:Ax\leq b\}biểu diễn từ phía ngoài (A,b ràng buộc P) thì biểu diễn (*) là biểu diễn từ phía trong, nghĩa là trong P có một số hữu hạn véctơ mà tất cả các véctơ khác có thể biểu diễn bằng các véctơ này.
  4. Với tập đóng, lồi và bị chặn, ta đã biết P=\mathrm{ConvExt}P.
  5. Hai cách biểu diễn như vậy giúp hiểu rõ cấu trúc của đa diện lồi, đồng thời còn giúp trả lời các vấn đề mà nếu chỉ sử dụng biểu diễn ngoài rất khó giải thích (xem tiếp ở dưới).
  6. Bổ đề về điều kiện cực biên của đa diện lồi là cơ sở của phương pháp đơn hình giải bài toán quy hoạch tuyến tính.

Định lý (các phép biến đổi đa diện lồi): Nếu P là đa diện lồi thì

  1. Ảnh của đa diện lồi qua ánh xạ affine ngược cũng là đa diện lồi.
  2. Ảnh của đa diện lồi qua ánh xạ affine cũng là đa diện lồi.
  3. Giao của hai đa diện lồi là đa diện lồi.
  4. Tổng của hai đa diện lồi là đa diện lồi (hay tổng quát hơn tổ hợp tuyến tính các đa diện lồi cũng là đa diện lồi).

Chứng minh: (1) và (3) là hệ quả trực tiếp của biểu diễn ngoài, (2) và (4) là hệ quả trực tiếp của biểu diễn trong vì đây là các phép toán biến đổi tập lồi và nón lồi (Lưu ý, rất khó chứng minh (2) và (4) nếu chỉ sử dụng biểu diễn ngoài).

Định lý (hàm tuyến tính bị chặn đạt cực trị trong đa diện lồi): Nếu hàm tuyến tính bị chặn trên (chặn dưới) trong đa diện lồi P thì nó đạt cực đại (cực tiểu) trong đa diện lồi đó.

Chứng minh: Nếu f^Tx bị chặn trên trong đa diện lồi P=\mathrm{Conv}V+\mathrm{Cone}R thì với mọi r\in\mathrm{Cone}R ta phải có f^Tr\leq 0. Thật vậy, nếu f^Tr>0, rõ ràng với mọi x\in P ta có f^T(x+tr) không bị chặn khi t\rightarrow \infty. Suy ra, với mọi x\in P, x=\displaystyle \sum_{i=1}^I\lambda_i v_i+r, r\in\mathrm{Cone}R ta có

\displaystyle f^T x=\sum_{i=1}^I\lambda_i f^Tv_i+f^Tr\leq\sum_{i=1}^I\lambda_i f^Tv_i\leq\max_{v_i\in V}f^Tv_i

Tức là cực đại của f^Tx trên V cũng là cực đại của f^Tx trên P.

Nhận xét:

  1. Định lý đảm bảo bài toán quy hoạch tuyến tính luôn có nghiệm nếu hàm mục tiêu bị chặn.
  2. Khi P không chứa đường thẳng, cực đại của hàm mục tiêu luôn có thể đạt được ở một trong các điểm cực biên.
  3. Với bài toán quy hoạch tuyến tính ở dạng chuẩn tắc
    \displaystyle \mathrm{Opt}(P)=\max \{c^Tx: Ax=b,x\geq 0\}

    các ràng buộc tạo nên tập nghiệm luôn có điểm cực biên (không chứa đường thẳng) vì các biến đều có ràng buộc không âm.

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: