Методы второго порядка

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

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

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

Стратегия поиска

Стратегия метода Ньютона [ Newton I. ] состоит в построении последова­тельности точек {х _k}, k = 0,1,..., таких, что  k = 0,1,.... Точки последовательности вычисляются по правилу

                          (5)

где х₀ задается пользователем; величина шага  определяется для каждого значения k по формуле

.                               (6)

Выбор  по формуле (6) гарантирует выполнение требования  при условии, что . Формула (6) получена из следующих соображений:

1. Функция f (х) аппроксимируется в каждой точке последовательности {х ^k} квадратичной функцией .

2. Направление  определяется из необходимого условия экстремума пер­вого порядка:  Таким образом, при выполнении требования  последовательность является последовательностью точек минимумов квадратич­ных функций F_k , k = 0,1,... (рис. 8). Чтобы обеспечить выполнение требования , k = 0,1,..., даже в тех случаях, когда для каких-либо значений матрица Гессе  не окажется положительно определенной, рекомендуется для соответствующих значений k вычислить точку   по методу градиентного спуска  с выбором величины шага     из условия .

Рис. 8

Построение последовательности {х _k} заканчивается в точке х _k, для кото­рой  где - заданное малое положительное число, или при  (М - предельное число итераций), или при двукратном одновременном выполне­нии двух неравенств ,  где - малое положительное число. Вопрос о том, может ли точка х _k рассматриваться как най­денное приближение искомой точки минимума, решается путем проведения дополнительного исследования, которое описано ниже.

Сходимость

Утверждение. Пусть f ( x ) дважды непрерывно дифференцируемая сильновыпуклая функция с константой l > 0 на Rⁿ и удовлетворяет условию

,

где L > 0, а начальная точка такова, что   , т.е.

,

где .. Тогда последовательность { x^k } сходится к точке минимума с квадратичной скоростью .

Замечание 1. Сходимость метода Ньютона доказана лишь для сильно выпуклых функ­ций и для достаточно хорошего начального приближения, определяемого услови­ем , практическое использование которого крайне затруднено, так как по­стоянные l и L , как правило, неизвестны или требуют трудоемкого исследования для их определения. Поэтому при практическом использовании метода Ньютона следует:

а) анализировать матрицу Н(х _k)на выполнение условия Н(х _k) < 0  и заменять формулу  на формулу  в случае его невыполнения;

б) производить анализ точки х _k с целью выяснения, является ли она най­денным приближением искомой точки х_*.

Замечание 2. При решении задачи поиска безусловного максимума формула (6) не изменяется, так как в этом случае Н(х _k ) < 0.