Приложение 6. Метод Фибоначчи

Метод Фибоначчи является процедурой линейного поиска минимума унимодальной функции f(x) на замкнутом интервале [a, b], отличающейся от процедуры золотого сечения тем, что очередная пробная точка делит интервал локализации в отношении двух последовательных чисел Фибоначчи. Последовательность чисел Фибоначчи задаётся условиями F₀= F₁= 1, F_k+1= F_k+ F_k-1, k = 1,2,... Начальными членами последовательности будут 1, 1, 2, 3, 5, 8, 13,... Стратегия поиска Фибоначчи требует заранее указать n - число вычислений минимизируемой функции и- константу различимости двух значений f(x). Рассмотрим один из возможных вариантов метода.

Начальный этап

(1) Задать начальный интервал [a₁, b₁], длину конечного интервала L_nи определить число n так, чтобы выполнялось условие F_n> (b₁- a₁)/L_n. Вычислить≤L₁/F_n+1.

(2) Взять две пробные точки ₁= a₁+ (F_n-2/F_n)(b₁- a₁) и₁= a₁+ (F_n-1/F_n)(b₁-a₁). Положить k = 1.

Основной этап

Шаг 1. Сократить текущий интервал локализации:

(1) Если f(_k) < f(_k), то положить a_k+1= a_k, b_k+1=_k,_k+1=_kи вычислить новую точку_k+1= a_k+1+ (F_n-k-2/F_n-k)L_k+1, где L_k+1= b_k+1- a_k+1; перейти на шаг 2.

(2) Если f(_k)≥ f(_k),то положить a_k+1=_k, b_k+1= b_k,_k+1=_kи вычислить_k+1= a_k+1+ (F_n-k-1/F_n-k) L_k+1.

Шаг 2. Проверить критерий окончания поиска:

(1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе - на шаг 1.

Шаг 3. Найти аппроксимирующий минимум х^(*):

(1) Положить _k=_k+.

(2) Если f(_k) > f(_k), то x^(*)= (_k+ b_k)/2. В противном случае - x^(*)= (a_k+_k)/2.

Приложение 7. Метод Зангвилла

Основная стратегия метода базируется на свойстве квадратичных функций, называется свойством параллельного подпространства. Если x^k+1- точка минимума квадратичной функции, полученная в результате серии одномерных поисков из начальной точки x¹по всем направлениям системы_k= {pⁱ}, i = 1,2,...,k, а z^k+1- точка минимума этой же функции вдоль тех же направлений_k, но из другой начальной точки z₁, то вектор p^k+1= z^k+1- x^k+1сопряжен со всеми направлениями системы_k.

Начальный этап. Задать начальную точку x¹, константу. Положитьp₁= - grad y(x¹), k = 1.

Основной этап. Шаг 1. Оптимальный поиск точки x^k+1= x^k+_kp^k. Если k = n, то перейти к шагу 4.

Шаг 2 Перейти в другую начальную точку z¹= x^k+1+*d, где d = -grad y(x^k+1) - новое поисковое направление,* - оптимальное решение задачи минимизации y(x^k+1+d). Положить i = 1.

Шаг 3. Проверить критерий окончания поиска и, если он не выполняется, выполнить спуск вдоль направлений _kв точку z^k+1:

(1) Если grad y (zⁱ)≤, то остановиться: x* = zⁱ- искомый минимум.

(2)Найти оптимальный шаг _iв точку zⁱ⁺¹= zⁱ+pⁱ.

(3)Если i < n, то заменить i на i+1 и вернуться к операции (2); иначе - построить новое сопряженное направление p^k+1= z^k+1- x^k+1, заменить k на k+1 и перейти к шагу 1.

Шаг 4. Установить новые начальные условия для очередной итерации:

(1) взять xⁿ⁺¹за новую начальную точку x¹= xⁿ⁺¹, принять p¹= - grad y(x¹);

(2) заменить k на k+1 и перейти к шагу 1.

Приложение 8. Алгоритм lPтпоиска

Для зондирования гипер-параллелепипеда в алгоритме случайного поиска можно используют точки LPτ–последовательности, обладающие на сегодняшний день наилучшими свойствами равномерного покрытия области.

Для генерации точек LPτпоследовательности можно использовать один из двух алгоритмов: логический и арифметический.

Логический алгоритм обладает большим быстродействием, но требует наличия в программном обеспечении ЭВМ специальных логических функций для типа с плавающей точкой.

Арифметический алгоритм имеет меньшее, хотя и приемлемое быстродействие.

В соответствии с арифметическим алгоритмом i-ая координатаj-ой точки в гиперкубеD:{X| 0 ≤X_i≤ 1} вычисляется в соответствии с выражением (*):

aij= ∑k=1,m2-k+1{(1/2) ∑l=1,m[2 {i* 2-l}] [2 {rjl*2k-1-l}]},

(П 8.1)

где m = 1 + [ln(i) / ln(2)],

[…] – операция взятия целой части числа,

{…} – операция взятия дробной части числа,

r_jl– элемент таблицы числителей направляющих чисел.

Матрицы числителей направляющих чисел составлены для достаточно большого количества точек и для большой размерности, достаточной для решения практических задач. Например, матрица 8 x10 см. рис. П 8.1. дает возможность вычислять до 2¹⁰= 1024 точек при векторе варьируемых параметров размерностью до 8.

rjl	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	3	5	15	17	51	85	255	257	771
3	1	1	7	11	13	61	67	79	465	721
4	1	3	7	5	7	43	49	147	439	1013
5	1	1	5	3	15	51	125	141	177	759
6	1	3	1	1	9	59	25	89	321	835
7	1	1	3	7	31	47	109	173	181	949
8	1	3	3	9	9	57	43	43	255	113

Рис. П 8.1. Матрица направляющих чисел 8 х 10

Для перевода точки, полученной в соответствии с выражением (П 8.1), в произвольный гипер-параллелепипед, обычно используют линейное преобразование:

Xij=Aj+aij(Bj-Aj),

(П 8.2)

Однако, если границы гипер-параллелепипеда имеют значительный разброс и отличаются друг от друга на несколько порядков, то для обеспечения попадания пробных точек в пограничные области обычно применяют логарифмическое преобразование границ вариации и варьируемого вектора:

Xij= 10 в степени (log(Aj)+aij(log(Bj) –log(Aj))),

(П 8.3)