Регулярные методы минимизации функций (прямые методы и методы сопряженных направлений).

Конспект:

Прямые методы (при работе не используются производные от целевой функции)

Методы сопряженных направлений (тоже не используются производные от целевой функции)

К прямым относят симплексные методы (Нелдера-Мида)

<= что это за рисунок и какому методу – без понятия.

Википедия:

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

Суть метода заключается в последовательном перемещении и деформировании симплекса вокруг точки экстремума.

Метод находит локальный экстремум и может «застрять» в одном из них. Если всё же требуется найти глобальный экстремум, можно пробовать выбирать другой начальный симплекс. Более развитый подход к исключению локальных экстремумов предлагается в алгоритмах, основанных на методе Монте-Карло, а также в эволюционных алгоритмах.

Липа какая-то:

Метод сопряженных направлений Пауэлла

Описание алгоритма:

Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:

приводится к виду сумма полных квадратов

то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.

В методе Пауэлла поиск реализуется в виде:

вдоль направлений , , называемых -сопряженными при линейной независимости этих направлений.

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

Алгоритм метода:

Шаг 1. Задать исходные точки ,  и направление . В частности, направление  может совпадать с направлением координатной оси;

Шаг 2. Произвести одномерный поиск из точки  в направлении  получить точку , являющуюся точкой экстремума на заданном направлении;

Шаг 3. Произвести одномерный поиск из точки  в направлении  получить точку ;

Шаг 4. Вычислить направление ;

Шаг 5. Провести одномерный поиск из точки  (либо ) в направлении  с выводом в точку .

Методы минимизации функций (случайный поиск).

Применяются численные методы поиска экстремума функции. Эти методы делятся на 2 группы:

1. методы случайного поиска минимума ф-ции

2. регулярные методы

методы случайного поиска

Методы случайного поиска бывают без обучения и с самообучением.

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

Методы с самообучением. При работе используется информация об оптимальных значениях параметров на предыдущих шагах поиска. Недостаток – точность недостаточная для решения практических задач.

1. метод покоординатного обучения

2. метод повторяющегося случайного поиска

3. метод случайного поиска с постоянным радиусом

4. метод переменного поиска с переменным радиусом