Выпуклая оптимизация — неравенство Дженсена

Пусть S — непустое выпуклое множество в $\ mathbb {R} ^ n$ и $f: S \ rightarrow \ mathbb {R} ^ n$. Тогда f выпуклая тогда и только тогда, когда для каждого целого числа $k> 0$

$x_1, x_2, ... x_k \ in S, \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1, \ lambda_i \ geq 0, \ forall i = 1,2, s, k$, у нас есть $f \ left (\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i \ right) \ leq \ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda _if \ left (x \ right)$

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

По индукции на к.

$k = 1: x_1 \ in S$ Следовательно, $f \ left (\ lambda_1 x_1 \ right) \ leq \ lambda_i f \ left (x_1 \ right)$, потому что $\ lambda_i = 1$.

$k = 2: \ lambda_1 + \ lambda_2 = 1$ и $x_1, x_2 \ in S$

Следовательно, $\ lambda_1x_1 + \ lambda_2x_2 \ in S$

Следовательно, по определению, $f \ left (\ lambda_1 x_1 + \ lambda_2 x_2 \ right) \ leq \ lambda _1f \ left (x_1 \ right) + \ lambda _2f \ left (x_2 \ right)$

Пусть утверждение верно для $n <k$

Следовательно,

$f \ left (\ lambda_1 x_1 + \ lambda_2 x_2 + .... + \ lambda_k x_k \ right) \ leq \ lambda_1 f \ left (x_1 \ right) + \ lambda_2 f \ left (x_2 \ right) + ... + \ lambda_k f \ left (x_k \ right)$

$k = n + 1:$ Let $x_1, x_2, .... x_n, x_ {n + 1} \ in S$ и $\ displaystyle \ sum \ limit_ {i = 1} ^ {n + 1} = 1$

Поэтому $\ mu_1x_1 + \ mu_2x_2 + ....... + \ mu_nx_n + \ mu_ {n + 1} x_ {n + 1} \ in S$

таким образом, $f \ left (\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n + \ mu_ {n + 1} x_ {n + 1} \ right)$

$= f \ left (\ left (\ mu_1 + \ mu_2 + ... + \ mu_n \ right) \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n} {\ mu_1 + \ mu_2 + \ mu_3} + \ mu_ {n + 1} x_ {n + 1} \ right)$

$= f \ left (\ mu_y + \ mu_ {n + 1} x_ {n + 1} \ right)$ где $\ mu = \ mu_1 + \ mu_2 + ... + \ mu_n$ и

$y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n} {\ mu_1 + \ mu_2 + ... + \ mu_n}$, а также $\ mu_1 + \ mu_ {n + 1} = 1, y \ in S$

$\ Rightarrow f \ left (\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n + \ mu_ {n + 1} x_ {n + 1} \ right) \ leq \ mu f \ left (y \ right) + \ mu_ {n +1} f \ left (x_ {n + 1} \ right)$

$\ Rightarrow f \ left (\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n + \ mu_ {n + 1} x_ {n + 1} \ right) \ leq$

$\ left (\ mu_1 + \ mu_2 + ... + \ mu_n \ right) f \ left (\ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n} {\ mu_1 + \ mu_2 + ... + \ mu_n} \ right) + \ mu_ {n + 1} f \ left (x_ {n + 1} \ right)$

$\ Rightarrow f \ left (\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n + \ mu_ {n + 1} x_ {n + 1} \ right) \ leq \ left (\ mu_1 + \ mu_2 + ... + \ mu_n \ верно)$

$\ left [\ frac {\ mu_1} {\ mu_1 + \ mu_2 + ... + \ mu_n} f \ left (x_1 \ right) + ... + \ frac {\ mu_n} {\ mu_1 + \ mu_2 + ... + \ mu_n} f \ left (x_n \ right) \ right] + \ mu_ {n + 1} f \ left (x_ {n + 1} \ right)$

$\ Rightarrow f \ left (\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_nx_n + \ mu_ {n + 1} x_ {n + 1} \ right) \ leq \ mu_1f \ left (x_1 \ right) + \ mu_2f \ left ( x_2 \ right) + ....$

Отсюда доказано.