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

Learn & Enjoy …

Định lý Caratheodory, Radon, Helley

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

Định lý Caratheodory: Nếu \dim X=m thì mọi điểm x\in\mathrm{Conv}X có thể biểu diễn bằng tổ hợp lồi của không quá m+1 điểm thuộc X.

Chứng minh: Xét x\in\mathrm{Conv}X và giả sử tổ hợp lồi

x=\displaystyle \sum_{i=1}^k\lambda_i x_i, \sum_{i=1}^k\lambda_i=1,\lambda_i>0,x_i\in X

là tổ hợp lồi có số véctơ k nhỏ nhất có thể được của x. Ta sẽ chứng minh k\leq m+1. Thật vậy, giả sử ngược lại, k>m+1, các vectơ \{x_1,\ldots,x_k\} không thể độc lập affine\dim X=m, như vậy, các véctơ \{x_2-x_1,\ldots,x_k-x_1\} không thể độc lập tuyến tính. Tức là tồn tại bộ số (\gamma_2,\ldots,\gamma_k)\neq 0 sao cho

\displaystyle \sum_{i=2}^k\gamma_i(x_i-x_1)=0

Nếu đặt \gamma_1=\displaystyle -\sum_{i=2}^k\gamma_i, ta có

\displaystyle \sum_{i=1}^k\gamma_i x_i=0,\sum_{i=1}^k\gamma_i =0, (\gamma_1,\ldots,\gamma_k)\neq 0

Như vậy, x có thể viết lại như sau

x=\displaystyle \sum_{i=1}^k\lambda_i x_i=\sum_{i=1}^k(\lambda_i+t\gamma_i) x_i=\sum_{i=1}^k\lambda_i(t) x_i

Rõ ràng, với t đủ nhỏ, biểu thức trên vẫn là tổ hợp lồi của x. Tuy nhiên nếu ta chọn

t=\displaystyle\min_{\gamma_i<0}\frac{\lambda_i}{|\gamma_i|}

thì số hệ số dương trong tổ hợp lồi sẽ ít hơn số hệ số dương trong tổ hợp ban đầu, mâu thuẫn với giả thiết k là nhỏ nhất có thể được (Lưu ý: chắc chắn tồn tại i,\gamma_i<0\displaystyle \sum_{i=1}^k\gamma_i =0, (\gamma_1,\ldots,\gamma_k)\neq 0).

Định lý Radon: Một tập có ít nhất n+2 điểm trong \mathbb{R}^n có thể chia thành hai tập con có bao lồi giao nhau.

Chứng minh: Một tập có m \geq n+2 điểm \{x_1, x_2, \ldots, x_m\} không thể độc lập affine, vì thế, tồn tại bộ số (a_1,a_2,\ldots,a_m) \neq 0 sao cho

\displaystyle\sum_{i=1}^m a_i x_i = 0\displaystyle\sum_{i=1}^m a_i = 0.

Đặt I = \{i: a_i > 0\}, J = \{i: a_i \leq 0\}. Ta có

\displaystyle\sum_{i \in I} a_i x_i = -\sum_{j \in J} a_j x_j\displaystyle\sum_{i \in I} a_i = -\sum_{j \in J} a_j.

Suy ra \displaystyle\frac{\sum_{i \in I} a_i x_i}{\sum_{i \in I} a_i} = \frac{-\sum_{j \in J} a_j x_j}{-\sum_{j \in J} a_j} = z. Nghĩa là

z \in  \mathrm{Conv}\{x_i:i \in I\} \cap \mathrm{Conv}\{x_j:i\in J\}.

Định lý Helley. Nếu C_1, C_2, \ldots, C_m là các tập lồi trong \mathbb{R}^n sao cho giao của n+1 tập bất kì đều khác rỗng thì giao của tất cả các tập cũng khác rỗng.

Chứng minh: (Quy nạp theo m)

Cơ sở: Định lý đúng với mọi m \leq n+1.

Quy nạp: Giả sử định lý đúng với m \geq n+1 tập lồi. Xét m+1 tập C_1, C_2, \ldots, C_{m+1} sao cho n+1 tập bất kì giao nhau khác rỗng.

Đặt B_i = \bigcap_{j\neq i}^{m+1} C_i. Theo giả thiết quy nạp, B_i khác rỗng, tức là tồn tại x_i \in B_i. Ta có thể phân chia tập \{x_1, x_2, \ldots, x_{m+1}\} thành hai tập có bao lồi giao nhau (theo định lý Radon). Không mất tính tổng quát, giả sử tồn tại z sao cho

z \in \mathrm{Conv}\{x_1,x_2,\ldots,x_l\}\cap \mathrm{Conv}\{x_{l+1},\ldots,x_{m+1}\}

Ta sẽ chứng minh z \in C_k với mọi k = 1, 2, \ldots, m+1. Thật vậy, nếu k > l, ta có x_i \in C_k, \forall i \leq l, vì thế

z \in \mathrm{Conv}\{x_1,x_2,\ldots,x_l\} \subset C_k.

Ngược lại, nếu k \leq l, ta có x_i \in C_k, \forall i > l, vì thế

z \in  \mathrm{Conv}\{x_{l+1},\ldots,x_{m+1}\} \subset C_k.

Nhận xét:

  1. Các định lý Caratheodory, Radon, Helly là các kết quả rất sâu, là nền móng cho chuyên ngành toán Hình học tổ hợp (Combinatorial Geometry).
  2. Ứng dụng của các định lý này cũng rất rộng rãi, đặc biệt ta sẽ gặp lại chúng ở các bài về Quy hoạch tuyến tính, Hệ bất phương trình tuyến tính. Các định lý này sẽ được ứng dụng để phân tích điều kiện của nghiệm tối ưu.

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: