Методы безусловной одномерной оптимизации. Шипилов С.А. - 8 стр.

UptoLike

ВУЗ: 

НФИ КемГУ | Новокузнецк

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

Рубрика: 

8
1 2 3
a
1
= a
0
≤ x
*
≤ x
2
= b
1
a
1
= x
1
≤ x
*
≤ b
0
= b
1
a
1
= x
1
≤ x
*
≤ x
2
= b
1
Рисунок 1 – Возможные ситуации при сужении отрезка
1
Если y
1
= f(x
1
) < y
2
= f(x
2
) , то положим a
1
= a
0
и b
1
= x
2
и получим
меньший отрезок унимодальности [a
1
, b
1
] .
2
Если y
1
= f(x
1
) > y
2
= f(x
2
) , то естественно принять a
1
= x
1
и b
1
= b
0
.
3
Если y
1
= f(x
1
) = y
2
= f(x
2
) , то a
1
= x
1
и b
1
= x
2
.
3.2.4 Метод половинного деления
Метод половинного деления, называемый также методом дихотомии,
является процедурой последовательного поиска. Пусть определен отрезок
[a
0
, b
0
], которому принадлежит точка локального минимума x
*
, и функция f(x)
является унимодальной на этом отрезке. Далее для сужения промежутка уни-
модальности используем две точки x
1
и x
2
, расположенные симметрично на рас-
стоянии
δ
> 0 от середины отрезка:
δ
−
+
=
2
00
1
ba
x ;
δ
+
+
=
2
00
2
ba
x
.
Константа
δ
должна быть меньше допустимой конечной длины отрезка,
Δ
k
= b
k
- a
k
> 0.
Рассчитываем значение функции в этих точках y
1
=f(x
1
) и y
2
=f(x
2
) и в зави-
симости от их соотношения новые границы отрезка унимодальности [a
1
, b
1
] бу-
дут следующие:
•
y
1
< y
2
, a
1
=a
0
и b
1
=x
2
;
•
y
1
> y
2
, a
1
=x
1
и b
1
=b
0
;
•
y
1
= y
2
, a
1
=x
1
и b
1
= x
2
.
Название метода половинного деления мотивировано тем, что если вели-
чина
ε достаточно мала, то длина отрезка унимодальности (b – a) уменьшается
почти вдвое.
x
1
x
2
b
0
a
0
y
x
y
1
=y
2
x
x
1
x
2
b
0
a
0
y
y
1
y
2
x
2
x
1
b
0
a
0
y
y
2
y
1
x
b
0
a
0
y
y
2
y
1 
                1                                  2                               3
    y                                 y                                y


y2
                                     y1

y1                                                                 y1=y2
                                     y2



        a0 x1          x2 b0     x        a0 x1         x2 b0      x       a0 x1        x2 b0       x
        a1 = a0 ≤ x* ≤ x2 = b1            a1 = x1 ≤ x* ≤ b0 = b1           a1 = x1 ≤ x* ≤ x2 = b1

                    Рисунок 1 – Возможные ситуации при сужении отрезка

         1 Если y1 = f(x1) < y2 = f(x2) , то положим a1 = a0 и b1 = x2 и получим
            меньший отрезок унимодальности [a1, b1] .
         2 Если y1 = f(x1) > y2 = f(x2) , то естественно принять a1 = x1 и b1 = b0 .
         3 Если y1 = f(x1) = y2 = f(x2) , то a1 = x1 и b1 = x2 .

         3.2.4 Метод половинного деления
       Метод половинного деления, называемый также методом дихотомии,
является процедурой последовательного поиска. Пусть определен отрезок
[a0, b0], которому принадлежит точка локального минимума x*, и функция f(x)
является унимодальной на этом отрезке. Далее для сужения промежутка уни-
модальности используем две точки x1 и x2, расположенные симметрично на рас-
стоянии δ > 0 от середины отрезка:
                a + b0
            x1 = 0      −δ ;
                    2
                 a + b0
            x2 = 0      +δ .
                    2
       Константа δ должна быть меньше допустимой конечной длины отрезка,
Δk= bk- ak > 0.
       Рассчитываем значение функции в этих точках y1=f(x1) и y2=f(x2) и в зави-
симости от их соотношения новые границы отрезка унимодальности [a1, b1] бу-
дут следующие:
        •      y1 < y2,  a1=a0 и b1=x2 ;
        •      y1 > y2,  a1=x1 и b1=b0 ;
        •      y1 = y2,  a1=x1 и b1= x2 .
      Название метода половинного деления мотивировано тем, что если вели-
чина ε достаточно мала, то длина отрезка унимодальности (b – a) уменьшается
почти вдвое.

8

Страницы