Bài giảng 7: Tổ Hợp Lồi

(Nếu công thức chưa load được hoặc mờ, các bạn ấn refresh để công thức hiện và rõ nét hơn nhé!)

Bài trước chúng ta đã xét các tổ hợp tuyến tính đặc biệt dưới dạng $c_1\mathbf{v}_1+c_2\mathbf{v}_2+\cdots+c_k\mathbf{v}_k$ , trong đó $c_1+c_2+\cdots+c_k=1$ . Bài này giới hạn thêm các hệ số (trọng số) phải không âm.

Định Nghĩa

Một tổ hợp lồi của các điểm  trong  là một tổ hợp tuyến tính có dạng:



sao cho:
 và  với mọi . Tập hợp tất cả các tổ hợp lồi của các điểm trong một tập  được gọi là bao lồi của , ký hiệu là conv .

Bao lồi của một điểm duy nhất $\mathbf{v}_1$ chỉ là tập $\{\mathbf{v}_1\}$ , giống như bao afin. Trong các trường hợp khác, bao lồi sẽ nằm đúng bên trong bao afin. Hãy nhớ rằng bao afin của hai điểm phân biệt $\mathbf{v}_1$ và $\mathbf{v}_2$ là đường thẳng:

$\mathbf{y}=(1-t)\mathbf{v}_1+t\mathbf{v}_2,\qquad t\in\mathbb{R}$

Do các hệ số trong tổ hợp lồi phải không âm, các điểm thuộc conv $\{\mathbf{v}_1,\mathbf{v}_2\}$ có thể được viết thành:

$\mathbf{y}=(1-t)\mathbf{v}_1+t\mathbf{v}_2,\qquad 0\leq t\leq 1$

đây chính là đoạn thẳng nối giữa $\mathbf{v}_1$ và $\mathbf{v}_2$ , được ký hiệu là $\overline{\mathbf{v}_1\mathbf{v}_2}$ .

Nếu một tập $S$ là afin độc lập, và nếu $\mathbf{p}\in\text{aff}\,S$ , thì $\mathbf{p}\in\text{conv}\,S$ khi và chỉ khi các tọa độ barycentric của $\mathbf{p}$ đều không âm. Ví dụ 1 minh họa một tình huống đặc biệt trong đó tập $S$ còn hơn cả afin độc lập.

Ví dụ 1: Cho

$\mathbf{v}_1=\begin{bmatrix}3\\0\\6\\-3\end{bmatrix},\,\mathbf{v}_2=\begin{bmatrix}-6\\3\\3\\0\end{bmatrix},\,\mathbf{v}_3=\begin{bmatrix}3\\6\\0\\3\end{bmatrix},\,\mathbf{p}_1=\begin{bmatrix}0\\3\\3\\0\end{bmatrix},\,\mathbf{p}_2=\begin{bmatrix}-10\\5\\11\\-4\end{bmatrix},$

và $S=\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\}$ . Lưu ý rằng $S$ là một tập trực giao. Xác định xem $\mathbf{p}_1$ có nằm trong Span $S$ , aff $S$ , và conv $S$ hay không. Sau đó làm điều tương tự cho $\mathbf{p}_2$ .

Giải: Nếu $\mathbf{p}_1$ ít nhất là một tổ hợp tuyến tính của các điểm trong $S$ , thì các hệ số rất dễ tìm vì $S$ là một tập trực giao. Gọi $W$ là không gian con được sinh bởi $S$ . Một phép tính tương tự cho thấy rằng phép chiếu vuông góc của $\mathbf{p}_1$ lên $W$ chính là $\mathbf{p}_1$ :

$\text{proj}_W\mathbf{p}_1=\frac{\mathbf{p}_1\cdot\mathbf{v}_1}{\mathbf{v}_1\cdot\mathbf{v}_1}\mathbf{v}_1+\frac{\mathbf{p}_1\cdot\mathbf{v}_2}{\mathbf{v}_2\cdot\mathbf{v}_2}\mathbf{v}_2+\frac{\mathbf{p}_1\cdot\mathbf{v}_3}{\mathbf{v}_3\cdot\mathbf{v}_3}\mathbf{v}_3=\frac{18}{54}\mathbf{v}_1+\frac{18}{54}\mathbf{v}_2+\frac{18}{54}\mathbf{v}_3$

