Tháng Mười Hai 2009
T2	T3	T4	T5	T6	T7	CN
« Tháng 7
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

Posts Tagged ‘biến đổi’

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

Đăng bởi tqlong 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:

Đa diện lồi là tập đóng, lồi.
$\mathbb{R}^n$ cũng là đa diện lồi khi ta chọn $A=0, b\geq 0$ .
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:

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

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

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$ .
Đặt $P^*=P\cap\mathrm{Im}A^T=\{x\in \mathrm{Im}A^T,Ax\leq b\}$ thì $P=P^*+\mathrm{Null}A$ và $P^*$ 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:

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$ ).
$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

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$ .
Hơn nữa, với $r$ như vậy, với mọi $y\in P, y+tr\in P,\forall t>0$ .
$P=\mathrm{ConvExt}P+\{r:Ar\leq 0\}$ .
Tập $V=\mathrm{Ext}P$ hữu hạn.
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): Vì $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\}$ đỡ $P$ ở $x^*$ , đặ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}$ và $(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:

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=1$ và $I, J$ hữu hạn.
Có thể chứng minh mọi tập có dạng (*) đều là đa diện lồi.
Nếu coi biểu diễn $\{x:Ax\leq b\}$ là 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.
Với tập đóng, lồi và bị chặn, ta đã biết $P=\mathrm{ConvExt}P$ .
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).
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ì

Ảnh của đa diện lồi qua ánh xạ affine ngược cũng là đa diện lồi.
Ảnh của đa diện lồi qua ánh xạ affine cũng là đa diện lồi.
Giao của hai đa diện lồi là đa diện lồi.
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:

Đị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.
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.
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.

Đăng trong Giải tích lồi, Quy hoạch tuyến tính | Tagged: bao lồi, bao nón, biến đổi, biểu diên, cấu trúc, cực tiểu, cực đại, chiếu, Quy hoạch tuyến tính, ràng buộc, siêu phẳng đỡ, tập lồi, tổ hợp nón, đa diện lồi, điểm cực biên, đơn hình, đường thẳng | Leave a Comment »

Tập lồi (3) – Phép toán giữ nguyên tính lồi

Đăng bởi tqlong on Tháng Hai 11, 2008

Định lý: Các phép toán sau đây giữ nguyên tính lồi

Phép giao: Nếu $X_\alpha, \alpha\in\Lambda$ lồi thì $\displaystyle \bigcap_{\alpha\in\Lambda}X_\alpha$ lồi.
Tích Đề-các: Nếu $X_i\subset \mathbb{R}^{n_i},i=1,\ldots,m$ lồi thì $X=X_1\times\ldots\times X_m\subset \mathbb{R}^{n_1+\ldots+n_m}$ lồi.
Tổ hợp tuyến tính: Nếu $X_i\subset \mathbb{R}^n,i=1,\ldots,m$ lồi thì $\lambda_1 X_1+\ldots+\lambda_m X_m$ lồi.
Biến đổi affine: Nếu $X\subset \mathbb{R}^n$ lồi thì tập $Y=\{y:y=Ax+b,x\in X\}$ lồi.
Biến đổi ngược của biến đổi affine: Nếu $X\subset \mathbb{R}^n$ lồi thì tập $Y=\{y:Ay+b\in X\}$ lồi.

Chứng minh (1): hiển nhiên vì giao của các tập chứa đoạn thẳng $\left[x,y \right]$ nếu đoạn thẳng này nằm trong tất cả các tập.

Chứng minh (2): hiển nhiên (dùng định nghĩa).

Chứng minh (3): hiển nhiên (dùng định nghĩa).

Chứng minh (4): Nếu $y_1,y_2\in Y$ , suy ra $y_1=Ax_1+b, y_2=Ax_2+b$ . Nếu $z=\lambda y_1+(1-\lambda)y_2$ thì $z=A(\lambda x_1+(1-\lambda)x_2)+b$ , nghĩa là $z\in Y$ .

