Методы прямого поиска (сканирования)

11.4.2.1. Общие сведения о методах прямого поиска Ряд методов минимизации основан на сравнении значений функции f, вычисляемой в точках x₁, x₂,…, x_N. Эти методы часто называют методами прямого поиска, или методами сканирования, а точки x_i - пробными точками.
Методы прямого поиска применяются главным образом для определения экстремумов функций одной переменной. Несмотря на то что такие задачи могут показаться тривиальными, они находят применение и при решении многомерных задач.
Идея методов прямого поиска проста. Сначала определяется интервал неопределенности, который содержит искомую точку оптимума. Затем длина интервала последовательно уменьшается до тех пор, пока не будет найдена точка оптимума. Процедура строится таким образом, что длину интервала, содержащего оптимальное решение, можно сделать сколь угодно малой.
Задача заключается в локализации экстремума функции одной переменной, заданной на интервале [a, b] с точностью до Δ.
Пусть требуется найти приближение x^p к точке минимума x* функции f(x), заданной на отрезке [a,b]. Число пробных точек заранее фиксируется и за приближение x^p к точке минимума принимается одна из этих точек.
Метод решения поставленной задачи, в котором задается правило вычисления сразу всех пробных точек x₁, x₂,…, x_N и за x^p принимается та точка x_k, для которой f(x_k)=minf(x_i) по всем i=1,2,...,N, называется методом пассивного поиска. Этот метод требует больших затрат времени (зависящего от значения Δ), но главное его преимущество − это определение глобального экстремума. Иллюстрация метода пассивного поиска приведена на рис. 11.15.

Рис. 11.19. Метод пассивного поиска (произвольные интервалы)

В том случае, когда пробные точки расположены равномерно на исследуем отрезке [a,b], погрешность метода становится минимальной, поэтому такой метод иногда называют оптимальным пассивным поиском. При решении задачи минимизации скалярной функции методом оптимального пассивного поиска весь интервал разбивается на участки величиной Δ. В узлах разбиения вычисляются значения функции и из них выбирается экстремальное. Гарантированная погрешность для него |x−x*|≤(b−a)/(N+1), где N − количество интервалов, на которые разбивается отрезок [a,b].

Рис. 11.20. Метод оптимального пассивного поиска (равномерная сетка)

В качестве конкретного примера на рис. 11.21 приведена блок-схема алгоритма поиска минимума функции Q(x) на отрезке [a,b].

Рис. 11.21. Блок-схема минимизации функции Q(x) на отрезке [a,b]

11.4.2.2. Модифицированные варианты методов прямого поиска
С целью повышения точности и сокращения вычислений метод пассивного поиска может быть модифицирован следующим образом. В первой серии пробных точек находится отрезок [x_k-1,x_k], на котором имеется минимум функции f(x) и затем процедура оптимального пассивного поиска проводится уже не для отрезка [a,b], а только для его части [x_k-1,x_k]. Такую модификацию метода оптимальног опоиска можно назвать поиск (сканирование) с уточнением. Цель такого подхода состоит в сокрашении суммарного объема вычислений. В этом случае процедура равномерного сканирования выполняется n раз.

Алгоритм поиска (сканирования) с уточнением

1. На 1-м этапе осуществляется сканирование во всей зоне поиска (на всем отрезке) Δ⁽⁰⁾=[a⁽⁰⁾;b⁽⁰⁾], где a⁽⁰⁾=a;b⁽⁰⁾=b. При этом выполняется N₁ вычислений, т.е. исходный отрезок разбивается на N₁ интервалов длины h⁽¹⁾=(b−a)/N₁, в средних точках которых вычисляются значения функции f(x). В результате находится значение x⁽¹⁾, в котором функция имеет минимальное (максимальное) значение. Точка x¹ принадлежит k-тому интервалу отрезка [a,b] (1≤k≤N₁].

2. На втором этапе процедура сканирования повторяется вновь, но уже для интервала Δ⁽¹⁾=[a⁽¹⁾;b⁽¹⁾], где границы интервала сканирования a⁽¹⁾,b⁽¹⁾ совпадают с границами k-того интервала, выявленного на шаге 1 (очевидно, что a⁽¹⁾≤x_k≤b⁽¹⁾). Фигурально выражаясь, на втором этапе происходит "вгрызание" в k-тый интервал.

3. На третьем и последующем этапах процедура "вгрызания" повторяется до тех пор, пока не будет обеспечена заданная точность вычислений ε. С этой целью проверяется выполнение условия Δ⁽ⁱ⁾<ε. Если "да" − конец вычислений, если "нет" - переход к следующей итерации i=i+1.

Очевидно, что можно предложить дальнейшие модификации метода прямого поиска, связанные с вариантами выбора размера интервала