Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 82
Текст из файла (страница 82)
-+ О при й — е . Теорема доказана. Заметим, что хотя метод (2) — (7) для своей реализации не требует знания градиента минимизируемой функции, однако в условии теоремы 1 содержится требование гладкости этой функ- ции. Оказывается, если функция Х(и) не является гладкой, то МЕТОД ПОКООРДННАТНОГО СПУСКА а 111 345 метод покоординатного спуска может не сходиться ко множеству решений задачи (1). Об этом говорит следующий Пример 1. Пусть 1(и)=х'+ у' — 2(х — у)+2(х — у~, и=(х, у)«вЕ'. Нетрудно проверить, что 1(и) сильно выпукла на Е' и, следовательно, ограничена снизу и достигает своей нижней грани на Е* в единственной точке. Возьмем в качестве начального приближения точку и,=(0, 0).
Тогда имеем 1(и«+ссе«)= =1(ссе,)=а" — 2сс+2!и!>0=1(0), 1(и,+ие,)=1(ае )=се'— в 2а+ 2!и! > 0=1(0) при всех действительных а. Отсюда следует, что все итерации метода (2) — (7) при начальной точке и« =(О, 0) и любом выборе начального параметра а =и«>0 будут неудачными, т. е. и,= и, при всех й = О, 1, ... Однако в точке и, = (О, 0) функция 1(и) не достигает сноси нижней грани яа Е'. например, в точке о = (1, 1) имеем 1(о)= — 2 < <1(и,)= О. 2.
Описанный выше метод покоординатного спуска нетрудно модифицировать применительно к задаче минимизации функции на параллелепипеде: 1(и)» 1п1; и «н П = ((и', ..., и ): а < и < Ьь 1 = 1, ..., п), (9) где аь Ь« — заданные числа, а«<Ь«(1=1, ..., и). А именно, пусть й-е приближение и„«н П и число а,> 0 при некотором й>0 уже найдены. Выберем вектор рь=е« согласно формуле (2), составим точку и„+ се,р, и проверим условия и, + и«р«ж П, 1(ив+ а«р«) < 1(и«). (10) Если оба условия (10) выполняются, то следующее приближение иь+ь а,+, определяем по формулам (4). Воли же хотя бы одно условие (10) не выполняется, то составляем точку и,— — а„р„и проверяем условия и,— а,р,~П, 1(и,— и,р,)<1(и,). (11) В случае выполнения обоих условий (11) следующее приближение определяем по формулам (6), а если хотя бы одно из условий (11) не выполняется, то следующее приближение находится из неравенств (7). Теорема 2.
Пусть функция 1(и) выпукла на П и 1(и)~ «-=С'(П). Тогда при любом выборе начальных и,«в П и сь«>0 последовательность (и„), получаемая методом (10), (4), (11), (6), (7), минимизирует функцию 1(и) на П и сходится ко множеству решений задачи (9). Доказательство. Так как П вЂ” параллелепипед, то множество 1я(и,)=(и: и«н П, 1(и)<1(и,)) ограничено. Так как 1(и„„,) <1(и,) (й = О, 1,;,.), то (и,) «н П и существует 346 МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ ~ГЛ.
Ь 1нп Х(ид))Хе. Так же, как в теореме 1, доказывается сущед-~ ствование бесконечного числа номеров й,<...<й (... итераций, на которых длина шага а, дробится, и поэтому 11ш ад = О. д ю В силу ограниченности М(и,) из (ид ( можно выбрать сходящуюся подпоследовательность. Не умаляя общности, можем д и1 считать, что(ид )-д.и„= (и„...,и,). При каждом 1=1, ..., и возможны следующие три случая. 1) ад(и,(ЬО Так как 1пп ад= О, то найдется номер йг такой, что ид + ад„,е;ЯП и ид — с'д еден П при всех т >1г'. Поскольку ад при й = й„дробится, то Х(ид + ад е;))Х(ид ), Х(ид — ад е;))Х(ид ) для всех т > Х Отсюда, как и в теореме 1, получаем Х„;(ид1 =- = О, так что Х„~ (и„) (и — и' ) = О, а; ( и' ( Ьи 2) и' = аь Тогда и, + ад е~яЪХ и Х(ид + ад е;))Х(ид ) при всех т>Х Следовательно, (Х'(ид + О ад е;)ад >О или Х„д(ид + О,ад е,)))0 для каждого т)дг. Отсюда при т-д-со получим Х„д(ид) 0 или Х„;(и )(и — а;) = Х;(и )(и' — и',)) >О (ад~( и (Ьд).
3) и'„= Ь;. Тогда ид — ад едя сг и Х(ид — ад ед)= Х(ид ) при всех т) Х. Поэтому (Х (ид — О ад е;), е;) ( — ад ))О или Х„д(ид,„— О, ад еа1~<0 (т>Л"). Отсюда при т-1- оо получим Х„д(и„)( О, следовательно, Х д(ид) (и' — Ь;) = Х„;(и ) (и' — и~ ) ) О, ад ( и' ( Ьд. Объединяя все три рассмотренных случая, заключаем, что Х,д(ие) (и' — и'„)) О, ад е-. ид(ЪЕ 1 = 1,..., и. Суммирун эти неравенства по всем 1 = 1, ..., и, получим (Х'(и. ),и — и ) )0 для всех и ~ (Х.
Согласно теореме 4.2.3 тогда и ~ (Хе. Следовательно,11шХ(ид) = д ю = 1пп Х (ид ) = Х(иа) = Х, т. е. (ид) — минимизирующая послетл-~ довательность. Отсюда и из теоремы 2 1.2 следует, что 1пп р(ию (Х ) = О. Теорема 2 доказана. 3. Существуют и другие варианты метода покоординатного спуска. Можно, например, строить последовательность (и„) по $12) МЕТОД ПОИСКА ГЛОВАЛЬНОГО МИНИМУМА 347 правилу (12) из+~ = ид + ссдрд, где р„ определяется согласно (2), а ад — условиями ад)0, уд(сед) = пап ~д(а), )д(а) = Х(ид+ ссра).
(13) - с<сс<+ Метод (12), (13) имеет смысл применять в том случае, когда величина ад иа (13) находится в явном виде. Так будет, если функция з(и) — квадратичная, т. е. л' (и) = — (Аи, и) — (Ь, и), и ~ Е", (14) где А — симметричная положительно определенная матрица Ь~ ~Е". Нетрудно убедиться, что для функции (14) метод (12), (13) приводит к хорошо известному методу Зейделн из линейной алгебры [4]. Хотя и скорость сходимости метода покоординатного спуска, вообще говоря, невысокая, благодаря простоте каждой итерации, скромным требованиям к гладкости минимизируемой функции этот метод довольно широко применяется на практике.
Существуют н другие методы минимизации, использующие лишь значения функции и не требующие для своей реализации вычисления производных. Например, используя вместо производных их разностные аппроксимации, можно построить модификации рассматривавшихся в предыдущих параграфах методов, требующие вычисления лишь значений функции в подходящим Образом выбранных точках (ср. с $9, 10).
Другой подход для минимизации негладких функций, основанный лишь на вычислении значений функции, дает метод случайного поиска, который будет рассмотрен ниже в 4 17. Метод поиска глобального минимума, излагаемый в следующем параграфе, такнсе относится к методам, не требующим вычисления производных минимизируемой функции. Унражн ения. 1. Нарисуйтелинии уровня У(а) =С =сопз1 функции из примера 1 и поясните причину расходимости метода покоординатного спуска для этой функции при выборе ис = (О, 0). 2. Опишите метод покоординатного спуска и докажите его сходимость для случая, когда в задаче (9) ас = — се или Ьс = со для каких-либо 4 д 1<с, ]<п. 3.
Докажите сходимость метода (12), (13) для функции (14) [4]. 5 12. Метод поиска глобального минимума 1. Заметим, что если задача минимизации г(и)- (п1; и ш су является мнозозкстремальной — так называются задачи, в которых имеется хотя бы одна точка локального минимума, отличная от точки глобального минимума, то с помощью описанных 343 методы минимизАции ФункциЙ мноГих пеРеменных игл. э выше методов удается найти, вообще говоря, лишь приближение к какой-либо точке локального минимума. Поэтому упомянутые методы часто называют локальными методами. Для ре1пения многоэкстремальной задачи (1) локальные методы обычно используются по следующей схеме: на множестве. 11 задают некоторую сетку точек и, выбирая в качестве начальных приближений точки этой сетки, с помощью того или иного локального метода находят локальные минимумы функции, а затем, сравнивая полученные результаты, определяют ее глобальный минимум.
Однако ясно, что такой подход к решению много- экстремальных задач весьма трудоемок и не всегда приводит к цели. Поэтому представляют большой интерес методы поиска глобального минимума в многоэкстремальных задачах. Если относительно свойств функции Х(и) ничего неизвестно„ то вряд ли можно предложить какой-либо подход к решению задачи (1), кроме вычисления значений функции Х(и) во всех точках и 1я (7. Понятно, что такой подход практически нереализуем.
И как показывает наш предыдущий опыт, для построения эффективных численных методов решения задачи (1) на функцию, а также на множество приходится накладывать те или иные ограничения. Ниже будут изложены методы поиска глобального минимума в задаче (1) для случая, когда множество 7Х является параллелепипедом, т. е. (7=(и=(и1, и', ..., и"): а1(и1~Ь1, 1=1, ..., и), (2) аь Ь,— заданные числа, а1(Ь, (1=1, ..., и), а функция Х(и) удовлетворяет условию Липшица )Х(и) — Х(и))(Х!и — о/ зи,ге=11', 1 =сонэ()0. (3) Эти методы являются обобщением методов покрытий, рассмотренных в 3 1.7 для минимизации функции одной переменной на отрезке.
Как и в 3 1.7, через (1(Е) обозначим класс функций, удовлетворяющих условию (3) с одной и той же для всех функций этого класса константой Х > О. Пусть р — какой-либо метод, представляющий собой правило выбора т точен и„..., и из 17, в которых вычисляются значения функции Х(и,), ..., Х(и ) и затем определяется величина ппп Х(и1), принимаемая за приближенное значение 1<1~п~ Х~ = ш(Х(и). Зададимся вопросом: как выбрать число т и метод и р = (и„..., и ) так, чтобы ппп Х(и;) <Х + е 'з'Х(и)ее()(Х), (4) 1~1~п где е ) 0 — заданная точность? Поставленную задачу будем кратно называть задачей (1) — (4).
МЕТОД ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА 349 2 121 2. Можно предложить следующее правило выбора точек и„..., и„: пусть эти точки из ХУ таковы, что объединение шаров Я(и», В)=(ишВ": !и — и»((Л), 1=1, ..., и, с центрами в точках и» и радиуса В= с/Х покрывает множество »»» УУ, т. е.
(УС: (У Я(и»,В) Оказывается, при таком выборе то»=1 чек и„..., и, приняв величину ш»п Х(и») за приближение к 1~»<»» Х,„, мы решим задачу (1) — (4). В самом деле, возьмем любую точку ишХУ. Так как шары Я(и», В) (1=1, ..., т), покрывают множество ХУ, то точка и принадлежит одному из шаров Я(и», В), т. е. ~и — и»! ~ В = ЕУХ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
