XIV Аттетков и др. Методы оптимизации (Зарубин В.С., Крищенко А.П. - Комплекс учебников из 21 выпуска), страница 8

Эти методы являя>тся также существенной составной частью методов многомерной минимизации, при помощи которых находят наименьшее значение действительных функций многих переменных. Пусть область определения РЦ) функции ~(х) есть промежуток числовой прямой. Напомним [П], что если РЦ) 51 2.1. Прадааритальиые аамеяаиия отрезок и 1(х) непрерывна на нем, то она имеет на этом отрезке наименьшее зна аение. Но при наличии на отрезке точек разрыва функции она может не иметь на нем наименьшего значения. Оно может не существовать и в том случае, когда Р() ) является интервалом или полуинтервалом.

Если функция 1" (х) не имеет на множестве Р(1') наименьшего значения,то (2.1) следует заменить формулировкой задачи в виде (см. 1.5) (2.2) 1(х) — + ш1, х Е РЯ С К. Тогда под решением задачи минимизации такой функции на Р(1) следУет понимать постРоение последовательности 1ха1 точек из Л(1), для которой существует предел 12.3) 1ша 1(х„) = шГ 1(х) =1„, и ~аа х еВ(Л и нахождение этого предела. Если функция 1" (х) достигает на множестве Р(1) своего наименьшего значения 1„, то 1„= 1,. Например, функция 1(х) = 1/х на множестве Р(1) = ~1,2) не достигает наименьшего значения, хотя и ограничена снизу.

Точная нижняя грань 1'„функции в данном случае равна 1/2. В качестве последовательности 1х„1 точек в полуинтервале ~1, 2), для которой справедливо (2.3). можно выбрать 12 — 1/п1. Тогда Пх.) = — '= х„2 — 1/и 2п — 1' и последовательность (1'(ха)1 сходится к числу 1,12 = 1„. Функция может достигать наименьшего значения как в единственной точке, так и на некотором множестве точек, конечном, счетном или несчетном.

