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

Learn & Enjoy …

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

Posted by Trần Quốc Long 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ớin=k\geq 2. Xét tổ hợp lồi củak+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:

  1. Là giao của tất cả các tập lồi chứa X.
  2. 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\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ênZ 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:

  1. Là giao của tất cả các tập affine chứa X.
  2. 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\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:

  1. Là số chiều của không gian con L gắn với X, tức là X=a+L.
  2. 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\dim X.

Chứng minh: Đặt k=\dim La_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

\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)

\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: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ụ:

  1. Trong \mathbb{R}^2, điểm, đoạn thẳng, tam giác là các đơn hình.
  2. 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\}.
  3. 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:\{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):

  1. 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.
  2. 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ụ:

  1. \mathbb{R}_+^n=\{x\in\mathbb{R}^n:x\geq 0 \} là nón lồi.
  2. 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.
  3. 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

\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

  1. Là giao của tất cả các nón lồi chứa X.
  2. 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\mathrm{Cone}X.

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: