OPTIMIZATION OF UNIMODAL FUNCTIONS USING PARABOLIC PREDICTOR SEARCH
Journal: VESTNIK OF ASTRAKHAN STATE TECHNICAL UNIVERSITY. SERIES: MANAGEMENT, COMPUTER SCIENCE AND INFORMATICS
№ 3
, 2018
Rubrics: MATHEMATICAL MODELING
Authors:
1.
Siberian Federal University
Type:
Article
Pages:
from 101
to 108
Status:
Published
Received:
05.07.2018
Accepted:
25.07.2018
Published:
25.07.2018
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 519.67
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 519.67
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
parabolic predictor, unimodal function, smooth function, piecewise function, sloping function, flat function, function minimization, golden section search, parabola method, Brent method, speed of method
Abstract (English):
A combined parabolic predictor search is proposed for the conditional minimization of the unimodal function using the predictive-based selective application of phases of extremum search by golden section search and parabolic search. The formula for calculating the value of parabolic predictor function is given, with its help it is possible to work out the forecast and tactics of extremum search of the minimized function. Predictor includes forecasting extremeness, monotony and constancy of function on a segment of uncertainty. Identification forecast for a direct function is described, using which allows to find a solution in three calculations. The assertion is made that if three successive computations of a function give points with similar ordinates, then abscissa of each point can be a solution of the problem. The procedure of identifying non-direct monotonic functions is described. It is shown that the reliability of monotonicity forecast can be determined by five calculations of the function. There has been described the procedure of using phases of parabolic method, which can be performed at favorable prediction of detecting the internal extremum of function. It has been stated that carrying out these phases, even with favorable forecast, can be considered inexpedient for cases when it is recognized that the problem is weakly sensitive or insensitive to the parabolic forecast. Block diagrams of algorithms implementing the method are given. It is shown that, compared to golden section search, the predictor has 3-5 times faster response for smooth functions and is comparable by this criterion to Brent method. The predictor achieves the greatest speed when minimizing monotonic functions. The method works somewhat slower than golden section search, however, it is much faster than Brent method when searching for the minimum of piecewise, flat, planar and other functions of a similar nature for which approximation of parabola does not give the expected effect. In comparison with Brent method, parabolic predictor has 1.5-4 times more speed in solving problems of such type.
A combined parabolic predictor search is proposed for the conditional minimization of the unimodal function using the predictive-based selective application of phases of extremum search by golden section search and parabolic search. The formula for calculating the value of parabolic predictor function is given, with its help it is possible to work out the forecast and tactics of extremum search of the minimized function. Predictor includes forecasting extremeness, monotony and constancy of function on a segment of uncertainty. Identification forecast for a direct function is described, using which allows to find a solution in three calculations. The assertion is made that if three successive computations of a function give points with similar ordinates, then abscissa of each point can be a solution of the problem. The procedure of identifying non-direct monotonic functions is described. It is shown that the reliability of monotonicity forecast can be determined by five calculations of the function. There has been described the procedure of using phases of parabolic method, which can be performed at favorable prediction of detecting the internal extremum of function. It has been stated that carrying out these phases, even with favorable forecast, can be considered inexpedient for cases when it is recognized that the problem is weakly sensitive or insensitive to the parabolic forecast. Block diagrams of algorithms implementing the method are given. It is shown that, compared to golden section search, the predictor has 3-5 times faster response for smooth functions and is comparable by this criterion to Brent method. The predictor achieves the greatest speed when minimizing monotonic functions. The method works somewhat slower than golden section search, however, it is much faster than Brent method when searching for the minimum of piecewise, flat, planar and other functions of a similar nature for which approximation of parabola does not give the expected effect. In comparison with Brent method, parabolic predictor has 1.5-4 times more speed in solving problems of such type.
Keywords:
parabolic predictor, unimodal function, smooth function, piecewise function, sloping function, flat function, function minimization, golden section search, parabola method, Brent method, speed of method
parabolic predictor, unimodal function, smooth function, piecewise function, sloping function, flat function, function minimization, golden section search, parabola method, Brent method, speed of method
Введение Среди численных методов условной минимизации унимодальных функций наибольшее использование находят метод золотого сечения (МЗС) и метод парабол (МП) [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. Fedorov V. V. Chislennye metody maksimina. M.: Nauka, 1979. 272 s.
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.
