Алгоритм метода сопряжённых градиентов

 

Шаг 0.   Задать параметр точности , выбрать х⁰ , вычислить f(x⁰).

Шаг 1. Положить к=0, p⁰= - ;

Шаг 2. Решить задачу одномерной минимизации

  Ф(α)=f(х⁰+ α p^k) , т.е. найти α_k.

Шаг 3. Положить х ^{k +1} =х ^k + α _k p^k.

Проверить критерий останова: ||  ||< .

Если он выполнен, то вычисления завершить, полагая

       x *= x^{k +1}, f *= f (x^{k +1}).

Шаг 4. Проверить условие к+1=n. Если оно выполняется, то положить

  x⁰=x^k+1, f(x⁰)=f(x^k+1) и перейти к шагу 1 (обновление метода).

Шаг 5. Вычислить коэффициент   и

          найти новое направление поиска p^{k +1} = - + p^k.

          Положить к=к+1 и перейти к шагу 2.

Замечание 1. Описанный метод является методом первого порядка, поэтому для решения задачи одномерной минимизации на шаге 2 целесообразно использовать, например, метод хорд, выбирая в качестве интервала поиска α отрезок [0,1].

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

Пример 1. Найти методом сопряжённых градиентов точку минимума функции , начав поиск с точки .

Решение.

=(8 x ₁ -4 x ₂ +1;6 x ₂ -4 x ₁).

Итерация 1.

0. Зададим =0,01, x ⁰ =(0,0), = (1,0), || ||=1.

1. Положим к=0, p⁰= - = (-1,0).

2. Решим задачу одномерной минимизации по α:

α₀=1/8.

3. Найдем х¹=х⁰+ α₀ p ⁰ =(-1/8,0), (0,1/2), .

4.

5. = 1/4.

p ¹ = - + p ⁰ =(-1/4,-1/2).

Итерация 2.

2. Решим задачу одномерной минимизации по α:

 

   α₁=1/4.

3. Найдем х²=х¹+ α₁ p ¹ = (-3/16,-1/8). (0,0) - получено оптимальное решение, x *= x ²

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

 

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

Если в результате преобразования x = zQ матрица квадратичной формы приводится к единичной (т. е. ), то метод наискорейшего спуска z ¹ =z⁰- α* , получает решение за один шаг.

В пространстве переменных х данный переход запишется в виде

х¹ =х⁰ - α*      или х¹ =х⁰- α* .

Так как = H ^-1, то х¹ =х⁰- α* H ^-1. Итеративный метод вида

х ^{k +1} =х^k- α_k H ^-1 носит название метода Ньютона.

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

Существенным недостатком метода Ньютона является необходимость вычисления и обращения матрицы Гессе на каждой итерации.

 

Алгоритм метода Ньютона

Шаг 0. Задать параметр точности , выбрать х⁰ , вычислить f(x⁰).

Шаг 1. Найти  и проверить критерий останова: || ||< .

       Если он выполнен, то вычисления завершить, полагая

       x *= x ⁰, f *= f (x ⁰).

Шаг 2. Положить х⁰=х⁰- H ^-1, вычислить f(x⁰) и перейти к шагу 1.

Пример 1. Найти методом Ньютона точку минимума функции 

           , начав поиск с точки .

Решение. Посчитаем вектор-градиент функции =(8 x ₁ -4 x ₂ +1;6 x ₂ -4 x ₁).

Матрица вторых частных производных имеет вид H = .

 

Найдем обратную матрицу H ^-1 = .

0. Выберем   =0.001, , f(x⁰)=0.

1. Посчитаем =(1,0), || ||=1> .

2. Положим х⁰=х⁰- H ^-1 = , f(x⁰)=  

3. =(0,0) -найдено оптимальное решение x*= .

Целевая функция квадратичная, поэтому решение задачи получено за одну итерацию.

Задачи для самостоятельного решения

 

1. Найти различными методами точку минимума следующих функций:

 

 

2. Показать, что для квадратичной функции в методе Ньютона шаг .

 

1. Классификация численных методов поиска условного экстремума 2. Метод возможных направлений для задач с линейными ограничениями 3. Метод возможных направлений Зойтендейка 4. Метод линеаризации Франка – Вулфа 5. Метод секущих плоскостей 6. Метод гладких штрафов 7. Метод точных штрафных функций

Глава 10