Численные методы отыскания безусловного экстремума в одномерном случае

Лекция 3 Тема 2.1. Численные методы отыскания безусловного экстремума в одномерном случае 2.1.1. Введение В некоторых случаях ограничения в задаче оптимизации позволяют через один из параметров оптимизации выразить остальные и исключить их из целевой функции. В результате задача будет сведена к поиску наибольшего или наименьшего (в зависимости от цели оптимизации) значения скалярной действительной функции f(x)), х D(f) R, выражающей критерий оптимальности. Выбирая тот или иной знак перед этой функцией, всегда можно ограничиться лишь поиском ее наименьшего значения в области определения D(f), заданной с учетом ограничений на параметр оптимизации х. Поэтому далее в этой главе будем рассматривать задачу f(x) —> min, х D(f) R, (2.1.1) поиска наименьшего значения f* = f(х*) функции f(x) и точки х* D(f), в которой f(x) принимает это значение. Для краткости будем говорить об одномерной минимизации, имея в виду нахождение наименьшего значения функции f(x) на множестве D(f) и точек, в которых это значение достигается. Изучение методов одномерной минимизации важно не только для решения задачи (2.1.1), имеющей самостоятельное значение. Эти методы являются также существенной составной частью методов многомерной минимизации, при помощи которых находят наименьшее значение действительных функций многих переменных. Пусть область определения D(f) функции f(x) есть промежуток числовой прямой. Известно, что если D(f) — отрезок и f{x) непрерывна на нем, то она имеет на этом отрезке наименьшее значение. Но при наличии на отрезке точек разрыва функции она может не иметь на нем наименьшего значения. Оно может не существовать и в том случае, когда D(f) является интервалом или полуинтервалом. Если функция f(x) не имеет на множестве D(f) наименьшего значения, то (2.1.1) следует заменить формулировкой задачи в виде (см. 1.5) f(x) —> inf, х D(f) R. (2.1.2) Тогда под решением задачи минимизации такой функции на D(f) следует понимать построение последовательности {хп} точек из D(f), для которой существует предел f(xn) = = , (2.1.3) и нахождение этого предела. Если функция f(x) достигает на множестве D(f) своего наименьшего значения f*, то = f* . Например, функция f(x) = 1/х на множестве D(f) = [1, 2) не достигает наименьшего значения, хотя и ограничена снизу. Точная нижняя грань функции в данном случае 1 равна 1/2. В качестве последовательности {хn} точек в полуинтервале [1, 2), для которой справедливо (2.1.3), можно выбрать {2 — 1/n}. Тогда f(xn) = = = , и последовательность {f(xn)} сходится к числу 1/2 = . Функция может достигать наименьшего значения как в единственной точке, так и на некотором множестве точек, конечном, счетном или несчетном. Например, функция f(x) = х4 определена на всей числовой прямой и достигает своего наименьшего значения f* = 0 в единственной точке х* = 0, которая является ее точкой минимума. Функция f(x) = =x4 — 2х2 + 2 также определена на всей числовой прямой и достигает наименьшего значения f* = 1 в точках х* = ±1. Функция f(x) = cos x достигает наименьшего значения на счетном множестве D* = {х R: х = π + 2πk, k Z}, а функция f(x) = |х + 1| + |х — 1| — на несчетном множестве D* = [— 1, 1]. Функцию f(x) называют унимодальной ( одновершинной ) функцией на отрезке [а,b], если существует такая точка х* [а, b], что функция f(x) в полуинтервале [а, х*) убывает, а в полуинтервале (х*,b] возрастает. Примеры графиков унимодальных функций приведены на рис. 2.1.1 Рис. 2.1.1 Точка х* может быть внутренней точкой отрезка [а, b] (т.е.а < х* < b, см. рис. 2.1.1, а-г) или совпадать с одним из его концов (х* = а или х* = b, см. рис. 2.1, ∂-е). Унимодальная функция не обязательно непрерывна на отрезке [а, b] (см. рис. 2.1, в, г). Функцию f(x), достигающую на отрезке [а, b] наименьшего значения в единственной точке х* [а, b], убывающую при x [а, х*] и возрастающую при х [х*, b], будем называть строго унимодальной на отрезке [а, b] (на рис. 2.1.1 строго унимодальными являются все функции, кроме функции на рис. 2.1.1, г). Область определения D(f) минимизируемой функции f(x) может состоять из нескольких промежутков, не имеющих общих граничных точек. В этом случае, чтобы найти наименьшее значение функции на множестве D(f), достаточно определить 2 наименьшее значение функции в каждом из промежутков, составляющих D(f), а затем, сравнивая, выбрать среди этих значений минимальное. Если функция дифференцируема в промежутке, то возможно использование необходимого и достаточного условий локального минимума. Однако в прикладных задачах нередки ситуации, когда трудно вычислить производные функции (например, если функция не задана в аналитическом виде). Более того, не исключено, что значения функции известны или могут быть вычислены только в отдельных точках. В таких ситуациях использование необходимого и достаточного условий локального минимума невозможно и следует применять другие методы решения задачи оптимизации. Методы минимизации функции одного переменного, в которых используют значения функции в точках рассматриваемого промежутка и не используют значения ее производных, называют методами прямого поиска. 2.1.2. Пассивный и последовательный поиск Пусть требуется найти наименьшее значение или точную нижнюю грань f* скалярной действительной функции f(x) одного переменного на отрезке [а,b]. Предположим, что задан алгоритм вычисления значения функции для любой точки х [а, b]. Можно выделить две группы методов прямого поиска, соответствующие двум принципиально различным ситуациям: 1) все N точек xk., k = , в которых будут вычислены значения функции, выбирают заранее (до вычисления функции в этих точках); 2) точки xk. выбирают последовательно (для выбора последующей точки используют значения функции, вычисленные в предыдущих точках). В первом случае поиск значения f* называют пассивным, а во втором — последовательным. Естественно ожидать, что последовательный поиск лучше пассивного. В этом можно убедиться, вспомнив детскую игру, в которой надо найти спрятанную вещь, задавая вопросы и получая на них ответы „да" или „нет". Задавая вопросы последовательно с учетом предыдущих ответов, можно найти спрятанную вещь за меньшее число вопросов (итераций), чем, задав определенное количество заранее подготовленных вопросов сразу. Так как в прикладных задачах вычисление каждого значения функции может быть достаточно трудоемким, то целесообразно выбрать такую стратегию поиска, чтобы значение f* с заданной точностью было найдено наиболее экономным путем. Будем считать, что стратегия поиска определена, если: - определен алгоритм выбора точек xk., k = ; - определено условие прекращения поиска, т.е. условие, при выполнении которого значение f* считают найденным с заданной точностью. Для методов пассивного поиска алгоритм выбора точек xk., k = , — это правило, по которому заранее определяют все N точек xk., k = , в которых затем будут вычислены значения функции f(x). Для методов последовательного поиска алгоритм выбора точек xk. — это правило, по которому последовательно определяют каждую 3 следующую точку xk. по информации о расположении точек xi., i = и о вычисленных значениях f(xi) функции f(x) в этих точках. Выбор очередной точки xk. и вычисление значения f(xk) называют шагом последовательного поиска. В методах последовательного поиска количество точек xk обычно не задают заранее. Однако объективное сравнение различных методов прямого поиска нужно проводить при одинаковом количестве n вычисленных значений функции f(x). После n вычислений обычно указывают интервал (или отрезок) длины ln, называемый интервалом неопределенности, в котором гарантированно находится точка х*, соответствующая значению f*. Условие прекращения вычислений в случае пассивного или последовательного поиска примем одинаковым — выполнение неравенства ln ≤ ε*, где ε* — заданная наибольшая допустимая длина интервала неопределенности. Длина ln зависит как от самого метода прямого поиска Р, так и от минимизируемой функции f(x), т.е. ln = ln (Р, f). Зависимость ln от n дает оценку скорости сходимости конкретного метода прямого поиска Р к искомому значению f* заданной функции f(x). Различные методы из некоторого множества P методов прямого поиска сравнивают обычно при выбранном фиксированном значении n = N на некотором достаточно широком классе функций. В качестве такого класса можно выбрать множество F унимодальных функций, определенных на фиксированном отрезке X R. Для метода прямого поиска Р P примем наихудшую оценку Если “наихудшей" унимодальной функции не найдется, то оценку принимаем в виде Значение lN (Р) представляет собой оценку сверху погрешности вычисления точки х* X, соответствующей искомому значению f* произвольной функции f F, которая получена методом прямого поиска Р P по N вычисленным значениям этой функции. Метод прямого поиска Р* считаем наилучшим, если Этот критерий сравнения методов поиска определяет минимаксный метод поиска. Такой метод является наилучшим для всего множества F унимодальных функций на отрезке X R том смысле, что он дает наименьшую погрешность вычисления точки х*, соответствующей значению f* любой из рассматриваемых функций f F. Хотя вполне возможно, что существует некоторый конкретный метод, который для определенной специально подобранной унимодальной функции из множества F обеспечит еще меньшую погрешность. Все методы прямого поиска можно строить и сравнивать между собой на отрезке X = [0, 1]. Полученные результаты при необходимости нетрудно перенести на случай 4 произвольного отрезка [а, b], так как любую точку отрезка [0, 1] можно перевести в соответствующую ей точку отрезка [а, b] растяжением в b-а раз и сдвигом на а. Если минимизируемая функция f(x) не является унимодальной на отрезке [а, b] (такую функцию называют мультимодальной функцией на этом отрезке), то, даже если она непрерывна на [а, b], при поиске наименьшего значения f* функции на отрезке может возникнуть ошибка: будет найдена точка локального минимума, в которой значение функции не f*, а другое, большее. Чтобы избежать такой ошибки, в процесс минимизации включают предварительный этап, на котором отрезок минимизации разделяют на несколько отрезков, на каждом из которых минимизируемая функция унимодальна. Сравнительный анализ наименьших значений функции на этих отрезках позволяет найти искомое наименьшее значение f* на всем отрезке минимизации. Пример 2.1.1. Рассмотрим один из возможных подходов к выделению из промежутка X в области определения D(f) минимизируемой функции f(x) отрезка [а, b], на котором эта функция является унимодальной. Пусть известна такая точка х0 X , что при х ≥ х0 функция f(x) сначала убывает, а затем начиная с пока неизвестного значения х = х* X возрастает, хотя далее в промежутке X могут быть расположены и другие участки немонотонного поведения этой функции. Выберем начальное значение h > 0 приращения аргумента х функции f(x), в несколько раз меньшее предполагаемого расстояния между точками х0 и х*, и вычислим значения f(xo) и f(x1), где х1 = x0 + h. Может оказаться, что f(x0) ≤ f(x1),. Тогда за искомый отрезок [а, b] можно сразу принять отрезок [х0, х1 ]. Но можно продолжить вычисления и, используя последовательный поиск, определять значения f(xk)в точках xk = х0 + 2k-l, k = 2, 3 ..., до тех пор, пока не будет выполнено неравенство f(xk) < f(х0). Тогда следует принять [а, b] = [х0, хk-1] (на рис- 2.1.2 [а, b] = [х0, х2], поскольку точка x* должна быть либо на отрезке [х0, х3], либо на отрезке [х3, х2]). Надо сказать, что при этом можно “не заметить" по крайней мере еще один отрезок, на котором функция унимодальна (штриховая линия на рис. 2.1.2). Рис. 2.1.2 Рис. 2.1.3 Если f(х0) > f(х1), то, используя последовательный поиск, вычисляем значения f(x'k), где x'k = x0 + (k - l)/h, k = 2, 3 ...,пока не будет выполнено неравенство f(x'k-1) ≤ f(x'k), что позволяет принять [а, b] = [x'k-2, x'k] (на рис. 2.1.3 [а, b] = [x'2, x'4], так как точка х* должна быть либо на отрезке [x'2, x'3], либо на [x'3, x'4] ). 5 Отметим, что описанный подход не гарантирует нахождения отрезка унимодальности функции. Например, на рис. 2.1.3 штриховой линией показан график функции, для которой этот подход не позволяет обнаружить искомый отрезок. 6