Методы оптимизации. Азарнова Т.В - 40 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

42
y
1
y
2
Метод сопряжённых градиентов
Данный метод позволяет получать сопряженные направления
k
p для
квадратичной функции f(x) с использованием ее производных. В качестве
0
p
выбирается вектор-антиградиент, а остальные направления вычисляются по
формуле p
k+1
= - )(
1
+
∇
k
xf +
k
β
p
k
, 1,0 −= nk , где
221
||)(||||)(||
kk
k
xfxf ∇∇=
+
β . Формула пересчета точки
1
+
k
x
имеет вид
х
k+1
=х
k
+ α
k
p
k
, причем шаг α
k
ищется по правилу наискорейшего спуска.
При отсутствии вычислительных погрешностей метод сопряжённых
градиентов обеспечивает отыскание минимума квадратичных функций не
более чем за n итераций. Для неквадратичных функций сходимость метода за
конечное число итераций не гарантирована.
Алгоритм метода сопряжённых градиентов.
Шаг 0. Задать параметр точности
ε
, выбрать х
0
n
R
∈
,вычислить f(x
0
).
Шаг 1. Положить к =0, p
0
= - )(
0
xf ∇ ;
Шаг 2. Решить задачу одномерной минимизации
Ф (α)=f(х
0
+ α p
k
)
0>
→
α
min
, т.е. найти α
k
.
Шаг 3. Положить х
k+1
=х
k
+ α
k
p
k
.
Проверить критерий останова: || )(
1
+
∇
k
xf ||<
.
Если он выполнен, то вычисления завершить, полагая
x*=x
k+1
, f*=f(x
k+1
) .
Шаг 4. Проверить условие к+1=n . Если оно выполняется , то положить
x
0
=x
k+1
, f(x
0
)=f(x
k+1
) и перейти к шагу 1 (обновление метода).
Шаг 5. Вычислить коэффициент
221
||)(||||)(||
kk
k
xfxf ∇∇=
+
β и
найти новое направление поиска p
k+1
= - )(
1
+
∇
k
xf +
k
p
k
.
Положить к = к +1 и перейти к шагу 2.
Замечание 1. Описанный метод является методом первого порядка, поэтому
для решения задачи одномерной минимизации на шаге 2 целесообразно
использовать, например, метод хорд , выбирая в качестве интервала поиска α
отрезок [0,1].
0.5
x
1
x* 
                                           42


                       x*          0.5
                             x1
                                     y1
                            y2




                   Метод сопряжённых градиентов
      Данный метод позволяет получать сопряженные направления p k для
квадратичной функции f(x) с использованием ее производных. В качестве p 0
выбирается вектор-антиградиент, а остальные направления вычисляются по
формуле      pk+1=     - ∇ f ( x k +1 ) + βk   pk,    k =0, n −1 ,    где
β k =|| ∇ f ( x k +1 ) || 2 || ∇ f ( x k ) || 2 . Формула пересчета точки x k +1 имеет вид
хk+1=хk+ αk pk , причем шаг αk ищется по правилу наискорейшего спуска.
        При отсутствии вычислительных погрешностей метод сопряжённых
градиентов обеспечивает отыскание минимума квадратичных функций не
более чем за n итераций. Для неквадратичных функций сходимость метода за
конечное число итераций не гарантирована.
                      Алгоритм метода сопряжённых градиентов.
Шаг 0. Задать параметр точности ε , выбрать х0 ∈R n ,вычислить f(x0).
Шаг 1. Положить к=0, p0= - ∇ f ( x 0 ) ;
Шаг 2. Решить задачу одномерной минимизации
        Ф(α)=f(х0+ α pk) → min , т.е. найти αk.
                                  α >0
Шаг 3. Положить х =х + αk pk .
                      k+1   k

       Проверить критерий останова: || ∇ f ( x k +1 ) ||< ε .
       Если он выполнен, то вычисления завершить, полагая
            x*=xk+1, f*=f(xk+1) .
Шаг 4. Проверить условие к+1=n . Если оно выполняется, то положить
      x0=xk+1, f(x0)=f(xk+1) и перейти к шагу 1 (обновление метода).
Шаг 5. Вычислить коэффициент β k =|| ∇ f ( x k +1 ) || 2 || ∇ f ( x k ) || 2 и
         найти новое направление поиска pk+1= - ∇ f ( x k +1 ) + β k pk .
         Положить к=к+1 и перейти к шагу 2.
Замечание 1. Описанный метод является методом первого порядка, поэтому
для решения задачи одномерной минимизации на шаге 2 целесообразно
использовать, например, метод хорд, выбирая в качестве интервала поиска α
отрезок [0,1].

Страницы