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

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

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

Часовой пояс: 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
Сообщений: 1497
Cпасибо сказано: 0
Спасибо получено:
274 раз в 267 сообщениях
Очков репутации: 65

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

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

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

Вернуться к началу
 Профиль  
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
Сообщений: 4277
Cпасибо сказано: 129
Спасибо получено:
1504 раз в 1391 сообщениях
Очков репутации: 214

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Методы оптимизации функции с большим количеством неизвестных
СообщениеДобавлено: 03 сен 2019, 13:08 
Не в сети
Light & Truth
Зарегистрирован:
12 окт 2017, 13:50
Сообщений: 2135
Cпасибо сказано: 78
Спасибо получено:
649 раз в 625 сообщениях
Очков репутации: 194

Добавить очки репутацииУменьшить очки репутации
[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
Сообщений: 5869
Cпасибо сказано: 69
Спасибо получено:
917 раз в 872 сообщениях
Очков репутации: 168

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

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

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

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

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

Спасибо.

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

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

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

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

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

Aleks

0

354

17 дек 2012, 00:53

Консультация (методы оптимизации)

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

Sylar

0

164

18 авг 2017, 16:39

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

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

VladKomosh

1

208

14 май 2016, 20:14

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

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

Vasya1992

2

551

26 май 2013, 13:38

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

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

67xk

2

260

01 апр 2016, 14:33

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

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

black1978

67

937

10 янв 2018, 00:41

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

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

Human

1

424

25 июл 2012, 19:47

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

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

Majestio

4

204

17 авг 2017, 04:29

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

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

lanc3r

8

451

04 дек 2015, 17:17

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

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

Sammi2186

0

174

29 май 2014, 21:09


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



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

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


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

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

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

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