$=\frac{1}{3}\begin{bmatrix}3\\0\\6\\-3\end{bmatrix}+\frac{1}{3}\begin{bmatrix}-6\\3\\3\\0\end{bmatrix}+\frac{1}{3}\begin{bmatrix}3\\6\\0\\3\end{bmatrix}=\begin{bmatrix}0\\3\\3\\0\end{bmatrix}=\mathbf{p}_1$

Điều này cho thấy rằng $\mathbf{p}_1$ nằm trong Span $S$ . Hơn nữa, vì tổng các hệ số bằng 1 nên $\mathbf{p}_1$ cũng nằm trong aff $S$ . Thực tế, $\mathbf{p}_1$ nằm trong conv $S$ , vì các hệ số cũng không âm.

Đối với $\mathbf{p}_2$ , một phép tính tương tự cho thấy rằng $\text{proj}_W\mathbf{p}_2\ne\mathbf{p}_2$ . Vì $\text{proj}_W\mathbf{p}_2$ là điểm gần nhất trong Span $S$ tới $\mathbf{p}_2$ , nên $\mathbf{p}_2$ không nằm trong Span $S$ . Do đó, $\mathbf{p}_2$ cũng không thể nằm trong aff $S$ hoặc conv $S$ .

Nhớ rằng một tập hợp $S$ là afin nếu nó chứa tất cả các đường thẳng được xác định bởi các cặp điểm trong $S$ . Khi ta chỉ xét đến các tổ hợp lồi, điều kiện thích hợp cần xem xét là các đoạn thẳng thay vì các đường thẳng.

Định Nghĩa

Một tập hợp  được gọi là lồi nếu với mọi , đoạn thẳng nối  và  (ký hiệu là ) nằm hoàn toàn trong .

Hiểu một cách trực quan, một tập hợp $S$ là lồi nếu bất kỳ hai điểm nào trong tập đều có thể “nhìn thấy nhau” mà đường thẳng nối giữa chúng không rời khỏi tập hợp đó. Hình 1 minh họa cho ý tưởng này.

Kết quả tiếp theo tương tự như định lý 2 đối với các tập hợp afin.

Định Lý 7
Một tập hợp  là lồi nếu và chỉ nếu mọi tổ hợp lồi của các điểm trong  đều nằm trong . Nói cách khác,  là lồi khi và chỉ khi .

Chứng minh: Lập luận tương tự như chứng minh định lý 2. Khác biệt duy nhất nằm ở bước quy nạp. Khi xét một tổ hợp lồi của $k+1$ điểm, ta xét $\mathbf{y}=c_1\mathbf{v}_1+\dots+c_k\mathbf{v}_k+c_{k+1}\mathbf{v}_{k+1}$ trong đó $c_1+\dots+c_{k+1}=1$ và $0\leq c_i\leq 1$ với mọi $i$ . Nếu $c_{k+1}=1$ , thì $\mathbf{y}=\mathbf{v}_{k+1}$ , rõ ràng thuộc $S$ , không cần chứng minh thêm. Nếu $c_{k+1}<1$ , đặt $t=c_1+\dots+c_k=1-c_{k+1}>0$ . Khi đó:

(1) $\begin{equation*}\mathbf{y}=(1-c_{k+1})\left(\frac{c_1}{t}\mathbf{v}_1+\dots+\frac{c_k}{t}\mathbf{v}_k\right)+c_{k+1}\mathbf{v}_{k+1}\end{equation*}$

Theo giả thiết quy nạp, điểm $\mathbf{z}=\left(\frac{c_1}{t}\right)\mathbf{v}_1+\dots+\left(\frac{c_k}{t}\right)\mathbf{v}_k$ thuộc $S$ vì các hệ số không âm và tổng là 1. Do đó, phương trình trên biểu diễn $\mathbf{y}$ là tổ hợp lồi của hai điểm trong $S$ . Theo nguyên lý quy nạp, mọi tổ hợp lồi của các điểm như vậy đều nằm trong $S$ .

Định lý 9 dưới đây cung cấp một mô tả mang tính hình học hơn về bao lồi của một tập hợp. Tuy nhiên, trước đó ta cần một kết quả sơ bộ về giao của các tập hợp. Nhớ lại rằng giao của hai không gian con cũng là một không gian con. Thật vậy, giao của bất kỳ họ nào gồm các không gian con cũng là một không gian con. Một kết quả tương tự cũng đúng đối với tập hợp afin và tập hợp lồi.

