Методы прямого поиска. Оптимальный пассивный поиск

Ряд методов минимизации основан на сравнении значений функции f, вычисляемых в точках х ₁, х ₂, …, х_N. Эти методы часто называют методами прямого поиска, а точки х_i - пробными точками.

Уточним постановку задачи. Требуется найти приближение к точке минимума унимодальной на отрезке [ A, B ] функции f. Предположим также, что число пробных точек N заранее фиксируется и за приближение к точке минимума принимается одна из этих точек.

Оптимальный пассивный поиск. Метод решения поставленной задачи, в котором задаётся правило вычисления сразу всех пробных точек х ₁, х ₂, …, х_N и за принимается та точка х_k, для которой , называется методом пассивного поиска.

Оценим погрешность этого метода. Для удобства положим х ₀ = A, х_N+1 = B. В силу выбора точки справедливы неравенства f (x_k-1) ≥ f (x_k) и f (x_k) ≤ f (x_k+1). Поэтому из п.3 утверждения 2 следует, что [ x_k-1, x_k+1 ]. Следовательно,

| - x_k | £ max { x_k - x_k-1, x_k+1 - x_k }.

Так как положение точки минимума на отрезке [ A, B ] заранее неизвестно, то для справедлива лишь следующая гарантированная оценка погрешности:

. (2.1)

Можно показать, что величина, стоящая в правой части неравенства (1), станет минимальной, если точки х ₁, х ₂, …, х_N расположить на отрезке [ A, B ] равномерно в соответствии с формулой x_i = A + ih, где h = , Δ = B – A. Метод с таким выбором пробных точек называется оптимальным пассивным поиском. Гарантированная оценка погрешности для него выглядит так:

. (2.2)

Пример 2.

Используем оптимальный пассивный поиск для того, чтобы найти с точностью ε = 0.1 точку локального минимума функции f (х) = х² – х + е^-х, локализованную на отрезке [0, 1].

Из формулы (2) следует, что для решения задачи потребуется вычислить значения функции в девяти пробных точках вида x_i = 0.1 i, где i = 1, 2, …, 9. Приведём таблицу этих значений:

x	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
y	0.81	0.63	0.47	0.33	0.23	0.17	0.14	0.16	0.24

Так как минимальное значение достигается в точке х ₇ = 0.7, то = 0.7±0.1.

Если бы мы попытались найти с точностью ε = 10^-2, то оптимальный пассивный поиск потребовал бы вычисления значений функции уже в 99 точках.

На рис 2.1 приведена блок-схема алгоритма метода оптимального пассивного поиска.

F(x) – заданная целевая функция – должна быть описана отдельно.

Входные данные: А, B – значения концов отрезка локализации [ A, B ];

Eps – заданная точность вычислений;

Результаты: Xmin - приближение к искомому значению абсциссы точки минимума;

Fmin – значение целевой функции в точке минимума.

Начало

Ввод А, В, Eps

N = round ((B - A)/Eps)

Xmin = A

Fmin = F(A)

i = 1.. N

x = A + i* Eps

Fx = F(x)

-

Fmin > Fx

		+

Xmin = x

Fmin = F(x)

Вывод Xmin, Fmin

end

 

Рисунок 2.1 - Блок-схема алгоритма метода оптимального пассивного поиска