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

Пассивные методы являются простейшими методами нулевого порядка. Их можно применять для оптимизации целевых функций 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}, равна:

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

^{2 i  N-1}

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

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

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

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

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

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

 (n) {М_i} = _min +_i , где _i  0 ,

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

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

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

h h h h

y₁ y₂ y_n-1 y_n

a=x₁ x₂ x_n-1 b=x_n

Рис. 2.4

Рис.10.3

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

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

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

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

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

h h h h

y₁ y₂ y_n-1 y_n

a x₁ x_n b

Рис. 2.4

Рис.10.4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(b–a) = (₁+₂)+...+(_N-2+_N-1)  (N–1)/2_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)   (N -1)/2 с учётом N = n+2 имеем:   2(b-a)/(n+1) = _min. Из неравенства   _min следует, что точность любого оптимального пассивного метода с нечётным числом узлов всегда в точности равна _min :

 = _min = 2(b - a) /( n+1).

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

у_2s+1 = а+_min  s.

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

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

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

Рис.10.5

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

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

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

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

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

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

Оптимальных методов не существует.

Доказательство. Рассмотрим произвольный пассивный метод на отрезке [a,b] и разобьём интервалы между узлами {у₁,у₂,…,у_N} на пары интервалов (_2s-1,_2s) =([у_2s-1, у_2s] [у_2s, у_2s+1]) (s=1,…,p) и одиночный последний интервал  _N-1= [у _{N - 1}, у_N ].

Из определения точности следует:

_2s-1+_2s; (s=1,…,p) ; _N-1< (так как _N-2+_N-1, _N-2>0) .

Поскольку рассматриваемые интервалы в сумме дают весь отрезок [a,b], то из этих оценок вытекают неравенство:

(b-a)=₁+(₂+₃)+…+(_N-2+_N-1)<+p=(p+1).

Отсюда следует:  > (b-a)/(p+1)= _min.

Данная точность асимптотически достигается на пассивных методах со следующим расположением узлов:

y₁ = a; y_N = b; y_2s = a + s_min -; y_2s+1 = a + s _min +; s = 1,…,p. (10.3)

Точность таких  - оптимальных методов равна  =_min + .

Как следует из Теорем 10.1,10.2, для нечетного n=2p+1 (10.1) и четного n=2p (10.2) чисел пробных точек пассивного метода минимальная гарантированная точность совпадает и равна _min = (b–a)/(p+1). Однако, в первом случае оптимальные методы существуют, а во втором – нет.

Если при четном n=2p числе пробных точек необходимо получить гарантированную точность , строго большую минимально возможной точности _min=(b–a)/(p+1), то –оптимальный метод может быть всегда построен.

Пример 2. Рассмотрим построение пробных точек для пассивного метода на отрезке [a,b] для n=2, N=4 – при p=1 паре пробных точек (рис.10.6) в случае заданной точности , которая строго превышает минимально возможную _on = (b-a)/(p+1)= (b-a)/2.

Решение. Введем  =  -  _on. С учетом a + (b-a)/2 = (a+b)/2 из (10.3) получим следующие узлы, обеспечивающие заданную точность  :

y₁ = a; y₂ = x₁ = 0,5(a+b) -  ; y₃ = x₂ = 0,5(a+b) +  ; y₄ = b.

Рис.10.6

При 0 гарантированная точность рассмотренного в примере 2 метода   0,5(a+b). В то же время, при равномерном распределении пробных точек (x₁=(a+b)/3; x₂ =2(a+b)/3) гарантированная точность метода была бы равна 2(a+b)/3, т.е. большей величине.

Пример 3. Построим пробные точки для пассивного метода на отрезке [a,b] для n=4, N=6 – при p=2 парах пробных точек (рис.10.7) в случае заданной точности , строго превышающей минимально возможную _on = (b-a)/(p+1)= (b-a)/3.

Решение. Обозначим  =  -  _on. Из (10.3) получим следующие узлы, обеспечивающие заданную точность  :

y₁ = a; y₂ = x₁ = a +  _оп - ; y₃ = x₂ = a +  _оп + ;

y₄ = x₃ = a + 2 _оп - ; y₅ = x₄ = a + 2 _оп + ; y₆ = b .

Рис.10.7

Из Теорем 10.1 и 10.2 вытекает следующий алгоритм выбора оптимального числа пробных точек n пассивного метода по заданному исходному доверительному отрезку [a; b] и точности :

1) расчет числа полных пар пробных точек по формуле p = ](b - a)/[;

2) расчет минимальной гарантированной точности, которую может обеспечить пассивный метод при найденном числе p: _min = (b-a)/(p+1);

