4 МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ОДНОМЕРНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ
Некоторые методы решения многомерных задач оптимизации (если размерность вектора варьируемых параметров X больше единицы, то детерминированная задача оптимизации называется многопараметрической задачей оптимизации) требуют решения одномерной задачи глобальной оптимизации (ставится задача отыскания глобального минимума критерия оптимальности f(x)).
4.1 Метод перебора. Одномерный метод Монте-Карло
Рассматривается следующая одномерная задача условной глобальной оптимизации (если задача оптимизации является задачей условной оптимизации и отыскивается глобальный минимум критерия оптимальности f(x), то эта задача оптимизации называется задачей глобальной условной оптимизации): найти минимум, вообще говоря, многоэкстремальной функции f(x), определенной в замкнутой области допустимых значений D = [a;b]:
(4.1)
Алгоритм метода перебора
![]() |
Рис. 4.1. Иллюстрация метода перебора
Шаг 1. Покрываем интервал [a;b] некоторой сеткой с узлами .
Шаг 2. Производим испытание в точке ,
т.е. вычисляем значения
функции f(x) в этой точке.
Шаг 3. Полагаем r = 2.
Шаг 4. Производим испытание в точке xr и вычисляем значение fr = f(xr) функции f(x) в этой точке.
Шаг 5. Если , то
выполняем присваивания
.
Шаг 6. Если r < N, то выполняем присваивание r = r + 1 и переходим к шагу 4, иначе заканчиваем вычисления.
Шаг 7. Принимаем в качестве приближенного
значения точки глобального минимума функции f(x) на интервале [a;b] или каким-либо из рассмотренных одномерных методов
локальной оптимизации организуем в окрестности точки поиск локального минимума
этой функции.
При выборе количества узлов сетки можно
исходить из требуемой точности решения
–
максимальный шаг сетки принять равным этой величине.
Замечание. Метод перебора, как и любой другой метод глобальной оптимизации, при отсутствии априорной информации о свойствах минимизируемой функции не гарантирует нахождение глобального минимума (пунктирный график на рис. 4.1).
Алгоритм одномерного метода Монте-Карло
Шаг 1. Генерируем с помощью какого-либо программного генератора случайных
чисел, равномерно распределенных в интервале [a;b], случайное число .
Шаг 2. Производим испытание в точке и
вычисляем значения
функции f(x) в этой точке.
Шаг 3. Полагаем r = 2.
Шаг 4. Аналогично шагу 1 генерируем случайное число .
Шаг 5. Производим испытание в точке –
вычисляем значение fr = f(xr) функции f(x) в этой точке.
Шаг 6. Если , то выполняем
присваивания
.
Шаг 7. Если r < N, то выполняем присваивание r = r + 1 и переходим к шагу 4, иначе заканчиваем вычисления. Здесь N – количество испытаний.
Шаг 8. Принимаем в качестве приближенного
значения точки глобального минимума функции f(x) на интервале [a;b] или каким-либо из рассмотренных одномерных методов
локальной оптимизации организуем в окрестности точки
поиск
локального минимума этой функции.
При достаточно большом N метода гарантирует нахождение глобального минимума с высокой вероятностью.
4.2 Метод выделения интервалов унимодальности
Рассмотрим одномерную задачу условной глобальной оптимизации: найти минимум одномерной многоэкстремальной функции f(x), определенной в замкнутой области допустимых значений D = [a;b] и имеющей в этой области конечное число минимумов (4.1).
Метод выделения интервалов унимодальности функции f(x) требует априорного знания оценки d > 0 минимального расстояния между локальными минимумами этой функции.
Алгоритм метода выделения интервалов унимодальности (рис. 4.2):
Шаг 1. Полагаем r = 1.
Шаг 2. Если функция f(x)
в точке a возрастает, то полагаем и переходим к шагу 4.
Шаг 3. Если функция f(x)
в точке a убывает, то полагаем и переходим к шагу 5.
Рис. 4.2. К алгоритму метода выделения интервалов унимодальности
Шаг 4. Последовательно увеличивая х на величину по формуле
, находим первую точку
, в которой функция f(x) убывает. Здесь и
далее
– величина в несколько раз меньшая
величины d.
Шаг 5. Последовательно увеличивая х на величину по формуле
, находим первую точку
, в которой функция f(x) возрастает.
Шаг 6. В качестве r-го интервала
унимодальности принимаем интервал [].
Шаг 7. Если интервал [a;b] исчерпан, переходим шагу 8, иначе полагаем и переходим к шагу 4.
Шаг 8. Положим, что общее количество найденных интервалов унимодальности
функции f(x)
равно N – 1. Каким-либо одномерным методом
локальной оптимизации находим локальный минимум функции f(x) в каждом из N – 1
интервалов унимодальности. Обозначим точки этих минимумов . Соответствующие значения функции f(x) обозначим
. Добавим к точкам
точки
и
вычислим соответствующие значения
функции f(x).
Шаг 9. Найдем минимальную из величин и
соответствующее значение аргумента:
.
Шаг 10. В качестве решения задачи глобальной оптимизации (4.1) примем
точку .
На рис. 4.2 интервалами унимодальности являются интервалы .
Для определения того, возрастает или убывает в данной точке функция f(x), может использоваться
ее первая разность в этой точке , где
х – некоторая малая
величина. А именно, если
fx > 0,
то функция возрастает в точке х; иначе – убывает. Заметим, что при этом
в каждой точке требуется выполнить дополнительное испытание функции f(x).
Если функция f(x)
непрерывно дифференцируема в интервале [a;b], то для определения того, возрастает или убывает в
данной точке эта функция, можно, очевидно, использовать значения первой
производной функции f(x)
в этой точке. А именно, если , то в точке x функция f(x) возрастает; в противном случае – убывает.
Замечание
Если априорная оценка d минимального
расстояния между локальными минимумами функции f(x) отсутствует, то никаких оснований полагать, что в
интервалах, выделенных с помощью рассмотренного алгоритма, функция f(x) является унимодальной
функцией. Пусть, например, функция f(x) на интервале [c;d] постоянна (рис. 4.3). Если к такой функции применить
алгоритм выделения интервалов унимодальности с любым >
0, то в качестве интервала унимодальности будет выделен интервал
, на котором функция f(x) имеет бесконечное
количество минимумов, т.е. не является унимодальной функцией.
Рис. 4.3. Иллюстрация к замечанию
4.3 Метод аппроксимирующих моделей
Рассмотрим одномерную задачу условной глобальной оптимизации: найти минимум одномерной мультимодальной функции f(x), определенной в замкнутой области допустимых значений D = [a;b] (4.1).
Алгоритм метода аппроксимирующих моделей:
Рис. 4.4. Алгоритм метода аппроксимирующих моделей. N = 5
Шаг 1. Покрываем интервал [a;b] некоторой сеткой с узлами и
производим испытания в точках
, т.е. вычисляем
значения функции f(x)
в этих точках
.
Шаг 2. Строим аппроксимирующую функцию ,
проходящую через точки
. Эту функцию
принято называть математической моделью минимизируемой функции f(x) или модельной
функцией.
Шаг 3. Оцениваем адекватность построенной модели .
Для этого:
производим дополнительные испытания функции f(x) в некоторых точках;
вычисляем значения модельной функции и
функции f(x) в
этих точках
;
вычисляем погрешность аппроксимации, например, .
Шаг 4. Если погрешность аппроксимации превышает заданную, то по
результатам всех предшествующих испытаний строим новую модельную функцию и переходим к шагу 3.
Шаг 5. Определяем положение глобального минимума модельной функции , который или принимается в
качестве глобального минимума функции f(x), или уточняется с помощью какого-либо метода локальной
оптимизации.
На
рис. 4.4 – точки локального минимума
модельной функции
; точка
– приближенное значение точки
глобального минимума функции f(x) на интервале [a;b].
В качестве модельных функций чаще всего
используют полиномы и сплайны.
Рассмотрим использование в качестве модельной функции полиномов.
Аппроксимирующий полином Лагранжа
Будем искать аппроксимирующий полином в виде
(4.2)
где – неизвестные полиномы от х,
независящие от аппроксимируемой функции
.
Из того условия, что модельная функция должна
совпадать с аппроксимируемой функцией f(x) в узлах сетки
,
имеем систему из N + 1
равенств:
(4.3)
Для выполнения равенств (4.3) полиномы ,
очевидно, должны удовлетворять условиям
(4.4)
или, другими
словами, полином , должен иметь в качестве
корней все числа
, кроме числа xj, а при x = xj должен иметь значение, равное единице.
Условию (4.4) удовлетворяют только полиномы вида , где A
– неизвестная константа. Найдем эту константу из условия
:
Таким образом,
(4.5)
и искомый аппроксимирующий полином определяют выражением
(4.6)
Полином (4.6) называется аппроксимирующим полиномом Лагранжа.
Использование аппроксимирующего полинома Лагранжа (4.6) в качестве
модельной функции идейно очень просто, но обладает существенным недостатком.
Пусть после построения этого полинома на сетке и
проверке его адекватности выясняется, что погрешность аппроксимации превышает заданную.
Тогда, в соответствии с рассмотренным выше алгоритмом метода, необходимо
построить новый полином Лагранжа на сетке, полученной объединением сеток
,
,
что требует пересчета всех посчитанных ранее функций
. От этого недостатка свободна
модификация аппроксимирующего полинома Лагранжа – аппроксимирующий полином
Ньютона.
После построения аппроксимирующего полинома возникает задача нахождения
стационарных точек функции . Поскольку
аппроксимирующий полином непрерывен и, по крайней мере, один раз непрерывно
дифференцируем, его стационарные точки удобно искать как нули первой
производной – т.е. как корни уравнения
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.