Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Многомерная минимизация
СообщениеДобавлено: 11 июл 2021, 09:57 
Не в сети
Профи
Зарегистрирован:
27 апр 2021, 10:20
Сообщений: 483
Cпасибо сказано: 13
Спасибо получено:
55 раз в 50 сообщениях
Очков репутации: 5

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

Вот я взял книгу Васильева Федора Павловича "Численные методы решения экстремальных задач" 1988 г. В ней описано целых 17 методов минимизации функций многих переменных, не считая модификаций. Но все они кажутся мне слишком сложными в реализации, не говоря уже о том, что дифференцировать свою функцию я не умею. Другими словами, среди этих методов нет такого, который я взялся бы запрограммировать лично.

Поэтому мне интересно, какой метод многомерной (двумерной) минимизации вы считаете настолько простым, чтобы вместо обращения к стандартной программе вы взялись бы запрограммировать его ЛИЧНО? И нет ли у вас своего собственного метода, доморощенного? :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 11 июл 2021, 12:20 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Градиентный спуск

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 11 июл 2021, 12:48 
Не в сети
Профи
Зарегистрирован:
27 апр 2021, 10:20
Сообщений: 483
Cпасибо сказано: 13
Спасибо получено:
55 раз в 50 сообщениях
Очков репутации: 5

Добавить очки репутацииУменьшить очки репутации
градиентный спуск в строгом смысле - надо градиент знать

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 11 июл 2021, 13:26 
Не в сети
Последняя инстанция
Зарегистрирован:
08 апр 2015, 12:21
Сообщений: 7567
Cпасибо сказано: 229
Спасибо получено:
2751 раз в 2539 сообщениях
Очков репутации: 473

Добавить очки репутацииУменьшить очки репутации
dot618 писал(а):
дифференцировать свою функцию я не умею.

Используйте тогда методы оптимизации нулевого порядка: различные вариации одномерного поиска, Хука-Дживса, Розенброка, Пауэлла, Нелдера-Мида, которые не требуют вычисления производных целевой функции.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 11 июл 2021, 15:58 
Не в сети
Профи
Зарегистрирован:
27 апр 2021, 10:20
Сообщений: 483
Cпасибо сказано: 13
Спасибо получено:
55 раз в 50 сообщениях
Очков репутации: 5

Добавить очки репутацииУменьшить очки репутации
michel писал(а):
Используйте тогда методы оптимизации нулевого порядка: различные вариации одномерного поиска, Хука-Дживса, Розенброка, Пауэлла, Нелдера-Мида, которые не требуют вычисления производных целевой функции.
В книге Васильева я таких слов не обнаружил. :( Да и вопрос был не в том, какие методы существуют, а в том, какой метод вы бы не поленились запрограммировать сами, а не принялись искать и осваивать уже готовую программу. Я лично запрограммировал следующий двумерный алгоритм.

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

Недостатком данного алгоритма является то, что при неудачном выборе начальной точки сетка может измельчиться преждевременно и дальше шажки алгоритма будут чересчур мелкими... У меня так и получилось: когда шаг сетки достиг двух стотысячных, алгоритму, прежде чем перейти к одной стотысячной, пришлось сделать аж 211 таких шажков! - я почти три часа ждал (тогда-то и завел эту тему). :hh:)

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 11 июл 2021, 18:13 
Не в сети
Последняя инстанция
Зарегистрирован:
08 апр 2015, 12:21
Сообщений: 7567
Cпасибо сказано: 229
Спасибо получено:
2751 раз в 2539 сообщениях
Очков репутации: 473

Добавить очки репутацииУменьшить очки репутации
dot618 писал(а):
Если дальше идти невозможно, то пробуем сменить направление на перпендикулярное

Похоже на метод Розенброка.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 12 июл 2021, 08:02 
Не в сети
Профи
Зарегистрирован:
27 апр 2021, 10:20
Сообщений: 483
Cпасибо сказано: 13
Спасибо получено:
55 раз в 50 сообщениях
Очков репутации: 5

