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

UptoLike

ВУЗ: 

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

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

Рубрика: 

7
Для определения начального отрезка [a
0
, b
0
], на котором находится один
экстремум (промежутка унимодальности) могут быть использованы как анали-
тические так и графические методы анализа функции (если это возможно), а
также, как отмечалось ранее, такие методы, как метод сканирования или мето-
ды аппроксимации функций.
3.2.1 Равномерный поиск
Равномерный поиск является примером одномерного поиска, когда точки,
в которых вычисляется значение функции, выбираются заранее. Начальный от-
резок [a
0
, b
0
] делится на равные отрезки длиной d сеткой из n точек a
0
+ d·k для
k=1, ..., n и тогда b
0
= a
0
+(n+1)·d. Функция f(x) вычисляется в каждом из n узлов
полученной сетки, и выбирается точка x, в которой она имеет минимальное
значение. Этот метод обычно используется для начальной оценки отрезка
[x - d, x + d], которому принадлежит минимум. Для достижения высокой точно-
сти в этом методе необходимо осуществить большое число
вычислений функ-
ции. Однако его преимуществом является возможность поиска глобальных экс-
тремумов функции, когда нет уверенности в правильном определении началь-
ного отрезка унимодальности.
3.2.2 Метод локализации оптимума
С целью повышения точности и уменьшения числа расчетов f(x) можно
усовершенствовать стратегию равномерного поиска. После обычного равно-
мерного поиска в новом отрезке [x - d, x + d] вновь производится разбиение на
то же количество частей, определяется новый отрезок и т.д. Поиск производит-
ся до тех пор пока длина нового
отрезка не станет меньше заданной точности.
Доказано, что данный метод работает наиболее эффективно если текущий отре-
зок унимодальности делится на четыре части части, т.е. n = 3. При этом значе-
ние целевой функции в середине нового отрезка уже известно и на каждой по-
следующей итерации требуется вычислить только два значения функции. В
ре-
зультате каждый раз отрезок унимодальности делится надвое, поэтому метод
получил также название
метода деления отрезка пополам.
3.2.3 Общая схема сужения промежутка унимодальности
В методах, рассматриваемых далее, для дальнейшего сужения промежут-
ка унимодальности используют следующую идею.
Возьмем две точки x
1
и x
2
, принадлежащие начальному отрезку [a
0
, b
0
]
такие, что x
1
< x
2
. В каждом из трех следующих очевидных случаев можно
указать отрезок меньших размеров [a
1
, b
1
], содержащий точку минимума х
*
и
принадлежащий первоначальному отрезку (рисунок 1): 
      Для определения начального отрезка [a0, b0], на котором находится один
экстремум (промежутка унимодальности) могут быть использованы как анали-
тические так и графические методы анализа функции (если это возможно), а
также, как отмечалось ранее, такие методы, как метод сканирования или мето-
ды аппроксимации функций.

     3.2.1 Равномерный поиск
        Равномерный поиск является примером одномерного поиска, когда точки,
в которых вычисляется значение функции, выбираются заранее. Начальный от-
резок [a0, b0] делится на равные отрезки длиной d сеткой из n точек a0 + d·k для
k=1, ..., n и тогда b0= a0+(n+1)·d. Функция f(x) вычисляется в каждом из n узлов
полученной сетки, и выбирается точка x, в которой она имеет минимальное
значение. Этот метод обычно используется для начальной оценки отрезка
[x - d, x + d], которому принадлежит минимум. Для достижения высокой точно-
сти в этом методе необходимо осуществить большое число вычислений функ-
ции. Однако его преимуществом является возможность поиска глобальных экс-
тремумов функции, когда нет уверенности в правильном определении началь-
ного отрезка унимодальности.

     3.2.2 Метод локализации оптимума
      С целью повышения точности и уменьшения числа расчетов f(x) можно
усовершенствовать стратегию равномерного поиска. После обычного равно-
мерного поиска в новом отрезке [x - d, x + d] вновь производится разбиение на
то же количество частей, определяется новый отрезок и т.д. Поиск производит-
ся до тех пор пока длина нового отрезка не станет меньше заданной точности.
Доказано, что данный метод работает наиболее эффективно если текущий отре-
зок унимодальности делится на четыре части части, т.е. n = 3. При этом значе-
ние целевой функции в середине нового отрезка уже известно и на каждой по-
следующей итерации требуется вычислить только два значения функции. В ре-
зультате каждый раз отрезок унимодальности делится надвое, поэтому метод
получил также название метода деления отрезка пополам.

     3.2.3 Общая схема сужения промежутка унимодальности
      В методах, рассматриваемых далее, для дальнейшего сужения промежут-
ка унимодальности используют следующую идею.
      Возьмем две точки x1 и x2 , принадлежащие начальному отрезку [a0 , b0]
такие, что x1 < x2 . В каждом из трех следующих очевидных случаев можно
указать отрезок меньших размеров [a1, b1], содержащий точку минимума х* и
принадлежащий первоначальному отрезку (рисунок 1):




                                                                              7

Страницы