Классификация методов оптимизации
1. По числу параметров:
— одномерная оптимизация;
— многомерная оптимизация.
2. По использованию производных:
— методы нулевого порядка (прямые методы);
— методы первого порядка (градиентные методы);
— методы второго порядка.
— . . .
Целевую функцию Ф(Р) будем считать унимодальной.
Определение унимодальности функции
Предположим, что f — действительная функция, определенная на [0,1]. Предположим, далее, что имеется единственное значение х, такое, что f(
) — максимум f(x) на [0,1], и что f(x) строго возрастает для x ≤ и строго убывает для ≤ x. Такая функция называется унимодальной: для ее графика имеются три возможные формы:
Рис. 1.Графики унимодальной функции
Заметим, что унимодальная функция не обязана быть гладкой или даже непрерывной.
Задачу оптимизации сформулируем следующим образом:
найти множество абсцисс x1, x2… хk, в которых вычисляется функция, такое, что оптимальное значение f лежит при некотором i в интервале хi-1 ≤ х ≤ хi+1 (этот интервал называется интервалом неопределенности).
Алгоритм выбора абсцисс xi (i=1,…,k) называется планом поиска. Если известно только то, что f унимодальная, то какова оптимальная стратегия для нахождения х? При заданном количестве вычислений функции оптимальным планом поиска будет тот, который приводит к наименьшему интервалу неопределенности.
Большинство методов многомерной оптимизации сводится к задаче одномерной оптимизации.
Рассмотрим три известных метода одномерной оптимизации:
1. Метод дихотомии (деления отрезка пополам)
Пусть имеется целевая функция, изображенная на рис.2. Необходимо определить экстремум функии на участке (a, b)
Делим ось абсцисс на четыре равные части и вычисляем значение целевой функции в пяти точках, далее выбираем минимум из пяти найденных значений. Очевидно, что экстремум функции лежит в границах участка (a‘, b‘) прилегающего к точке найденного минимума. Интервал поиска сужается в два раза.
Если минимум находится в точке а или b, то интервал сужается в четыре раза.
Полученный интервал вновь разбиваем на четыре равные части. Поскольку значения целивой функции в трех точках были вычислены на предыдущем этапе следующий этап требует вычисления целевой функции в двух точках.
Загрузка...
