✨Định lý Carathéodory (bao lồi)

:Xem thêm các định lý Carathéodory khác Trong hình học lồi, định lý Carathéodory khẳng định nếu điểm x trong R^d nằm trong bao lồi của tập hợp P, thì tồn tại một tập hợp con P′ của P gồm tối đa d+1 điểm sao cho x nằm trong bao lồi của P′. Một cách phát biểu tương đương là x nằm trong một r-đơn hình với các đỉnh thuộc P, trong đó $r\; \backslash leq\; d$. Kết quả này được đặt tên theo Constantin Carathéodory, người đã chứng minh định lý này năm 1911 cho trường hợp P compact. Năm 1913, Ernst Steinitz mở rộng định lý Carathéodory cho mọi tập P trong R^d.

Sau đây là một ví dụ. Ta xét tập hợp P = {(0,0), (0,1), (1,0), (1,1)} trong R². Bao lồi của tập này là một hình vuông. Xét điểm x = (1/4, 1/4) nằm trong bao lồi của P. Ta có thể chọn tập {(0,0),(0,1),(1,0)} = P ′, với bao lồi là một hình tam giác chứa x và do đó định lý là đúng trong trường hợp này do |P′| = 3.

Chứng minh

Giả sử x là một điểm trong bao lồi của P. Khi đó, x là tổ hợp lồi của một tập hợp hữu hạn các điểm trong P:

:$\backslash mathbf\{x\}=\backslash sum\_\{j=1\}^k\; \backslash lambda\_j\; \backslash mathbf\{x\}\_j$

trong đó mọi x_j đều thuộc P, λ_j là số dương, và $\backslash sum\_\{j=1\}^k\backslash lambda\_j=1$.

Giả sử k > d + 1 (nếu không ta có ngay điều phải chứng minh). Khi đó, các điểm x₂ − x₁,..., x_k − x₁ là phụ thuộc tuyến tính, nên tồn tại μ₂,..., μ_k sao cho không phải tất cả chúng đều bằng 0 và

:$\backslash sum\_\{j=2\}^k\; \backslash mu\_j\; (\backslash mathbf\{x\}\_j-\backslash mathbf\{x\}\_1)=\backslash mathbf\{0\}.$

Nếu định nghĩa μ₁ như sau

:$\backslash mu$1:=-\sum{j=2}^k \mu_j

thì

:$\backslash sum\_\{j=1\}^k\; \backslash mu\_j\; \backslash mathbf\{x\}$j=\mathbf{0} :$\backslash sum${j=1}^k \mu_j=0

và không phải tất cả μ_j đều bằng 0. Do đó tồn tại ít nhất một μ_j>0. Ta có,

:$\backslash mathbf\{x\}\; =\; \backslash sum\_\{j=1\}^k\; \backslash lambda\_j\; \backslash mathbf\{x\}$j-\alpha\sum{j=1}^k \mu_j \mathbf{x}j = \sum{j=1}^k (\lambda_j-\alpha\mu_j) \mathbf{x}_j

cho mọi số thực α. Vì vậy đẳng thức trên là đúng khi chọn α như sau

:$\backslash alpha:=\backslash min\_\{1\backslash leq\; j\; \backslash leq\; k\}\; \backslash left\{\; \backslash tfrac\{\backslash lambda\_j\}\{\backslash mu\_j\}:\backslash mu\_j>0\backslash right\}=\backslash tfrac\{\backslash lambda\_i\}\{\backslash mu\_i\}.$

Ghi chú là α>0, và với mọi j từ 1 tới k, :$\backslash lambda\_j-\backslash alpha\backslash mu\_j\; \backslash geq\; 0.$

Ta nhận thấy λ_i − αμ_i = 0 theo cách chọn α. Vì vậy,

:$\backslash mathbf\{x\}\; =\; \backslash sum\_\{j=1\}^k\; (\backslash lambda\_j-\backslash alpha\backslash mu\_j)\; \backslash mathbf\{x\}\_j$

trong đó mọi $\backslash lambda\_j\; -\; \backslash alpha\; \backslash mu\_j$ là không âm, tổng của chúng bằng 1, và thêm vào đó, $\backslash lambda\_i-\backslash alpha\backslash mu\_i=0$. Nói cách khác, x là tổ hợp lồi của k-1 điểm trong P. Có thể lặp lại quá trình trên cho tới khi x là tổ hợp lồi của d + 1 điểm trong P.

Một cách chứng minh khác là sử dụng định lý Helly.