ĐỊNH LÝ 8
Cho một tập hợp các tập lồi . Khi đó, giao của tất cả các tập trong tập hợp này cũng là một tập lồi, tức là:  là một tập lồi.

Tương tự, nếu  là một tập hợp các tập afin, thì  là một tập afin.

Chứng minh: Giả sử $\mathbf{p}$ và $\mathbf{q}$ là hai điểm thuộc $\cap S_\alpha$ , nghĩa là $\mathbf{p}$ và $\mathbf{q}$ đều nằm trong mỗi tập $S_\alpha$ . Vì mỗi $S_\alpha$ là một tập lồi, nên đoạn thẳng nối giữa $\mathbf{p}$ và $\mathbf{q}$ cũng nằm trong $S_\alpha$ . Do đó, đoạn thẳng này nằm trong giao của tất cả các $S_\alpha$ . Vậy nên, $\cap S_\alpha$ là tập lồi. Lập luận tương tự áp dụng cho các tập afin để chứng minh rằng giao của các tập afin cũng là một tập afin.

Định lý 9
Với bất kỳ tập hợp nào , bao lồi của , ký hiệu là conv , chính là giao của tất cả các tập lồi chứa .

Chứng minh: Gọi $T$ là giao của tất cả các tập lồi chứa $S$ . Vì conv $S$ là một tập lồi và chứa $S$ , nên suy ra $T\subseteq\text{conv}\,S$ . Mặt khác, giả sử $C$ là một tập lồi bất kỳ chứa $S$ . Theo định lý 7, $C$ phải chứa mọi tổ hợp lồi của các điểm thuộc $C$ , do đó $C$ cũng chứa mọi tổ hợp lồi của các điểm trong tập con $S$ . Nói cách khác $\text{conv}\,S\subseteq C$ Vì điều này đúng với mọi tập lồi $C$ chứa $S$ , nên nó cũng đúng với giao của tất cả các tập như vậy. Tức là: $\text{conv}\,S\subseteq T$ . Từ hai điều trên, ta kết luận $\text{conv}\,S=T$ .

Định lý 9 cho thấy rằng conv $S$ là theo một nghĩa tự nhiên là tập lồi “nhỏ nhất” chứa $S$ . Ví dụ: giả sử một tập $S$ nằm bên trong một hình chữ nhật lớn trong $\mathbb{R}^2$ , và bạn tưởng tượng một sợi dây thun được quấn quanh bên ngoài $S$ . Khi sợi dây co lại quanh $S$ , nó tạo thành ranh giới của bao lồi của $S$ . Hoặc theo cách so sánh khác, bao lồi của $S$ lấp đầy mọi khoảng trống bên trong tập hợp $S$ và làm đầy tất cả các vết lõm ở biên của nó.

Ví dụ 2:

a) Bao lồi của hai tập $S$ và $T$ trong $\mathbb{R}^2$ được minh họa bên dưới.

b) Gọi $S$ là tập hợp gồm các vector đơn vị chuẩn trong $\mathbb{R}^3$ , tức là $S=\{\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3\}$ . Khi đó, bao lồi của $S$ là một mặt tam giác trong không gian $\mathbb{R}^3$ , với các đỉnh là $\mathbf{e}_1,\mathbf{e}_2$ , và $\mathbf{e}_3$ . Xem hình 2.

Ví dụ 3: Gọi $S=\left\{\begin{bmatrix}x\\y\end{bmatrix}:x\geq 0,\quad y=x^2\right\}$ . Chứng minh rằng bao lồi của $S$ là hợp của gốc tọa độ và tập hợp $\left\{\begin{bmatrix}x\\y\end{bmatrix}:x>0,\quad y\geq x^2\right\}$ . Xem hình 3.

Giải: Mỗi điểm trong conv $S$ phải nằm trên một đoạn thẳng nối hai điểm trong $S$ . Đường nét đứt trong hình 3 cho thấy rằng, trừ gốc tọa độ ra, trục $y$ dương không nằm trong conv $S$ , bởi vì gốc tọa độ là điểm duy nhất của $S$ nằm trên trục $y$ . Thoạt nhìn, có vẻ hợp lý khi cho rằng hình 3 thể hiện đúng conv $S$ , nhưng làm sao chắc được rằng một điểm như $(10^{-2},10^4)$ , chẳng hạn, nằm trên một đoạn thẳng từ gốc tọa độ đến một điểm thuộc đường cong trong $S$ ?

