Tập lồi (2) – Tổ hợp lồi, bao lồi, bao affine, chiều, đơn hình, nón lồi, bao nón « CS Study Fun

Tháng Hai 2008
T2	T3	T4	T5	T6	T7	CN
		Tháng 3 »
	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

Tập lồi (2) – Tổ hợp lồi, bao lồi, bao affine, chiều, đơn hình, nón lồi, bao nón

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

Định nghĩa (tổ hợp lồi): Tổ hợp tuyến tính $\displaystyle\sum_{i=1}^n\lambda_i x_i$ gọi là tổ hợp lồi của $x_1,\ldots,x_n\in\mathbb{R}^n$ nếu

$\lambda_i\geq 0,\forall i, \displaystyle\sum_{i=1}^n\lambda_i=1$

Định lý: Tập $X$ lồi nếu và chỉ nếu nó đóng với phép toán tổ hợp lồi.

Chứng minh:

“ $\Leftarrow$ “: Ta sẽ chứng minh tổ hợp lồi của các điểm trong tập lồi vẫn phải thuộc tập lồi đó. Thật vậy, quy nạp theo $n$ :

Cơ sở: rõ ràng định lý đúng với $n=1,2$ .

Quy nạp: Giả sử định lý đúng với $n=k\geq 2$ . Xét tổ hợp lồi của $k+1$ điểm.

$\displaystyle\sum_{i=1}^{k+1}\lambda_i x_i=\sum_{i=1}^k\lambda_i x_i+\lambda_{k+1}x_{k+1}$

$=\displaystyle\left(\sum_{i=1}^k \lambda_i\right)\sum_{i=1}^k\frac{\lambda_i}{\sum_{i=1}^k\lambda_i}x_i+\lambda_{k+1}x_{k+1}$

Rõ ràng tổ hợp này thuộc vào tập lồi $X$ vì theo giả thiết quy nạp $\sum_{i=1}^k\frac{\lambda_i}{\sum_{i=1}^k\lambda_i}x_i\in X$ .

“ $\Rightarrow$ “: hiển nhiên nếu ta xét $n=2$ .

Định lý (giao của tập lồi): Giao của họ bất kì các tập lồi là tập lồi

Chứng minh: hiển nhiên.

Định nghĩa (bao lồi): Bao lồi của một tập $X\in \mathbb{R}^n$ có thể định nghĩa theo các cách tương đương sau:

Là giao của tất cả các tập lồi chứa $X$ .
Là tập hợp tất cả các tổ hợp lồi của các điểm thuộc $X$ .

Kí hiệu bao lồi của $X$ là $\mathrm{Conv}X$ .

Chứng minh: Đặt $Y=\displaystyle\bigcap_\alpha X_\alpha$ với mọi $X_\alpha$ lồi và $X_\alpha\supset X$ và đặt $Z=\{z:\exists\lambda_i\geq 0,x_i\in X, z=\displaystyle\sum_{i=1}^n\lambda_i x_i, \sum_{i=1}^n\lambda_i=1\}$ .

Rõ ràng $Z$ đóng với phép toán tổ hợp lồi, nên $Z$ lồi và $Z\supset X$ , suy ra $Z\supset Y$ .

Ngược lại, nếu $X_\alpha$ lồi và $X_\alpha\supset X$ thì $X_\alpha$ phải chứa tất cả các tổ hợp lồi của $X$ (vì $X_\alpha$ đóng với phép toán tổ hợp lồi), suy ra $X_\alpha\supset Z$ với mọi $\alpha$ , tức là $Y\supset Z$ . Kết luận $Y=Z$ .

Tương tự như vậy, ta cũng có các định nghĩa về tổ hợp affine và bao affine.

Định nghĩa (tổ hợp affine): Tổ hợp tuyến tính $\displaystyle\sum_{i=1}^n\lambda_i x_i$ gọi là tổ hợp affine của $x_1,\ldots,x_n\in\mathbb{R}^n$ nếu

$\lambda_i\in \mathbb{R},\forall i, \displaystyle\sum_{i=1}^n\lambda_i$

Định lý: Tập $X$ là tập affine nếu và chỉ nếu nó đóng với phép toán tổ hợp affine.

Định nghĩa (bao affine): Bao affine của một tập $X\in \mathbb{R}^n$ có thể định nghĩa theo các cách tương đương sau:

Là giao của tất cả các tập affine chứa $X$ .
Là tập tất cả các tổ hợp affine của các điểm thuộc $X$ .

