Метод перебора

У этого термина существуют и другие значения, см. Перебор.

Метод перебора (метод равномерного поиска) — простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум, на минимум, на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной оптимизации.

Описание

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

Пусть задана функция $f(x):\;[a,\;b]\to\mathbb{R}$.
И задача оптимизации выглядит так: $f(x)\to\min_{x\in [a,\;b]}$
Пусть также задано число наблюдений $n$.

Тогда отрезок $\left[a,b\right]$ разбивают на $(n+1)\,\!$ равных частей точками деления:

$x_i=a+i\frac{\left(b-a\right)}{(n+1)},\quad i=1,\ldots,n\,\!$

Вычислив значения $F\left(x\right)$ в точках $x_i,\;i=1,\ldots,n \!$, найдем путем сравнения точку $x_m\,\!$, где $m\,\!$ — это число от $1\,\!$ до $n\,\!$ такую, что

$F\left(x_m\right)=\min F\left(x_i\right)$ для всех $i\,\!$ от $1\,\!$ до $n\,\!$.

Тогда интервал неопределённости составляет величину $2\frac{\left(b-a\right)}{(n+1)}$, а погрешность определения точки минимума $x_m\,\!$ функции $F\left(x\right)$ соответственно составляет :$\varepsilon=\frac{\left(b-a\right)}{n+1}$.

Модификация

Если заданное количество измерений чётно ($n=2k$), то разбиение можно проводить другим, более изощрённым способом:

$x_{2i}=a+\frac{(b-a)}{(n/2+1)}2i, \quad i=1,\ldots,n/2\!$

$x_{2i-1}=x_{2i}-\delta\!$, где $\delta$ — некая константа из интервала $\left(0,\;\frac{(b-a)}{(n/2+1)}\right)$.

Тогда в худшем случае интервал неопределённости имеет длину $\frac{(b-a)}{(n/2+1)}+\delta$.

Литература

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
3. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
4. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.