ОПТИМИЗАЦИЯ УНИМОДАЛЬНЫХ ФУНКЦИЙ МЕТОДОМ ПАРАБОЛИЧЕСКОГО ПРЕДИКТОРА
Журнал: ВЕСТНИК АСТРАХАНСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА. СЕРИЯ: УПРАВЛЕНИЕ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
№ 3
, 2018
Рубрики: МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Авторы:
1.
Сибирский федеральный университет
Тип:
Статья
Страницы:
с 101
по 108
Статус:
Опубликован
Получено:
05.07.2018
Одобрено:
25.07.2018
Опубликовано:
25.07.2018
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 519.67
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 519.67
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
параболический предиктор, унимодальная функция, гладкая функция, кусочная функция, пологая функция, плоская функция, минимизация функции, метод золотого сечения, метод парабол, метод Брента, быстродействие метода
Аннотация (русский):
Предложен комбинированный метод параболического предиктора для условной минимизации унимодальной функции, использующий основанное на прогнозе избирательное использование фаз поиска экстремума методом золотого сечения и методом парабол. Дана формула вычисления значения функции параболического предиктора, при помощи которой вырабатывается прогноз и тактика поиска экстремума минимизируемой функции. Предиктор включает прогнозирование экстремальности, монотонности и постоянства функции на отрезке неопределенности. Описан идентифицирующий прогноз для прямой функции, использование которого позволяет найти решение за три ее вычисления. Сформулировано утверждение о том, что если три последовательных вычисления функции дают точки с одинаковыми ординатами, то абсцисса любой из них является решением задачи. Описана процедура идентификации отличных от прямой монотонных функций. Показано, что достоверность прогноза монотонности может быть установлена за пять вычислений функции. Описана процедура использования фаз метода парабол, которые могут быть выполнены при благоприятном прогнозе обнаружения внутреннего экстремума функции. Установлено, что выполнение этих фаз даже при благоприятном прогнозе может быть признано нецелесообразным для случаев, когда признается, что задача слабо чувствительна либо нечувствительна к параболическому прогнозу. Приведены блок-схемы алгоритмов, реализующих метод. Показано, что в сравнении с методом золотого сечения предиктор имеет в 3-5 раз большее быстродействие для гладких функций и сопоставим по этому критерию с методом Брента. Наибольшее быстродействие предиктор обеспечивает при минимизации монотонных функций. Метод работает несколько медленнее метода золотого сечения, однако существенно быстрее метода Брента при поиске минимума кусочных, пологих, плоских и других функций подобного характера, для которых аппроксимация параболой не дает ожидаемого эффекта. В сравнении с методом Брента параболический предиктор имеет в 1,5-4 раза большее быстродействие при решении задач данного типа.
Предложен комбинированный метод параболического предиктора для условной минимизации унимодальной функции, использующий основанное на прогнозе избирательное использование фаз поиска экстремума методом золотого сечения и методом парабол. Дана формула вычисления значения функции параболического предиктора, при помощи которой вырабатывается прогноз и тактика поиска экстремума минимизируемой функции. Предиктор включает прогнозирование экстремальности, монотонности и постоянства функции на отрезке неопределенности. Описан идентифицирующий прогноз для прямой функции, использование которого позволяет найти решение за три ее вычисления. Сформулировано утверждение о том, что если три последовательных вычисления функции дают точки с одинаковыми ординатами, то абсцисса любой из них является решением задачи. Описана процедура идентификации отличных от прямой монотонных функций. Показано, что достоверность прогноза монотонности может быть установлена за пять вычислений функции. Описана процедура использования фаз метода парабол, которые могут быть выполнены при благоприятном прогнозе обнаружения внутреннего экстремума функции. Установлено, что выполнение этих фаз даже при благоприятном прогнозе может быть признано нецелесообразным для случаев, когда признается, что задача слабо чувствительна либо нечувствительна к параболическому прогнозу. Приведены блок-схемы алгоритмов, реализующих метод. Показано, что в сравнении с методом золотого сечения предиктор имеет в 3-5 раз большее быстродействие для гладких функций и сопоставим по этому критерию с методом Брента. Наибольшее быстродействие предиктор обеспечивает при минимизации монотонных функций. Метод работает несколько медленнее метода золотого сечения, однако существенно быстрее метода Брента при поиске минимума кусочных, пологих, плоских и других функций подобного характера, для которых аппроксимация параболой не дает ожидаемого эффекта. В сравнении с методом Брента параболический предиктор имеет в 1,5-4 раза большее быстродействие при решении задач данного типа.
Ключевые слова:
параболический предиктор, унимодальная функция, гладкая функция, кусочная функция, пологая функция, плоская функция, минимизация функции, метод золотого сечения, метод парабол, метод Брента, быстродействие метода
параболический предиктор, унимодальная функция, гладкая функция, кусочная функция, пологая функция, плоская функция, минимизация функции, метод золотого сечения, метод парабол, метод Брента, быстродействие метода
Введение Среди численных методов условной минимизации унимодальных функций наибольшее использование находят метод золотого сечения (МЗС) и метод парабол (МП) [1]. Первый отличается абсолютной надежностью, второй при благоприятных условиях привлекателен высокой скоростью сходимости к результату, под которой понимают существенно меньшее, в сравнении с первым методом, количество вычислений минимизируемой функции (МФ). В «чистом виде» МП имеет ограниченное использование, т. к. его преимущества в значительной мере определяются интервалом неопределенности и свойствами функции, которые обычно проявляются на финальной стадии вычислительного процесса вблизи точки экстремума. На ранних стадиях процесса метод имеет меньшее быстродействие, зачастую даже ниже, чем у МЗС, а в ряде применений получить результат не удается даже для гладких функций. В этой связи МП чаще применяют в комбинации с другими методами, в частности с МЗС, используя для ускорения последнего найденные при помощи МП промежуточные точки. Примером является используемый в пакете Matlab лучший на настоящее время с точки зрения быстродействия комбинированный метод Брента (МБ) [2]. В сравнении с МЗС данный метод имеет в 2-4 раза большее быстродействие для гладких, чувствительных к параболической аппроксимации (ПА) функций, однако уступает ему по этому показателю при минимизации малочувствительных к ПА функций, применение МП к которым не дает ожидаемого эффекта. В статье предложен и рассмотрен метод параболического предиктора (МПП), который учитывает чувствительность функций к ПА. В отличие от МБ, по найденной при помощи МП точке сначала строится прогноз, затем на его основе вырабатывается тактика оптимизации, состоящая, в частности, в избирательном обращении к МП для малочувствительных к ПА функций, что способствует повышению быстродействия метода. Описание метода Предлагаемый метод предназначен для нахождения абсциссы минимума унимодальной функции f(x) на отрезке G = [a, b] с точностью до ε. К числу входных относятся также параметры l и m. Первый из них накладывает ограничение на количество обращений к МП, при помощи второго контролируется скорость сходимости МП к результату. Существуют различные определения унимодальной функции, поэтому следует уточнить, что МПП применим к задаче для функции f(x), определенной на отрезке [a, b], если существуют числа α и β, а ≤ α ≤ β ≤ b, такие, что: - если а < α, то на отрезке [а, α] функция f(x) монотонно убывает; - если β < b, то на отрезке [β, b] функция f(x) монотонно возрастает; - на отрезке [а, β] функция f(x) функция постоянна и достигает своего минимума. В процессе выполнения МПП используется две его фазы - МЗС и МП. На первом шаге МПП на фазе МЗС вычисляются точки p и q золотого сечения: где и определяется новая точка p или q, а старая точка сохраняется в переменной w. Далее вычисляется значение функции параболического предиктора (ФПП). Для этого по точкам p, q, w с помощью известных формул [1] строится парабола c2x2 + c1x + c0 и определяется абсцисса v ее экстремума. Затем вычисляется значение целочисленной функции ФПП по формуле где d - малое число. На рис. 1 приведена блок-схема алгоритма вычисления функции g(v). На фазе МЗС использование функции g позволяет выработать тактику поиска, получив прогноз о необходимости проведения исследования МФ на монотонность, либо следует и дальше продолжать поиск при помощи МЗС или необходимо совершить переход к фазе МП. Наиболее просто идентифицируется прогноз монотонности МФ для g = 3, который, очевидно, указывает на прямую функцию. Количество вычислений МФ для такой задачи k = 3. Данный вывод позволяет сформулировать более общее утверждение: если три последовательных вычисления МФ по МЗС дают точки с одинаковыми ординатами, то абсцисса любой из них является решением задачи. Рис. 1. Блок-схема вычисления ФПП Блок-схема укрупненного головного алгоритма МПП показана на рис. 2. Рис. 2. Блок-схема головного алгоритма МПП При 1 £ g £ 2 абсцисса экстремума параболы находится за пределами интервала неопределенности, в крайнем случае на одной из его границ. Для таких случаев предиктор предсказывает, что, возможно, минимизации подвергнута отличная от прямой монотонная МФ. Проверка достоверности граничного прогноза производится один раз. Она заключается в вычислении МФ в абсциссе d внутренней точки интервала G, отстоящей на расстоянии ε от прогнозируемой границы и в граничной точке. Если при g = 1 числа f(a), f(d), f(px), f(qx) образуют неубывающую последовательность, то прогноз монотонности МФ достоверен для x = a, аналогично при g = 2 невозрастающая последовательность f(b), f(d), f(qx), f(px) указывает на x = b. Если граничный прогноз достоверен, то задача решена. В том случае, когда прогноз монотонности МФ не подтверждается, при g ¹ 0 МПП совершает новый шаг фазы МЗС без выработки параболического прогноза. Если g = 0, что указывает на благоприятный прогноз обнаружения внутреннего экстремума МФ, то совершается переход к фазе МП. На ней сначала вычисляется ордината v0,y точки, абсцисса v0,x которой найдена на последнем шаге фазы МЗС, затем по точкам p, q, v0 строится парабола, определяется новая точка v1 экстремума параболы и вычисляется значение функции g. Далее строится новый прогноз для проведения цикла фазы МП. Если g ¹ 0, то фаза МП прерывается и совершается переход к выполнению новой фазы МЗС. При g = 0 на первых итерациях фазы МП прогноз для ее продолжения считается благоприятным. При этом на последующих итерациях производится контроль скорости сходимости фазы МП, определяемый величиной nj = sign(vj,x - vj+1,x), где j - номер итерации фазы МП. Если на текущей итерации выполнится условие êS nj ê> m, то МП признается односторонним (монотонным) и, предположительно, медленным. В таких случаях дальнейшие вычисления ведутся только с помощью МЗС. Выполнение фаз МП даже при благоприятном прогнозе может быть признано нецелесообразным и по другой причине. Если окажется, что количество обращений к МП i > l, то признается, что задача слабо чувствительна либо нечувствительна к параболическому прогнозу. В этом случае финальные вычисления ведутся только с помощью МЗС. Вычислительный эксперимент и обсуждение его результатов Для оценки работоспособности и эффективности метода был проведен сравнительный вычислительный эксперимент на примерах минимизации унимодальных функций пяти типов: 1) параболических и функций близкой к ним кривизны; 2) гладких; 3) пологих, плоских (медленно меняющихся); 4) кусочных; 5) монотонных. Данный спектр охватывает основные типы минимизируемых функций. Примеры задач для таких функций приведены в табл. 1. Таблица 1 Примеры задач № задачи Минимизируемая функция Интервал G График МФ 1 [-0,6; 1,5] 2 [1,2; 4,0] Окончание табл. 1 № задачи Минимизируемая функция Интервал G График МФ 3 [-1,3; 1,0] 4 [-1,3; 0,5] 5 [0,2; 0,8] В качестве контрольных методов использовались МЗС и МБ. Расчетная процедура для МБ получена переводом лицензионного алгоритма Брента [3] с языка Fortran 90 на язык Delphi. Для приведенных в табл. 1 задач вычисления проводились для ε = 10-5 и d = 10-32 при помощи числового типа, поддерживающего 19-20 значащих цифр. За критерии оценки быстродействия методов приняты: количество k вычислений МФ по МЗС, k1 - по МПП, k2 - по МБ. Изучались величины k/k1 и k/k2 - приведенное к МЗС быстродействие МПП и МБ соответственно и их отношение k2/k1. Результаты эксперимента для данных задач приведены в табл. 2. Таблица 2 Результаты эксперимента № задачи k k1 k2 k/k1 k/k2 k2/k1 1 26 5 6 5,20 4,33 1,20 2 26 8 9 3,25 2,89 1,13 3 26 14 43 1,86 0,60 3,07 4 26 38 62 0,68 0,42 1,63 5 26 5 23 5,20 1,13 4,60 Эксперимент показал, что для гладких функций, экстремум которых находится в отрезке G (за исключением нечувствительной к МП функции), сходимость к результату достигалась за один цикл фазы МП. И, напротив, при многократном обращении к этому циклу для малочувствительных к ПА функций метод не давал желаемого эффекта, и завершать его выполнение приходилось при помощи МЗС, что значительно замедляло быстродействие поиска. Установлено, что с целью повышения быстродействия МПП следует исключить многократное обращение к МП, ограничившись значением l = 3 даже для тех случаев, когда прогноз вновь окажется благоприятным для перехода к фазе МП (g = 0). Вероятно, МБ выполняет данную процедуру. Лишь этим можно объяснить его низкое быстродействие при минимизации функций, для которых ПА малоэффективна (табл. 2, задача 4). По-видимому, фаза МП выполняется МБ и при медленной сходимости МП-компоненты метода к решению. Обычно это имеет место при минимизации пологих, плоских функций (задача 3). Основная причина значительного замедления такого процесса состоит в том, что он становится односторонним (монотонным). В этом случае в определенный момент его следует прервать и финальные вычисления проводить при помощи фазы МЗС. Эксперименты над десятками подобных задач показали, что такие процессы предпочтительно ограничивать количеством односторонних итераций m = 5. Из приведенных в табл. 2 данных следует, что для функций близкой к параболе кривизны и гладких функций (задачи 1 и 2) МПП и МБ дают примерно одинаковое быстродействие, которое в 3-5 раз превышают аналогичный показатель МЗС. Для функций, которые на отрезке G слабо поддаются ПА (задачи 3-5), МБ теряет свои качества и по эффективности уступает даже МЗС. На это указывают значения критерия k2/k для задач 3 и 4. В сравнении с МЗС эффективность МБ для них примерно вдвое ниже. При этом МПП по вышеприведенной причине показывает превосходящую по отношению к МЗС эффективность, которая в 1,5 и более раз выше в сравнении с МБ. Прогностический метод весьма эффективен при поиске минимума монотонных функций, для идентификации которого требуется не более k = 5 вычислений МФ. В сравнении с МБ и МЗС применение МПП к монотонным функциям ускоряет поиск в 1,5-5 раз. Цена риска обнаружения недостоверного граничного прогноза при проверке МФ на монотонность составляет два ее вычисления. Проверку можно отключить, если наперед известно, что МФ является экстремальной. При этом если она окажется монотонной, то экстремум будет найден МПП при помощи одной фазы МЗС. В наглядной форме преимущества МПП перед МБ представлены на диаграмме (рис. 3). Рис. 3. Диаграмма сравнительного быстродействия МПП (k/k1) и МБ (k/k2) для задач 1-5 (табл. 1) Упомянутые оценки пригодны для методов, скорость машинной реализации которых определяется временем вычисления значения функции. Не меньший интерес представляют и оценки, которые касаются быстро вычисляемых функций, поскольку прочий процедурный механизм методов в данных случаях может отразиться на времени работы алгоритма, реализующего метод для функций таких типов. Это обстоятельство в полной мере относится к МПП, т. к. МЗС прост и время его работы определяется временем вычисления МФ, тогда как МПП помимо этого требует расчета параметров параболы, а также выбора тактики расчетов. С целью получения оценок времени минимизации таких функций проводился дополнительный вычислительный эксперимент, при котором для каждой функции расчеты выполнялись многократно. При этом замерялось не только общее количество обращений к функции, но и время расчетов. В табл. 3 приведены результаты расчетов для задач табл. 1, каждая из которых последовательно обрабатывалась на обычном офисном ПК 500 000 раз, после чего производился замер суммарного времени минимизации, где t соответствует МЗС, t1 - МПП, t2 - МБ (для сравнения в таблицу добавлены данные по количеству вычислений МФ из табл. 2). Таблица 3 Данные эксперимента по расчету затрат времени № задачи t, с t1, с t2, с t / t1 t / t2 t2 / t1 k2/k1 1 22,8 5,0 5,9 4,57 3,89 1,17 1,20 2 22,8 7,6 8,3 3,00 2,77 1,08 1,13 3 22,8 13,3 39,4 1,72 0,58 2,96 3,07 4 22,8 34,2 52,0 0,67 0,44 1,52 1,63 5 22,8 4,7 19,8 4,91 1,15 4,25 4,60 Из данных табл. 3 следует, что не связанные с определением значений МФ вычисления по МПП слабо сказываются на общих затратах времени вычислений и, следовательно, быстродействие метода можно по-прежнему оценивать по количеству обращений к МФ. Заключение Таким образом, предложенный метод параболического предиктора для условной минимизации унимодальной функции в сравнении с методом золотого сечения имеет в 3-5 раз большее быстродействие для гладких функций и сопоставим по этому критерию с методом Брента. Наибольшее быстродействие предиктор обеспечивает при минимизации монотонных функций. Метод работает несколько медленнее метода золотого сечения, однако существенно быстрее метода Брента при поиске экстремума кусочных, пологих, плоских и других функций подобного характера, для которых аппроксимация параболой не дает ожидаемого эффекта. В сравнении с методом Брента параболический предиктор имеет в 1,5-4 раза большее быстродействие при решении задач данного типа.
1. Федоров В. В. Численные методы максимина. М.: Наука, 1979. 272 с.
2. Brent R. P. Algorithms for Minimization without Derivatives. Chapter 4: An Algorithm with Guaranteed Convergence for Finding a Zero of a Function. Englewood Cliffs, NJ: Prentice-Hall, 1973. 43 p.
3. Brent R. P. Algorithms for Minimization Without Derivatives. Dover, 2002. 195 p.
