- •Лабораторная работа 1. Исследование методов одномерного поиска минимума унимодальных функций
- •Лабораторная работа 2. Исследование методов полиномиальной интерполяции для поиска минимума целевых функций
- •Лабораторная работа 3. Исследование методов линейного поиска
- •3.1 Требования задания
- •3.2 Контрольные вопросы
- •3.3 Содержание отчета
- •Лабораторная работа 4. Исследование градиентных методов
- •4.1 Требования задания
- •4.2 Контрольные вопросы
- •4.3 Содержание отчета
- •Лабораторная работа 5. Проектирование программы оптимизации
- •5.1 Требования задания
- •5.2 Контрольные вопросы
- •5.3 Содержание отчета
- •Лабораторная работа 6. Исследование модификаций ньютоновских оптимизационных процессов
- •6.1 Требования задания
- •6.2 Контрольные вопросы
- •6.3 Содержание отчета
- •Лабораторная работа 7. Исследование методов безусловной оптимизации первого порядка
- •7.1 Требования задания
- •7.2 Контрольные вопросы
- •7.3 Содержание отчета
- •Лабораторная работа 8. Исследование методов безусловной оптимизации нулевого порядка
- •8.1 Требования задания
- •8.2 Контрольные вопросы
- •8.3 Содержание отчета
- •Лабораторная работа 9. Исследование алгоритмов случайного поиска
- •9.1 Требования задания
- •9.2 Контрольные вопросы
- •8.3 Содержание отчета
- •Приложения Приложение 1. Метод средней точки (метод Больцано)
- •Приложение 2. Метод трехточечного поиска на равных интервалах
- •Приложение 3. Метод Ньютона
- •Приложение 4. Метод линейной интерполяции (метод секущих)
- •Приложение 5. Метод кубической интерполяции для одномерной минимизации
- •Приложение 6. Метод Фибоначчи
- •Приложение 7. Метод Зангвилла
- •Приложение 8. Алгоритм lPтпоиска
- •Приложение 9. Минимизация целевых функций в MicrosoftEcxel8.0
- •Приложение 10. Тестовые функции
- •Список рекомендуемой литературы
Приложение 6. Метод Фибоначчи
Метод Фибоначчи является процедурой линейного поиска минимума унимодальной функции f(x) на замкнутом интервале [a, b], отличающейся от процедуры золотого сечения тем, что очередная пробная точка делит интервал локализации в отношении двух последовательных чисел Фибоначчи. Последовательность чисел Фибоначчи задаётся условиями F0= F1= 1, Fk+1= Fk+ Fk-1, k = 1,2,... Начальными членами последовательности будут 1, 1, 2, 3, 5, 8, 13,... Стратегия поиска Фибоначчи требует заранее указать n - число вычислений минимизируемой функции и- константу различимости двух значений f(x). Рассмотрим один из возможных вариантов метода.
Начальный этап
(1) Задать начальный интервал [a1, b1], длину конечного интервала Lnи определить число n так, чтобы выполнялось условие Fn> (b1- a1)/Ln. Вычислить≤L1/Fn+1.
(2) Взять две пробные точки 1= a1+ (Fn-2/Fn)(b1- a1) и1= a1+ (Fn-1/Fn)(b1-a1). Положить k = 1.
Основной этап
Шаг 1. Сократить текущий интервал локализации:
(1) Если f(k) < f(k), то положить ak+1= ak, bk+1=k,k+1=kи вычислить новую точкуk+1= ak+1+ (Fn-k-2/Fn-k)Lk+1, где Lk+1= bk+1- ak+1; перейти на шаг 2.
(2) Если f(k)≥ f(k),то положить ak+1=k, bk+1= bk,k+1=kи вычислитьk+1= ak+1+ (Fn-k-1/Fn-k) Lk+1.
Шаг 2. Проверить критерий окончания поиска:
(1) Заменить k на k+1. (2) Если k = n - 1, перейти на шаг 3, иначе - на шаг 1.
Шаг 3. Найти аппроксимирующий минимум х(*):
(1) Положить k=k+.
(2) Если f(k) > f(k), то x(*)= (k+ bk)/2. В противном случае - x(*)= (ak+k)/2.
Приложение 7. Метод Зангвилла
Основная стратегия метода базируется на свойстве квадратичных функций, называется свойством параллельного подпространства. Если xk+1- точка минимума квадратичной функции, полученная в результате серии одномерных поисков из начальной точки x1по всем направлениям системыk= {pi}, i = 1,2,...,k, а zk+1- точка минимума этой же функции вдоль тех же направленийk, но из другой начальной точки z1, то вектор pk+1= zk+1- xk+1сопряжен со всеми направлениями системыk.
Начальный этап. Задать начальную точку x1, константу. Положитьp1= - grad y(x1), k = 1.
Основной этап. Шаг 1. Оптимальный поиск точки xk+1= xk+kpk. Если k = n, то перейти к шагу 4.
Шаг 2 Перейти в другую начальную точку z1= xk+1+*d, где d = -grad y(xk+1) - новое поисковое направление,* - оптимальное решение задачи минимизации y(xk+1+d). Положить i = 1.
Шаг 3. Проверить критерий окончания поиска и, если он не выполняется, выполнить спуск вдоль направлений kв точку zk+1:
(1) Если grad y (zi)≤, то остановиться: x* = zi- искомый минимум.
(2)Найти оптимальный шаг iв точку zi+1= zi+pi.
(3)Если i < n, то заменить i на i+1 и вернуться к операции (2); иначе - построить новое сопряженное направление pk+1= zk+1- xk+1, заменить k на k+1 и перейти к шагу 1.
Шаг 4. Установить новые начальные условия для очередной итерации:
(1) взять xn+1за новую начальную точку x1= xn+1, принять p1= - grad y(x1);
(2) заменить k на k+1 и перейти к шагу 1.
Приложение 8. Алгоритм lPтпоиска
Для зондирования гипер-параллелепипеда в алгоритме случайного поиска можно используют точки LPτ–последовательности, обладающие на сегодняшний день наилучшими свойствами равномерного покрытия области.
Для генерации точек LPτпоследовательности можно использовать один из двух алгоритмов: логический и арифметический.
Логический алгоритм обладает большим быстродействием, но требует наличия в программном обеспечении ЭВМ специальных логических функций для типа с плавающей точкой.
Арифметический алгоритм имеет меньшее, хотя и приемлемое быстродействие.
В соответствии с арифметическим алгоритмом i-ая координатаj-ой точки в гиперкубеD:{X| 0 ≤Xi≤ 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)],
[…] – операция взятия целой части числа,
{…} – операция взятия дробной части числа,
rjl– элемент таблицы числителей направляющих чисел.
Матрицы числителей направляющих чисел составлены для достаточно большого количества точек и для большой размерности, достаточной для решения практических задач. Например, матрица 8 x10 см. рис. П 8.1. дает возможность вычислять до 210= 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) |