Метод локализации точки экстремума унимодальной функции

Рассмотрена комбинация численных методов типа Regula falsi и секущих для прямого поиска экстремума унимодальной функции общего вида на заданном отрезке. Предложенная комбинация не требует какого-либо предварительного анализа характера функции для начала поиска ее экстремума. Реализуется своеобразный...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2016
Hauptverfasser:	Шелудько, Г.А., Угримов, С.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інстиут проблем машинобудування ім. А.М. Підгорного НАН України 2016
Schriftenreihe:	Проблемы машиностроения
Schlagworte:	Прикладная математика
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/99260
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Метод локализации точки экстремума унимодальной функции / Г.А. Шелудько, С.В. Угримов // Проблемы машиностроения. — 2016. — Т. 19, № 1. — С. 44-53. — Бібліогр.: 18 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-99260
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-992602025-02-09T10:09:42Z Метод локализации точки экстремума унимодальной функции The localization method of extremum point for unimodal function Шелудько, Г.А. Угримов, С.В. Прикладная математика Рассмотрена комбинация численных методов типа Regula falsi и секущих для прямого поиска экстремума унимодальной функции общего вида на заданном отрезке. Предложенная комбинация не требует какого-либо предварительного анализа характера функции для начала поиска ее экстремума. Реализуется своеобразный метод с минимальной глубиной памяти в направлении поиска. Он является универсальным и независимым от класса минимизируемой функции. Принятый апостериорный подход позволяет отыскивать экстремум недифференцируемых, в том числе алгоритмически заданных функций. Метод отличается большой общностью. Он обеспечивает гарантированную сходимость к экстремальной точке благодаря использованию средневзвешенного способа реализации решения. Если даже минимизируемая функция на заданном отрезке оказывается не унимодальной, то всегда предлагаемый метод осуществляет получение хотя бы относительного минимума. Изложенная методика может быть легко распространена на многомерный случай.Проведен массовый вычислительный эксперимент на гладких и негладких функциях. Рассмотрено применение предложенного метода к выпукло-вогнутым с разрывом первого рода функциям, к разнонаклоненным функциям, а также эмпирически заданным функциям сложной геометрии. Показано, что индекс эффективности комбинации методов превышает таковой у отдельно взятых методов с теми же начальными условиями. Розглянуті триточкові методи пошуку екстремуму кусково-негладкої функції. Особлива увага приділяється застосуванню методів розв'язання задач з поганою обумовленістю, що викликана різнонахильністю функції, яка мінімізується. Завдяки комбінації лінійних методів Regula falsi та пересічних хорд вдалося помітно підвищити ефективність пошукового засобу. На тестових прикладах продемонстровано ефект запропонованого підходу. The combination of numerical methods such as Regula falsi method and secant method for direct search of extremum of unimodal function on the given interval is considered. The proposed combination does not require any prior analysis of character of the functions to begin its search for an extremum. The unique method with a minimum of memory depth in the search area is implemented. It is universal and independent of the class of minimized function. Accepted a posteriori approach allows to find the extremum of non-differentiable functions, including algorithmically defined functions. The method is quite general. It provides a guaranteed convergence to the extreme point due to the use ща the weighted average method for realizing solutions. If the minimized function in a given interval is not unimodal, the suggested method is always provides obtaining at least a relative minimum. The stated method can be easily extended to the multidimensional case. The massive computational experiments on smooth and non-smooth functions are carried out. The application of the proposed method to the convex-concave functions with a first-order gap, to functions with a asymmetrical character in vicinity of solution, as well as empirically given functions of complex geometry. It is shown that the efficiency index of combination methods exceeds index of the individual methods with the same initial conditions. 2016 Article Метод локализации точки экстремума унимодальной функции / Г.А. Шелудько, С.В. Угримов // Проблемы машиностроения. — 2016. — Т. 19, № 1. — С. 44-53. — Бібліогр.: 18 назв. — рос. 0131-2928 https://nasplib.isofts.kiev.ua/handle/123456789/99260 519.853.3 ru Проблемы машиностроения application/pdf Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Прикладная математика Прикладная математика
spellingShingle	Прикладная математика Прикладная математика Шелудько, Г.А. Угримов, С.В. Метод локализации точки экстремума унимодальной функции Проблемы машиностроения
description	Рассмотрена комбинация численных методов типа Regula falsi и секущих для прямого поиска экстремума унимодальной функции общего вида на заданном отрезке. Предложенная комбинация не требует какого-либо предварительного анализа характера функции для начала поиска ее экстремума. Реализуется своеобразный метод с минимальной глубиной памяти в направлении поиска. Он является универсальным и независимым от класса минимизируемой функции. Принятый апостериорный подход позволяет отыскивать экстремум недифференцируемых, в том числе алгоритмически заданных функций. Метод отличается большой общностью. Он обеспечивает гарантированную сходимость к экстремальной точке благодаря использованию средневзвешенного способа реализации решения. Если даже минимизируемая функция на заданном отрезке оказывается не унимодальной, то всегда предлагаемый метод осуществляет получение хотя бы относительного минимума. Изложенная методика может быть легко распространена на многомерный случай.Проведен массовый вычислительный эксперимент на гладких и негладких функциях. Рассмотрено применение предложенного метода к выпукло-вогнутым с разрывом первого рода функциям, к разнонаклоненным функциям, а также эмпирически заданным функциям сложной геометрии. Показано, что индекс эффективности комбинации методов превышает таковой у отдельно взятых методов с теми же начальными условиями.
format	Article
author	Шелудько, Г.А. Угримов, С.В.
author_facet	Шелудько, Г.А. Угримов, С.В.
author_sort	Шелудько, Г.А.
title	Метод локализации точки экстремума унимодальной функции
title_short	Метод локализации точки экстремума унимодальной функции
title_full	Метод локализации точки экстремума унимодальной функции
title_fullStr	Метод локализации точки экстремума унимодальной функции
title_full_unstemmed	Метод локализации точки экстремума унимодальной функции
title_sort	метод локализации точки экстремума унимодальной функции
publisher	Інстиут проблем машинобудування ім. А.М. Підгорного НАН України
publishDate	2016
topic_facet	Прикладная математика
url	https://nasplib.isofts.kiev.ua/handle/123456789/99260
citation_txt	Метод локализации точки экстремума унимодальной функции / Г.А. Шелудько, С.В. Угримов // Проблемы машиностроения. — 2016. — Т. 19, № 1. — С. 44-53. — Бібліогр.: 18 назв. — рос.
series	Проблемы машиностроения
work_keys_str_mv	AT šeludʹkoga metodlokalizaciitočkiékstremumaunimodalʹnojfunkcii AT ugrimovsv metodlokalizaciitočkiékstremumaunimodalʹnojfunkcii AT šeludʹkoga thelocalizationmethodofextremumpointforunimodalfunction AT ugrimovsv thelocalizationmethodofextremumpointforunimodalfunction
first_indexed	2025-11-25T18:08:06Z
last_indexed	2025-11-25T18:08:06Z
_version_	1849786721660567552
fulltext	ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 44 Г. А. Шелудько, С. В. Угримов, канд. техн. наук Институт проблем машиностроения им. А. Н. Подгорного НАН Украины, г. Харьков, e-mail: sugrimov@ipmach.kharkov.ua УДК 519.853.3 МЕТОД ЛОКАЛИЗАЦИИ ТОЧКИ ЭКСТРЕМУМА УНИМОДАЛЬНОЙ ФУНКЦИИ Розглянуті триточкові методи пошуку екстремуму кусково- негладкої функції. Особлива увага приділяється застосуванню методів розв'язання задач з поганою обумовленістю, що ви- кликана різнонахильністю функції, яка мінімізується. Завдяки комбінації лінійних методів Regula falsi та пересічних хорд вдалося помітно підвищити ефективність пошукового засобу. На тестових прикладах продемонстровано ефект запропоно- ваного підходу. Ключові слова: екстремум, унімодальна фу- нкція, одновимірний пошук, кусково-лінійні наближення, середньозважені операції, хара- ктеристичні числа, індекс ефективності. Введение В условиях все более возрастающих массовых трудоемких расчетов различных процессов и объектов предъявляются повышенные требования к вычислительным средствам вообще и к состав- ляющим их элементам в частности. Успех решения сложной задачи минимизации во многом зависит от уровня качества (скорости и точности) решения ее подзадач, по возможности меньшей размерно- сти. Стремление к определенному улучшению методов экстремальных задач породило огромное ко- личество всевозможных подходов, что естественно вызвало затруднение при выборе нужного метода и привело в значительной степени к усложнению постановок и их реализации [1–3]. Поэтому наибольшее распространение в вычислительной практике приобретает получение простейших приемов, обладающих относительно хорошей эффективностью при необходимой точно- сти результата. Многие задачи легко сводятся к отысканию наименьшего или наибольшего значений функ- ции, однако методы решения данных задач существенно зависят от свойств самой функции. В связи с этим стали обращать внимание на создание методов без привлечения производных [3–5], а также на приемы использования апостериорной информации, возникающей в ходе самого процесса поиска решения. Это способствует сведению до минимума требований к характерным свойствам исследуе- мой функции. Обычно задача оптимизации заключается в отыскании точки )(extrarg ],[ * XfX BAX  . (1) Рассматриваемая здесь одномерная минимизация почти всегда выступает обязательным эле- ментом во многих известных методах многомерной минимизации [1, 2]. Хотя на первый взгляд зада- ча одномерной минимизации – самая простая, однако ясно, что не всегда исследуемая функция f(X) дифференцируема на заданном отрезке [A, B], чтобы, приравняв нулю ее производную, получить не- обходимое условие для отыскания точки минимума. Поэтому в тех случаях, когда функция f(X) не является дифференцируемой, все равно возникает необходимость искать прямые способы поиска ми- нимума такой функции. К настоящему времени уже известно достаточно большое количество методов, решающих за- дачу (1), но при этом требования к функции весьма разнообразны. Неудачный выбор метода, т.е. ка- ким из них следует воспользоваться при решении конкретной задачи с заданными свойствами функ- ции f(X) на [A, B], как правило, влечет за собой заметное снижение эффективности решения. Поводом для написания данной статьи явились результаты работы Е. А. Воронцовой [6], в ко- торой скорость сходимости процесса поиска точки экстремума доведена почти до уровня квадратиче- ской прямым методом, т. е. свободным от знания точных производных. Действительно, предложен- ный алгоритм достаточно хорошо начинает себя вести в весьма малой окрестности решения, когда  Г. А. Шелудько, С. В. Угримов, 2016 ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 45 линейная аппроксимация оправдана. Но в качестве объекта минимизации были в основном выбраны почему-то только функции с минимумом в точке со скачком производной. Здесь рассматривается один из приемов решения задач оптимизации унимодальной функции (рис. 1), не требующий дополнительной информации об ее внутренней структуре. Следовательно, могут быть задействованы не только негладкие, но даже алгоритмически заданные функции. Алго- ритм решения позволяет находить различные характерные точки в заданной области, имеются в виду корни нелинейных уравнений, точки экстремума функции, точки перегиба, возврата и т. п. [7, 8]. Эта информация обычно служит для построения линий уровня, осей оврагов и других компонентов на различных этапах решения задач анализа и синтеза [9]. Здесь коснемся лишь тех методов, которые не используют напрямую производные исследуе- мой функции в заданной области. Чаще всего будем заменять производные их конечно-разностными аналогами, что позволяет расширить класс решаемых задач. Постановка задачи Рассмотрим наиболее простой одномерный случай: поиск точки X *  [A, B], доставляющей минимальное значение заданной функции f(X), определенной на сегменте [A, B], т. е. удовлетворяю- щей неравенству f(X * )  f(X) X  [A, B]. (2) Известно, что унимодальная функция f(X), определенная на [A, B], обязательно достигает сво- его наименьшего (наибольшего) значения в некоторой точке X *  [A, B]. Задачу поиска минимума f(X) будем определять как установление подсегмента [a, b]  [A, B] заданной длины  с решением (целью) X * . Несмотря на определенную простоту постановки одномерной минимизации (2) существует большое разнообразие вариантов поведения функции (перемежающиеся участки выпуклости и во- гнутости, точки перегиба, перелома и конечных разрывов), в частности, по характеру функции в окрестностях решения X * (скачки и конечные разрывы производных), а также по степени разно- наклоненности функции f(X), т.е. по значению критерия BXAX BXAX X   het (3) в окрестности решения (здесь XY = f(X) – f(Y))/(X – Y) – кусочно-линейная аппроксимация производ- ной функции f(X) в некоторой точке Z  [X, Y]). На рис. 2 изображены типичные варианты окрестностей минимума унимодальных функций, заданных на отрезках. Далее будем различать всякие точки вообще и информативные точки с вычисленным в них значением функции f(X). Рис. 1. Типичный образец унимодальной функции ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 46 Среди известных относи- тельно простых прямых методов поиска точки экстремума унимо- дальной функции f(X), определен- ной на сегменте [A, B] (рис. 3), наибольшее распространение полу- чили метод Больцано (биссекции), где для каждого такта метода при- ходится использовать две информа- тивные точки, а оптимальный ме- тод Фибоначчи и субоптимальный метод золотого сечения [1, 3] тре- буют одну информативную точку. Все они предъявляют весьма слабые требования к характеру функции f(X). Достаточно лишь иметь воз- можность вычисления значения функции в любой точке сегмента [A, B]. Нетрудно видеть, если f(X) выпукла или строго квазивыпукла (унимодальна), то, вычисляя ее в двух точках C и D сегмента [A, B], можно указать содержащие точку минимума X * подсегменты: [A, C], если f(C) > f(D), и [D, B], если f(C) < f(D). Это позволяет исключать отрезки сегмента [A, B], не содержащие решения X * . Так, в методе биссекции точка экстремума локализуется при сравнении двух значений функ- ции в точках, отстоящих от середины сегмента на 0,5 ( > 0 – параметр метода). После n итераций длина подсегмента локализации решения X * становится равной (B – A)2 –n + (1 – 2 –n ). Обычно счита- ют приближенным значением X * середину отрезка [a, b]  [A, B] длиною b – a = , содержащего ре- шение X * . Здесь  – достигнутая точность. Отметим, что задание и четырех информативных начальных точек A, C, B, D еще не может однозначно определить окрестность экстремальной точки X * при использовании того или иного дис- кретного метода локализации (рис. 3). Так, на рис. 3, в имеем одинаковую исходную информацию (A, fA), (C, fC), (B, fB), (D, fD), однако расположение минимумов X * (i) для функций f(1) и f(2) не совпадают. Все зависит от природы функции f(X). И поэтому понятно, что именно алгоритм поискового метода должен учитывать складывающуюся ситуацию и определять последовательность действий, чтобы поисковые затраты были как можно меньшими. Средства минимизации Предлагаемые здесь способы дискретной локализации экстремальных точек X * пригодны как для гладких, так и негладких функций f(X), определенных на сегменте [A, B], и, как минимум, требу- ют трихотомии, т.е. использования трех информативных точек. Однако для некоторых одинаково- Рис. 2. Варианты окрестностей минимума функций а) б) в) Рис. 3. Расположение точек X * (i) минимума для функции f(i): а), в) – с одинаковыми информативными точками; б) – на краю сегмента ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 47 наклоненных уни-модальных функций f(X) возможно применение дихотомии, т.е. достаточно двух информативных точек на одной итерации. На рис. 3 а, б представлены варианты расположения точек * )(iX минимума ряда выпуклых функций f(i) на [A, B]. Действительно, минимум X * функции f(X) может оказаться в любом из подотрезков, в кото- рых имеется самая меньшая ордината. Но в каком именно из подотрезков [A, C] или [C, B], связано уже с характером изменения функции f(X) на [A, B]. Информацию о поведении функции в точке C можно косвенно установить по знаку производной, используя какое-либо приближенное выражение ее или запоминая тенденцию при спуске на предыдущем этапе поиска. После того как удалось уста- новить, в каком из подотрезков [A, C] или [C, B] (см. рис. 3) расположено решение X * , то ко всем этим случаям применим известный простой метод Regula falsi (RF) поиска корней. Если заменить значение функции f(C) на –f(C), то можно использовать метод RF и записать BC BC AC AC ff CfBf X ff CfAf X       (4) для [A, C] или [C, B] соответственно. Вид формул (4) подсказывает, что можно также привлечь в качестве дихотомического реше- ния взвешенные средние BC BC AC AC ff CfBf X ff CfAf X       (5) соответственно для [A, C] или [C, B]. В отличие от (4) эти формулы позволяют продвигаться к реше- нию дальше от концов A и B подсегментов [A, C] или [C, B], что особенно важно при одинаково наклоненной функции f(X), в окрестности решения. Выражения (5) представляют собой взвешенные средние пар точек A, C или C, B с весами, равными значениям функции fA, fC или fC, fB. Текущая точка X, получаемая по формулам (5), всегда оказывается в области [A, B] и распола- гается ближе к образующей точке C. Однако этот положительный момент, удобный при отыскании экстремума одинаково наклоненной функции, как раз препятствует успешному поиску цели X * в случае разнонаклоненной функции, тем более что заранее может быть неизвестно, является ли данная функция таковой. И только после нескольких вычислений по фор- мулам (4) или (5), т.е. после добавочных затрат, удается устано- вить этот факт. Когда становится известным разнонаклоненность функ- ции, то можно, не вычисляя дополнительно новых значений функ- ции (рис. 4, а, б), продвигаться в окрестность решения X * , исполь- зуя способ pRF AC AC p BC BC p fpf CfpAf X fpf CfpBf X       (6) соответственно для [C, B] или [A, C] при p > 1. Примечательно, что точка Xp всегда принадлежит своему подсегменту при любом дей- ствительном p  [0, [. Если надлежащим образом выбирать параметр p, то можно ускорить попадание точки X в окрестность решения X * . Принцип построения выражений (6) позволяет строить другие последова- тельности неинформативных точек X1, X2, X3,..., удовлетворяющие различным иным условиям, которые просто учесть и реализовать. Для этого можно использовать новые начальные точки, лежащие на образующих прямых CB, CB и соответственно AC, CA (см. рис. 4). а) б) Рис. 4. Итерации по методу pRF ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 48 Уже, например, при p = 2 реализуется схема мето- да секущих [10], обладающего сверхлинейной скоростью схо- димости, в отличие от метода RF. Так, на рис. 5 показан фрагмент процесса pRF на под- сегменте [C, B], из которого следует, что использование да- же постоянного значения p, например p = 5, ускоряет поиск (светлые точки), против обыч- ного p = 1 (темные точки). Чем положе одна из ветвей функции f(X), тем больше необходимо привлечь информативных точек, чтобы попасть в окрестность решения. Каким бы ни был закон изменения параметра p, на самом деле важно, чтобы при нарушении условия fX > fC на [A, C]  fX > fB на [C, B] (7) p увеличивалось и, по понятным причинам, не следует опасаться, что его значение для сложившейся ситуации вдруг окажется чрезмерным. Как только при движении к цели X * по методу pRF текущее значение функции становится больше предыдущего, то значение параметра p следует уменьшать, до- водя его до p = 1. Этот прием позволяет без особых трудностей направить процесс поиска в противо- положном направлении до точки, в которой функция увеличится в сравнении с предыдущим значе- нием. Такой затухающий колебательный процесс приводит к цели X * тем быстрее, чем лучше органи- зовано управление параметром p. Если же поставить имеющийся неуправляемый выбор параметра p в зависимость от получаемых результатов, то можно еще больше ускорить продвижение к цели. Вспомним хорошо известный способ комбинирования методов Дэвиса, Свенна, Кемпи [11], где спуск производился с нарастающим шагом до тех пор, пока не локализовалась окрестность с це- лью X * . Далее использовался метод Пауэлла [12], производящего квадратичную интерполяцию до не- обходимой точности. Подобную идею самоуправления можно применить и к изменению параметра p. Приведенные способы RF и pRF достаточно хорошо проявляют себя в случае небольших ве- личин конечной точности , а для более точного определения минимизирующей точки X * целесооб- разно применять методы, учитывающие наклоны функции f(X) по обе стороны от решения. Добавление четвертой информативной точки D (рис. 6) в поиске X * при соответствующем ис- пользовании возникшей ситуации должно поднять эффективность процесса. Действительно, привле- чение кусочно-линейных приближений AС и DB (3) приводит к методу пересекающихся хорд (ПХ), который при малых подотрезках [A, C] и [B, D] может способствовать заметному продвижению к це- ли X * . При попадании текущей точки X в довольно малую окрестность точки X * , когда линейная ап- проксимация функции f(X) становится достаточной, использование метода ПХ наиболее целесооб- разно. Для случая (см. рис. 6, б) запишем приближение к X * )( )( 1 Cf Bf X B C      . (8) Здесь использованы характеристические числа BD BD AC AC ff DfBf ff CfAf       , , (9) Рис. 5. Возможное ускорение поиска по методу pRF ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 49 которые являются результатом действия метода секущих [10], проявляющего сверхлинейную ско- рость сходимости, особенно когда точки C и B достаточно близки к цели X * . Если же воспользоваться хордами AB и CD (см. рис. 6), можно получить другой вариант метода ПХ, поменяв характеристи- ческие числа (9) на выражения ., CD CD AB AB ff DfCf ff BfAf       Однако когда присутствует разнонаклоненность (см. рис. 6, а или в), применение (8) напря- мую уже не оправдано. Исправить возникшее положение в этом случае, в особенности если разно- наклоненность значительна и когда точки C, X (рис. 6, а) и X, B (рис. 6, в) оказываются весьма близ- кими друг к другу, можно, вернувшись к трехточечному варианту (6) с информативными тройками A, C, X или X, B, D (см. рис. 6). При этом желательно постепенно увеличивать значение параметра p с учетом текущей точности . Но заранее неизвестно, как назначать начальное значение параметра p в (6). Известно только, что оно будет отличаться для каждой функции f(X) и для каждой новой ситуации. Понятно, что его значение должно увеличиваться (см. рис. 6, а и в) по мере приближения текущей точки X к окрестно- сти решения X * . Хотя значения p могут принимать любые действительные числа из сегмента [0, [, однако не стоит нарушать ограничения    1)(21)(2 1111   CBffpACffp kCBkCA соответственно для [A, C] или [B, D] (k – точность, принятая на k -м этапе минимизации). Так или иначе локализация окрестности решения X * основана на сходящейся последователь- ности вложенных отрезков (например, справа) [A1, C1, B1]  [A2, C2, B2]  [A3, C3, B3]  … и порождает соответствующую ей убывающую последовательность значений функций f(C1) ≥ f(C2) ≥ f(C3) ≥ … . Удобно продвижение текущей точки Ci ускорить, поменяв в формуле (6) значение fC на фик- сированное значение 1Cf . В результате устраняется неопределенность в выборе параметра p. При этом спуск завершается до получения точки Ci, когда 1  ii CC ff , т. е. до нарушения условия (7). Затем информативная точка Ci может быть включена в четверку точек для продолжения поиска по методу ПХ. Обнаружение разнонаклоненности, а важнее ее степени (3), позволяет осознанно вводить ве- личину параметра p. Например, на начальных шагах работы метода pRF, когда могут сильно раз- ниться значения крайних ординат fA и fB, можно принимать базовую величину p, равную max(\|fA\|/\|fB\|, \|fB\|/\|fA\|), а затем, по необходимости, увеличивать p по принятому способу, до получения точки X со значением функции fX > fC. C этого момента, до перехода на метод ПХ, желательно уточ- а) б) в) Рис. 6. Случаи распределения информативных точек по методу ПХ ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 50 нять окрестность решения X * до выполнения усло- вия fA  fB, наиболее благоприятного для использо- вания формулы (8). Можно, например, ввести экспоненциаль- ную адаптацию с линейными параметрами, не тре- бующую знания производных для соответствующе- го изменения параметра p, что еще больше ускорит процесс минимизации. Возможен также прием перехода к формуле (8), когда выясняется, что окрестность решения X * , в силу разнонаклоненности f(X) находится вне рабо- чего подсегмента [A, C] или [C, B]. Для этого под- ключаем одну информативную точку слева от точки A (вариант а) или справа от точки D (вариант в) (см. рис. 6). Такими точками могут служить, напри- мер, уже известные прежние информативные точки, ближайшие к точкам A или D. Таким образом, реа- лизуется своеобразный метод с минимальной глуби- ной памяти [9] в направлении поиска. Классический вариант метода ПХ с четырьмя информативными точками (рис.6) легко пере- водится в трехточечный (см. рис. 7) с той же структурой формулы (8), если характеристическое число  (9) заменить = (CfB + BfC)/(fB + fC), когда минимум функции f(X) расположен на подсегменте [C, B], оставив  тем же. Если же минимум попадает на подсегмент [A, C], то следует принять вместо  выражение = (CfA + AfC)/(fA + fC). Но так как и здесь остается в силе прием использования параметра p, смещающего текущее решение в окрестность минимума в случае разнонаклоненной функции f(X), то подобная замена при- ближенным значением не является большой потерей. Для этого достаточно значение fC поменять на pfC, но с естественным ограничением pfC  fA, если X *  [C, B], и pfC  fB, если X *  [A, C]. Способы такой корректировки неизбежно приводят к идее поэтапного обмена методами pRF и ПХ, где признаком перехода выступает, с одной стороны, установление разнонаклоненности, а с другой – достигнутая точность на том или ином этапе поиска. Детали алгоритма В используемом здесь подходе pRF и ПХ необходимо иметь сначала не более четырех ин- формативных точек. При генерации начальной четверки точек X1, X2, X3, X4, лежащих в заданном сегменте [A, B], целесообразно принять за старт информативную точку X1 = 0,5 (A + B), т.к. к этому моменту еще нет никаких сведений о характере функции f(X), кроме ее унимодальности на сегменте [A, B]. По понятным причинам можно назначить следующей информативной точкой X2 = X1 + 0,51, где 1 – некоторое кратное от финальной точности . В зависимости от того, в какой стороне находит- ся минимум функции, третьей точкой выбираем X3 = 0,25[B + A + X2 + X1 + (B – A + X2 – X1)sgn(f1 – f2)]. По той же схеме назначаем четвертую точку X4 = 0,25{[X1 + X3 + A + (X1 + X3 – A)sgn(f3 – f1)](1 – sgn(f1 – f2)) + + [X2 + X3 + B + (X2 + X3 – B)sgn(f3 – f1)](1 + sgn(f1 – f2))}, если еще не достигнута так называемая «яма». Из четырех информативных точек X1, X2, X3, X4 выбираем три X1, X2, X3   X2, X3, X4, среди которых срединная X2  X3 всегда оказывается с меньшим значением функции, если, конечно, мини- мум функции случайно не попадает на один из концов сегмента [A, B]. Поскольку одной из особенностей в принятом алгоритме является ступенчатость в дости- жении того или иного значения точности, то процесс поиска снабжен приемом, носящем название Рис. 7. Трехточечный вариант метода ПХ ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 51 «переброс». Закон изменения шага ступени k может быть выбран в каждом отдельном случае по же- ланию. В данном алгоритме принята геометрическая прогрессия со знаменателем q = 0,1. После получения очередной точки C основного процесса проверяются условия B – k < C (или A + k > C). Если они выполнены, то вычисляем в точке X = B – k (или X = A + k) функцию f(X) и пе- реходим на новую ступень точности k+1 = 0,1k с новой информативной тройкой A = B – k, C = C, B = B (или A = A, C = C, B = A + k). Естественно, такой «переброс» осуществляется само собой про- тив спада функции f(X) в соответствующем подсегменте [C, B] (или [A, C]), где присутствует реше- ние. Операция «переброс», очевидно, наиболее продуктивна к концу установления конкретной точ- ности k. Остановкой поиска служит, как уже отмечалось, достижение точности  = b – a, а решение принимается в виде X = C. Численный эксперимент Тестирование описанного подхода реализовано на представительной серии функций, заим- ствованных из известных источников [4–7, 11, 13–18], использованных непосредственно или преоб- разованных к виду ((X) = f 2 (X), (X) = \|f(X)\|), чтобы получить в решении разный характер точки экс- тремума. В частности, приведено уравнение И. Ньютона, иллюстрирующего на нем свой метод [10], и уравнение Леверье, решение которого послужило открытию планеты Нептун [13]. Выбирались функции с различным характером поведения на A, B и разным уровнем разнонаклоненности, неко- торые из них являются выпукло-вогнутыми, особенно трудными для реализации классическими средствами. Нами задавался заведомо протяженный сегмент, учитывая форму (2), чтобы подчеркнуть «чистоту» эксперимента, а также для демонстрации возможностей испытуемого метода. Непосредственное отыскание точки X * экстремума функции f(X), предполагая определенные затраты, должно опираться на некоторый критерий эффективности метода. В данном случае эффек- тивность поиска оценивалась, подобно работе 10, индексом эффективности E = N –1 ln[(B – A)/(b – a)], (10) где N – количество вычислений функции f(X) для достижения подсегмента [a, b]  A, B заданной длины , содержащего цель X * . В табл. 1 представлены решения ряда примеров комбинированным методом pRF-ПХ и уста- новлено одно и то же конечное значение  = b – a = 10 –15 . Полученная эффективность во всех случаях оказывается намного выше, чем когда решение производилось каждой частью метода pRF-ПХ в от- дельности, несмотря на выпукловогнутость функций. Функции (см. табл. 1) – гладкие, остальные в решении претерпевают скачок. Таблица 1. Характеристики решений примеров по методу pRF-ПХ Функция A, B X * E (10) (X 3 – 2X – 5) 2 10 –2; 5 2,094551481542326 1,20302 X 6 + 4,224X 5 + 6,5071X 4 + 7,5013X 3 + + 8,4691X 2 + 3,3641X + 1,6252 13 [–2,3; –1,5] –1,921227833020143 1,19579 (X 20 – 1) 2 7 0; 5 1,000000000000000 1,29031 (e sinX – 0,2X – 1) 2 14 –1; 1,3 0,000000000000000 1,31421 2 1 Xe 15 –5; 8 0,000000000000000 1,32513 (e X – X 2 + 3X – 2) 2 4 –12; 10 0,257530285439861 1,34392 arctg[(X – 3)(X 2 + 4) –1 ] [16] [–10; 6,5] –0,605551275032148 1,24470 \|exp{X 2 + 7X – 30} – 1\| 17 –5; 4 3,000000000000000 1,35059 \|2 – X 2 – cos(X – 3 –1 )\| 8 0; 3 1,145437529920276 1,27276 \|e X – 5X + 4\| 10 –20; 30 1,609437912434101 1,30588 \|10Xexp(–X 2 ) – 1\| 5 1; 5 1,679630610428450 1,40687 \|11X 11 – 1\| 18 –3; 2 0,804133097503664 1,06318 ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 52 В табл. 2 даны результаты сравнения минимизации функций f(X) = max{ 2 X 2 , e –X }, (11) заданных на сегменте –20; 30 и реализованных методом Воронцовой (МВ) работы 6, а также ме- тодом pRF-ПХ. Таблица 2. Данные сравнения решений примера (11) Точность  Количество вычислений функции N и эффективность E  = 1  = 10  = 100 МВ pRF-ПХ МВ pRF-ПХ МВ pRF-ПХ N E N E N E N E N E N E 10 –1 14 0,4439 9 0,6905 15 0,4143 11 0,3556 10 0,3912 10 0,6215 10 –2 20 0,4258 14 0,6084 15 0,5678 13 0,6552 15 0,5678 11 0,7743 10 –3 20 0,5410 16 0,6762 17 0,6364 20 0,5410 16 0,6762 18 0,5694 10 –4 20 0,6561 18 0,7210 18 0,7290 20 0,6561 17 0,7719 19 0,6906 10 –5 20 0,7712 18 0,8569 20 0,7712 22 0,7011 18 0,8569 24 0,6413 10 –6 24 0,7386 18 0.9849 26 0,6818 22 0,8052 20 0,8864 24 0,7386 10 –7 28 0,7153 20 1,0015 26 0,7704 22 0,9105 21 0,9538 24 0,8346 10 –8 38 0,5877 20 1,1664 26 0,8589 24 0,9305 23 0,9710 24 0,9305 10 –9 38 0,6483 22 1,1198 26 0,9475 25 0,9854 24 1,0265 26 0,9475 10 –10 38 0,7089 22 1,2244 26 1,0361 25 1,0775 29 0,9288 26 1,0361 10 –11 38 0,7695 22 1,3291 26 1,1246 25 1,1696 37 0,7903 28 1,0443 10 –12 38 0,8300 22 1,4338 26 1,2132 25 1,2617 41 0,7693 28 1,1265 10 –13 38 0,8906 24 1,4102 26 1,3017 25 1,3539 45 0,7521 28 1,2088 10 –14 38 0,9513 24 1,5061 26 1,3903 25 1,4459 53 0,6820 28 1,2910 10 –15 38 1,0118 24 1,5021 26 1,4789 25 1,5380 57 0,6746 28 1,3732 Как видно из таблицы, способ МВ показал хороший результат только при  = 10, в то время как методу pRF-ПХ даже с постоянным параметром p удается за счет принятой комбинации успешно находить решения при разных степенях разнонаклоненности в окрестности решения. Выводы Опыт показывает, что причиной неудачного использования известных эффективных методов является разный абсолютный наклон ветвей функции, особенно в окрестности решения. Традиционно разнонаклоненность функции преодолевается за счет повышения порядка производных, используе- мых в методах. Но эти методы, к сожалению, оказываются достаточно эффективными лишь на опре- деленных классах функций. С другой стороны, стремление переходить к прямым методам заставляет прибегать к аппроксимации производных и тем самым усложнять средства реализации поиска экс- тремума. В данной работе использование принятого апостериорного подхода и соответствующей ком- бинации всего лишь линейных методов pRF и ПХ удается успешно ускорять продвижение к цели даже при значительной степени разнонаклоненности исследуемых на экстремум функций. Метод pRF-ПХ устроен таким образом, что в начале поиска отдается предпочтение методу pRF, а затем вступает в действие метод ПХ. Это связано с тем, что на начальном этапе устанавливается степень разнонаклоненности и осуществляется вход в окрестность решения, а также создаются необходимые условия, способствующие более успешному функционированию метода ПХ, который по мере про- движения решения к финальной точке начинает приобретать свойства, приближающие его к методу касательных. Предложенный подход позволяет строить более совершенные эффективные механизмы поиска характерных точек, поскольку не налагает каких-либо специальных требований к свойствам функции, кроме унимодальности. Допускаются в конечном числе точек разрывы функции первого рода. Благодаря комбинированному подходу метод pRF-ПХ почти обладает универсальным характе- ром, т. е. может успешно обслуживать не только выпуклые или вогнутые, но и выпукло-вогнутые ПРИКЛАДНАЯ МАТЕМАТИКА ISSN 0131–2928. Пробл. машиностроения, 2016, Т. 19, № 1 53 унимодальные функции. Не требуются решения каких-либо вспомогательных задач для получения достаточно узкой окрестности экстремальной точки. Полученные результаты могут быть широко использованы для многомерной оптимизации, в частности, для функций овражного строения, в том числе для некоторых функций с разрывной про- изводной. Метод не требует какого-либо предварительного исследования минимизируемой функции по выявлению ее особенностей или по установлению окрестности притяжения к решению и позволяет находить оптимум для достаточно широкого класса функций, задаваемых иногда даже эмпирически. Литература 1. Васильев, Ф. П. Численные методы решения экстремальных задач / Ф. П. Васильев. – М.: Наука, 1980. – 520 с. 2. Аоки, М. Введение в методы оптимизации / М. Аоки. – М.: Наука, 1977. – 344 с. 3. Шор, Н. З. Методы минимизации недифференцируемых функций и их приложения / Н. З. Шор. – Киев: Наук. думка, 1979. – 200 c. 4. Yasmin, N. Some derivative free iterative methods for solving non-linear equations / N. Yasmin, M. Junjua // Aca- demic Research Intern. – 2012. – Vol. 2, № 1. – P. 75–82. 5. Soleymani, F. New derivative-free quasi-secant algorithm for solving non-linear equations / F. Soleymani // World academi Sciences, Eng. and Thehnology. – 2002. – Vol. 31. – P. 719–721. 6. Воронцова, Е. А. Быстросходящийся алгоритм линейного поиска в недифференцируемой оптимизации / Е. А. Воронцова // Моделирование систем. – 2012. – № 2 (32). – С. 39–48. 7. Трауб, Дж. Итерационные методы решения уравнений / Дж. Трауб. – М.: Мир, 1985. – 264 с. 8. Ганшин, Г. С. К теории итерационных процессов / Г. С. Ганшин // Вычисл. и прикл. математика. – Киев: Изд-во Киев. ун-та. – 1973. – № 19. – С. 143–147. 9. Мелешко, В. И. Градиентные методы оптимизации с памятью / В. И. Мелешко // Изв. АН СССР. Техн. ки- бернетика. – 1973. – Т 1, № 1. – С. 38–51. 10. Островский, А. М. Решение уравнений и систем уравнений / А. М. Островский. – М.:Изд-во иностр. лит., 1963. – 219 с. 11. Box, M. J. Non-linear optimization techniques / M. J. Box, D. Davies, W. H. Swann. – Edinburgh: Oliver&Boyd, 1969. – 60 p. 12. Powell, M. J. D. An iterative method for finding stationary values of a function of several variаbles / M. J. D. Powell // Comp. J. – 1958. – Vol. 5, № 2. – P. 147–151. 13. Мелентьев, П. В. Несколько новых методов и приемов приближенных вычислений / П. В. Мелентьев. – Л.; М.: Гл. ред. техн. теорет. Лит, 1937. – 148 с. 14. Chen, J. An exponential regula falsi method for solving nonlinear equations / J. Chen, W. Li // Numerical Algo- ritms. – 2006. – Vol. 41, № 4. – P. 327–338. 15. Soleymani, F. Computing simple roots by a sixth order iterative method / F. Soleymani // Int. J. Pure and Appl Maths. – 2011. – Vol. 69, № 1. – P. 41–48. 16. Вирченко, Н. А. Графики функций. Справочник / Н. А. Вирченко, И. И. Ляшко, К. И. Швецов. – Киев: Наук. думка, 1979. – 320 с. 17. Thukral, R. New family hinher order Steffensen-type methods for solving nonlinear equations / R. Thukral // J. Modern Methods in Numerical Maths. – 2012. – Vol. 3, № 1. – P. 1–10. 18. Soleymani, F. A new derivative-free quasi-Secant algorithm for solving non-linear equations / F. Soleymani, M. Sharifi // Intern. J. Math. Comp., Phys. Electr. and Computer Eng. – 2009. – Vol. 3, № 7. – P. 554–556. Поступила в редакцию 02.03.16

Метод локализации точки экстремума унимодальной функции

Institution

Ähnliche Einträge