Chứng minh (5): Nếu $y_1,y_2\in Y$ , suy ra $x_1=Ay_1+b, x_2=Ay_2+b\in X$ . Nếu $z=\lambda y_1+(1-\lambda)y_2$ thì $Az+b=A(\lambda y_1+(1-\lambda)y_2)+b=\lambda x_1+(1-\lambda)x_2\in X$ , nghĩa là $z\in Y$ .

Ví dụ:

Tập $X=\{x:Ax\leq b\}$ lồi vì $X=\bigcap_i\{a_i^Tx\leq b_i\}$ .
Tập $Y=\{y:\exists x\in X, x\leq y\}$ lồi vì $Y=X+\mathbb{R}_+^n$ .
Tập $Z=\{z:\exists y\in Y, |z_i-y_i|\leq \epsilon,\forall i\}$ lồi vì:
+ Tập $Y_i$ là lân cận $\epsilon$ của phép chiếu $Y$ lên trục $y_i$ là tập lồi.
+ Tập $Z=Y_1\times\ldots\times Y_n$ là tập lồi.

Định lý: Đối với các nón lồi ta có các phép toán sau đây

Giao của các nón lồi là nón lồi.
$\displaystyle \bigcap_{\alpha\in\Lambda}C_\alpha$ là nón lồi nếu $C_\alpha,\alpha\in\Lambda$ là nón lồi
Tổ hợp tuyến tính các nón lồi là nón lồi.
$\displaystyle \sum_{i=1}^n\lambda_i C_i,\lambda_i\in \mathrm{R}$ là nón lồi nếu $C_i,i=1,\ldots,n$ là nón lồi.
Tích Đề-các: Nếu $X_i\subset \mathbb{R}^{n_i},i=1,\ldots,m$ là nón lồi thì $X=X_1\times\ldots\times X_m\subset \mathbb{R}^{n_1+\ldots+n_m}$ là nón lồi.
Biến đổi affine: Nếu $X\subset \mathbb{R}^n$ là nón lồi thì tập $Y=\{y:y=Ax+b,x\in X\}$ là nón lồi.
Biến đổi ngược của biến đổi affine: Nếu $X\subset \mathbb{R}^n$ là nón lồi thì tập $Y=\{y:Ay+b\in X\}$ là nón lồi.

Chứng minh (1): Giao của nón lồi là tập lồi, đồng thời nếu tia $\{\lambda x,\lambda\geq 0\}$ thuộc vào tất cả các nón thì nó thuộc vào giao của các nón.

Chứng minh (2): Tổ hợp nón của các nón lồi là tập lồi (định lý trên). Nếu tia $\{\lambda x,\lambda\geq 0\}$ với $x$ nằm trong tổ hợp nón của các nón lồi rõ ràng cũng nằm trong tổ hợp nón của các nón lồi. Để thấy tổ hợp tuyến tính của các nón lồi cũng là nón lồi, lưu ý rằng nếu $C$ là nón lồi thì $-C$ cũng là nón lồi.

Chứng minh (3),(4),(5): Tương tự như chứng minh (1),(2).

Đăng trong Giải tích lồi | Tagged: biến đổi, tập lồi | Leave a Comment »

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

	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Phân lớp bằng siêu phẳng (1) …
	Khuyen Nguyen trong bài Phân lớp bằng siêu phẳng (1) …
	tqlong trong bài Bất đẳng thức xác suất (1) …
	H.T.D. trong bài Bất đẳng thức xác suất (1) …

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

Learn & Enjoy …

Phân loại

Lưu trữ

Thống kê

Bài gần đây

Lời bình gần đây

Trang

Blogroll

Quản trị

Lịch

Theo dõi

Blog D.Q. Huy

Các phương pháp điểm trong

Xem nhiều nhất

Từ khóa

Posts Tagged ‘biến đổi’

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

Tập lồi (3) – Phép toán giữ nguyên tính lồi