15. Постановка задачи безусловной оптимизации фнп. Методы второго порядка. Метод Ньютона.

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

Суть методов состоит в следующем:Необходимым условием экстремума функции многих переменных f(x) в точке х* является равенство нулю ее градиента в этой точке:f’(х^*) 0, т.е g(x)= 0 или , i=1...n

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

Метод Ньютона основан на линейном приближении вектор-функции g(x)=(g1(x),g2(x),...,gn(x)), а именно:

g(x) ≈ g(x0 ) + G(x0 )*(x - x0 ) ,

где - матрица первых производных функции g(x) , она же матрица Гессе (матрица вторых производных) для оптимизируемой функции f(x).

Т.к. необходимо найти x*, для которого g(x*)= 0, то, подставляя ноль в левую часть равенства (3), получим формулы для приближения корня системы уравнений (2):

G(x0)*Dx = - g(x0), x = x0 + Dx

В дальнейшем вектор приращения или направление поиска Dx будем обозначать буквой р.

Алгоритм:

1. Выбор x0 (начального приближения), eg и ex (точности решения по градиенту и аргументу).

2. k:= 0. (инициализация счетчика итераций)

3. Аналитическое определение всех частных производных функции f(x) - g_j(x), т.е. вектора градиента и G(x) - матрицы вторых производных - для оптимизируемой функции.

4. Расчет g(x0).

5. Расчет G(x0).

6. Решение системы (4), например, методом Гаусса или методом Зейделя, т.е. определение р=Dx - шага.

7. x:= x0 + р ; k:=k+1.

8. расчет g(x).

9. Если |р|< ex (точность по аргументу) или |g(x)|< eg , то идти к п.11.

10. x0:= x ; g(x0):=g(x); идти к п.5.

11. Оценка погрешностей измерения значения функции df и определения оптимума dx.

12. Выводим вектор x и g(x) , значения оптимизируемой функции f(x) и количества итераций к.

16. Пз безусловной оптимизации фнп. Методы второго порядка. Метод Ньютона с дробным шагом. Алгоритм выбора длины шага.

ПЗ: Дана непрерывно дифференцируемая функция n переменных. Необходимо найти хотя бы одну точку локального оптимума этой функции:

, где , ,

К методам 2-го порядка относятся метод Ньютона и метод Ньютона с дробным шагом.

Метод Ньютона с дробным шагом: Делаем пробный шаг, если удовлетворяет условиям, то идем дальше, если нет, то делаем дробный шаг.

Ньютоновское направление:

,

шаг

Перед расчетом оптимума необходимо найти первую и вторую производные функции:

g(x) = df/dx

Алгоритм метода Ньютона состоит в следующем.

1. В начальной точке х₀ вычисляется вектор p

2. На k-й итерации определяются шаг α и точка х[k+1].

3. Вычисляется величина f(х[k+1]).

4. Проверяются условия выхода из подпрограммы, реализующей данный алгоритм. Эти условия аналогичны условиям выхода из подпрограммы при методе наискорейшего спуска. Если эти условия выполняются, осуществляется прекращение вычислений. В противном случае вычисляется новое направление р[k+1] и осуществляется переход к следующей итерации.

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

Определение длины шага:

1. α:=1

2. while f(x+p* α)-f(x)>=0 уменьшаем шаг α:= α*γ

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