Xét một điểm bất kỳ $\mathbf{p}$ nằm trong vùng tô bóng của hình 3, giả sử:

$\mathbf{p}=\begin{bmatrix}a\\b\end{bmatrix}$ với $a>0$ và $b\geq a^2$

Đường thẳng đi qua $(0,0)$ và $\mathbf{p}$ có phương trình $y=(b/a)t$ , với $t$ là biến số thực. Đường thẳng này cắt tập $S$ tại điểm $(t,t^2)$ khi $(b/a)t=t^2\Rightarrow t=b/a$ . Vì vậy, $\mathbf{p}$ nằm trên đoạn thẳng nối từ gốc tọa độ đến điểm $\begin{bmatrix}b/a\\b^2/a^2\end{bmatrix}$ thuộc đường cong $S$ , điều này chứng minh hình (3) .

Định lý sau đây là cơ bản trong việc nghiên cứu các tập lồi. Nó được chứng minh lần đầu tiên bởi Constantin Carathéodory vào năm 1907. Nếu một điểm $\mathbf{p}$ nằm trong bao lồi của tập $S$ , thì theo định nghĩa, $\mathbf{p}$ phải là một tổ hợp lồi của các điểm trong $S$ . Tuy nhiên, định nghĩa này không quy định rõ cần bao nhiêu điểm của $S$ để tạo nên tổ hợp lồi đó. Định lý đáng chú ý của Carathéodory nói rằng: Trong một không gian nn-chiều, số điểm của $S$ cần thiết trong tổ hợp lồi đó không bao giờ vượt quá $n+1$ .

Định lý 10 (caratheodory)

Nếu  là một tập con khác rỗng của , thì mọi điểm trong conv  đều có thể được biểu diễn dưới dạng một tổ hợp lồi của không quá  điểm thuộc .

Chứng minh: Cho $\mathbf{p}\in\text{conv}\,S$ , ta có thể viết $\mathbf{p}=c_1\mathbf{v}_1+\cdots+c_k\mathbf{v}_k$ , trong đó $\mathbf{v}_i\in S$ , $c_1+\cdots+c_k=1$ , và $c_i\geq 0$ , với một số $k$ và $i=1,\ldots,k$ . Mục tiêu là chứng minh rằng tồn tại một biểu thức như vậy cho $\mathbf{p}$ với $k\leq n+1$ .

Nếu $k>n+1$ , thì tập $\{\mathbf{v}_1,\ldots,\mathbf{v}_k\}$ là phụ thuộc afin. Do đó, tồn tại các hệ số $d_1,\ldots,d_k$ , không phải tất cả đều bằng 0, sao cho:

$\sum_{i=1}^{k}d_{i}\mathbf{v}_1=\mathbf{0}$ và $\sum_{i=1}^{k}d_{i}=0$

Xét hai phương trình:

$c_1\mathbf{v}_1+c_2\mathbf{v}_2+\cdots+c_k\mathbf{v}_k=\mathbf{p}$

và

$d_1\mathbf{v}_1+d_2\mathbf{v}_2+\cdots+d_k\mathbf{v}_k=\mathbf{0}$

Bằng cách trừ đi một bội số thích hợp của phương trình thứ hai khỏi phương trình thứ nhất, ta sẽ loại bỏ được một trong các hạng tử $\mathbf{v}_i$ và thu được một tổ hợp lồi của ít hơn $k$ phần tử của $S$ sao cho bằng $\mathbf{p}$ .

Vì không phải tất cả các hệ số $d_i$ đều bằng 0, ta có thể giả sử (bằng cách sắp xếp lại các chỉ số nếu cần thiết) rằng $d_k>0$ và rằng ${c_k}/{d_k}\leq{c_i}/{d_i}$ với mọi $i$ sao cho $d_i>0$ . Với $i=1,\ldots,k$ , đặt $b_i=c_i-\left({c_k}/{d_k}\right)d_i$ . Khi đó $b_k=0$ và

$\sum_{i=1}^k b_i=\sum_{i=1}^k c_i-\frac{c_k}{d_k}\sum_{i=1}^k d_i=1-0=1$

Hơn nữa, mỗi $b_i\geq 0$ . Thật vậy, nếu $d_i\leq 0$ , thì $b_i=c_i-\left({c_k}/{d_k}\right)d_i\geq c_i\geq 0$ . Nếu $d_i>0$ , thì

$b_i=d_i\left(\frac{c_i}{d_i}-\frac{c_k}{d_k}\right)\geq 0$

