Метод исключения интервалов. Правило исключения интервалов.

Методы поиска, которые позволяют определить оптимум функции одной переменной путем уменьшения интервала поиска, носят название методов исключения интервалов.

Все методы одномерной оптимизации основаны на предположении, что исследуемая целевая функция в допустимой области по крайней мере обладает свойством унимодальности, так как для унимодальной функции W(x) сравнение значений W(t) в двух различных точках интервала поиска позволяет определить в каком из заданных двумя указанными точками подынтервалов точки оптимума отсутствуют.

Правила исключения интервалов.

Пусть  унимодальна на интервале  и достигает минимума в точке . Рассмотрим точки  и  такие, что если , то точка  принадлежит интервалу  , а интервал  исключается.

Если , то исключаются оба интервала  и , а точка оптимума находится принадлежит интервалу .

Достоинства метода.

1. единственное ограничение на функцию – её унимодальность;
2. требуется вычисления только значений функции.

Эвристический метод.

, где 

- произвольно выбранная точка

- шаг, определяется путём сравнения значений , ,

Если  то  правее, чем  и .

Если  то  левее, чем  и .

Если  то  лежит между точками  и  и поиск завершён.

Если при поиске минимума оказывается, что  , то функция не унимодальна.

Пусть W(x) унимодальна на отрезке [a,b], а ее минимум достигается в точке x^*. Рассмотрим x₁ и x₂, расположенные a_{12< p=""> <>}

1. _{Если W(x1)>W(x2), то точка минимума W(x) не лежит в интервале (a,x1), т.е. x^*О (x1,b).}
2. _{Если W(x1)2), то точка минимума W(x) не лежит в интервале (x2,b), т.е. x^*О (a,x2).}

_{Это правило позволяет реализовать процедуру поиска путем последовательного исключения частей исходного ограниченного интервала. Поиск завершается тогда, когда оставшийся подынтервал уменьшается до достаточно малых размеров.}

_{Главное достоинство поисковых методов - основаны на вычислении только значений функции и, следовательно, не требуют выполнения условия дифференцируемости и записи в аналитическом виде. Последнее свойство особенно ценно при имитационном моделировании.}

_{Процесс применения методов поиска на основе исключения интервалов включает два этапа:}

1. _{этап установления границ интервала;}
2. _{этап уменьшения интервала.}

_{Этап установления границ интервала}

_{Выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно используется эвристический метод, например, Свенна, в котором (k+1) пробная точка определяется по рекуррентной формуле}

_{xk+1 = xk + 2^k D , k=0,1,2... (3.1)}

_где

_{xo - произвольно выбранная начальная точка;}

_{- подбираемая величина шага.}

_{Знак D определяется путем сравнения значений W(x), W(xo + | D | ), W(xo -| D | ):}

1. _{если W(xo -| D | ) і W(x) і W(xo + | D | ), то D имеет положительное значение;}
2. _{если W(xo -| D | ) Ј W(x) Ј W(xo + | D | ), то D имеет отрицательное значение;}
3. _{если W(xo -| D | ) і W(x) Ј W(xo + | D | ), то точка минимума лежит между если xo -| D | и xo + | D | и поиск граничных точек завершен;}
4. _{если W(xo -| D | ) Ј W(x) і W(xo + | D | ), то имеем противоречие предположению об унимодальности.}

_{Пример
W(x)=(100-x)², xo=30, | D | =5.
Определим знак D :
W(30)=4900;
W(30+5)=4225;
W(30-5)=5625.
Выполняется условие W(xo -| D | ) і W(x) і W(xo + | D | ), следовательно, D имеет положительное значение; x^*=30.
x1=xo+2⁰D = 35;
x2=x1+2¹D = 45, W(45)=3025 < W(x1) Ю x^*>35;
x3=x2+2²D = 65, W(65)=1225 < W(x2) Ю x^*>45;
x4=x3+2³D = 105, W(105)=25 < W(x3) Ю x^*>65;
x5=x4+2⁴D = 185, W(185)=7225 > W(x4) Ю x^*<185.
Искомый интервал 65^*<185.}