МО26

Методы минимизации функций многих переменных

Методы безусловной минимизации функций
многих переменных
Поверхностью уровня функции f(x) называется множество
точек, в которых функция принимает постоянное значение,
то есть f(x)=const
Определение
Примеры

Функция f(x) называется дифференцируемой в точке
, если существует такой вектор , что
для любого x в окрестности справедливо
асимптотическое равенство:
Пусть задано пространство и некоторое
множество.
Необходимое условие оптимальности для дифференцируемых функций
скалярное произведение векторов по
правилу ;
- евклидова норма вектора;
Определение
- величина бесконечно малая по сравнению с

Если f(x) дифференцируема, то направлением наибыстрей-
шего убывания функции f(x) в точке является направ-
ление антиградиента
Оптимальное решение , минимизирующее
дифференцируемую функцию f(x) на множестве X,
находится либо на границе множества Х, либо на
множестве решений уравнения
Вектор называется градиентом функции f(x) в
точке и для
Определение
Утверждение

Матрицей Гессе H(x) дважды непрерывно дифференцируемой в точке x
функции f(x) называется матрица частных производных второго порядка,
вычисленных в данной точке
Определение
Пример

Определение

Методы безусловной минимизации функций
многих переменных
Метод покоординатного спуска ( конфигураций или Хука-Дживса)
Метод конфигураций включает два основных этапа:
Поиск вокруг базисной точки (исследующий поиск);
Поиск в направлении, выбранном для оптимизации (поиск по образцу)
В различных вариантах методов спуска
используются разные способы выбора скаляра λ ( метод с постоянным шагом, с дроблением шага, метод наискорейшего спуска)

Метод покоординатного спуска
Основная идея метода покоординатного спуска

Метод покоординатного спуска

Метод покоординатного спуска

Алгоритм метода покоординатного спуска

Геометрическая
интерпретация

ПРИМЕР

Метод наискорейшего спуска
Идея метода наискорейшего спуска
Геометрическая
интерпретация

ВЫБРАТЬ
- начальная точка
Метод наискорейшего спуска
НАЧАЛО
КОНЕЦ
+
-

Метод наискорейшего спуска
Замечания:
Метод наискорейшего спуска сходится достаточно быстро, если для минимизирующей функции поверхности уровня близки к сферам. Однако, если поверхности уровня минимизирующей функции сильно вытянуты в некотором направлении, то метод сходится, но может застревать в локальном минимуме.
В двумерном случае рельеф поверхности напоминает рельеф местности с оврагом. Поэтому такие функции называются «овражными». Вдоль направления, характеризующего дно оврага «овражная» функция меняется незначительно, а в других направлениях, характеризующих склон оврага происходит резкое изменение функции. Если начальная точка попадает на склон оврага, то направление градиентного спуска оказывается перпендикулярным к дну оврага и очередное приближение попадает на противоположный склон оврага. В результате, вместо того, чтобы двигаться вдоль дна оврага в направлении к точке минимума, траектория спуска совершает зигзагообразные скачки поперек оврага, почти не приближаясь к точке минимума.

ПРИМЕР

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

Обоснование метода сопряженных градиентов
Определение
Нулевая итерация

Метод сопряженных градиентов
ВЫБРАТЬ
НАЧАЛО
КОНЕЦ
+
-

Замечание: Если требуется найти глобальный минимум функции f(x), То для строго выпуклой f(x) Решение этой задачи аналогично поиску локального минимума функции. В случае, когда f(x) имеет несколько локальных минимумов, поиск глобального минимума осуществляется в результате перебора всех локальных минимумов.

ПРИМЕР

Метод Ньютона
Метод Ньютона относится к градиентным методам второго порядка, в котором направление минимизации выбирается умножением вектора антиградиента на матрицу, обратную матрице Гессе.

Метод Ньютона

Алгоритм метода Ньютона

Алгоритм метода Ньютона

ПРИМЕР