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

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

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 11:14 
Не в сети
Начинающий
Зарегистрирован:
03 сен 2019, 10:59
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте. Сразу оговорюсь, я не математик по образованию и за какие то неточности или даже может быть глупости, написанные мной, прошу прощения.
Создается ПО. Одной из задач стоящей перед этим ПО будет нахождения минимума функции с большим количеством неизвестных (в районе 30-100 неизвестных).
Вопросы:
1. Какие методы оптимизации существуют для подобной ситуации? Сам я отыскал два метода. Метод градиентного спуска и метод нелдера-Мида.
2. Какой из существующих методов оптимизации обладает наилучшей точностью и быстродействием? (время работы ПО имеет важное значение)

Спасибо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 12:06 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
28 апр 2016, 13:40
Сообщений: 1366
Cпасибо сказано: 0
Спасибо получено:
247 раз в 241 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
evYpe
методов поиска минимума (максимума) функции многих переменных существует много. Скорость сходимости зависит от многих факторов: вида целевой функции, области поиска и т.д.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 12:28 
Не в сети
Light & Truth
Зарегистрирован:
08 апр 2015, 12:21
Сообщений: 3768
Cпасибо сказано: 112
Спасибо получено:
1274 раз в 1183 сообщениях
Очков репутации: 182

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 12:37 
Не в сети
Начинающий
Зарегистрирован:
03 сен 2019, 10:59
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

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


Большое спасибо за ответ. Правильно ли я понял? Для лучшего решения задачи следует использовать несколько методов? Сначала нулевого, потом первого и потом второго порядка? Или какой то из методов можно пропустить?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 12:43 
Не в сети
Light & Truth
Зарегистрирован:
08 апр 2015, 12:21
Сообщений: 3768
Cпасибо сказано: 112
Спасибо получено:
1274 раз в 1183 сообщениях
Очков репутации: 182

Добавить очки репутацииУменьшить очки репутации
Обычно используют сочетание методов нулевого и второго порядков, если требуется и скорость, и точность. При этом критерии запуска методов первого и второго порядков одинаковые, поэтому можно пропустить градиентные методы при переходе.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 13:08 
В сети
Beautiful Mind
Зарегистрирован:
12 окт 2017, 13:50
Сообщений: 1801
Cпасибо сказано: 60
Спасибо получено:
526 раз в 506 сообщениях
Очков репутации: 183

Добавить очки репутацииУменьшить очки репутации
[math]evYpe,[/math]
Есть много методов для оптимизации ф-ии с большим количеством неизвестных и методы прямого поиска и
градиентные! Я рекомендую Вам маленкая, но хорошая книжечку Брайэна Банди "методы оптимизации.Вводной курс"!
Описаны методов оптимизации и одного и многих переменных.
Здесь есть и немного теории и описания алгоритмов и блок-схемы и листинги программы на Бейсик!
Вот Вам и ссылку для скачивания :
http://elprivod.nmu.org.ua/files/optimi ... %D0%B8.pdf

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 14:09 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
15 мар 2016, 15:08
Сообщений: 5548
Cпасибо сказано: 59
Спасибо получено:
853 раз в 813 сообщениях
Очков репутации: 163

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 14:30 
Не в сети
Light & Truth
Зарегистрирован:
08 апр 2015, 12:21
Сообщений: 3768
Cпасибо сказано: 112
Спасибо получено:
1274 раз в 1183 сообщениях
Очков репутации: 182

Добавить очки репутацииУменьшить очки репутации
В своё время работал с целевыми функциями (достаточно гладкими, но с очень овражными минимумами) с несколькими десятками переменных, которые требовали большого машинного времени. Метод Ньютона-Рафсона вне конкуренции по сравнению не только с градиентными методами, но и с методами Дэвидона-Флетчера-Пауэлла, которые до сих пор пытаются навязать как альтернативу ньютоновским методам, но в действительности они дают такую же линейную сходимость, как и градиентные методы. Ну может быть выигрыш 500 итераций вместо 1000 по сравнению с чисто градиентными. Зато ньютон-рафсоновские алгоритмы позволяли достичь нужной точности не более, чем за 10 итераций (квадратичная сходимость итераций). И это для очень плохих матриц Гессе с числом обусловленности несколько порядков. Замечу, что в моих задачах вычисление матрицы Гессе занимало очень много времени, чем расчет градиентов, но эти затраты потом окупались за счет высокой сходимости.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 22:09 
Не в сети
Light & Truth
Зарегистрирован:
03 ноя 2013, 19:19
Сообщений: 2779
Cпасибо сказано: 443
Спасибо получено:
798 раз в 682 сообщениях
Очков репутации: 135

Добавить очки репутацииУменьшить очки репутации
evYpe писал(а):
Одной из задач стоящей перед этим ПО будет нахождения минимума функции с большим количеством неизвестных (в районе 30-100 неизвестных).
Вопросы:
1. Какие методы оптимизации существуют для подобной ситуации? Сам я отыскал два метода. Метод градиентного спуска и метод нелдера-Мида.
2. Какой из существующих методов оптимизации обладает наилучшей точностью и быстродействием? (время работы ПО имеет важное значение)

Спасибо.

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

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

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Консультация (методы оптимизации)

в форуме Объявления участников Форума

Sylar

0

148

18 авг 2017, 16:39

Методы оптимизации производства

в форуме Математическая статистика и Эконометрика

Aleks

0

348

17 дек 2012, 00:53

Задача на классические методы оптимизации

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

VladKomosh

1

204

14 май 2016, 20:14

Вариационное исчисление и методы оптимизации

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

Vasya1992

2

528

26 май 2013, 13:38

Исследование операций и методы оптимизации в образовании

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

67xk

2

249

01 апр 2016, 14:33

Пространство с большим числом измерений

в форуме Размышления по поводу и без

black1978

67

889

10 янв 2018, 00:41

Рациональное приближение с бесконечно большим знаменателем

в форуме Интересные задачи участников форума MHP

Human

1

423

25 июл 2012, 19:47

Подсчет вероятности, связь с количеством комбинаций

в форуме Комбинаторика и Теория вероятностей

lanc3r

8

418

04 дек 2015, 17:17

Решение задач с недостаточным количеством информации

в форуме Размышления по поводу и без

Majestio

4

199

17 авг 2017, 04:29

Фу-ия двух переменных с нужным количеством точек экстремума

в форуме Дифференциальное исчисление

Sammi2186

0

174

29 май 2014, 21:09


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



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

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


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

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

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

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