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

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

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

(1)

Заметим, что (1) представляет собой квадратичную форму .

(2)

Необходимое условие для точки минимума квадратичной формы будет иметь вид:

(3)

(3')

(4)

Из (4) итерационная формула МН, ответственного за поиск точки минимума .

, (5)

Вывод формулы (5) позволяет рассматривать МН как метод последовательного нахождения точек минимума аппроксимирующих функций квадратичной формы ; последовательность этих точек минимума сходится к точке минимума функции - точке .

Вышесказанное иллюстрирует следующий график.

 

 

Последовательность точек с квадратичной скоростью сходимости к точке .

 

Г. Минимизация квадратичной формы методом Ньютона.

Докажем, что квадратичная форма вида:

(1)

минимизируется методом Ньютона за один (1) шаг.

Квадратичная форма (1) характеризуется матрицей , размерностью , , .

Заметим, что элементы матрицы - постоянные числа, характерные для соответствующей квадратичной формы.

Точку минимума квадратичной формы (1) находим из условия: . (2)

; (3)

Легко понять, что без доказательства вышеупомянутого необходимо воспользоваться итерационной формулой МН и получить такой же результат, как и (4).

, (5)

Очевидно, что для (1) матрица совпадает с матрицей квадратичной формы размерности .

(6)

(7)

Подставляем (7) в (6) и получаем:

(8)

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

 

ЛК №16

05.06.2003

 

(9) – результат, совпадающий с (4), что и доказывает существенный факт: квадратичную форму переменных МН минимизирует за один шаг - .

 

Д. Обобщенные методы Ньютона.

Сравним итерационную формулу обычного МН:

(1)

с итерационной формулой метода спуска (обобщенной итерационной формулой методов спуска): , (2)

Из сравнения (1) и (2) видно, что обычно в МН

(3)

а параметр .

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

Для того, чтобы сходимость МН не зависела от начального приближения, в итерационную формулу (1) вводят параметр , регулирующий длину шага и определенный точно также, как в МД или же МНС.

Если определяется так, как в МД , то говорят об обобщенном методе Ньютона первом, если определяется как в МНС, то говорят о втором обобщенном методе Ньютона (ОМН).

(4)

Итерационная формула (4) является общей для первого и второго обобщения.

 

Е. О модификации ОМН.

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

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

Естественно, что II-ая модификация дает лучшее приближение, чем I-ая.

 

См [3]

 

Детальное исследование см. [9].

Т.1

 

Т.2

 

 

См. определения сильно выпуклых функций.

 

 

Вывод.

 

III-я модификация ОМН основана на приведении матрицы вторых производных к диагональному виду.

 

Ж. Теоремы о сходимости МН.

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

,

дает последовательность точек , сходящуюся к точке с квадратичной скоростью:

, .

Аналогично формулируется Т.1 и для случая, когда решается задача минимизации функции , т.е. когда решается система уравнений метода Ньютона.

Как видно из Т.1, сходимость МН зависит от выбора начального приближения. Этот недостаток МН преодолим путем введения регулируемого параметра в ОМН.

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

,

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

Если условие Липшица не выполняется для матрицы двух производных, то скорость сходимости ОМН сверхлинейная.

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

 

 

Основное достоинство метода Ньютона: квадратичная скорость сходимости, скорость более высокая, чем у градиентных методов. Этот метод является эффективным методом минимизации функций, близких к квадратичным функциям (обратность функций МН " не опасна" при этом).

Недостаток МН: необходимость формировать матрицу и находить по ней .

Заметим, что МН является численным методом многомерной безусловной оптимизации второго порядка.

 

Краткие выводы.

В I части курса МО изучены:

1) аналитические и аналитико-численные методы решения задач многомерной безусловной оптимизации: и классической задачи условной оптимизации: ;

2) численные методы одномерной и многомерной безусловной оптимизации:

а) МД и МЗС;

б) МД , МНС, МПКС (М1П или М I П);

в) МН, ОМН (М2П или М II П).

 

ЛК №1

03.09.2003

 

 

Осенний семестр 2003-2004 г.

МЕТОДЫ ОПТИ­МИЗАЦИИ (МО), Часть 2

 

ГЛАВА 2

⇐ Предыдущая234567891011Следующая ⇒

Поделиться: