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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

37
2. Зададим x
0
=(0.5,1), f(x
0
)=1.5. Выберем
ε
=0.01,
1
=
α
.
3. )(
0
xf ∇ = (2, 2), || )(
0
xf ∇ ||>
ε
.
4. Положим х
1
=х
0
- )(
0
xf ∇ =(0.5 -2, 1-2)=(-1.5,-1), f(x
1
)=5,5, f(x
1
)>f(x
0
).
5. Положим
2
α
α = =1/2 и перейдем к шагу 2.
6. Положим х
1
=х
0
-
2
1
)(
0
xf ∇ =(0.5 -1, 1-1)=(-0.5,0), f(x
1
)=0.5. Так как
f(x
1
)<f(x
0
), то полагаем х
0
= х
1
=(-0.5,0) , f(x
0
)=f(x
1
)=0.5 и переходим к шагу
1.
Итерация 2.
7. )(
0
xf ∇ =(-2,0), || )(
0
xf ∇ ||>
ε
8. Положим х
1
=х
0
-
2
1
)(
0
xf ∇ =(-0.5 +1, 0)=(0.5,0), f(x
1
)=0.5, f(x
1
)=f(x
0
).
9. Положим
2
α
α = =1/4 и перейдем к шагу 2.
10. Положим х
1
=х
0
-
4
1
)(
0
xf ∇ =(-0.5 +0.5, 0)=(0,0), f(x
1
)=0, f(x
1
)<f(x
0
).
Полагаем х
0
= х
1
=(0,0) , f(x
0
)=f(x
1
)=0 и переходим к шагу 1.
11. )(
0
xf ∇ =(0,0), || )(
0
xf ∇ ||=0<
ε
- останов, найдено точное решение.
Алгоритм метода наискорейшего спуска .
Шаг 0. Задать параметр точности
ε
, выбрать х
0
n
∈
.
Шаг 1. Найти )(
0
xf ∇ и проверить критерий останова: || )(
0
xf ∇ ||<
ε
.
Если он выполнен, то вычисления завершить, полагая
x*=x
0
, f*=f(x
0
) .
Шаг 2. Решить задачу одномерной оптимизации
Ф (α )=f(х
0
- α
)(
0
xf ∇
)
0 >
→
α
min
, т.е. найти α *.
Положить х
0
= х
0
- α * )(
0
xf ∇ и перейти к шагу 1.
Пример 1.
Решить задачу min)( →−−+=
21
2
2
2
1
x2x4xxxf методом
наискорейшего спуска.
Решение.
),()( 2x24x2xf
21
−
−
=
∇
Итерация 1.
0.Зададим x
0
=(4,5). Выберем
ε
=0.01.
1. )(
0
xf ∇ = (4, 8), || )(
0
xf ∇ ||>
ε
.
2. Решим задачу одномерной минимизации по α :
.min)()(
)()())()(
→−−−−
−−+−=∇−=Φ
αα
αααα
852444
8544xf
220 0
f(х
α *=0.5. х
0
=х
0
- α * )(
0
xf ∇ =(4-4·0.5, 5-8·0.5)=(2,1).
Итерация 2.
3. )(
0
xf ∇ =(0,0), || )(
0
xf ∇ ||=0<
ε
- останов, найдено точное решение.
Графическая иллюстрация решения
приведена на рисунке. В данном случае
линии уровня являются концентрическими
о
к
ружностями . Вектор
-
градиент, 
                                                        37
2. Зададим x0=(0.5,1), f(x0)=1.5.                            Выберем ε =0.01, α =1 .
3. ∇ f ( x 0 ) =(2, 2), || ∇ f ( x 0 ) ||>ε .
4. Положим х1=х0- ∇ f ( x 0 ) =(0.5 -2, 1-2)=(-1.5,-1), f(x 1)=5,5, f(x1)>f(x0).
5. Положим α =α =1/2 и перейдем к шагу 2.
                        2
6. Положим х =х - 2 ∇ f ( x 0 ) =(0.5 -1, 1-1)=(-0.5,0), f(x1)=0.5. Так как
                 1   0 1


   f(x1)ε
8. Положим х1=х0-           1
                            2
                                ∇ f ( x 0 ) =(-0.5 +1, 0)=(0.5,0), f(x1)=0.5, f(x1)=f(x0).
9. Положим α =α =1/4 и перейдем к шагу 2.
                           2
10. Положим х =х - 4 ∇ f ( x 0 ) =(-0.5 +0.5, 0)=(0,0), f(x1)=0, f(x1)0
                                                  0
             Положить х =х - α* ∇ f ( x ) и перейти к шагу 1.
                                0   0

Пример 1.
       Решить задачу f ( x) =x12 +x 22 −4 x1 −2 x 2 → min методом
наискорейшего спуска.
       Решение. ∇ f ( x) =(2 x1 −4,2 x 2 −2)
                                              Итерация 1.
0.Зададим x =(4,5). Выберем ε =0.01.
                0

1. ∇ f ( x 0 ) =(4, 8), || ∇ f ( x 0 ) ||>ε .
2. Решим задачу одномерной минимизации по α :
   Φ(α ) = f(х 0 −α∇ f ( x 0 )) = (4 −4α ) 2 +(5 −8α ) 2 −
       −4(4 −4α ) −2(5 −8α ) → min .
       α*=0.5. х0=х0- α* ∇ f ( x 0 ) =(4-4·0.5, 5-8·0.5)=(2,1).
                                          Итерация 2.
          0                    0
3. ∇ f ( x ) =(0,0), || ∇ f ( x ) ||=0<ε - останов, найдено точное решение.
                                                Графическая    иллюстрация     решения
                                                приведена на рисунке. В данном случае
                                                линии уровня являются концентрическими
                                                                    В

Страницы