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

Пусть 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 \ limits_ {j = 1} ^ k \ lambda_jx_j, \ displaystyle \ sum \ limits_ {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 \ limits_ {j = 2} ^ k \ mu _j \ left (x_j-x_1 \ right) = 0 $

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

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

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

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

$ х = \ Displaystyle \ сумма \ пределы_ {1} ^ к \ влево (\ лямбда_j- \ альфа \ mu_j \ вправо) 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 $

Если $ \ 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, ... k $

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

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

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

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

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