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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

36
одномерной минимизации:
.min)1(25.0)1()(
2
→+−+=Φ ααα
α *=-0.875.
х
1
=(-0.25,0.125), f(x
1
)=0.11.
4. Проверяем критерий останова :
|0.375-0.11|=0.265>
ε
5. В качестве направления снова
выбираем e
1
. Решим задачу
одномерной минимизации по α :
.min)25.0(125.0)25.0(2)(
2
→+−++−=Φ ααα
α *
≈
0.22. х
1
=(-0.03,0.125), f(x
1
)
≈
0.021.
6. Полагаем х
0
= х
1
.
7. В качестве направления выбираем е
2
. Записываем задачу одномерной
минимизации: .min)125.0(03.0)125.0()(
2
→+−+=Φ ααα
α *=-0.11. х
1
=(-0.03,0.015), f(x
1
)
≈
0.001.
4. Проверяем критерий останова : |0.021-0.001|=0.02<
ε
. Полагаем
x*=(-0.03,0.015), f*=0.001.
Замечание. Из графической иллюстрации видно , что оптимальным решением
является центр концентрических эллипсов - точка (0,0) .
Методы градиентного поиска .
Представленные далее методы используют условие дифференцируемости
функции f(x) в R
n
. В качестве критерия останова таких методов, как правило,
выбирается условие || )(
k
xf ∇ ||<
ε
. В качестве направления движения для
отыскания минимума в методах градиентного спуска на каждом шаге
выбирается вектор - антиградиент )(
kk
xfy −∇= . Как известно , в малой
окрестности точки x
k
антиградиент обеспечивает наискорейшее убывание
функции. Приведем два варианта методов градиентного спуска
( отличающиеся способом отыскания величины α ) .
Алгоритм метода дробления шага .
Шаг 0. Задать параметр точности
ε
, начальный шаг
0
>
α
, выбрать
х
0
n
R
∈
,вычислить f(x
0
).
Шаг 1. Найти )(
0
xf ∇ и проверить критерий останова: || )(
0
xf ∇ ||<
ε
.
Если он выполнен, то вычисления завершить, полагая
x*=x
0
, f*=f(x
0
) .
Шаг 2. Положить х
1
= х
0
- α )(
0
xf ∇ , вычислить f(x
1
). Если f(x
1
)<f(x
0
),
то положить х
0
= х
1
, f(x
0
)=f(x
1
) и перейти к шагу 1.
Шаг 3. Положить
2
α =
и перейти к шагу 2.
Пример . Решить задачу
min2)(
2
2
2
1
→+= xxxf
методом градиентного
спуска.
Решение. ),()(
21
x2x4xf
=
∇
.
Итерация 1.
0,5 
                                        36
                                          одномерной минимизации:
                                        Φ(α ) =(1 +α ) 2 −0.25(1 +α ) → min .
                                                       α*=-0.875.
                  0,5                     х =(-0.25,0.125), f(x1)=0.11.
                                           1

                                        4. Проверяем критерий останова :
                                              |0.375-0.11|=0.265>ε
                                        5. В качестве направления снова
                                            выбираем e1. Решим задачу
                                           одномерной минимизации по α:
                                      2
                 Φ(α ) =2 ( −0.25 +α ) +0.125 (−0.25 +α ) → min .
                     α* ≈0.22. х1=(-0.03,0.125), f(x1) ≈0.021.
               0   1
6. Полагаем х =х .
7. В качестве направления выбираем е2. Записываем задачу одномерной
   минимизации: Φ(α ) =(0.125 +α ) 2 −0.03(0.125 +α ) → min .
α*=-0.11. х1=(-0.03,0.015), f(x1) ≈0.001.
      4. Проверяем критерий останова : |0.021-0.001|=0.02<ε . Полагаем
 x*=(-0.03,0.015), f*=0.001.
Замечание. Из графической иллюстрации видно, что оптимальным решением
является центр концентрических эллипсов - точка (0,0) .
                     Методы градиентного поиска.
Представленные далее методы используют условие дифференцируемости
функции f(x) в Rn. В качестве критерия останова таких методов, как правило,
выбирается условие || ∇ f ( x k ) ||< ε . В качестве направления движения для
отыскания минимума в методах градиентного спуска на каждом шаге
выбирается вектор - антиградиент y k =−∇ f ( x k ) . Как известно, в малой
окрестности точки xk антиградиент обеспечивает наискорейшее убывание
функции. Приведем два варианта методов градиентного спуска
(отличающиеся способом отыскания величины α).
                           Алгоритм метода дробления шага.
    Шаг 0. Задать параметр точности ε , начальный шаг α >0 , выбрать
          х0 ∈R n ,вычислить f(x0).
    Шаг 1. Найти ∇ f ( x 0 ) и проверить критерий останова: || ∇ f ( x 0 ) ||<ε .
          Если он выполнен, то вычисления завершить, полагая
    x*=x0, f*=f(x0) .
    Шаг 2. Положить х1=х0- α ∇ f ( x 0 ) , вычислить f(x1). Если f(x1)

Страницы