Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 64
Текст из файла (страница 64)
Тогда 1пп (У(и») — У(и»+,)) = 0 и из (12) будем оометь 1пп У'(и») = О. »-г »,- Наконец, пусть множество М,(и,) ограничено. Суммируя неравенства (13) по и от 0 до т — 1, получим о| — 1 У (ит) ~ (Х (и,) + Х 6» (~ Х (ио) + 6, по = 1, 2, ..., т. е. (и,)шМ,(и,). По теореме Больцано — Вейерштрасса ограниченная последовательность (и„) имеет хотя бы одну предельную точку. Пусть ио — произвольная предельная точка (и,1 и [и„! -~ ио. Пользуясь непрерывностью з'(и), отсюда имеем 266 мктоды мннимизлции Фтнкцни многих пкгвменных игл, з 1(ш Х' (иь ) = Х' (иа) = О, т.
е. ивен Я . Так как расстояние р (и, Я. ) непрерывно (см. лемму 2А.2), то Иш р(и„, Я ) = р(и, Я ) = О. ~э-ко Отсюда следует, что числовая последовательность (р (ию Я )) имеет единственную предельную точку, равную нулю, т. е. Ишр(ию Яэ) = О. Теорема 1 доказана. Теорема 2. Пусть выполнены все условия теоремы 1 и, кроме того, гдункция Х(и) выпукла на Е". Тогда для последовательности (иЭ, определяемой условиями (3), (6), имеют место соотношения (11).
Если, кроме того, в (6) (бз) = 0()г '), то справедлива оценка 0<Х(ид) — Х, (сг)с ~, се =совзС)0. (14) Доказательство. Из ограниченности ЛХ,(и,), непрерывности Х(и) согласно теореме 2.1.2 имеем Х„) — со, 0э чь И, 0в с= Лтг(иг). Тогда для любой точки и„ен Уэ с помощью неравенства (4.2.4) получаем О(Х(иь) — Х =Х(иь) — Х(и )((Х'(иь),иь — и )( (~Х'(ид)! )иь — иэ~(д)Х'(иь)~, к=0,1, ..., (15) где д)61аш Мв(иг) = зпр ~и — о~ — дкаметр множества чг ямг(ыг] ЛХ,(и,). В теореме 1 было доказано, что Иш Х'(и„) = О.
Отсюда и из (15) следует, что Иш Х(ид) = Х, . Учитывая включение (иь) ш ь-+со шМг(и,), тогда с помощью теоремы 2.1.2 получаем второе из равенств (11). Докажем оценку (14). Обозначим аь = Х(и„) — Ха. Из неравенств (12), (15) имеем аь — аз+, = Х(иь) — Х(иь+д)'= (1!(2Ь))Х Х1Х'(иь)~~ — бь))аь/(2ЬсР) — дь. По условию бь=0(й '), т. е. О~д„~с,7г-' (Й=1, 2, ..., с,=солзЪ>0). Полагая А = шах (с,; 2ЬУ), получим а + (аь — аь(А+ Ай гг )г = 1,2, ° ° ° Отсюда и из леммы 2.3.5 при Хг=(1, 2... ), Х,=в следует оценка (14).
Если 6„= 0 (к = О, 1, ...), то оценка (14) вытекает из неравенств (12), (15) и леммы 2.3.4. Теорема 2 доказана. Теорема 3. Пусть Х(и)ш С' '(Е"), Х(и) сильно выпукла на Е". Тогда для последовательности (и„>, получаемой иэ (3), (6) при любом начальном приближении и„справедливы соотношения (11). Если при этом 6„=0(7г '), то имеет место оценка (14). Если 6„=0 (7г=О, 1, ...), то верна более сильная, чем (14), оценка 0<Х(и„) — Х <(Х(и ) — Х ) дь,. (16) ~ иь — ив ~з~~(2/)ь) (Х(иг) — Х„) дь, )г = О, 1, „„(17) 267 ГРАДИЕНТНЫЙ МЕТОД $ О еде и — точка лсинииума У(и) на Е", о = 1 — )дИ, 0 < д < 1, 1д— постоянная из теорелды 4.3.3.
Д о к а з а т е л ь с т в о. Согласно теореме 4.3.1 множество М,(и,) ограничено, Хд) — оо, Уз состоит из единственной точки из. Поэтому равенства (11) и оценка (14) следуют из теорем 1, 2. Докажем оценки (15), (16). Из (4.3.7) при и=ад, и = из имеем а =,7(и,) — У(и„) ((Г (и„), ид — из) — х(ид — иа ('»( ((у' (ид) ) ° (ид — и ( — х (ид — из )~( ( зпр (!,Т' (ид) (г — хг') = ( Г (ид) /д((4х), ало т. е.
ад — у(ид) у(и )().)" (ид))'~(4х), й = О, '1,... (18) Подставив неравенство (18) в правую часть (12) при 6,=0, получим 4х 2н ад — ад+д ) 2ь ад = ь ад й = 0 1. " В з 4.3 было установлено, что 2х= р<Е. Поэтому 0< д = 1 — (р/Х)< 1, и предыдущее неравенство можно переписать в виде 0<а„т,<а„(1 — р/Е)=да,. Отсюда имеем ад<да,,»< < д'ад, «... о'а„что равносильно оценке (16). Наконец, из неравенства (4.3.2) следует х(ид — и ('(У(ид) — Х(и„,) =ад, й = 0,1, ...
Отсюда и из (16) получим оценку (17). Теорема 3 доказана. Метод скорейшего спуска имеет простой геометрический смысл: оказывается, точка и„„„определяемая условиями (3), (4), лежит на луче Е,=(и: и = и„— аУ'(и„), а~ 0) в точке его касания линии уровня (прп и ~ 3 — поверхности уровня) Гдз, = = (и ~ Е": Х(и) = Х(и,~,)), а сам луч Ед перпендикулярен к линии уровня Г„ = (и ~и Е": 1(и) = У(и,)) — см. рис. 5 1 п 5 2. В самом деле, пусть и = и(г), а < г < Ь вЂ” некоторое параметрическое уравнение линии уровня Г„т. е.
1(и(г))=Х(и,)= сопзг, а < с< < Ь, причем и (Ц = и,, Тогда — „, У (и (г)) = (,у' (и (г)), й (г) > = О, а < д < Ь. В частности, при д = гд имеем (У'(и,), й (й) ) = О. Это означает, что градиент (пли антиградиент) л'(ид) перпендпкулярен к касательному направлению поверхности уровня Г, в точке и„ или, плаче говоря, луч Ед перпендикулярен к Г,. Далее, из условия (4) при сц ) 0 получаем Д,(ид) = — <У' (ид — адУ' (ид)), У'(ид)) = — (У'(ид+,), У'(ид)) = О.Но вектор У'(и,~,) перпендикулярен к Г,з, в точке и,~„поэтому последнее равенство означает, что направление л'(и,) и, следовательно, луч Лд явля1отся касательными к линии уровня Г,+, в точке и„+о 268 МНГОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ [ГЛ, Ь 3.
Иа рис. 5Л и 5,2 можно понять, что чем ближе линии уровня 1(и) соле« к окружности, тем лучше сходится метод скорейшего спуска. Это же явление можно усмотреть и из оценок (тб), (т7) — чем ближе рУА к единице (для функции У(и) 1и(«, у которой линиями уровня являются окружности (сферы), как раз имеем [[/Ь 1), тем ближе д к нулю и тем лучше сходимость. Те же рис.
5Л и 5.2 показывают, а теоретические исследования и численные зксперименты подтверждают, что метод скорейшего спуска и другие варианты градиентного метода медленно Рис. 5Л Рис. 5.2 сходятся в тех случаях, когда поверхности уровня функции 1(и) сильно вытянуты и функция имеет так называемый «овражный» характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений фупкции— зта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно (на рис. 5.2 и 5.3 изображены Рис.
5.3 линии уровня «овражной» функции двух переменных) . Если точка лежит на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», и в результате приближения (и„), получаемые градиентным методом, будут поочередно находиться то на одном, то на дру- ГРАДИЕНТНЫЙ МЕТОД 269 гом «склоне оврага». Если «склоны оврага» достаточно круты, то такие скачки «со склона на склон» точек и, могут сильно замедлить сходимость градиентного метода.
Для ускорения сходимости этого метода прп поиске минимума «овражной» функции можно предложить следующий эвристический прием, называемый овражным методом. Сначала опишем простейший вариант этого метода. В начале поиска задаются две точки Ре но из котоРых пРоизвоДЯт спУск с помоЩью какого- либо варианта градиентного метода, и получают две точки и„ и, на «дне оврага». Затем полагают и, = и, — (и, — и,) [и, — и,[ 'Ь з1яп(у(и,) — у(и,) ), где я — положительная постоянная, называемая овражным шагом.
Из точки Р,, которая, вообще говоря, находится на «склоне оврага», производят спуск с помощью градиентного метода и определяют следующую точку и, на «дне оврага». Если уже известны точки и,, и„..., и„(й > 2), то из точки и+,=и,— (и,— и,,)[и,— и,,[ Ьз1дп[Х(и„) — У(и„,)) (19) совершают спуск с помощью градиентного метода и находят следующую точку и„+, на «дне оврага» (см.
рис. 5.3; спуск из точки и, в точку и„, состоящий, быть может, из нескольких итерационных шагов градиентного метода, условно изображен отрезком прямой, соединяющей точки Р„, и„й = О, 1, ...). Величина овражного шага й подбирается эмпирически с учетом информации о минимизируемой функции, получаемой в ходе поиска минимума. От правильного выбора й существенно зависит скорость сходимости метода. Если шаг Ь велик, то на крутых поворотах «оврага» точки Р» могут слишком удаляться от «дна оврага» и спуск из точки Р«в точку и, может потребовать большого объема вычислений. Кроме того, при больших й на крутых поворотах может произойти выброс точки о„иа «оврага», и правильное направление поиска точки минимума будет потеряно.
Если шаг Ь слишком мал, то поиск может очень замедлиться и эффект от применения овражного метода может стать незначительным. Эффективность овражного метода может существенно возрасти, если величину овражного шага выбирать переменной, реагирующей на повороты «оврага» с тем,чтобы: 1) по возможности быстрее проходить прямолинейные участки на «дне оврага» за счет увеличения овражного шага; 2) на крутых поворотах «оврага» избежать выброса из «оврага» за счет уменьшения овражного шага; 3) добиться по воаможности меньшего отклонения точек в» от «дна оврага» и тем самым сократить объем вычислений, требуемый для градиентного спуска из точки Р„ в точку и„ (й О, 1, ...).
Интуитивно ясно, что для правильной реакции на поворот «оврага» надо учитывать «кривизну дна оврага», причем 270 методы минимизАции Функций многих пегеменных ггл. » информацию о «кривизне» желательно получить, опираясь на результаты предыдущих итераций овражного метода. В работе [276) предлагается следующий способ выбора овражного шага: Ьд+г — Ь».сею~» «»-г Ь вЂ” 2 3 (20) где а„— угол между векторами и„— и„„и,— и„„определяемый условием сов а» = <Р, — и, „и„— и„,>1Є— и,,)-'(и„— и»,)-', Рвс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
