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

Пусть S — замкнутое выпуклое множество в $\ mathbb {R} ^ n$. Ненулевой вектор $d \ in \ mathbb {R} ^ n$ называется направлением S, если для каждого $x \ in S, x + \ lambda d \ in S, \ forall \ lambda \ geq 0.$

• Два направления $d_1$ и $d_2$ в S называются различными, если $d \ neq \ alpha d_2$ для $\ alpha> 0$.

• Направление $d$ в $S$ называется крайним направлением, если его нельзя записать в виде положительной линейной комбинации двух разных направлений, т. Е. Если $d = \ lambda _1d_1 + \ lambda _2d_2$ для $\ lambda _1, \ лямбда _2> 0$, затем $d_1 = \ alpha d_2$ для некоторого $\ alpha$.

• Любое другое направление может быть выражено как положительная комбинация экстремальных направлений.

• Для выпуклого множества $S$ направление d такое, что $x + \ lambda d \ in S$ для некоторого $x \ in S$ и всех $\ lambda \ geq0$ называется рецессивным для $S$.

• Пусть E — множество точек, в которых некоторая функция $f: S \ rightarrow$ над непустым выпуклым множеством S в $\ mathbb {R} ^ n$ достигает своего максимума, тогда $E$ называется открытой гранью $S$. Направления открытых лиц называются открытыми направлениями.

• Луч, чье направление является экстремальным, называется экстремальным.

Два направления $d_1$ и $d_2$ в S называются различными, если $d \ neq \ alpha d_2$ для $\ alpha> 0$.

Направление $d$ в $S$ называется крайним направлением, если его нельзя записать в виде положительной линейной комбинации двух разных направлений, т. Е. Если $d = \ lambda _1d_1 + \ lambda _2d_2$ для $\ lambda _1, \ лямбда _2> 0$, затем $d_1 = \ alpha d_2$ для некоторого $\ alpha$.

Любое другое направление может быть выражено как положительная комбинация экстремальных направлений.

Для выпуклого множества $S$ направление d такое, что $x + \ lambda d \ in S$ для некоторого $x \ in S$ и всех $\ lambda \ geq0$ называется рецессивным для $S$.

Пусть E — множество точек, в которых некоторая функция $f: S \ rightarrow$ над непустым выпуклым множеством S в $\ mathbb {R} ^ n$ достигает своего максимума, тогда $E$ называется открытой гранью $S$. Направления открытых лиц называются открытыми направлениями.

Луч, чье направление является экстремальным, называется экстремальным.

пример

Рассмотрим функцию $f \ left (x \ right) = y = \ left | x \ right |$, где $x \ in \ mathbb {R} ^ n$. Пусть d будет единичным вектором в $\ mathbb {R} ^ n$

Тогда d является направлением для функции f, потому что для любого $\ lambda \ geq 0, x + \ lambda d \ in f \ left (x \ right)$.