Контрольная работа по "Методы оптимизации"

Для удобства введем обозначения: .

Таким образом,

Запишем изменение градиента  при переходе от точки  к точке . С учетом обозначений имеем:

    или  ,

что выражает свойство квадратичных функций.

Схема алгоритма  МСГ.

Положить  .

Ш. 1 Пусть - начальная точка; ,

.

Ш. 2 Определить , где

.

Затем ,

,

 находится из условия  (сопряжены относительно матрицы ).

Ш. 3 Положить Ш. 2.

Критерий останова одномерного  поиска вдоль каждого из направлений записывается в виде:  .

Значения  выбираются таким образом, чтобы направление было -сопряжено со всеми построенными ранее направлениями.

7. Метод Дэвидона–Флетчера–Пауэлла.

 

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

Если функция  не квадратичная, то МН не отличается высоким быстродействием и надежностью. В модифицированном МН последовательность итераций строится в соответствии с формулой: .

 

Метод сопряженных градиентов.

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

.

Идея метода состоит  в последовательном построении направлений , взаимно сопряженных относительно матрицы ( -сопряженных). На каждом шаге " " направление получается как линейная комбинация градиентов [ ] в точке и предшествующих направлений ( ), причем коэффициенты линейной комбинации выбираются так, чтобы было сопряженным ко всем предшествующим направлениям.

Для удобства введем обозначения: .

Таким образом,

Запишем изменение градиента  при переходе от точки  к точке . С учетом обозначений имеем:

    или  ,

что выражает свойство квадратичных функций.

Метод Флетчера–Ривза (МФР).

Флетчер и Ривз расширили  предшествующий метод на случай произвольных функций. В применении к квадратичным функциям он становится равносильным методу сопряженных градиентов.

 

Квазиньютоновские методы основаны на свойствах квадратичных функций. Данные методы обладают положительными чертами метода Ньютона, однако используют только первые производные. С чем это связано?

Итерационный поиск  по методу Ньютона осуществлялся  по формуле (обобщенный случай с ):

.   (7.1)

Трудность может возникнуть, когда матрица Гессе  не является положительно определенной. В этом случае направление перемещения

  (7.2)

может не быть направлением спуска и глобальная сходимость метода не будет обеспечена.

В таких ситуациях  обратную матрицу Гессе  заменяют положительно определенной матрицей , дающей направление перемещения, исходя из градиента . Отсюда получаем итерационную формулу

,    (7.3)

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

Очевидно, что матрица  на каждой итерации модифицируется так, чтобы для каждой квадратичной функции вида (с положительно определенной матрицей ) матрицы сходились к обращению матрицы Гессе функции .

Следовательно, на конечном этапе сходимости мы вновь придем к методу Ньютона.

Если метод применяется  к произвольной функции, то может рассматриваться на каждом шаге как аппроксимация (положительно определенная) обращения матрицы Гессе функции .

Для аппроксимации матрицы  пользуются следующим рекуррентным соотношением:

,    (7.4)

где - корректирующая матрица.

Матрица будет использоваться в формулах (7.1), (7.2), (7.3). Задача заключается в том, чтобы построить матрицу таким образом, чтобы последовательность давала приближение к . При этом для получения решения требуется один дополнительный поиск вдоль прямой, если - квадратичная функция. Данный подход приводит к успеху при решении задач с нелинейными ЦФ общего вида.

Еще раз напомним свойства квадратичных функций

Изменение градиента  при переходе из точки  в выражается соотношением

или 

.    (7.5)

Предположим, что матрица  аппроксимируется по формуле

,

где - скалярная величина. Наиболее предпочтительным является приближение, удовлетворяющее соотношению (7.5), то есть .

Однако построить такую  аппроксимацию невозможно, т.к. для  того чтобы найти , необходимо знать матрицу . Здесь используются следующие обозначения:

,    .

С другой стороны, можно  потребовать, чтобы новое приближение  удовлетворяло также формуле (7.5) с учетом свойств квадратичных функций:

,  .    (7.6)

Подставляя (7.4) в (7.6), получим:

.

Выразим отсюда :  

.    (7.7)

С помощью непосредственной подстановки можно убедиться, что матрица

   (7.8)

Этот алгоритм использует матрицу коррекции ранга 2. В формуле (7.8) положим

  и  .

Тогда получим:

  (7.9)

Данная рекуррентная формула сохраняет свойства симметрии и положительной определенности матриц. Поэтому, если - симметричная положительно определенная матрица, то матрицы будут так же симметричными положительно определенными матрицами (см. ниже теорему).

Обычно удобно выбирать , где - единичная матрица. Точка получается из перемещением в направлении .

В формуле (4.34): .

Обозначим .

Достоинства метода

1. Метод ДФП – наиболее широко используемый градиентный метод.
2. Устойчивость – при решении самых различных задач, возникающих на практике.

Недостаток. Необходимость хранения матрицы порядка .

 

 

8. Найти минимум целевой  функции одним из квазиньютоновских  методов:

Решаем методом Дэвидона–Флетчера–Пауэлла.

Градиент функции:

.

Направление для поиска:

Находим точку  .

 

Итерация 1.

;

;

;

 

 

Следующее направление для поиска:

Находим точку 

 

Итерация 2.

;

Следующее направление для поиска:

Находим точку  .

Итерации продолжаются аналогично.

 

 

 

9. К какому методу  относится данное уравнение 

1. Метод Марквардта
2. Метод Коши
3. Модифицированный метод Ньютоа
4. Метод Ньютона

 

Итерационная формула  метода Ньютона:

.

Эта формула есть не что  иное, как МН в применении к решению системы нелинейных уравнений:

.

Уравнение относится к методу Ньютона.