Г. О сходимости градиентных методов.

Детальное исследование этого вопроса изложено в [9].

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

Сформулируем две теоремы о сходимости градиентных методов [9].

Теорема: Если ограничена снизу и ее градиент удовлетворяет условию Липшица: , , - постоянная Липшица; а параметр определяется способом, указанным в МД или в МНС, то выполнимо следующее предельное соотношение: при ,

Эта теорема подтверждает правомерность условия окончания вычислений в градиентных методах поиска точки . Как известно, эти условия имеют вид: , .

Теорема: Пусть сильно выпуклая функция, т.е. функция, матрица вторых производных которой удовлетворяет условию:

 

Повторить понятия: " выпуклая функция", " сильно выпуклая функция".

 

 

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

Отметим, что при , и скорость сходимости ГМ существенно снижается, при , скорость ГМ существенно возрастает.

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

Итак, ГМ обладает относительно простым алгоритмом.

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

 

Численные методы многомерной безусловной оптимизации второго порядка.

Метод Ньютона: сущность, итерационная формула, геометрическая интерпретация, сходимость.

А. Метод Ньютона, как метод нахождения корней уравнения или метод решения системы уравнений .

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

, . (2)

Заметим, что система уравнений (2) в общем случае нелинейная. Заметим, что систему (2) кратко можно представить в виде: , где ; . (2')

 

ЛК №15

29.05.2003

 

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

Пусть - -ое приближение к корню уравнения (1). Разложим функцию в ряд Тейлора в окрестности точки ограничиваясь линейным приближением по приращению .

(3)

Подставляя (3) в (1), получаем выражение для .

(4) - итерационная формула МН (метода касательных), ответственного за поиск корня уравнения (1).

Система уравнений (2) (или (2')) МН выглядит так:

- итерационная формула МН " ответственного" за решение системы уравнений .

 

Б. Метод Ньютона как метод нахождения экстремальных точек функции .

Пусть в системе уравнений (1) векторная функция векторного аргумента равна , где - минимизируемая скалярная функция векторного аргумента, тогда система уравнений (1) принимает вид: . (2)

Общеизвестно, что (2) – есть необходимое условие для точки локального минимума (максимума) функции .

В связи с этим, решение системы уравнений (2) представляет точку минимума функции .

Итерационную формулу для решения системы уравнений (2) легко получить, если в (5) пункта А вместо функции написать т.е. воспользоваться равенством:

, (3)

где - итерации 0, 1, 2, …

(3) – итерационная формула метода Ньютона, ответственного за нахождение точки минимума функции .

 

 

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

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

Для реализации МН необходимо сформировать и обратить матрицу .

 

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

Поделиться: