Сибирский федеральный университет

Перевод названия: OPTIMIZATION OF UNIMODAL FUNCTIONS USING PARABOLIC PREDICTOR search

Тип публикации: статья из журнала

Год издания: 2018

Идентификатор DOI: 10.24143/2072-9502-2018-3-101-108

Ключевые слова: пологая функция, метод парабол, быстродействие метода, sloping function, Parabola method, speed of method, parabolic predictor, unimodal function, Smooth function, Piecewise function, flat function, function minimization, Golden section search, Brent method, параболический предиктор, унимодальная функция, гладкая функция, кусочная функция, плоская функция, минимизация функции, метод золотого сечения, метод Брента

Аннотация: Предложен комбинированный метод параболического предиктора для условной минимизации унимодальной функции, использующий основанное на прогнозе избирательное использование фаз поиска экстремума методом золотого сечения и методом парабол. Дана формула вычисления значения функции параболического предиктора, при помощи которой вырабатывается прогноз и тактика поиска экстремума минимизируемой функции. Предиктор включает прогнозирование экстремальности, монотонности и постоянства функции на отрезке неопределенности. Описан идентифицирующий прогноз для прямой функции, использование которого позволяет найти решение за три ее вычисления. Сформулировано утверждение о том, что если три последовательных вычисления функции дают точки с одинаковыми ординатами, то абсцисса любой из них является решением задачи. Описана процедура идентификации отличных от прямой монотонных функций. Показано, что достоверность прогноза монотонности может быть установлена за пять вычислений функции. Описана процедура использования фаз метода парабол, которые могут быть выполнены при благоприятном прогнозе обнаружения внутреннего экстремума функции. Установлено, что выполнение этих фаз даже при благоприятном прогнозе может быть признано нецелесообразным для случаев, когда признается, что задача слабо чувствительна либо нечувствительна к параболическому прогнозу. Приведены блок-схемы алгоритмов, реализующих метод. Показано, что в сравнении с методом золотого сечения предиктор имеет в 3-5 раз большее быстродействие для гладких функций и сопоставим по этому критерию с методом Брента. Наибольшее быстродействие предиктор обеспечивает при минимизации монотонных функций. Метод работает несколько медленнее метода золотого сечения, однако существенно быстрее метода Брента при поиске минимума кусочных, пологих, плоских и других функций подобного характера, для которых аппроксимация параболой не дает ожидаемого эффекта. В сравнении с методом Брента параболический предиктор имеет в 1,5-4 раза большее быстродействие при решении задач данного типа. 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.

Журнал: Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика

Выпуск журнала: № 3

Номера страниц: 101-108

ISSN журнала: 20729502

Место издания: Астрахань

Издатель: федеральное государственное бюджетное образовательное учреждение высшего образования "Астраханский государственный технический университет"

• Коднянко Владимир Александрович (Сибирский федеральный университет)

• РИНЦ (eLIBRARY.RU)
• Список ВАК