- •(23) Эргодические и неэргодические случайные процессы. (Тихонов Харисов стр. 69-70)
- •(24) Спектральное описание случайных процессов. Случайный спектр. (Тихонов Харисов стр. 80-82)
- •(29) Методы одномерной оптимизации дихотомии и Фибоначчи.
- •(30) Методы одномерной оптимизации, использующие информацию о производной.
- •(31) Методы многомерной оптимизации.
- •Часть 3. (33-43)
- •(33) Методы многомерной оптимизации первого порядка.
- •(34) Методы многомерной оптимизации второго порядка.
Часть 3. (33-43)
(33) Методы многомерной оптимизации первого порядка.
Методы 1-го порядка используют информацию о производной функции. Если ограниченная снизу целевая функция является дифференцируема на множестве , то алгоритм поиска точки минимума можно построить, используя информацию, по крайней мере, о градиенте этой функции.
Рассмотрим 2 типа методов:
- метод наискорейшего спуска (Коши);
- методы сопряжённых градиентов (Флетчера - Ривса и Поллака - Райвера)
Метод наискорейшего спуска
Идея его проста: градиент целевой функции в любой точке есть вектор в направлении наибольшего возрастания значения функции. Следовательно, антиградиент будет направлен в сторону наибольшего убывания функции и является направлением наискорейшего спуска. Антиградиент (и градиент) ортогонален поверхности уровня в точке .
Пусть в точке требуется определить направление наискорейшего спуска (то есть направление наибольшего локального уменьшения . Разложим в ряд Тейлора в окрестности точки и отбросим члены
второго порядка по и выше
Локальное уменьшение определяется вторым слагаемым, т.е. наибольшее уменьшение будет тогда, когда будет иметь наибольшую отрицательную величину. Этого можно добиться выбором , вектор спуска коллинеарен антиградиенту. Этот случай соответствует наискорейшему локальному спуску .
Формула нахождения следующей точки , где . Параметр находим решением задачи одномерной оптимизации
Методы сопряженных градиентов
В методе сопряженных направлений происходит отклонение направления наискорейшего спуска путем добавления к нему направления, используемого на предыдущем шаге. В методе сопряженного градиента строится последовательность точек
где
направления поиска , являются линейными комбинациями градиента текущего направления наискорейшего спуска, и предыдущих направлений поиска, т.е.
Направления и будут H сопряжёнными, то есть . Модификация метода определяют выбором параметров и оператора Н.
(34) Методы многомерной оптимизации второго порядка.
Методы, использующие информацию о производной второго порядка. Если функция дважды дифференцируема, то эффективность поиска точки минимума можно повысить, используя информацию не только о градиенте функции, но и о её матрице Гессе H(x).
Методы, использующие вторые производные, возникли из квадратичной аппроксимации целевой функции: f(x), которую можно получить при разложении функции в ряд Тейлора 2-го порядка: