Выпуклая оптимизация — выпуклый набор

Пусть $S \ subseteq \ mathbb {R} ^ n$. Множество S называется выпуклым, если отрезок, соединяющий любые две точки множества S, также принадлежит S, т. Е. Если $x_1, x_2 \ in S$ , тогда $\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S$, где $\ lambda \ in \ left (0,1 \ right)$.

Примечание —

• Объединение двух выпуклых множеств может быть или не быть выпуклым.
• Пересечение двух выпуклых множеств всегда выпукло.

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

Пусть $S_1$ и $S_2$ — два выпуклых множества.

Пусть $S_3 = S_1 \ cap S_2$

Пусть $x_1, x_2 \ in S_3$

Так как $S_3 = S_1 \ cap S_2$, таким образом, $x_1, x_2 \ in S_1$ и $x_1, x_2 \ in S_2$

Поскольку $S_i$ является выпуклым множеством, $\ forall$ $i \ in 1,2,$

Таким образом, $\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_i$, где $\ lambda \ in \ left (0,1 \ right)$

Поэтому $\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_1 \ cap S_2$

$\ Rightarrow \ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ in S_3$

Следовательно, $S_3$ является выпуклым множеством.

• Средневзвешенное значение в форме $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i$, где $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1$ и $\ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right]$ называется конической комбинацией $x_1, x_2, .... x_k.$

• Средневзвешенное значение вида $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i$, где $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1$ называется аффинной комбинацией $x_1 , x_2, .... x_k.$

• Средневзвешенное значение вида $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i$ называется линейной комбинацией $x_1, x_2, .... x_k.$

Средневзвешенное значение в форме $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i$, где $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1$ и $\ lambda_i \ geq 0 , \ forall i \ in \ left [1, k \ right]$ называется конической комбинацией $x_1, x_2, .... x_k.$

Средневзвешенное значение вида $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i$, где $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_i = 1$ называется аффинной комбинацией $x_1 , x_2, .... x_k.$

Средневзвешенное значение вида $\ displaystyle \ sum \ limit_ {i = 1} ^ k \ lambda_ix_i$ называется линейной комбинацией $x_1, x_2, .... x_k.$

Примеры

Шаг 1 — Докажите, что множество $S = \ left \ {x \ in \ mathbb {R} ^ n: Cx \ leq \ alpha \ right \}$ является выпуклым множеством.

Решение

Пусть $x_1$ и $x_2 \ in S$

$\ Rightarrow Cx_1 \ leq \ alpha$ и andCx2 leq alpha$\: and \: Cx_2 \ leq \ alpha$

Показать: y= left( lambdax1+ left(1− lambda right)x2 right) inS forall lambda in left(0,1 верно)$\: \: y = \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) \ in S \: \ forall \: \ lambda \ in \ left (0,1 \ верно)$

$Cy = C \ left (\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right) = \ lambda Cx_1 + \ left (1- \ lambda \ right) Cx_2$

$\ Rightarrow Cy \ leq \ lambda \ alpha + \ left (1- \ lambda \ right) \ alpha$

$\ Rightarrow Cy \ leq \ alpha$

$\ Rightarrow y \ in S$

Следовательно, $S$ является выпуклым множеством.

Шаг 2 — Докажите, что множество $S = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} \ leq 8x_2 \ right \}$ равно выпуклое множество.

Решение

Пусть $x, y \ in S$

Пусть $x = \ left (x_1, x_2 \ right)$ и $y = \ left (y_1, y_2 \ right)$

$\ Rightarrow x_ {1} ^ {2} \ leq 8x_2$ и $y_ {1} ^ {2} \ leq 8y_2$

Чтобы показать — $\ lambda x + \ left (1- \ lambda \ right) y \ in S \ Rightarrow \ lambda \ left (x_1, x_2 \ right) + \ left (1- \ lambda \ right) \ left (y_1, y_2 \ right) \ in S \ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda) y_2] \ in S \ right) \ right]$

$Теперь \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} = \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) x_1y_1$

Но $2x_1y_1 \ leq x_ {1} ^ {2} + y_ {1} ^ {2}$

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

$\ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda ^ 2x_ {1} ^ {2} + \ left (1- \ lambda \ right) ^ 2y_ {1} ^ {2} +2 \ lambda \ left (1- \ lambda \ right) \ left (x_ {1} ^ {2} + y_ {1} ^ {2} \ right)$

$\ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq \ lambda x_ {1} ^ {2} + \ left (1- \ lambda \ right) y_ {1} ^ {2}$

$\ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ lambda x_2 + 8 \ left (1- \ lambda \ right) y_2$

$\ Rightarrow \ left [\ lambda x_1 + \ left (1- \ lambda \ right) y_1 \ right] ^ {2} \ leq 8 \ left [\ lambda x_2 + \ left (1- \ lambda \ right) y_2 \ right]$

$\ Rightarrow \ lambda x + \ left (1- \ lambda \ right) y \ in S$

Шаг 3 — Показать, что множество $S \ in \ mathbb {R} ^ n$ является выпуклым тогда и только тогда, когда для каждого целого числа k каждая выпуклая комбинация любых k точек из $S$ находится в $S$.

Решение

Пусть $S$ — выпуклое множество. затем, чтобы показать;

$c_1x_1 + c_2x_2 + ..... + c_kx_k \ in S, \ displaystyle \ sum \ limit_ {1} ^ k c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ...., k$

Доказательство по индукции

Для $k = 1, x_1 \ in S, c_1 = 1 \ Rightarrow c_1x_1 \ in S$

Для $k = 2, x_1, x_2 \ in S, c_1 + c_2 = 1$ и поскольку S — выпуклое множество

$\ Rightarrow c_1x_1 + c_2x_2 \ in S.$

Пусть выпуклая комбинация m точек S находится в S, т. Е.

$c_1x_1 + c_2x_2 + ... + c_mx_m \ in S, \ displaystyle \ sum \ limit_ {1} ^ m c_i = 1, c_i \ geq 0, \ forall i \ in 1,2, ..., m$

Теперь пусть $x_1, x_2 ...., x_m, x_ {m + 1} \ in S$

Пусть $x = \ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m + \ mu_ {m + 1} x_ {m + 1}$

Пусть $x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) \ frac {\ mu_1x_1 + \ mu_2x_2 + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m} + \ mu_ {т + 1} X_ {т + 1}$

Пусть $y = \ frac {\ mu_1x_1 + \ mu_2x_2 + ... + \ mu_mx_m} {\ mu_1 + \ mu_2 + ......... + \ mu_m}$

$\ Rightarrow x = \ left (\ mu_1 + \ mu_2 + ... + \ mu_m \ right) y + \ mu_ {m + 1} x_ {m + 1}$

Теперь $y \ in S$, потому что сумма коэффициентов равна 1.

$\ Rightarrow x \ in S$, поскольку S — выпуклое множество и $y, x_ {m + 1} \ in S$

Следовательно, доказано по индукции.