Чис. методы оптимизации в 1d и nd. Смещение акцентов.

[_hum_]

Не совсем понимаю, почему в дисциплине "Численные методы оптимизации" в одномерном случае рассматривают главным образом:
- унимодальные функции (хотя, имхо, они не являются слишком рапространенными);
- методы типа отсечений - когда область разбивается на подобласти и на основе проверки каких-то условий, одна из подобластей отсекается, тем самым сужая область поиска (типичный пример - метод дихотомии)
а в многомерном случае все это сразу же пропадает, и речь начинает идти о :
- произвольных (ну, или дифференцируемых/выпуклых) функциях;
- шаговых методах (методах спуска, типа градиентных).

Что такого происходит при переходе в высшую размерность, что так сильно меняет акценты? Ведь, по идее, можно было бы в качестве аналога унимодальной для многомерного случая рассмотреть квазивыпуклую функцию и использовать ту же идею на каком-нибудь гиперкубе (делить его надвое и т.д.)...

p.s. И почему так запросто используют методы одномерной оптимизации в многомерном линейном поиске (в том же методе наискорейшего спуска), если они изначально заточены на унимодальные функции?

[atlakatl]

Чисто педагогические соображения. Идеи метода определить в наипростейшем случае.
Мы и в многомерном пространстве можем искать экстремум вдоль прямой. Но проще всего дихотомию преподнести для $y=f(x)$.
Ну а наискорейший спуск - во всех его нюансах - показывается на $f(x,y,z)$.

[_hum_]

atlakatl в сообщении #1266534 писал(а):

исто педагогические соображения. Идеи метода определить в наипростейшем случае.

чисто педагогические соображения наоборот заставляли бы говорить "в многомерном случае все аналогично, потому мы его рассматривать не будет". Ан нет же - многмерному посвящают большую половину курса.

atlakatl в сообщении #1266534 писал(а):

Мы и в многомерном пространстве можем искать экстремум вдоль прямой.

Вдоль какой? Их там становится уйма, а потому сам выбор прямой становится отдельным методом.

[atlakatl]

Ваши претензии к преподаванию лучше изложить конструктивно: набросать учебный план с методами и размерностями задач. Тогда можно говорить о методике.

[Andrey_Kireew]

Дело в том, что метод дихотомии (или метод золотого сечения) в многомерном случае применять не рационально, из за большой трудоёмкости. Гораздо эффективнее сначала выбрать направление поиска, а затем применить одномерную оптимизацию. Так обычно и поступают, в частности в градиентных методах.
В одномерном случае градиент, разумеется, не предусмотрен, за ненадобностью, так как там направление выбирать не приходится. Если же речь заходит о методах второго порядка (метод Ньютона), то они применяются как в одномерном, так и в многомерном случаях, и формулы выглядят почти одинаково.

По поводу произвольной формы оптимизируемой функции в многомерном случае - Вы заблуждаетесь. Основной математический аппарат там разработан так же только для унимодальных функций. Просто эти задачи более актуальные, и им уделяется больше внимания в литературе. Реальные функции, встречающиеся в практических задачах, конечно полимодальные. И всегда есть проблема локальных экстремумов. Путь её преодоления один, что в многомерном, что в одномерном случаях - это случайный поиск. Или в чистом виде, или в симбиозе с другими алгоритмами.

[_hum_]

Andrey_Kireew в сообщении #1266596 писал(а):

Дело в том, что метод дихотомии (или метод золотого сечения) в многомерном случае применять не рационально, из за большой трудоёмкости.

А можно поподробнее, почему? Навскидку, выбираем первую координату, делим по ней гиперкуб $\Pi$ на два, выбираем нужную часть. Потом делаем то же самое по другой координате. Итого, за $n$ шагов уменьшаем объем области неопределенности в 2 раза. Таким образом, для нахождения точки минимума с точностью до $\varepsilon$ нужно порядка $n\log_2 \frac{\Pi}{\varepsilon}$ шагов. Это считается неэффективным?
upd. Кажется, понял. В многомерном случае нельзя узнать, какую часть куба отбросить по проверке значений в одной точке.

Andrey_Kireew в сообщении #1266596 писал(а):

Гораздо эффективнее сначала выбрать направление поиска, а затем применить одномерную оптимизацию. Так обычно и поступают, в частности в градиентных методах.

Так там же проблема - как выбрать направление на точку минимума.

Andrey_Kireew в сообщении #1266596 писал(а):

В одномерном случае градиент, разумеется, не предусмотрен, за ненадобностью, так как там направление выбирать не приходится.

Ну как же не предусмотрен - это же обычная производная, которая показывает в какую сторону нужно двигаться (вправо или влево), чтобы приближаться к точке минимума.

Andrey_Kireew в сообщении #1266596 писал(а):

По поводу произвольной формы оптимизируемой функции в многомерном случае - Вы заблуждаетесь. Основной математический аппарат там разработан так же только для унимодальных функций.

Ммм...То, что я видел, там из унимодальных в явном виде выступают только выпуклые функции (соответственно, речь про выпуклое программирование). Все остальные, вроде, работают с полимодальными, рассчитывая на поиск локального экстремума.

[Andrey_Kireew]

Сложность зависит от реализации. Если оптимизировать по каждой переменной до достижения максимума, то она будет возрастать со степенью размерности. Дело в том, что после оптимизации по очередной переменной, все ранее оптимизированные значения перестанут быть оптимальными. Всё придётся повторять по новой и не 1 раз. Если оптимизировать последовательно, по каждой переменной только на 1 шаг, то процесс пойдёт быстрее, но это уже будет походить на градиентный поиск, так как направление, хоть и неявно, но будет определяться, и не самым эффективным способом.

Направление на точку минимума точно не выбрать никак не нельзя, равно как нельзя точно определить шаг в методе отсечений. Их уточняют итеративно - это единственный способ.

Если Вы сами не догадались, то во всех одномерных методах отсечения производная, хоть и неявно, но оценивается.

О том я и писал, работать они могут с чем угодно, но нахождение глобального минимума не гарантируют, причём ни те не другие.

[B@R5uk]

_hum_ в сообщении #1266532 писал(а):

...а в многомерном случае все это сразу же пропадает, и речь начинает идти о...

Может потому что даже в аналитическом случае (не численном) при переходе от одного измерения к двум всё кардинально меняется, не? Вспомните, например, всякие седловые точки. В численном случае тоже появляются всякие сложности. Как вам, например, оптимизация такой функции: $f\left( x,y \right)=0.01y+{{\left( y-{{x}^{2}} \right)}^{2}}$? Я забыл как зовут автора этой дьявольской задачи, но она довольно известна в своих кругах и является стандартным тестом работоспособности любого алгоритма численной оптимизации в жёстких условиях. А ведь какая (на первый взгляд) хорошая функция: всего один экстремум и она бесконечно дифференцируема!