Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 9 ] |
|
Автор | Сообщение | |
---|---|---|
dot618 |
|
|
Вот я взял книгу Васильева Федора Павловича "Численные методы решения экстремальных задач" 1988 г. В ней описано целых 17 методов минимизации функций многих переменных, не считая модификаций. Но все они кажутся мне слишком сложными в реализации, не говоря уже о том, что дифференцировать свою функцию я не умею. Другими словами, среди этих методов нет такого, который я взялся бы запрограммировать лично. Поэтому мне интересно, какой метод многомерной (двумерной) минимизации вы считаете настолько простым, чтобы вместо обращения к стандартной программе вы взялись бы запрограммировать его ЛИЧНО? И нет ли у вас своего собственного метода, доморощенного? |
||
Вернуться к началу | ||
swan |
|
|
Градиентный спуск
|
||
Вернуться к началу | ||
dot618 |
|
|
градиентный спуск в строгом смысле - надо градиент знать
|
||
Вернуться к началу | ||
michel |
|
|
dot618 писал(а): дифференцировать свою функцию я не умею. Используйте тогда методы оптимизации нулевого порядка: различные вариации одномерного поиска, Хука-Дживса, Розенброка, Пауэлла, Нелдера-Мида, которые не требуют вычисления производных целевой функции. |
||
Вернуться к началу | ||
dot618 |
|
|
michel писал(а): Используйте тогда методы оптимизации нулевого порядка: различные вариации одномерного поиска, Хука-Дживса, Розенброка, Пауэлла, Нелдера-Мида, которые не требуют вычисления производных целевой функции. В книге Васильева я таких слов не обнаружил. Да и вопрос был не в том, какие методы существуют, а в том, какой метод вы бы не поленились запрограммировать сами, а не принялись искать и осваивать уже готовую программу. Я лично запрограммировал следующий двумерный алгоритм.Берем квадратную сетку с заданным шагом (или прямоугольную, если необходимо) и начинаем ходить по ней, стартуя из некоторой начальной точки, в направлении убывания целевой функции, причем не обязательно в направлении наибыстрейшего убывания, а просто в первом попавшемся. Зато сохраняем это направление до упора - пока функция убывает. Если дальше идти невозможно, то пробуем сменить направление на перпендикулярное, одно или другое, а если и это невозможно, значит мы худо-бедно локализовали искомый минимум и далее для достижения нужной точности сетку в этом месте надо измельчать... Недостатком данного алгоритма является то, что при неудачном выборе начальной точки сетка может измельчиться преждевременно и дальше шажки алгоритма будут чересчур мелкими... У меня так и получилось: когда шаг сетки достиг двух стотысячных, алгоритму, прежде чем перейти к одной стотысячной, пришлось сделать аж 211 таких шажков! - я почти три часа ждал (тогда-то и завел эту тему). Однако проблема выбора подходящей начальной точки, во-первых, характерна для многих алгоритмов и, во-вторых, если алгоритм шагает слишком медленно, то можно прервать его и начать все сначала, но уже из достигнутой точки. И для упомянутого случая я это с успехом проверил. В общем, вполне себе работоспособный простой метод минимизации. Может, у него и фамилия чья-то есть? |
||
Вернуться к началу | ||
michel |
|
|
dot618 писал(а): Если дальше идти невозможно, то пробуем сменить направление на перпендикулярное Похоже на метод Розенброка. |
||
Вернуться к началу | ||
dot618 |
|
|
michel писал(а): Похоже на метод Розенброка. Прочитал про этот метод в книжке Т. Шупа (заодно внес ссылку на нее в Вики). Нет, это не то. Он рассчитан на легкое вычисление значений целевой функции, поскольку ведет поиск сразу по всем направлениям. А у меня эти значения вычисляется как раз очень сложно - неспроста в упомянутом случае я ждал почти три часа. И в том методе, что использовал я, из четырех направлений до упора выбирается одно - предыдущее. |
||
Вернуться к началу | ||
dot618 |
|
|
Реализовал в используемом методе общую идею - идти в благоприятном направлении не просто, а с ускорением. Толку никакого: программа усложнилась и считать стала дольше. Зато другая идея оказалась хорошей. Поскольку целевая функция у меня вычисляется очень долго, то я взял и аппроксимировал ее полиномом (9-го порядка). Программа стала считать просто мгновенно, теперь можно и поэкспериментировать...
|
||
Вернуться к началу | ||
dot618 |
|
|
dot618 писал(а): Реализовал в используемом методе общую идею - идти в благоприятном направлении не просто, а с ускорением. Толку никакого: программа усложнилась и считать стала дольше. Зато другая идея оказалась хорошей. Поскольку целевая функция у меня вычисляется очень долго, то я взял и аппроксимировал ее полиномом (9-го порядка). Программа стала считать просто мгновенно, теперь можно и поэкспериментировать... Я немного соврал. На самом деле я аппроксимировал не саму целевую функцию, а некоторую тяжелую ее подфункцию. Целевая функция у меня погрешность, ее я минимизирую. Теперь очередь дошла до несколько другой задачи, как бы обратной. Обратные задачи, как известно, часто некорректные. И такое впечатление, что моя целевая функция состоит сплошь из локальных минимумов. Задам одну начальную точку - получу один локальный минимум, задам другую - получу другой, задам третью - получу третий, и так без конца. Благо, что аппроксимации вычисляются просто и их можно посмотреть в целом во всей области определения хоть в миллионе точек. Но проблема возникла и остается: погрешность аппроксимации значительно превосходит разницу в значениях целевой функции в точках локальных минимумов, т.е. доверия к ним никакого. Как говорится, бежали от волка, попали на медведя. Не знаю пока, что с этим делать. |
||
Вернуться к началу | ||
[ Сообщений: 9 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Многомерная задача ранцевого типа - объединение ограничений | 7 |
490 |
13 авг 2015, 16:38 |
|
минимизация в КНФ | 0 |
100 |
02 окт 2021, 15:50 |
|
Минимизация | 23 |
401 |
30 окт 2019, 14:32 |
|
Минимизация анлитечески | 2 |
285 |
22 ноя 2014, 20:41 |
|
Минимизация невязки
в форуме Численные методы |
26 |
306 |
18 авг 2023, 00:07 |
|
Минимизация функции | 2 |
318 |
01 июл 2020, 19:57 |
|
Минимизация функции | 1 |
183 |
18 ноя 2022, 18:46 |
|
Минимизация обрезков | 1 |
437 |
23 июл 2015, 15:54 |
|
Минимизация количества вычислений
в форуме Информатика и Компьютерные науки |
7 |
497 |
21 дек 2016, 11:23 |
|
Динамическое программирование. Минимизация затрат | 3 |
769 |
30 дек 2014, 09:07 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |