Tập Lồi (2) – Tổ Hợp Lồi, Bao Lồi, Bao Affine, Chiều, đơn Hình, Nón Lồi ...

Có thể bạn quan tâm

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