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

 

Методы безусловной оптимизации второго порядка используют некоторые частные производные минимизируемой функции . Суть этих методов состоит в следующем [3,11]:

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

(57)

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

, где (58)

- обратная матрица для матрицы Гессе, а - направление спуска.

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

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

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

(59)

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

(60)

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

Алгоритм метода Ньютона – Рафсона состоит в следующем:

1. В точке вычисляется ;

2. На k- том шаге в соответствии с выражениями (59) и (60) определяются шаг и точка ;

3. Вычисляется величина ;

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

и осуществляется переход к п.2.

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

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

Предлагаю ознакомиться с аналогичными статьями: