ГЛАВА 8. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ ФУНКЦИЙ

8.1. Метод золотого сечения

Рассмотрим задачу поиска минимума функции одной переменной (рис. 8.1) на интервале где расположено несколько локальных минимумов, среди которых можно выбрать глобальный. В общем случае функция может быть как непрерывной, так и разрывной в области поиска минимума. Чтобы перейти к поиску максимумов функции достаточно изменить знак функции на противоположный и действовать по алгоритмам отыскания минимумов.

Рис. 8.1. Функция имеющая минимумы

Минимумы дифференцируемой функции определяются из уравнения

для решения которого можно использовать алгоритмы и программы гл. 1. Известно, что корень х уравнения (8.1) является точкой минимума функции если и точкой максимума при

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

Когда функция недифференцируема и вычисление ее значений для аппроксимации производной связано со значительными затратами времени, минимизацию осуществляют по алгоритмам, не связанным с решением уравнения (8.1). Один из таких алгоритмов рассмотрим в настоящем разделе.

Поиск минимумов функции разделяется на два этапа.

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

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

На втором этапе осуществляется уточнение местоположений минимумов на интервалах унимодальности функции. Пусть функция унимодальна на интервале необходимо построить такую последовательность чтобы минимум функции находился в интервале неопределенности Алгоритм выбора элементов последовательности называют стратегией поиска. При заданном количестве вычислений функции оптимальной является стратегия, которая приводит к наименьшему интервалу неопределенности Установлено, что стратегия поиска минимума будет оптимальной, если для построения последовательности использовать числа Фибоначчи [12]

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

Недостатком метода Фибоначчи является зависимость точек, где проводятся вычисления функции от общего числа вычислений так как на первой итерации точка выбирается из условия деления интервала в отношении Для отношения чисел Фибоначчи установлен предел [12]

Деление отрезка в отношении (8.2) называют золотым сечением, так как в этом случае отношение длины большей части отрезка ко всей его длине будет равно отношению длины меньшей части к длине большей части. Действительно, принимая длину отрезка за единицу, из определения золотого сечения будем иметь

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

положительный корень которого будет равен

Рис. 8.2. Расположение точек деления отрезка методом золотого сечения

Можно на каждой итерации поиска минимума делить интервал неопределенности в одном и том же отношении (точка а другую точку выбирать симметрично точке относительно середины отрезка (рис. 8.2). При этом выбор очередного интервала неопределенности осуществляется так же, как и в методе Фибоначчи, на основании свойств унимодальности функции . Такой метод называют методом золотого сечения. Здесь расположение точек деления и отрезка не зависит от общего числа итераций и вычисления прекращаются, когда длина интервала неопределенности становится меньше заданной величины. После вычислений функции интервал неопределенности местоположения минимума становится равным

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

Метод золотого сечения незначительно уступает оптимальному методу Фибоначчи по времени поиска минимума. Установлено, что при одинаковом числе итераций метод золотого сечения приводит к отрезку неопределенности, лишь на 17% большему, чем метод Фибоначчи [12].

Метод золотого сечения иногда сочетают с одним из методов аппроксимации минимизируемой функции, которую в области минимума обычно приближают параболой, минимум которой определяется по аналитической формуле. Программа на языке Фортран, реализующая подобный алгоритм, имеется в [19].

Программы 8.1 составлены в соответствии с блок-схемой рис. 8.3.

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

Рис. 8.3. Блок-схема программы минимизации функции методом золотого сечения

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

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

В качестве примера функции в программах 8.1 используется радиальная волновая функция электрона атома водорода, находящегося в возбужденном состоянии [67],

где расстояние между электроном и ядром, нормированное на боровскрй радиус с - нормирующий множитель.

Рис. 8.4. Радиальная волновая функция -электрона [67]

Функция (8.3) на интервале [0, 15] имеет два корня, минимум и максимум (рис. 8.4). Вычисление функции осуществляется в отдельной подпрограмме. Здесь же функция изменяется в зависимости от значения условного числа

В программе подпрограмма метода золотого сечения записана в строках 100-190, а функции в строках 200-290.

В программах метод золотого сечения реализован в подпрограммах с именем с параметрами: границы интервала изменения аргумента функции допустимая погрешность нахождения минимума; X - результат - точка минимума; имя подпрограммы вычисления функции

Таблица 8.1

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

(см. скан)

(см. скан)

(см. скан)