Kí hiệu bao affine của $X$ là $\mathrm{Aff}X$ .

Định nghĩa (số chiều của tập affine): Số chiều của tập affine $X$ có thể định nghĩa bằng các cách tương đương sau:

Là số chiều của không gian con $L$ gắn với $X$ , tức là $X=a+L$ .
Là số $m$ nhỏ nhất để tồn tại $m+1$ véctơ $x_0,\ldots,x_m$ sao cho $X=\mathrm{Aff}\{x_0,\ldots,x_m\}$ .
Các véctơ này gọi là cơ sở affine của $X$ .

Kí hiệu số chiều của $X$ là $\dim X$ .

Chứng minh: Đặt $k=\dim L$ và $a_1,\ldots,a_k$ là cơ sở của $L$ . Ta sẽ chứng minh $X=\mathrm{Aff}\{a,a+a_1,\ldots,a+a_k\}$ . Thật vậy, nếu $x\in X$ , ta có thể viết $x$ dưới dạng:

$x=a+\displaystyle\sum_{i=1}^k\gamma_i a_i=(1-\sum_{i=1}^k\gamma_i)a+\sum_{i=1}^k\gamma_i(a+a_i)$ ,

tức là $x$ là tổ hợp affine của các véctơ $\{a,a+a_1,\ldots,a+a_k\}$ . Ngược lại, xét một tổ hợp affine bất kì của $\{a,a+a_1,\ldots,a+a_k\}$

$y=\lambda_0 a+\displaystyle\sum_{i=1}^k\lambda_i(a+a_i)=a+\displaystyle\sum_{i=1}^k\lambda_i a_i\in X$

vì $\displaystyle\sum_{i=0}^k\lambda_i=1$ . Vậy $X=\mathrm{Aff}\{a,a+a_1,\ldots,a+a_k\}$ . Suy ra $k\geq m$ .

Để chứng minh $m\geq k$ , ta sẽ chứng minh $L\subset\mathrm{Lin}\{x_1-x_0,\ldots,x_m-x_0\}$ . Thật vậy, vì $L=X-x_0$ nên với mọi véctơ $y\in L$ , ta có $y=x-x_0$ với $x\in X$ . Suy ra

$y=x-x_0=\displaystyle\sum_{i=0}^m\lambda_i x_i -x_0=\sum_{i=1}^m\lambda_i(x_i -x_0)$

vì $\displaystyle\sum_{i=0}^m\lambda_i=1$ . Tức là $y$ là tổ hợp tuyến tính của $\{x_1-x_0,\ldots,x_m-x_0\}$ . Vậy $L\subset\mathrm{Lin}\{x_1-x_0,\ldots,x_m-x_0\}$ . Suy ra $m\geq k$ . Kết luận $k = m$ (lưu ý: có thể chứng minh $L=\mathrm{Lin}\{x_1-x_0,\ldots,x_m-x_0\}$ ).

Định lý (cơ sở của tập affine): Nếu $\{x_0,x_1,\ldots,x_m\}$ là cơ sở affine của tập affine $X$ thì mọi véctơ $x\in X$ chỉ có thể biểu diễn bằng một tổ hợp affine duy nhất của cơ sở này và ta nói các véctơ này độc lập affine với nhau.

Chứng minh: Vì $m$ là số chiều của $X$ nên theo định lý trên, $m$ là số chiều của không gian con $L$ gắn với $X$ . Rõ ràng $L\subset\mathrm{Lin}\{x_1-x_0,\ldots,x_m-x_0\}$ nên $\{x_1-x_0,\ldots,x_m-x_0\}$ chính là cơ sở của $L$ . Với mọi véctơ $x\in X$ , ta có $x=x_0+y$ với $y\in L$ . Véctơ $y$ chỉ có thể biểu diễn bằng một tổ hợp tuyến tính duy nhất của cơ sở của $L$ nên ta suy ra chỉ có một biểu diễn affine duy nhất của $x$ trên cơ sở afffine của $X$ .

Định nghĩa (số chiều của tập bất kì): Số chiều của tập $X$ bất kì là số chiều của bao affine của tập đó.

$\dim X=\dim \mathrm{Aff}X$

Định nghĩa (đơn hình): Đơn hình với các đỉnh $\{x_0,x_1,\ldots,x_m\}$ độc lập affine là bao lồi của các đỉnh này.

$\Delta(x_0,x_1,\ldots,x_m)=\mathrm{Conv}\{x_0,x_1,\ldots,x_m\}$

