Теорема Каратеодори

Пусть S — произвольное множество в $\ mathbb {R} ^ n$. Если $x \ in Co \ left (S \ right)$, то $x \ in Co \ left (x_1, x_2, ...., x_n, x_ {n + 1} \ right)$.

доказательство

Так как $x \ in Co \ left (S \ right)$, то $x$ представляется выпуклой комбинацией конечного числа точек в S, т. Е.

$x = \ displaystyle \ sum \ limit_ {j = 1} ^ k \ lambda_jx_j, \ displaystyle \ sum \ limit_ {j = 1} ^ k \ lambda_j = 1, \ lambda_j \ geq 0$ и $x_j \ in S, \ forall j \ in \ left (1, k \ right)$

Если $k \ leq n + 1$, полученный результат, очевидно, верен.

Если $k \ geq n + 1$, то $\ left (x_2-x_1 \ right) \ left (x_3-x_1 \ right), ....., \ left (x_k-x_1 \ right)$ линейно зависимы ,

$\ Rightarrow \ существует \ mu _j \ in \ mathbb {R}, 2 \ leq j \ leq k$ (не все ноль), так что $\ displaystyle \ sum \ limit_ {j = 2} ^ k \ mu _j \ left (x_j-x_1 \ right) = 0$

Определите $\ mu_1 = - \ displaystyle \ sum \ limit_ {j = 2} ^ k \ mu _j$, затем $\ displaystyle \ sum \ limit_ {j = 1} ^ k \ mu_j x_j = 0, \ displaystyle \ sum \ limit_ {j = 1} ^ k \ mu_j = 0$

где не все $\ mu_j's$ равны нулю. Так как $\ displaystyle \ sum \ limit_ {j = 1} ^ k \ mu_j = 0$, по крайней мере один из $\ mu_j> 0,1 \ leq j \ leq k$

Тогда $x = \ displaystyle \ sum \ limit_ {1} ^ k \ lambda_j x_j + 0$

$x = \ displaystyle \ sum \ limit_ {1} ^ k \ lambda_j x_j- \ alpha \ displaystyle \ sum \ limit_ {1} ^ k \ mu_j x_j$

$x = \ displaystyle \ sum \ limit_ {1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) x_j$

Выберите $\ alpha$ так, чтобы $\ alpha = min \ left \ {\ frac {\ lambda_j} {\ mu_j}, \ mu_j \ geq 0 \ right \} = \ frac {\ lambda_j} {\ mu _j},$ для некоторых $i = 1,2, ..., k$

Если $\ mu_j \ leq 0, \ lambda_j- \ alpha \ mu_j \ geq 0$

Если  muj>0,то frac lambdaj muj geq frac lambdai mui= alpha Rightarrow lambdaj− alpha muj geq0,J=1,2,...к$\ mu_j> 0, то \: \ frac {\ lambda _j} {\ mu_j} \ geq \ frac {\ lambda_i} {\ mu _i} = \ alpha \ Rightarrow \ lambda_j- \ alpha \ mu_j \ geq 0, J = 1,2, ... к$

В частности, $\ lambda_i- \ alpha \ mu_i = 0$ по определению $\ alpha$

$x = \ displaystyle \ sum \ limit_ {j = 1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) x_j$, где

$\ lambda_j- \ alpha \ mu_j \ geq0$ и $\ displaystyle \ sum \ limit_ {j = 1} ^ k \ left (\ lambda_j- \ alpha \ mu_j \ right) = 1$ и $\ lambda_i- \ alpha \ mu_i = 0$

Таким образом, x можно представить в виде выпуклой комбинации не более (k-1) точек.

Этот процесс восстановления может повторяться до тех пор, пока x не будет представлен как выпуклая комбинация (n + 1) элементов.