Ф.П. Васильев - Методы оптимизации (1125241), страница 72
Текст из файла (страница 72)
е. х, е Я„. Так как расстояние р(х, Я.) непрерывно (см. лемму 2.1.2), то 1пп р(х„, Я„) = р(х„, Я„) =О, Отсюда следует, что числовая последовательность (р(х, Я,)) имеет единственную предельную точку, равную нулю, т. е. !!ш р(х„, Я,) = О. Теорема 1 доказана. С! Теорема 2. Пусть выполнены всг условия теоремы 1 и, кроме того, функция /(х) выпукла на Е". Тогда, для последовательности х,), определяемой условиями (3), (6), имеют место соотношения (11). сли, кроме того, в (6) (б,) = 0(й '), то справедлива оценка 0</(х,) — /,<с й ', с =сопз1>0.
(14) Д о к а з а т е л ь с т в о. Из ограниченности М (х ), непрерывности /(х), согласно теореме 2.1.2, имеем /„> — оо, Х, Ф!31, Х„С М,(х„). Тогда для любой точки х„Е Х, с помощью неравенства (4.2.4) получаем О < /(х,) — /. = /(х„) — /(х,) < (7'(х,), х„— х,) < < )/(х,)! ~х, — х„) < сЦс(х,)~, й =0,1,..., (15) где с( > д!ашМ,(х) = зпр !и — о! — диаметр множества М,(х,).
В теа юемд ~! ореме 1 было доказано, что !!ш /'(х„) = О. Отсюда и из (15) следует, что !пп /(х,) =/,. Учитывая включение (хс) е М,(х ), тогда с помощью теоремы 2.1.2 получаем второе из равенств (11). Докажем оценку (14). Обозначим а„=/(х„) — /„. Из неравенств (12), (15) имеем аь — а„, =/(х,) — /(х,ч,) > (1/(25)) !/'(хь)/~ — бь > азь/(2Ьс!з) — б„. По условию 1„= 0(й-'), т. е.
0 < б„< с,й з, й = 1, 2,..., с, = сопз1 > О, Полагая А = шах(с,; 2Х а'), получим а„ч, <а„— а~,/А+Ай з, й=1,2,... Отсюда и из леммы 2.6.5 при Ть=(1,2,...), Хс = З следует оценка (14), Если Б, =О, й = О, 1,..., то оцейка (14) вытекает из неравенств (12), (15) и леммы 2.6.4. Теорема 2 доказана, П 240 Гл. 5, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Теорема 3.
Пусть /(х)е Сь'(Л"), /(х) сильно выпукла на Е". Тогда для последовательности (х»), получаемой из (3), (б) при любом начальном приближении х„справедливы соотношения (11). Если при этом Б» = 0(й '), то имеет место оценка (14). Если 5„=0, й =О, 1,..., то верни более сильная, чем (14), оценка 0 < /(х») — /, < (/(х ) — /„)д», (16) !х, — х,!2 < (2/г»)(/(хи) — /,)д», й = О, 1,..., (17) где х„— точка минимума /(х) на Я", д =1 — р/Ь, 0 < д < 1, р — посто янная из теорем»в 4.3.3. Доказательство.
Согласно теореме 4.3.1 множество М,(х) огра ничено, /, > — оо, Х состоит из единственной точки х„. Поэтому равенст ва (11) и*оценка (!4) следуют из теорем 1, 2, Докажем оценки (16), (17) Из (4.3.9) при и = х„, и = х, имеем а„=/(х„) — /(х„) < (/'(х»), х, — х„) — х(х„— х„'Г/2 < (/'(х»)~~х — х.~— — х(х„х )»/2 < зпр ()/'(х„))г — хг»/2) — (/~(х„и'/(2х), х>О т. е. а„= /(х») — /(х„) < ~/'(х»)~'/(2х), й = О, 1,, (18) Подставив неравенство (18) в правую часть (12) при б„= О, получим 2х х а, — а„ „, > 25 а„ = 5 а„ й = О, 1,.
В $ 4.3 было установлено, что х = р < Ь. Поэтому 0 < д = 1 — (р/Ь) < < 1, и предыдущее неравенство можно переписать в виде 0 < а„, < а„(!в — р/Х )= да». Отсюда имеем а„< да», < уса», «... д»а, что равносильно оценке (16). Наконец, из неравенства (4.3.3) следует х/х» — х,/' < /(х») — /(х,) = а„, й = О, 1, Отсюда и из (16) получим оценку (17). Теорема 3 доказана. ГЗ Метод скорейшего спуска имеет простой геометрический смысл: оказывается, точка х„ о определяемая условиями (3), (4), лежит на луче Ь» = (х: х = х„ — с«/'(х»), а > О) в точке его касания поверхности уровня Г„», = (х е Е": /(х) = /(х»«,)), а сам луч Ь» перпендикулярен к поверхности уровня Г„ = (х е Е : /(х) = /(х»)) — см.
рис. 5.1 и 5.2, В самом деле, пусть х = х(1), а < г < 5 — некоторое параметрическое уравнение кривой, принадлежащей Г„, т. е. /(х(1)) =/(х») =сопз1, а <1 < 5, причем х(ги) = х„. Тогда ~-/(х(г)) = (/'(х(1)), х($)) =О, а< г < (г. В частности, при г = 1 имеем (~'(х»), х(1 )) = О. Это означает, что градиент (или антиградиент) '(х„) перпендикулярен к касательному направлению поверхности уровня „ в точке х, или, иначе говоря, луч Ь» перпендикулярен к Г,. Далее, из условия ('1) при а„> 0 получаем д„'(а„) = — (/'(х» — а»/'(х )), /'(х )) = = — (/'(х»,), /'(х )) =О.
Но вектор /'(х»,) перпендикулярен к Г„, в точке х,» и поэтому последнее равенство означает, что направление /'(х„) и, следовательно, луч Х,„являются касательными к поверхности уровня Г„, в точке х„ $ Е ГРАДИЕНТНЫЙ МЕТОД 241 3. Из рис. 5.1 и 5.2 можно понять, что чем ближе поверхность уровня /(х) = сопз1 к сфере, тем лучше сходится метод скорейшего спуска. Это же явление можно усмотреть и из оценок (16), (17) — чем ближе г»/Ь к единице (для функции /(х) = ~х~', у которой поверхностями уровни являются сферы, как раз имеем р/Ь =1), тем ближе д к нулю и тем лучше 1.' сходимость. ':::Г'' Те же рис.
5.1 и 5.2 показывают, а теоретические исследования и численные эксперименты подтверждают, что метод скорейшего спуска я другие хо ! - -« 'и» :.1," ',« в Рис. 5.2 Рис. 5Л варианты градиентного метода медленно сходятся в тех случаях, когда поверхности уровня функции /(х) сильно вытянуты и функция имеет так называемый «овражный> характер. Это означает, что небольшое изменение некоторых переменных приводит к резкому изменению значений функции — эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дна оврага», функция меняется незначительно (на рис.
5.2 и 5.3 изображены линии уровня «овражной» Рис. 5.3 функции двух переменных), Если точка лежит на «склоне оврага», то направление спуска из этой точки будет почти перпендикулярным к направлению «дна оврага», и в результате приближения (х„), получаемые градиентным методом, будут поочередно находиться то на одном, то на другом «склоне оврага». Если «склоны оврага» достаточно круты, то такие скачки «со склона на склон» точек х„могут сильно замедлить сходимость градиентного метода.
(19) откуда имеем х„, = х„— с«»А»7"'(х»), с«»>0, Ь=0,1,..., 242 Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Для ускорения сходимости этого метода пуи поиске минимума «овражной» функции можно предложить следующии эвристический прием, называемый овразхным методом. Сначала опишем простейший вариант этого метода. В начале поиска задаются две точки и„я!, из которых производят спуск с помощью какого-либо варианта градиентного метода, и получают две точки х, х, на «дне оврага».
Затем полагают — (х — )~ — ~ 'ЬзМп(Х( ) — 7( )) где Ь вЂ” положительная постоянная, называемая овражным шагом, Из точки тю которая, вообще говоря, находится на «склоне оврага», производят спуск с помощью градиентного метода и определяют следующую точку х, на «дне оврага». Если уже известны точки х», х,„..., х», Ь > 2, то из точки , = х„— (х„— х» !)~х — х»,~ 'Ь з!еп(7(х») — Лх» !Н совершают спуск с помощью градиентного метода и находят следующую точку х», на «дне оврага» (см. Рис.
5.3; спуск нз точки «!» в точку х„ состоящий, быть может, из нескольких итерационных шагов градиентного метода, условно изображен отрезком прямой, соединяющей точки о», х„, Ь =О, 1,,). Величина овражного шага Ь подбирается эмпирически с учетом информации о минимизируемой функции, получаемой в ходе поиска минимума.
От правильного выбора Ь существенно зависит скорость сходимости метода. Если шаг Ь велик, то на крутых поворотах «оврага» точки о» могут слишком удаляться от «дна оврага» и спуск из точки т» в точку х„, может потребовать большого объема вычислений. Кроме того, при больших Ь на крутых поворотах может произойти выброс точки о» из «оврага», и правильное направление поиска точки минимума будет потеряно.
Если шаг Ь слишком мал, то поиск может очень замедлиться и эффект от применения овражного метода может стать незначительным. Эффективность овражного метода может существенно возрасти, если величину овражного шага выбирать переменной, реагирующей на повороты «оврага» с тем, чтобы: 1) по возможности быстрее проходить прямолинейные участки на «дне оврага» за счет увеличения овражного шага; 2) на крутых поворотах «оврага» избежать выброса из «оврага» за счет уменьшения овражного шага; 3) добиться по возможности меньшего отклонения точек «!» от «дна оврага» и тем самым сократить объем вычислений, требуемый для градиентного спуска из точки ь» в точку х., Ь = О, 1,...
Интуитивно ясно, что для правильной реакции на поворот «оврага» надо учитывать «кривизну дна оврага», причем информацию о «кривизне» желательно получить, опираясь на результаты предыдущих итераций овражного метода. В работе 1657) предлагается следующий способ выбора овражного шага; (20) где с« — угол между векторами о» вЂ” х„„х — х„„определяемый условием соз а» = («!» — х „х„— х» !)1«! — х» !~ !(х» — х» !( ', а постоянная с > 1 является параметром алгоритма. Точка о» ! определяется из (19) при Л = Ь», Разность соз ໠— соз с«» ! в равенстве (20) $1 ГРАДИЕНТНЫЙ МЕТОД 243 связана с «кривизной дна оврага» и, кроме того, обладает важным свойством указывать направление изменения «кривизны».
А именно, при переходе с участков «дна оврага» с малой «кривизной» на участки с большей «кривизной» будем иметь созе«» — сова» ! <0 (см. Рис. 5.4). Тогда, в силу (19) имеем Ь», < Ь„, т. е. овражный шаг уменьшается, приспосабливаясь к повороту «дна оврага», что в свою очередь приводит к уменьшению выбросов точки «!» ! на «склоны оврага», При переходе с участков «дна оврага» с большой «кривизной» ~»-! на участки с меньшей «кривизной», наоборот, соз г«» — сова» ! > О, поэтому овражный шаг увеличится и появится возмо«кность сравнительно бы- ~» ! стро пройти участки с малой «кривизной», в частности, прямолинейные участки на «дне оврага». Если «кри- ~! ! визна дна оврага» на некоторых участках остается постоянной, то разность »» сов໠— созе«» ! будет близка к нулю, и поиск минимума на таких участках будет проводиться с почти посто- ~»+! »+2 янным шагом, сформированным с учетом величины «кривизны» при выходе »»!! на рассматриваемый участок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
