МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ОДНОМЕРНЫХ МНОГОЭКСТРЕМАЛЬНЫХ ФУНКЦИЙ

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. Производим испытание в точке x_r и вычисляем значение f_r = f(x_r) функции 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. Производим испытание в точке  – вычисляем значение f_r = f(x_r) функции 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), может использоваться ее первая разность в этой точке , где х – некоторая малая величина. А именно, если   f_x > 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)

или, другими словами, полином , должен иметь в качестве корней все числа , кроме числа x_j, а при x = x_j должен иметь значение, равное единице.

Условию (4.4) удовлетворяют только полиномы вида , где A – неизвестная константа. Найдем эту константу из условия :

Таким образом,

    (4.5)

и искомый аппроксимирующий полином определяют выражением

                                     (4.6)

Полином (4.6) называется аппроксимирующим полиномом Лагранжа.

Использование аппроксимирующего полинома Лагранжа (4.6) в качестве модельной функции идейно очень просто, но обладает существенным недостатком. Пусть после построения этого полинома на сетке  и проверке его адекватности выясняется, что погрешность аппроксимации превышает заданную. Тогда, в соответствии с рассмотренным выше алгоритмом метода, необходимо построить новый полином Лагранжа на сетке, полученной объединением сеток , , что требует пересчета всех посчитанных ранее функций . От этого недостатка свободна модификация аппроксимирующего полинома Лагранжа – аппроксимирующий полином Ньютона.

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