Ví dụ:

Trong $\mathbb{R}^2$ , điểm, đoạn thẳng, tam giác là các đơn hình.
Trong $\mathbb{R}^n$ với hệ cơ sở chuẩn $\{e_1,\ldots,e_n\}$ . Đơn hình có đỉnh là các véc tơ trong hệ cơ sơ chuẩn chính là tập $\{x:x_i\geq 0,\displaystyle\sum_{i=1}^n x_i=1\}$ .
Trong $\mathbb{R}^n$ , đơn hình có đỉnh $\{0,e_1,\ldots,e_n\}$ chính là tập $\{x:x_i\geq 0,\displaystyle\sum_{i=1}^n x_i\leq 1\}$ .

Định lý: Mọi điểm trong đơn hình $\Delta(x_0,x_1,\ldots,x_m)$ chỉ có thể biểu diễn bằng một tổ hợp lồi duy nhất các đỉnh của nó.

Chứng minh: Vì $\{x_0,x_1,\ldots,x_m\}$ độc lập affine nên tổ hợp lồi của một điểm trong đơn hình cũng là tổ hợp affine duy nhất của điểm đó trong bao affine $\mathrm{Aff}\{x_0,x_1,\ldots,x_m\}$ .

Định nghĩa (nón lồi):

Một tập gọi là nón nếu nó đóng với phép toán co dãn
$X$ là nón nếu và chỉ nếu $\forall x\in X\Rightarrow \lambda x\in X,\lambda\geq 0$ .
Một tập gọi là nón lồi nếu nó vừa là tập lồi vừa là nón.

Ví dụ:

$\mathbb{R}_+^n=\{x\in\mathbb{R}^n:x\geq 0 \}$ là nón lồi.
Nón Lorentz $\mathbb{L}^n=\{x\in\mathbb{R}^n:x_n\geq\sqrt{x_1^2+\ldots+x_{n-1}^2}\}$ là nón lồi.
Tập các ma trận xác định không âm là nón lồi.

Định nghĩa (tổ hợp nón): Tổ hợp tuyến tính $\displaystyle\sum_{i=1}^n\lambda_i x_i$ gọi là tổ hợp nón của $x_1,\ldots,x_n\in\mathbb{R}^n$ nếu

$\lambda_i\geq 0,\forall i, \displaystyle\sum_{i=1}^n\lambda_i$

Định lý: Tập $X$ là nón lồi nếu và chỉ nếu nó đóng với phép toán tổ hợp nón.

Chứng minh:

“ $\Leftarrow$ “: Hiển nhiên, vì $X$ là nón lồi và tổ hợp lồi cũng là tổ hợp nón nên $X$ đóng với phép toán tổ hợp lồi.

“ $\Rightarrow$ “: Nếu $X$ là nón lồi, xét một tổ hợp nón $\displaystyle\sum_{i=1}^n\lambda_i x_i$ bất kì của $X$ . Rõ ràng

$\displaystyle\sum_{i=1}^n\lambda_i x_i=\left(\sum_{i=1}^n\lambda_i\right)\sum_{i=1}^n\frac{\lambda_i}{\sum_{i=1}^n\lambda_i}x_i\in X$

vì $\sum_{i=1}^n\frac{\lambda_i}{\sum_{i=1}^n\lambda_i} x_i\in X$ .

Định nghĩa (bao nón): Bao nón của tập $X$ có thể định nghĩa theo các cách tương đương sau

Là giao của tất cả các nón lồi chứa $X$ .
Là tập hợp của tất cả các tổ hợp nón của các điểm thuộc $X$ .

Kí hiệu bao nón của $X$ là $\mathrm{Cone}X$ .

Bài viết này được đăng vào Tháng Hai 11, 2008 lúc 12:19 sáng và tập tin được lưu ở Giải tích lồi. Tagged: bao affine, bao lồi, bao nón, chiều, nón lồi, tập lồi, Tổ hợp lồi, đơn hình. Bạn có thể theo dõi các phản hồi của bài viết này thông qua RSS 2.0 dòng thông tin. Bạn có thể bỏ qua phần còn lại và gửi phản hồi. Ping đã bị khóa.

Để lại hồi âm

« Tập lồi (1) – Định nghĩa và một số ví dụ

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

	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

Tập lồi (2) – Tổ hợp lồi, bao lồi, bao affine, chiều, đơn hình, nón lồi, bao nón

Để lại hồi âm