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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

43
Замечание 2. Обновление метода, как правило, производится и для
квадратичных функций, так как решение задач одномерной минимизации
зачастую сопровождается вычислительными погрешностями .
Пример . Найти методом сопряжённых градиентов точку минимума
функции
121
2
2
2
1
434)( xxxxxxf +−+= , начав поиск с точки )0,0(
0
=x .
Решение.
)
(
x
f
∇
=(8x
1
-4x
2
+1;6x
2
-4x
1
).
Итерация 1.
0. Зададим
ε
=0,01, x
0
=(0,0), )(
0
xf ∇ = (1,0), || )(
0
xf ∇ ||=1.
1. Положим к=0, p
0
= - )(
0
xf ∇ = (-1,0).
2. Решим задачу одномерной минимизации по α : .min4)0,(
2
→−=−Φ ααα
α
0
=1/8.
3. Найдем х
1
=х
0
+ α
0
p
0
=(-1/8,0), =∇ )(
1
xf (0,1/2), ε>=∇ 1/2xf ||)(||
1
.
4.
n
k
+
1
5.
2021
0
||)(||||)(|| xfxf ∇∇=β = 1/4.
p
1
= -
)(
1
xf ∇
+
0
β
p
0
=(-1/4,-1/2).
Итерация 2.
2. Решим задачу одномерной минимизации по α :
min.4 α 1/8
2α)4α4(1/8)2( α 3)4α4(1/8)2α,4α1/8
2
→−−
−+−++=−−−Φ (
α
1
=1/4.
3. Найдем х
2
=х
1
+ α
1
p
1
= (-3/16,-1/8). =∇ )(
2
xf (0,0) - получено оптимальное
решение, x*=x
2
Решение получено в результате двух итераций, поскольку целевая функция
квадратичная и одномерные задачи оптимизации решены точно.
Метод Ньютона
Если в результате преобразования x=zQ матрица квадратичной формы
приводится к единичной (т. е.
EHQQ
T
=
), то метод наискорейшего спуска
z
1
=z
0
- α * )(
0
zf ∇ , получает решение за один шаг .
В пространстве переменных х данный переход запишется в виде
х
1
1
−
Q
=х
0
1
−
Q
- α *
)(
0
xf ∇
Q
или х
1
=х
0
- α *
)(
0
xf ∇
Q
1
−
Q
.
Так как
Q
1
−
Q
=H
-1
, то х
1
=х
0
- α *
)(
0
xf ∇
H
-1
. Итеративный метод вида
х
k+1
=х
k
- α
k
)(
k
xf ∇ H
-1
носит название метода Ньютона.
Для квадратичной функции с положительно определенной матрицей
Гессе применение метода Ньютона с шагом
1
=
α
обеспечивает получение
точки глобального минимума ровно за одну итерацию , независимо от выбора
начальной точки . Для выпуклой неквадратичной функции применение этого
метода обеспечивает, как правило, быструю сходимость. Однако если точка 
                                             43
Замечание 2. Обновление метода,               как правило, производится и для
квадратичных функций, так как решение задач одномерной минимизации
зачастую сопровождается вычислительными погрешностями.
Пример. Найти методом сопряжённых градиентов точку минимума
функции f ( x) =4 x12 +3 x 22 −4 x1 x 2 +x1 , начав поиск с точки x 0 =(0,0) .
Решение.
∇ f (x) =(8x1-4x2+1;6x2-4x1).
Итерация 1.
0. Зададим ε =0,01, x0=(0,0), ∇ f ( x 0 ) = (1,0), || ∇ f ( x 0 ) ||=1.
1. Положим к=0, p0= - ∇ f ( x 0 ) =(-1,0).
2. Решим задачу одномерной минимизации по α : Φ(−α ,0) =4α 2 −α → min .
   α0=1/8.
3. Найдем х1=х0+ α0 p0=(-1/8,0), ∇ f ( x 1 ) =(0,1/2), || ∇ f ( x 1 ) ||=1/2 >ε .
4. k +1 ≠n
5. β0 =|| ∇ f ( x 1 ) || 2 || ∇ f ( x 0 ) || 2 =1/4.
   p1= - ∇ f ( x 1 ) + β0 p0=(-1/4,-1/2).
   Итерация 2.
2. Решим задачу одномерной минимизации по α :
    Φ(−1/8 −α 4 , −α 2 ) =4(1/8 +α 4 ) +3 (α 2 ) 2 −4(1/8 +α 4 ) α 2 −
    −1/8 −α 4 → min.
     α1=1/4.
3. Найдем х2=х1+ α1 p1 = (-3/16,-1/8). ∇ f ( x 2 ) =(0,0) - получено оптимальное
   решение, x*=x2
Решение получено в результате двух итераций, поскольку целевая функция
квадратичная и одномерные задачи оптимизации решены точно.

                                       Метод Ньютона
       Если в результате преобразования x=zQ матрица квадратичной формы
приводится к единичной (т. е. QT HQ = E ), то метод наискорейшего спуска
z1=z0- α* ∇ f ( z 0 ) , получает решение за один шаг.
       В пространстве переменных х данный переход запишется в виде
        х1 Q −1 =х0 Q −1 - α* ∇ f ( x 0 ) Q    или х1 =х0- α* ∇ f ( x 0 ) Q Q −1 .
Так как Q Q −1 =H-1 , то х1 =х0- α* ∇ f ( x 0 ) H-1. Итеративный метод вида
хk+1 =хk- αk ∇ f ( x k ) H-1 носит название метода Ньютона.
       Для квадратичной функции с положительно определенной матрицей
Гессе применение метода Ньютона с шагом α =1 обеспечивает получение
точки глобального минимума ровно за одну итерацию, независимо от выбора
начальной точки. Для выпуклой неквадратичной функции применение этого
метода обеспечивает, как правило, быструю сходимость. Однако если точка

Страницы