3) если _min < , то выбирая =-_min, можно построить оптимальный пассивный метод с n = 2p пробными точками;

4) если же _min = , то оптимального пассивного метода с четным числом точек не существует и надо принимать n = 2p +1.

Пример 4. Найти доверительный интервал, содержащий точный минимум функции F(х) = х² –2х на исходном отрезке [0,2; 2] при заданной гарантированной точности  =0,5 пассивным методом с предварительным расчетом числа узлов.

Решение. Из Теорем 10.1,10.2 следует, что для заданных нечетного n=2p+1 и четного n=2p чисел пробных точек пассивного метода минимальная гарантированная точность совпадает и равна _min = (b-a)/(p+1). Отсюда с учетом соотношения _min  0,5 получим:

( p+1)= (b - a) /_min  (b - a) /0,5 = 1,8 /0,5 = 3,6.

Так как p -целое, отсюда следует: p =]3,6-1[=]2,6[=3.

Рассмотрим четное n=2p число пробных точек. Для него предельная гарантированная точность _min = (b-a)/(p+1) = 1,8/4 = 0,45. Для достижения действительной точности 0,5 используем величину  = 0,5-0,45 = 0,05. Рассчитаем положение пробных точек и значение функции в них:

x1 = a+0,45 - =0,6 ;	F(x1)= -0,84;
x2 = a+0,45+ =0,7;	F(x2)= -0,91;
x3 = a+2 0,45 - =1,05;	F(x3)= -0,9975;
x4 = a+2 0,45+ =1,15;	F(x4)= -0,9775;
x5 = a+3 0,45 - =1,5;	F(x5)= -0,75;
x6 = a+3 0,45+ =1,6;	F(x6)= -0,64.

В качестве искомого минимума выбираем точку x₃ = 1,05 с минимальным найденным значением функции F(x₃) = -09975.

Точный минимум, найденный аналитическим путем расположен в точке х=1, значение функции в этой точке F(x)=–1.

Ответ. Для решения задачи пассивным методом с гарантированной точностью  =0,5 необходимо использование не менее 6 пробных точек. Точное значение минимума находится на отрезке [x₂, x₄] = [0,7; 1,15]. Найдено приближенное положение точки минимума x_min=1,05, в котором значение функции F(x₃)=-0,9975.

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

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

Оценим асимптотические (при n  ) скорости роста зависимостей (n) и n() в оптимальных пассивных методах. Поскольку

и

то ε(n) и (b–a)/n имеют одинаковую скорость роста. Отсюда следует:

 (n) = O[(b-a)/n],

n() = O[(b - a)/] = O[М].

Вопросы для проверки знаний.

1. Чему равна гарантированная точность пассивного метода ?

2. Что называют минимальной гарантированной точностью пассивных методов ?

3. Какие методы из заданной группы называют оптимальными ?

4. Какие методы называют -оптимальными ?

5. Какие сетки называют равномерными ?

6. Как располагаются узлы на обычных равномерных сетках и сетках со сдвигом на шаг ?

7. Почему пассивный метод на сетке со сдвигом на шаг более предпочтителен по сравнению с методом на обычной сетке ?

8. При каких числах пробных точек оптимальные пассивные методы существуют, а при каких – не существуют ?

9. В чем заключаются преимущества и недостатки пассивных методов ?

Практические задания.

Найти доверительный интервал, содержащий точный минимум функции на исходном отрезке [a; b] при заданной гарантированной точности  пассивным методом с предварительным расчетом оптимального числа узлов.

1. F(х) = 3х² –9х+7, x [0,5;3],  =0,6;

2. F(х) = 5х² +3, x [-2; 5],  =0,8;

3. F(х) = 2х³ –9х², x [1,7;3,5],  =0,6;

4. F(х) = 3х³ –9х, x [-0,5;2,5],  =0,5;

5. F(х) = sin(0,5x), x [6,5;12],  =0,8;

6. F(х) = cos(2x), x [0;3],  =0,7;

7. F(х) = sin²x, x [-1,5;1,5],  =0,4;

8. F(х) = x³- 6x²+11x , х[1;4],  =0,6;

9. F(х) = cosx+sinx, х[-; /4],  = 0,4;

10. F(х) = cos²x –cosx, х [0; ],  = 0,5;

11. F(х) = 4^x- 2^x+3, х [0; 8],  = 2;

12. F(х) = 27^x- 9^x+0,5 + 3^x+2 - 2x, х [0; 8] , =2;

13. F(х) = sinx+х²+х, х  [-; /4] ,  = 0,6.