Обзор алгоритмов оптимизации Аспирант 1 г/о Максимов Алексей

Оптимизаци я Методы условной оптимизации, в большинстве своем, основаны, на сведении их к безусловной оптимизации (метод неопределенных множителей Лагранжа) Функци и Безусловная Условная (уравнения, неравенства) баланс масс, n i >= 0 Одной переменной Многих переменных

I.Метод золотого сечения II.Квадратичная интерполяция (Метод Пауэлла) III.Метод Брента (золотое сечение + квадратичная интерполяция) Функции одной переменной

IV. Кубическая интерполяция (Метод Дэвидона) Локальная замена минимизируемой функции многочленом третьей степени (три члена в разложении Тейлора) Интерполяционный многочлен строится по значениям функции и ее производной в двух точках + требуется задание приблизительного значения f min Функции одной переменной

Функции нескольких переменных Методы, использующие только значения функции Методы, требующие вычисления первых производных функции (градиента) Методы, требующие вычисления вторых производных функции Если нет замкнутого аналитического выражения для вычисления функции, то методы, требующие вычисления производных, практически не используются

Функции нескольких переменных I.Метод покоординатного спуска (метод релаксации) 1) Задается начальное приближение 2) Фиксируются все координаты, кроме одной, ищется минимум одномерным поиском. 3) Предыдущий шаг повторяется для всех координат.

Функции нескольких переменных II. Метод Хука – Дживса В начале работы алгоритма задается начальное приближение и шаг по каждой из координат. 1) Исследующий поиск 2) Шаг по образцу 3) Исследующий поиск

Симплекс в n-мерном пространстве – правильный многогранник с n+1 вершинами (n-мерное обобщение треугольника) – треугольник, тетраэдр… Симплекс – метод Низкая скорость сходимости (определяется размерами симплекса, а не поведением минимизируемой функции)

Метод деформируемого многогранника Нелдера - Мида Изменения в оригинальном «симплекс – методе»: 1) Отказ от сохранения одинаковых расстояний между вершинами (симплекс -> деформированный многогранник). 2) Произвольный коэффициент отражения. 3) Добавлено растяжение и сжатие многогранника (аналог шага по образцу в методе Хука - Дживса). В процессе поиска минимума многогранник вытягивается в направлении успешных шагов и сжимается в «неперспективных» направлениях

Методы с использованием производных Метод одномерного поиска Для избавления от ортогональности используется демпфирование, либо шаг заданной длины (идём не в самый минимум, а чуть-чуть от него отступаем)

Методы с использованием производных Квадратичная скорость сходимости Требуются вторые производные

Методы с использованием производных III. Модификации и улучшения метода Ньютона. 1. Метод Ньютона – Рафсона На очередной итерации метода Ньютона каким-либо из методов одномерной оптимизации выбирается оптимальный шаг. 2. Метод Флетчера – Ривса, Дэвидона–Флетчера–Пауэлла Гессиан не рассчитывается напрямую, а вычисляется на основе информации о кривизне целевой функции (требуется вычисление только первых производных). 3. Метод Левенберга – Марквардта Комбинация метода Ньютона с методом градиентного спуска

Вероятностные методы I.Метод имитации отжига (похож на метод градиентного спуска) II.Метод роя частиц III.Генетические алгоритмы