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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

44
х
0
выбрана недостаточно близко к оптимальному решению , то
последовательность х
k
может расходиться (как и в одномерном случае).
Существенным недостатком метода Ньютона является необходимость
вычисления и обращения матрицы Гессе на каждой итерации.
Алгоритм метода Ньютона .
Шаг 0. Задать параметр точности
ε
, выбрать х
0
n
R
∈
,вычислить f(x
0
).
Шаг 1. Найти )(
0
xf ∇ и проверить критерий останова: || )(
0
xf ∇ ||<
ε
.
Если он выполнен, то вычисления завершить, полагая
x*=x
0
, f*=f(x
0
) .
Шаг 2. Положить х
0
= х
0
-
)(
0
xf ∇
H
-1
, вычислить f(x
0
) и перейти к шагу 1.
Пример . Найти методом Ньютона точку минимума функции
121
2
2
2
1
xxx4x3x4xf +−+= )(
, начав поиск с точки
),( 00x
0
=
.
Решение. Посчитаем вектор- градиент функции
)
(
x
f
∇
=(8x
1
-4x
2
+1;6x
2
-4x
1
) .
Матрица вторых частных производных имеет вид H=
−
−
64
48
.
Найдем обратную матрицу H
-1
=
84
46
32
1
.
0. Выберем
ε
=0.001, ),( 00x
0
= , f(x
0
)=0.
1. Посчитаем )(
0
xf ∇ =(1,0), || )(
0
xf ∇ ||=1>
ε
.
2. Положим х
0
=х
0
- )(
0
xf ∇ H
-1
= ),(),( 8116346
32
1
−−=− , f(x
0
)= 323
−
3. )(
0
xf ∇ =(0,0) -найдено оптимальное решение x*= ),( 81163
−
−
.
Целевая функция квадратичная , поэтому решение задачи получено за одну
итерацию .
Задачи для самостоятельного решения
1. Найти различными методами точку минимума следующих функций:
),(,)() 01xx2x4x2xxf1
0
21
2
2
2
1
=+−+=
),(,)() 35xx12xx2xf2
0
1
2
2
2
1
=−+=
),(,)() 105xx4x2xxxf3
0
21
2
2
2
1
=−−+=
),(,)() 54xx2x4xxxf4
0
21
2
2
2
1
=−−+=
),(,)() 00xx32x6x4xxf5
0
21
2
2
2
1
=−−+=
),(,)() 21xxxxx2xf6
0
21
2
2
2
1
=−+=
),(,)() 02xxx2x3xxf7
0
21
2
2
2
1
=−+= 
                                                    44
х0 выбрана недостаточно близко к оптимальному          решению,     то
                    k
последовательность х может расходиться (как и в одномерном случае).
Существенным недостатком метода Ньютона является необходимость
вычисления и обращения матрицы Гессе на каждой итерации.

                              Алгоритм метода Ньютона.
Шаг 0. Задать параметр точности ε , выбрать х0 ∈R n ,вычислить f(x0).
Шаг 1. Найти ∇ f ( x 0 ) и проверить критерий останова: || ∇ f ( x 0 ) ||<ε .
      Если он выполнен, то вычисления завершить, полагая
      x*=x0, f*=f(x0) .
Шаг 2. Положить х0=х0- ∇ f ( x 0 ) H-1, вычислить f(x0) и перейти к шагу 1.

Пример. Найти методом Ньютона точку минимума функции
        f ( x) =4 x12 +3 x 22 −4 x1 x 2 +x1 , начав поиск с точки x 0 =(0,0 ) .

Решение. Посчитаем вектор-градиент функции ∇ f (x) =(8x1-4x2+1;6x2-4x1) .
                                                    � 8 −4 �
Матрица вторых частных производных имеет вид H= ��            �� .
                                                     � −4 6 �
                                   1 � 6 4�
Найдем обратную матрицу H-1=           �       � .
                                  32 �� 4 8 ��
0. Выберем ε =0.001, x 0 =(0,0 ) , f(x0)=0.
1. Посчитаем ∇ f ( x 0 ) =(1,0), || ∇ f ( x 0 ) ||=1>ε .
2. Положим х0=х0- ∇ f ( x 0 ) H-1= −32
                                     1 (6 ,4 ) =(−3 16 ,−1 8 ) , f(x0)= −3 32

3. ∇ f ( x 0 ) =(0,0) -найдено оптимальное решение x*= ( −3 16 ,−1 8 ) .
Целевая функция квадратичная, поэтому решение задачи получено за одну
итерацию.
                       Задачи для самостоятельного решения

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

1) f ( x ) =x12 +2 x 22 −4 x1 +2 x 2 ,       x 0 =(1,0 )
2) f ( x ) =2 x12 +x 22 −12 x1 ,       x 0 =(5,3)
3) f ( x) =x12 +x 22 −2 x1 −4 x 2 ,         x 0 =(5,10 )
4 ) f ( x ) =x12 +x22 −4 x1 −2 x2 ,        x 0 =(4,5)
5) f ( x) =x12 +4 x22 −6 x1 −32 x2 ,         x 0 =(0,0 )
6 ) f ( x) =2 x12 +x22 −x1 x2 ,        x 0 =(1,2)
7 ) f ( x ) =x12 +3 x 22 −2 x1 x 2 ,    x 0 =(2,0 )

Страницы