3.Нахождение безусловного экстремума градиентными методами

В отличии от методов прямого поиска градиентные методы поиска используют информацию о производных функции. Это позволяет уменьшить

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

3.1. Метод Коши

Описание алгоритма:

В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента.

- градиент функции

Алгоритм метода выглядит следующим образом:

, где - градиент.

Значение на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума вдоль направления градиента . Если в качестве взять некоторое положительное число, то получится простейший градиентный алгоритм:

Одно из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие:

Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.

Алгоритм метода:

Шаг 1. Задать: 1. Начальную точку х⁽⁰⁾ ;

2. Условие окончания поиска. Перейти к шагу 2.

Шаг 2. Вычислить направление поиска в виде антиградиента функции

s(x^(k) ) = - ∇f(x^(k) );

. Перейти к шагу 3.

Шаг 3. Найти новое приближение

, где - величина шага относительно текущего приближения. Перейти к шагу4.

Шаг 4. Проверка условия окончания поиска.

Да: закончить поиск;

Нет: перейти к шагу 2.

Ход решения:

Исходные данные:

_{Шаг 1.}

_Пусть

Шаг 2.

Вычислим компоненты градиента:

Итерация 1:

Шаг 3

Новое приближение определим по формуле:

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

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Итерация 2:

Шаг 3

Новое приближение определим по формуле:

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

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Итерация 3:

Шаг 3

Новое приближение определим по формуле:

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

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Итерация 4:

Шаг 3

Новое приближение определим по формуле:

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

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Решение поставленной задачи методом Коши представлено на рисунке 4.

Рисунок 4 – решение задачи методом Коши

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

Описание алгоритма:

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

, где:

- гессиан (матрица Гессе)

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

Алгоритм метода:

Шаг 1. Задать: начальную точку х⁽⁰⁾. Перейти к шагу 2.

Шаг 2. Вычислить направление поиска в виде

s(x^(k)) = –  .

Шаг 3. Найти новое приближение (являющееся решением задачи для квадратичной функции)

x^(k+1) = x^(k) + s(x^(k)) = x^(k) –  .

Шаг 4. Проверка на условие окончания вычислений.

Да: закончить процесс;

Нет: перейти к шагу 2.

Ход решения:

Исходные данные:

Шаг 1.

.

Шаг 2.

.

_{Шаг 3.}

Из формулы

,

Получаем:

, что совпадает с точным решением.

Решение поставленной задачи методом Ньютона представлено на рисунке 5.

Рисунок 5 – решение задачи методом Ньютона