Например, функция 11х) = х~ определена на всей числовой прямой и достигает своего наименьшего значения 1, = О в единственной точке х, = О, которая является ее точкой минимума. Функция 1(х) = х4 — 2х1+2 52 2. МЕТОДБ1 ОД11ОМЕРНОЙ МИНИМИЗАЦИИ также определена на всей числовой прямой и достигает наименьшего значения 1'„= 1 в точках х, = х1. Функция 1'(х) = = совх достигает наименьшего значения на счетном множестве Р, = 1х Е 2: х = к+ 2яй, 6 Е,'Ц, а функция 1'(х) = ~х+ 1~ + + [х — 1~ на несчетном множестве Р, = [ — 1, 1]. Функцию 1 (х) называют унимодальной амуницией на отрезке [а, 6], если существует такая точках, Е [и, 6], что функция 1'[х) в полуинтервалс [а,х,) убывает, а в полуинтсрвалс (х„6] возрастает. Примеры графиков унимодальных функций приведены на рис.

2.1. Рис. 2.1 Точка х, может быть внутренней точкой отрезка [а, 6] [т.с. а ( х„( 6, см. рис. 2.1, а — г) или совпадать с одним из его концов (х„= а или х„= 6, см. рис. 2.1, д, е). Ънимодальная функция не обязательно непрерывна на отрезке [и, 6] (см. рис. 2.1, в, г). Функцию 1'(х), достигая>щую на отрезке [а, 6] наименьшего значения в единственной точке х„Е [а, 6], убывающую при х Е [а, х.] и возрастающую при х Е [х., 6], будем называть строео унимодальной на отрезке [а, 6] (на рис. 2.1 строго унимодальными являются все функции, кроме функции на рис.

2.1, г). 53 2.2. Пассивный и послсдоватсльный воисн Область определения РЦ) минимизируемой функции 1(сс) может состоять из нескольких промежутков, не имеющих общих граничных точек. В этом случае, чтобы найти наименьшее значение функции на множестве Р(1), достаточно определить наименьшее значение функции в каждом из промежутков, составляющих Р(~), а затем, сравнивая, выбрать среди этих значений минимальное. Если функция дифференцируема в промежутке, то возможно использование необходимого и достаточного условий локального минимума [П[. Однако в прикладных задачах нередки ситуации, когда трудно вычислить производные функции (например, если функция нс задана в аналитическом виде).

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

2.2. Пассивный и последовательный поиск Пусть требуется найти наименьшее значение или точную нижнюю грань 1„скалярной действительной функции )(я) одного переменного на отрезке [а,б). Предположим, что задан алгоритм вычисления значения функции для любой точки т е [а, Ь[. Можно выделить две группы исшодов прямого поиски, соответствующие двум принципиально различным ситуациям: 1) все Х точек яя, и = 1, Х., в которых будут вычислены значения функции, выбирают заранее (до вычисления функции в этих точках); 2.

МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 2) точки хь выбирают последовательно (для выбора последующей точки используют значения функции, вычисленные в предыдущих точках). В первом случае поиск значения Т", называют пассивным, а во втором — последовательным. Естественно ожидать, что последовательный поиск лучше пассивного. В этом можно убедиться, вспомнив детскую игру, в которой надо найти спрятанную вещь, задавая вопросы и получая на них ответы „да' или „нет".

Задавая вопросы последовательно с учетом предыдущих ответов, можно найти спрятанную вещь за меньшее число вопросов (итераций), чем, задав определенное количество заранее подготовленных вопросов сразу. Так как в прикладных задачах вычисление каждого значения функции может быгь достаточно трудоемким, то целесообразно выбрать такую стратегию поиска, чтобы зна >ение Т"„с заданной точностью было найдено наиболее экономным путем. Будем считать,что стратегия поиска определена, если: — определен алгоритм выбора точек хы к = 1, Х; . определено условие прекращения поиска, т.е.

условие, при выполнении которого значение 1„считают найденным с заданной точностью. Для методов пассивного поиска алгоритм выбора точек хы й = 1, Х, — — это правило, по которому заранее определяют все Х точек хы й = 1, Х, в которых затем будут вычислены значения функции Т(х). Для методов последовательного поиска алгоритм выбора точек хь —. это правило, по которому последовательно определяют каждую следующую точку хь по информации о расположении точек хь 1 = 1, я — 1, и о вычисленных значениях ~(х>) функции ~(х) в этих точках. Выбор очередной точки хя и вычисление значения ~(хь) называя>т шагом последовательного поиска.

В методах последовательного поиска количество точек хь обычно не задают заранее. Однако объективное сравнение различных методов прямого поиска нужно проводить при одинако- 55 2.2. Пассивный и последовательиый поиск вом количестве п вычисленных значений функции ~(х). После п вычислений обычно указывают интервал (или отрезок) длины 1„, называемый интервалом неопределенности, в котором гарантированно находится точка х„ соответствующая значению у,. Условие прекращения вычислений в случае пассивного или последовательного поиска примем одинаковым— выполнение неравенства 1„< е„где, — заданная наибольшая допустимая длина интервала неопределенности.

Длина 1„ зависит как от самого метода прямого поиска Р, так и от минимизируемой функции ~(х), т.е. 1„, = 1в(Р, ~). Зависимость |в от п дает оценку скорости сходимости конкретного метода прямого поиска Р к искомому значению у„заданной функции у(х). Различные методы из некоторого множества Р методов прямого поиска сравнива1от обычно при выбранном фиксированном значении п = дс на некотором достаточно широком классе функций. В качестве такого класса можно выбрать множество Р унимодальных функций, определенных на фиксированном отрезке Х С аь Для метода прямого поиска Р Е Р примем наихудшую оценку 1м(Р) = шах 4 (Р, ) ).

усе Если „наихудшей" унимодальной функции не найдется, то оценку принимаем в виде 1л (Р) = аврал (Р, у). Уел Значение 1л (Р) представляет собой оценку сверху погрешности вычисления точки х„Е Х, соответствующей искомому значению ~, произвольной функции 2 Е Р, которая получена методом прямого поиска Р Е Р по Х вычисленным значениям этой функции. Метод прямого поиска Р* считаем наилучшим, если 1л(Р*) =шшшахЬ(Р~), или 1ь(Р*) =пйпвпр1у(РД.

РеР уев 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ Этот критерий сравнения методов поиска определяет минилеаксный метод поиска. Такой метод является наилучшим для всего множества У' унимодальных функций на отрезке Х С К в том смысле., что он дает наименьшую погрешность вычисления точки х„, соответствующей значению ~, любой из рассматриваемых функций 1' Е У. Хотя вполне возможно, что существует некоторый конкретный метод, который для определенной специально подобранной унимодальной функции из множества У обеспечит еще меньшую погрешность. Псе методы прямого поиска можно строить и сравнивать между собой на отрезке Х = [0,1]. Полученные результаты при необходимости нетрудно перенести на с лучай произвольного отрезка ~а, 6], так как любую точку отрезка ~0, 1] можно перевести в соответствующую ей точку отрезка ~а, 6] растяжением в 6 — а, раз и сдвигом на а.

Если минимизируемая функция ~(х) не является унимодальной на отрезке ~а, 6] (такую функцию называют мультилеодальной функцией на этом отрезке)., то, даже если она непрерывна на ~а, 6]), при поиске наименьшего значения ~, функции на отрезке может возникнуть ошибка: будет найдена точка локального минимума, в которой значение функции не 1„а другое, большее.

т1тобы избежать такой ошибки, в процесс минимизации включают предварительный этап, на котором отрезок минимизации разделяют на несколько отрезков, на каждом из которых минимизируемая функция унимодальна*. Сравнительный анализ наименьших значений функции на этих отрезках позволяет найти искомое наименьшее значение )„на всем от- резке минимизации. Пример 2.1. Рассмотрим один из возможных подходов к выделению из промежутка Х в области определения РЦ) минимизируемой функции Дл) отрезка ~а, 6], на котором эта функция является унимодальной. Пусть известна такая точка *См.: Васильев Ф.П., а также: Лесин В.В., Лисввеи Ю.П.