Формализация

Алгоритм

К-я итерация

Нулевая итерация

Обоснование метода

Основные понятия

Определим терминологию:

Пусть.

Введём на целевую функцию.

Вектора называются сопряжёнными, если:

где — матрица Гессе.

Теорема (о существовании). Существует хотя бы одна система сопряжённых направлений для матрицы, т.к. сама матрица (её собственные вектора) представляет собой такую систему.

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

Пусть

Тогда.

Определим направление так, чтобы оно было сопряжено с:

Разложим в окрестности и подставим:

Транспонируем полученное выражение и домножаем на справа:

В силу непрерывности вторых частных производных. Тогда:

Подставим полученное выражение в (3):

Тогда, воспользовавшись (1) и (2):

Если, то градиент в точке перпендикулярен градиенту в точке, тогда по правилам скалярного произведения векторов:

Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления:

На k-й итерации имеем набор.

Тогда следующее направление вычисляется по формуле:

где непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.

Это выражение может быть переписано в более удобном итеративном виде:

• Пусть — начальная точка, — направление антиградиента и мы пытаемся найти минимум функции. Положим и найдем минимум вдоль направления. Обозначим точку минимума.

• Пусть на некотором шаге мы находимся в точке, и — направление антиградиента. Положим, где выбирают либо (стандартный алгоритм), либо (алгоритм Полака–Райбера). После чего найдем минимум в направлении и обозначим точку минимума. Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив и повторив шаг.

1. Задаются начальным приближением и погрешностью:
2. Рассчитывают начальное направление:
• Если или, то и останов.
• Иначе
• если, то и переход к 3;
• иначе и переход к 2.

Методы оптимизации
Одномерные	Метод золотого сечения • Метод деления пополам • Метод дихотомии • Метод парабол • Метод равномерного поиска (перебора) • Метод равномерного блочного поиска • Метод троичного поиска
Прямые методы	Метод Гаусса • Метод Нелдера — Мида • Метод конфигураций • Метод Розенброка • Метод сопряжённых направлений • Метод Хука — Дживса
Первого порядка	Градиентный спуск • Метод покоординатного спуска • Метод сопряжённых градиентов
Второго порядка	Метод Ньютона • Метод Ньютона-Рафсона
Стохастические	Дифференциальная эволюция • Имитация отжига
Методы линейногопрограммирования	Метод эллипсоидов • Симплекс-метод • Метод потенциалов