Пассивные методы однопараметрической оптимизации

Пассивные методы являются простейшими методами нулевого порядка. Их можно применять для оптимизации целевых функций F (x) любого вида. Основным их недостатком является большое количество вычислений значений функции и, как следствие этого, большие общие затраты времени.

В пассивных методах указывается способ размещения сразу всех пробных точек { x_i } = { x ₁ ,..., x_n }на исходном заданном интервале, затем в них рассчитываются значения целевой функции { F (x ₁) ,..., F (x_n)}. В качестве приближённого оптимального (например, при поиске минимума) значения принимают тот узел x_k, в котором F (x_k) = min F (x_i), при всех i= 1 ,…,n. Наряду с пробными точками рассмотрим множество узлов, общее число которых обозначим через N. Поскольку в общем случае неизвестно, с какой стороны от приближённого оптимального аргумента у_k (на интервале [ у_{k- 1}, у_k ]или [ у_k, у_{k+ 1}]) расположено точное оптимальное значение аргумента x_min, то точность его положения в данном случае будет равна: у_{k+ 1}- у_{k - 1}. Гарантированная точность пассивного метода, который характеризуется своим способом задания узлов { у ₁ ,..., у_N }, равна:

e = m a x { у_{i+ 1}- у_{i - 1}}.

^{2£ i £ N-1}

Минимальной гарантированной точностью пассивных методов называют минимальную величину e, которую можно получить в них за счёт расположения пробных точек на исходном доверительном отрезке [ a,b ]:

e _min = min e = m i n m a x { у_{i+ 1} -у_{i - 1}}.

{ у_i } { у_i }^{2 £ i £ N- 1}

Оптимальными (среди некоторой группы) называют такие методы оптимизации, на которых достигается минимальная гарантированная точность e_min при заданном количестве вычислений функции n либо при заданной e достигается минимум числа n.

Характеристики e (n)и n (e), определяющие оптимальность метода (как пассивного, так и последовательного), зависят от способа выбора пробных точек { x_i } = { x ₀, x ₁ ,..., x_n }метода.

Если гарантированная точность e (n)на некоторой последовательности методов { М_i }= { М₁,М₂, … } асимптотически стремится к некоторому предельному минимальному значению e_min:

e (n){ М_i } = e_min +d_i, где d_i ® 0,

причём метода с точностью e_min не существует, то методы { М_i }называют d - оптимальными.

Чаще всего в пассивных методах пробные точки задают на равномерных сетках, у которых шаг между соседними точками h = х_{i+ 1}- х_i является постоянным. Очевидно, точность таких методов e (n) = 2 h. На практике используют два основных вида равномерных сеток.

1. Обычная сетка. Крайние пробные точки совпадают с конечными точками отрезка: x ₁ =a; x_n=b (рис. 10.3).

h h h h

y₁ y₂ y_n-1 y_n

Рис. 2.4

Рис.10.3

Формулы для пробных точек, точности и числа узлов имеют вид:

h= (b-a)/(n- 1); x_i = a + h (i- 1); i = 1 ,...,n; e (n) = 2(b - a)/(n- 1); N = n.

Число вычислений целевой функции n при заданной точности e находим из условия: (n- 1) h = (n- 1 )e /2 ³ (b-a).Отсюда получим:

n (e)=]2(b - a) /e [+1 = ]2 M [+1.

2. Сетка со сдвигом на шаг. Крайние пробные точки сетки отстоят на полный шаг h от крайних точек отрезка [ a,b ]: х ₁ = а + h; х_n = b - h.

h h h h

y ₁ y ₂ y_{n- 1} y_n

Рис. 2.4

Рис.10.4

Общие формулы:

h = (b - a) / (n+ 1); х_i =a+ hi; i= 1 ,…,n; e (n) = 2(b-a)/(n+ 1); N=n+ 2.

Из условия (n+ 1) h = (n+ 1)e /2 ³ (b-a) следует:

n(e) = ]2(b - a)/e[ - 1 = ]2 M [-1.

Обобщая формулы для шага и точности пассивных методов на равномерных сетках, получим:

h = (b - a) / (N -1); e (n) = 2 (b - a) /(N -1),

где N – общее число узлов на отрезке [ a,b ].

Выполненный анализ показывает, что пассивный метод на сетке со сдвигом на шаг наиболее предпочтителен с точки зрения оптимальности рассмотренных методов на равномерных сетках. Можно показать, что в оптимальных методах соотношение чисел узлов и пробных точек всегда следующее: N = n+ 2.

Для оптимальных пассивных методов с произвольными сетками необходимо рассмотреть отдельно случаи с нечётным и четным числом узлов N. Для этого введем наряду с числами пробных точек n и узлов N вспомогательный параметр p - полное число пар пробных точек. При четном числе пробных точек n = 2 p, при нечетном n = 2 p +1.

Теорема 10.1 (для нечётного числа узлов). При нечётном общем числе n = 2 p+ 1 вычислений целевой функции F (x) на исследуемом отрезке [ a,b ] минимальная гарантированная точность пассивных методов равна

e_min = 2(b - a)/(n+ 1) = (b - a) /(р+ 1) (10.1)

и достигается при количестве узлов N = n+ 2 = 2 p+ 3. Число оптимальных методов бесконечно.

Доказательство. Как показано выше, данная точность достигается на пассивном методе с равномерной сеткой со сдвигом на шаг, т.е. он является одним из возможных оптимальных пассивных методов.

Необходимо доказать, что оценка e_min не может быть уменьшена, т.е. выполняется для всех оптимальных пассивных методов с данным числом узлов. Рассмотрим произвольный оптимальный пассивный метод с N узлами { у ₁, у ₂, …,у_N } и точностью e £ e_min и (N -1)/2 пар интервалов (D _{k- 1}, D _k) = [ у_{k- 1} ,у_k ], [ у_k, у_{k+ 1}](k= 2,4 ,…,N- 1). По определению точности: ïD _{k- 1}ï+ïD _k ï£ e. Так как данные пары интервалов в сумме составляют весь отрезок [ a,b ], то из данной оценки вытекает следующее основное неравенство:

(b–a) = (ïD₁ï+ïD₂ï)+...+(ïD _{N- 2}ï+ïD _{N- 1}ï) £ e(N– 1)/2£e _min (N– 1)/2 = (b-a)(N -1)/(n+ 1).

Основное неравенство позволяет сделать следующие выводы.

1. Из (b - a) £ (b - a)(N -1)/(n+ 1)получим:(N -1) ³ (n+ 1), отсюда: N ³ n+ 2. Так как число узлов N не может превышать n+ 2, то для рассматриваемого произвольного оптимального метода: N = n+ 2.

2. Из(b - a) £ e (N -1)/2 с учётом N = n+ 2имеем: e ³ 2(b-a)/(n+ 1) = e _min. Из неравенства e £ e_min следует, что точность любого оптимального пассивного метода с нечётным числом узлов всегда в точности равна e_min:

e = e_min = 2(b - a) /(n+ 1).

3. Из определения точности метода следует, что для сумм длин подряд стоящих интервалов (D₁, D₂), (D₃, D₄),…выполняется неравенство:ïD _{k- 1}ï+ïD _k ï£ e _оп = 2(b - a)/(N -1), (k =2,4,…, N -1). Так как в сумме эти длины равны e_min (N -1)/2 = (b - a), то отсюда следует, что у оптимального пассивного метода должно выполняться точное равенство ïD _{k- 1}ï+ïD _k ï = e_min (k = 2,4,…, N- 1) и нечётные узлы у_{2s+ 1}(s= 0,1,…,(N- 1)/2) должны всегда размещаться на отрезке [ a,b ] с постоянным шагом, равным e_min:

у _{2 s+ 1} = а+e_min × s.

Чётные узлы у оптимального метода должны располагаться между нечётными с соблюдением условия ï у _{2 s+ 2} - у _{2 s} ï£ e_min, (s= 1 ,…, (N- 3)/2) – не обязательно на равномерной сетке с шагом e_min /2, следовательно, существует бесконечно много возможных вариантов выбора чётных узлов, а значит и число оптимальных методов бесконечно.

Пример 1. Рассмотрим один из возможных вариантов расположения пробных точек у оптимального пассивного метода с n= 3, N= 5 – при p =1 паре пробных точек.

Расположение пробных точек { х ₁, х ₂, х ₃} и узлов { y ₁, y ₂, y ₃, y ₄, y ₅} дано на рис.10.5.

Рис.10.5

В этом случае:

e_оп = 2(b - a)/(5 -1) = (b - a) /2,

у ₁ = a, у ₃ = х ₂= a+ (b - a)/2 = (a+ b)/2, у ₅ = b,

положение узлов y ₂, y ₄ (пробных точек х ₁, х ₃) выбрано произвольным образом из условия: ï у ₄ - у ₂ï=ï х ₃ -х ₁ï £ e_оп .

Теорема 10.2 (для чётного числа узлов). При чётном общем числе n= 2 p вычислений целевой функции F (x) и количестве узлов N = n+ 2 на исследуемом отрезке [ a,b ] минимальная предельная гарантированная точность пассивных методов равна

e_min = (b-a)/(p+ 1). (10.2)