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

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

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

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

где - матрица Гессе.

Если функция в некоторой точке имеет минимум, то в этой точке.

Отсюда следует, что если матрица имеет обратную, то точкуможно найти по формуле

.

Повторяя эту процедуру, получим рекуррентную формулу метода Ньютона:

,

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

Важнейшим обобщением метода Ньютона является метод Ньютона с регулировкой шага. Последовательность итераций строится в соответствии с формулой

,

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

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

Пример. Щелкнув по значку, откроется Mathcad документ метода Ньютона, в котором можно выполнить вычисления.

Минимизация функции

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

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

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

,

где

; (1)

; (2)

; (3)

. (4)

Следует отметить, что и- симметричные матрицы, следовательно,- симметричная и положительно определенная матрица. Матрицаобеспечивает сходимостьк; матрицаобеспечивает положительную определенностьна всех этапах и на конечном этапе исключает начальную. В качествеможно выбрать единичную.