theo giả thiết về cách chọn ${c_k}/{d_k}$ . Do cách xây dựng:

$\sum_{i=1}^{k-1}b_i\mathbf{v}_i=\sum_{i=1}^k b_i\mathbf{v}_i=\sum_{i=1}^k(c_i-\frac{c_k}{d_k}d_i)\mathbf{v}_i$

$=\sum_{i=1}^{k}c_i\mathbf{v}_i-\frac{c_k}{d_k}\sum_{i=1}^{k}d_i\mathbf{v}_i=\sum_{i=1}^{k}c_i\mathbf{v}_i=\mathbf{p}$

Do đó, $\mathbf{p}$ hiện là một tổ hợp lồi của $k-1$ điểm trong tập { $\{\mathbf{v}_1,\ldots,\mathbf{v}_k\}$ . Quá trình này có thể được lặp lại cho đến khi $\mathbf{p}$ được biểu diễn dưới dạng tổ hợp lồi của nhiều nhất $n+1$ điểm trong $S$ .

Ví dụ 4: Cho

$\mathbf{v}_1=\begin{bmatrix}1\\0\end{bmatrix},\quad\mathbf{v}_2=\begin{bmatrix}2\\3\end{bmatrix},\quad\mathbf{v}_3=\begin{bmatrix}5\\4\end{bmatrix},\quad\mathbf{v}_4=\begin{bmatrix}3\\0\end{bmatrix},\quad\mathbf{p}=\begin{bmatrix}\frac{10}{3}\\\frac{5}{2}\end{bmatrix},$

và $S=\{\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3,\mathbf{v}_4\}$ . Khi đó:

(2) $\begin{equation*}\frac{1}{4}\mathbf{v}_1+\frac{1}{6}\mathbf{v}_2+\frac{1}{2}\mathbf{v}_3+\frac{1}{12}\mathbf{v}_4=\mathbf{p}\end{equation*}$

Hãy sử dụng quy trình trong chứng minh Định lý Carathéodory để biểu diễn $\mathbf{p}$ như một tổ hợp lồi của ba điểm trong $S$ .

Giải: Tập $S$ là một tập phụ thuộc afin. Sử dụng kỹ thuật trong bài trước để thu được một quan hệ phụ thuộc afin:

(3) $\begin{equation*}-5\mathbf{v}_1+4\mathbf{v}_2-3\mathbf{v}_3+4\mathbf{v}_4=\mathbf{0}\end{equation*}$

Tiếp theo, chọn các điểm $\mathbf{v}_2$ và $\mathbf{v}_4$ trong phương trình (3), những điểm có hệ số dương. Với mỗi điểm, tính tỷ số giữa các hệ số trong phương trình (2) và (3). Tỷ số cho $\mathbf{v}_2$ là ${\frac{1}{6}}\div{4}=\frac{1}{24}$ , và cho $\mathbf{v}_4$ là ${\frac{1}{12}}\div{4}=\frac{1}{48}$ . Tỷ số cho $\mathbf{v}_4$ nhỏ hơn, nên ta trừ 1 lần phương trình (3) khỏi phương trình (2) để loại bỏ $\mathbf{v}_4$ :

$\left(\frac{1}{4}+\frac{5}{48}\right)\mathbf{v}_1+\left(\frac{1}{6}-\frac{4}{48}\right)\mathbf{v}_2+\left(\frac{1}{2}+\frac{3}{48}\right)\mathbf{v}_3+\left(\frac{1}{12}-\frac{4}{48}\right)\mathbf{v}_4=\mathbf{p}$

$\frac{17}{48}\mathbf{v}_1+\frac{4}{48}\mathbf{v}_2+\frac{27}{48}\mathbf{v}_3=\mathbf{p}$

Kết quả này nói chung không thể cải thiện thêm bằng cách giảm số lượng điểm cần thiết. Thật vậy, với bất kỳ ba điểm không thẳng hàng nào trong $\mathbb{R}^2$ , trọng tâm của tam giác tạo thành bởi ba điểm đó nằm trong bao lồi của cả ba điểm, nhưng không nằm trong bao lồi của bất kỳ cặp điểm nào.

Để lại một bình luận Hủy

Chịu trách nhiệm nội dung

Bản quyền

Ý kiến bạn đọc

Bài giảng 7: Tổ Hợp Lồi

Lesson Attachments

Để lại một bình luận Hủy