Похожие презентации:
Методы безусловной минимизации функций многих переменных
1. Методы безусловной минимизации функций многих переменных
Методы получения точек, соответствующих условию (2),называются методами спуска.
2. Методы минимизации функций многих переменных
3. Методы безусловной минимизации функций многих переменных
Поверхностью уровня функции f(x) называется множествоточек, в которых функция принимает постоянное значение,
то есть f(x)=const
4. Необходимое условие оптимальности для дифференцируемых функций
Пусть задано пространство Eмножество.
и X E некоторое
n
n
Функция f(x) называется дифференцируемой в точке
x 0 X , если существует такой вектор f ( x0 ), что
для любого x в окрестности
справедливо
асимптотическое равенство:
f ( x) f ( x0 ) f ( x0 , x x0 ) ( x x0 )
x0
f ( x0 , x x0 ) - скалярное произведение векторов по
правилу ( x, y ) xi yi ;
x x, x - евклидова норма вектора;
( ) - величина бесконечно малая по сравнению с
i
5.
Вектор f ( x0 ) называется градиентом функции f(x) вn
точке x 0 и для x R
f ( x 0 ) f ( x 0 )
f ( x 0 )
f ( x 0 )
,
,...,
x 2
x n
x1
*
Оптимальное решение x , минимизирующее
дифференцируемую функцию f(x) на множестве X,
находится либо на границе X множества Х, либо на
множестве решений уравнения f(x) 0
Если f(x) дифференцируема, то направлением наибыстрейk
шего убывания функции f(x) в точке x является направk
ление антиградиента f ( x )
6.
Матрицей Гессе H(x) дважды непрерывно дифференцируемой в точке xфункции f(x) называется матрица частных производных второго порядка,
вычисленных в данной точке
7.
8.
9. Методы безусловной минимизации функций многих переменных
В различных вариантах методов спускаиспользуются разные способы выбора скаляра λ ( метод с
постоянным шагом, с дроблением шага, метод наискорейшего спуска)
Метод покоординатного спуска ( конфигураций или Хука-Дживса)
Метод конфигураций включает два основных этапа:
1) Поиск вокруг базисной точки (исследующий поиск);
2) Поиск в направлении, выбранном для оптимизации (поиск по образцу)
10. Метод покоординатного спуска
Основная идея метода покоординатного спуска11. Метод покоординатного спуска
12. Метод покоординатного спуска
13.
Алгоритм метода покоординатного спуска14.
Геометрическаяинтерпретация
15.
ПРИМЕР16.
17. Метод наискорейшего спуска
Идея метода наискорейшего спускаГеометрическая
интерпретация
18. Метод наискорейшего спуска
НАЧАЛОВЫБРАТЬ
0, x1 - начальная точка
+
k 1
f ( xk )
-
S k f ( x k ); f x k S k min
0
x xk , f ( x ) f ( xk )
*
*
xk 1 xk S k
k k 1
КОНЕЦ
19.
20. Метод наискорейшего спуска
Замечания:Метод наискорейшего спуска сходится достаточно быстро, если для
минимизирующей функции поверхности уровня близки к сферам. Однако,
если поверхности уровня минимизирующей функции сильно вытянуты в
некотором направлении, то метод сходится, но может застревать в
локальном минимуме.
В двумерном случае рельеф поверхности напоминает рельеф местности с
оврагом. Поэтому такие функции называются «овражными». Вдоль
направления, характеризующего дно оврага «овражная» функция меняется
незначительно, а в других направлениях, характеризующих склон оврага
происходит резкое изменение функции. Если начальная точка попадает на
склон оврага, то направление градиентного спуска оказывается
перпендикулярным к дну оврага и очередное приближение попадает на
противоположный склон оврага. В результате, вместо того, чтобы
двигаться вдоль дна оврага в направлении к точке минимума, траектория
спуска совершает зигзагообразные скачки поперек оврага, почти не
приближаясь к точке минимума.
21.
ПРИМЕР22. Геометрическая интерпретация
Метод сопряженных градиентовГеометрическая
интерпретация
Иллюстрация последовательных приближений метода наискорейшего спуска и
метода сопряжённых градиентов к точке экстремума.
23. Обоснование метода сопряженных градиентов
Нулевая итерация24.
25. Метод сопряженных градиентов
НАЧАЛОВЫБРАТЬ
k 1
+
-
КОНЕЦ
k k 1
26.
Замечание: Если требуется найти глобальный минимум функции f(x), Тодля строго выпуклой f(x) Решение этой задачи аналогично поиску
локального минимума функции. В случае, когда f(x) имеет несколько
локальных минимумов, поиск глобального минимума осуществляется в
результате перебора всех локальных минимумов.
27.
ПРИМЕР28.
Метод НьютонаМетод Ньютона относится к градиентным методам второго порядка, в
котором направление минимизации выбирается умножением вектора
антиградиента на матрицу, обратную матрице Гессе.
29.
Метод Ньютона30.
31.
Алгоритм метода Ньютона32.
Алгоритм метода Ньютона33.
ПРИМЕР34. Работа: «Методы многомерного поиска»
ЦЕЛЬ РАБОТЫ Ознакомиться с методами могомерного поиска. Сравнитьразличные алгоритмы по эффективности на тестовых примерах.
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
ВАРИАНТЫ
ТЕСТОВЫХ
ЗАДАНИЙ
-
-
СОДЕРЖАНИЕ ОТЧЕТА
титульный лист; цель работы; задание;
таблицы с результатами исследований по каждому методу, сравнение
эффективности работы разных алгоритмов;
34
безмашинный вариант реализации двух итераций каждым методом;
выводы по всем пунктам задания.