Добавить очки репутацииУменьшить очки репутации
michel писал(а):
Похоже на метод Розенброка.
Прочитал про этот метод в книжке Т. Шупа (заодно внес ссылку на нее в Вики). Нет, это не то. Он рассчитан на легкое вычисление значений целевой функции, поскольку ведет поиск сразу по всем направлениям. А у меня эти значения вычисляется как раз очень сложно - неспроста в упомянутом случае я ждал почти три часа. И в том методе, что использовал я, из четырех направлений до упора выбирается одно - предыдущее.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 14 июл 2021, 18:23 
Не в сети
Профи
Зарегистрирован:
27 апр 2021, 10:20
Сообщений: 483
Cпасибо сказано: 13
Спасибо получено:
55 раз в 50 сообщениях
Очков репутации: 5

Добавить очки репутацииУменьшить очки репутации
Реализовал в используемом методе общую идею - идти в благоприятном направлении не просто, а с ускорением. Толку никакого: программа усложнилась и считать стала дольше. Зато другая идея оказалась хорошей. Поскольку целевая функция у меня вычисляется очень долго, то я взял и аппроксимировал ее полиномом (9-го порядка). Программа стала считать просто мгновенно, теперь можно и поэкспериментировать...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Многомерная минимизация
СообщениеДобавлено: 16 июл 2021, 07:08 
Не в сети
Профи
Зарегистрирован:
27 апр 2021, 10:20
Сообщений: 483
Cпасибо сказано: 13
Спасибо получено:
55 раз в 50 сообщениях
Очков репутации: 5

Добавить очки репутацииУменьшить очки репутации
dot618 писал(а):
Реализовал в используемом методе общую идею - идти в благоприятном направлении не просто, а с ускорением. Толку никакого: программа усложнилась и считать стала дольше. Зато другая идея оказалась хорошей. Поскольку целевая функция у меня вычисляется очень долго, то я взял и аппроксимировал ее полиномом (9-го порядка). Программа стала считать просто мгновенно, теперь можно и поэкспериментировать...
Я немного соврал. На самом деле я аппроксимировал не саму целевую функцию, а некоторую тяжелую ее подфункцию. Целевая функция у меня погрешность, ее я минимизирую. Теперь очередь дошла до несколько другой задачи, как бы обратной. Обратные задачи, как известно, часто некорректные. И такое впечатление, что моя целевая функция состоит сплошь из локальных минимумов. Задам одну начальную точку - получу один локальный минимум, задам другую - получу другой, задам третью - получу третий, и так без конца. Благо, что аппроксимации вычисляются просто и их можно посмотреть в целом во всей области определения хоть в миллионе точек. Но проблема возникла и остается: погрешность аппроксимации значительно превосходит разницу в значениях целевой функции в точках локальных минимумов, т.е. доверия к ним никакого. Как говорится, бежали от волка, попали на медведя. Не знаю пока, что с этим делать.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 9 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Многомерная задача ранцевого типа - объединение ограничений

в форуме Исследование операций и Задачи оптимизации

oxid

7

490

13 авг 2015, 16:38

минимизация в КНФ

в форуме Дискретная математика, Теория множеств и Логика

JAX7

0

100

02 окт 2021, 15:50

Минимизация

в форуме Дискретная математика, Теория множеств и Логика

LoganAG

23

401

30 окт 2019, 14:32

Минимизация анлитечески

в форуме Дискретная математика, Теория множеств и Логика

Schya4lo

2

285

22 ноя 2014, 20:41

Минимизация невязки

в форуме Численные методы

Exzellenz

26

306

18 авг 2023, 00:07

Минимизация функции

в форуме Исследование операций и Задачи оптимизации

Fukse

2

318

01 июл 2020, 19:57

Минимизация функции

в форуме Дискретная математика, Теория множеств и Логика

Zqquiet

1

183

18 ноя 2022, 18:46

Минимизация обрезков

в форуме Исследование операций и Задачи оптимизации

oleg_botanik

1

437

23 июл 2015, 15:54

Минимизация количества вычислений

в форуме Информатика и Компьютерные науки

st256

7

497

21 дек 2016, 11:23

Динамическое программирование. Минимизация затрат

в форуме Исследование операций и Задачи оптимизации

Tatyana_IS

3

769

30 дек 2014, 09:07


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved