Алгоритм
К-я итерация
Нулевая итерация
Обоснование метода
Основные понятия
Определим терминологию:
Пусть.
Введём на целевую функцию.
Вектора называются сопряжёнными, если:
где — матрица Гессе.
Теорема (о существовании). Существует хотя бы одна система сопряжённых направлений для матрицы, т.к. сама матрица (её собственные вектора) представляет собой такую систему. |
Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) к точке экстремума.
Пусть
Тогда.
Определим направление так, чтобы оно было сопряжено с:
Разложим в окрестности и подставим:
Транспонируем полученное выражение и домножаем на справа:
В силу непрерывности вторых частных производных. Тогда:
Подставим полученное выражение в (3):
Тогда, воспользовавшись (1) и (2):
Если, то градиент в точке перпендикулярен градиенту в точке, тогда по правилам скалярного произведения векторов:
|
|
Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления:
На k-й итерации имеем набор.
Тогда следующее направление вычисляется по формуле:
где непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.
Это выражение может быть переписано в более удобном итеративном виде:
- Пусть — начальная точка, — направление антиградиента и мы пытаемся найти минимум функции. Положим и найдем минимум вдоль направления. Обозначим точку минимума.
- Пусть на некотором шаге мы находимся в точке, и — направление антиградиента. Положим, где выбирают либо (стандартный алгоритм), либо (алгоритм Полака–Райбера). После чего найдем минимум в направлении и обозначим точку минимума. Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив и повторив шаг.
- Задаются начальным приближением и погрешностью:
- Рассчитывают начальное направление:
- Если или, то и останов.
- Иначе
- если, то и переход к 3;
- иначе и переход к 2.
Методы оптимизации | |
Одномерные | Метод золотого сечения • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод троичного поиска |
Прямые методы | Метод Гаусса • Метод Нелдера — Мида • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса |
Первого порядка | Градиентный спуск • Метод покоординатного спуска • Метод сопряжённых градиентов |
Второго порядка | Метод Ньютона • Метод Ньютона-Рафсона |
Стохастические | Дифференциальная эволюция • Имитация отжига |
Методы линейногопрограммирования | Метод эллипсоидов • Симплекс-метод • Метод потенциалов |