Ф.П. Васильев - Методы оптимизации (1125241), страница 92
Текст из файла (страница 92)
Если х„Е Х. и функция Т(х) дифференцируема в точке х„то необходимо выполняется равен- х, = !эх< '1(х, — а(С(т,,)) <7'(х„)) 1Усх > О. (4) Если, кроме того, 7(х) выпукла на Х, то всякая точка х„удовлетворяюсцая уравнению (4), принадлежит Х,, До к аз ат ел ь с т во. В силу (3) равенство (4) эквивалентно неравенству (С(х,Ях, — (х, — о(С(х„)) С'(х,)], у — х,) )~ 0 Чу Е Х, или (оу'(х,), у — х,) > 0 Чу Е Х. Поскольку о > О, то отсюда имеем; (У(х),у — х)>0 ЧуЕХ (5) Так как проведенные выкладки обратимы, то вариационные неравенства (4) и (5) равносильны, Отсюда и из теоремы 4.2.3 следует утверждение теоремы 1. П Рассмотрим систему дифференциальных уравнений [281: ф(с) = РХ«*'11(х(С) — о(С)(С(х(С)))-' С'(х(С))) — х(С), С > О, (6) где о(с) > 0 — заданная функция, Согласно теореме ! решение х, задачи (1) удовлетворяет уравнению (4) при о = о(с) > 0 Ус > О.
Это значит, что каждая точка х, е Х„ является точкой равновесия (стационарным решением) системы (6).Можно надеяться, что при некоторых ограничениях на функции С(х), о(с), матрицу С(х) траектория х(с) системы (6) при больших С приближается ко множеству Х,. непрерывный метод с переменной метрикой описан, Если Х вЂ” — Ь'", то Ряс<*1(х) = г Уг Е Ь'", и (6) превращается в систему х(С)=- (С)(С(х(С)))-'У(х(с)), С >О.
(7) Если Х ф Е , то уравнение (6) эквивалентно вариационному неравенству, которое вытекает из (3): (С(х(С))ф(С)+ о(с)7'(х(с)), у — х(С) — х(с)) > О, Уу е Х Ус > О. (8) Из (6), (7) видно, что при С(х) ш Т„метод (6) превращается в непрерывный вариант градиентного метода (1.45) или метода йроекции градиента (2.34). Посмотрим, что будет, если С(х) ш С'л(х), предполагая, что 7(х) е Сз(Е") и сильно выпукла на Ьа В случае Х = Е" из (7) имеем: х(с) = - (С)(ул(х(С)))-СУ'(х(С)), С > О, (9) Нетрудно видеть, что метод (10.39) является разностным аналогом (схема Эйлера) метода <91, а классический метод Ньютона (10.8) — зто разностный аналог метода (9) при о(с) = о [251 Если Х ф Ь", то иа (8) при С(х)щул(х) получим вариаиионное неравенство (Ул(х(с))х(с)+ о(С)!'(х(С)), у — х(С) — х(С)) > О, Чу Е Х, <Сс > О.
(10) Неравенство (1ОЛ2) моькно истолковать как разностный аналог неравенства (10). Как видим, метод (6) при С(х) = уз(х) является непрерывным аналогом метода Ньютона. Поэтому можно огкидать, что если в (6) матрицу С(х) выбирать близкой к Уз(х), то на этом пути удастся получить непрерывные аналоги квазиньютоновскик методов, также имеющих высокую скорость сходимости, хорошо приспособленных для минимизации овражных функций. Следует сказать, что проблема конструктивного выбора матрицы С(х) в методе (6) пока еще мало изучена, Приведем теорему скодимости метода (6), Те эре ив 2. Пуст~ Х вЂ” выпуклое замкнутое множестзо, функция С(х) Е С'(Ьз) и зьтУкло но ь'", г'„> -оо, х„ф Яс фУнкциа о(с) > ос >О, лелРгРызно диффеРэнциРУема и о(с) (0 тс > 0; матрица с(х) симметрична, и суи<естэует сильно выпуклая функция ф(х)ЕС (Ь'") токоя, чтофл(х)=С(х) авек".
Пусть траектория систямьс(6) с начальным условием х(0) = хо олредзлена лри всех С >О, Тогда существует точки о„=о (хо) Е Х„ такая, что !пп х(С) = и„!!Сп С'(х(с)) = 7"„, Пгп х(С) =О. До к а ватель ство. Примем в (5) у= х(с)+ х(с) Е Х, умножим на м(с) >0 н сложим с (8) при у= х„; (С( (С))х(С) 4 о(с)(У'(х(с)) - Т'(;)), х, — '(С) - х(с)) > О или (С(х(С))й(С), х(С)) -1- (С(х(С))х(С), х(С) — х )+ о(с)(7 (х(С)) — уч(х,), х(С))-1- + о(с)(1'(х(с)) — с'(х„), хОΠ— х,) ( 0 Чс > О, Чхь Е Х„.
(11) По условию теоремы существует функция ф(х), для которой фл(х) = С(х) эх Е Ь'", поэтому дс (ф(хл)-ф(х(С))+(ф'(х(С)),х(С)-хл))=(фл(х(С))х(С),х(с) — х„)=(С(х(С))х(С),х(С) — х„). Кроме того — (7(х(с)) — 7(х~) — (Р(х„), х(С) — х„))= (7'(х(С)) — 7'(х,), ф(С)), о(С) >О, (у'(х(с)) — 7'(х„), л(С) — л„) > 0 (12) Гл(' .Ггс :,л или СМ С!"," (Бсх(С))[х(С)-1- х(С) — (х(С) — гг(С)(С(х(С))) Г'(х(с)))1, у — (х(с)-<- х(с))) > 0 311 $12.
МЕТОД ПОКООРДИНАТНОГО СПУСКА 310 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ э силу выпуклости /(х) (теоремэ 4.2.4). С учетом этих соотношений иэ (11) имеем (С( (Э))х(0,х(Э))+ ф(Ч(х,) — «р(х(т))+(«р'( (т)) х(т) .))+ (т) О«(/( (1)) /(х ) (/«(х ) х(т) — х )) (О Чв >О, Чх, еХ,.
Интегрируя это нерээенстэо нэ проиээольном отрезке[в; Э], получим « ~в=« 1(С(х(В))х(э)«х(В))ов+(«Р(хт)-«/«(х(в))+(В/«(х(в)),х(в)-х«))[ ~в=« +п(э)(/(х(в))-/(х )-(/ (х,),х(в)-х,))[ — 1« а'(в)[/(х(в))-/(х )-(/'(хт)«х(в) — х,)]лв<0 Чт > т > О, Чх, Е Х„. (13) Из выпуклости /(ж) (теоремэ 4.2,2) н сильной выпуклости «/«(х) (теоремы 4,3.2 и 4.3.4) следует /(х(т)) — /(х ) — (/'(ж), х(т) — х ) >0 Чт >О, «/«(х ) — «/«(х(т)) + («/«(ж(э)), х(В) — х ) > х[ж(э) — х [, (с( (1))х(»), х(в)» х[х(в)[э ч» > о. Отсюда н иэ (13) с учетом ж(Э) > О, и'(1) < 0 имеем ] [ (В)!2,1 !.х]х(т) х !Э < «/«(х ) — «/«(х(т))+(«р'(х(т)) х(т)-х,)+п(т)/(хИ) т /(х)-(/'(х„),х(т)-х.)юи(т,х,) Чт>т>0«ЧхтЕХО.
(!5) Это означает, что [х(т) — х,[э ( и(0«х„)/х Чэ > 0 и [ ]ж(в)]~лв < ««(О, х,)/х. Поэтому сущесто кует последовательность [Ь]-«со такая, что (ж(Э;)] — «ж„(й(Э,)] — «О. Тэк кэк множество Х зэмкнуто, х(т) + х(э) е Х (/э > О, то 1нп (й(т ) + х(э )) = ж, е Х. Положим э (8) э = э;; при « -«ос с учетом !1ш п(т«) =п(со) > по >0 получим п(оо)(/(о,), р-ж,) > 0 ЧреХ. Соглэсно ОО 2 теореме 4 2 3 тогда ж, еХ,, Иэ (15) при ттО эв, х,=о, следует: [х(т) — о ] < и(во ж )/х Чэ >О. переходя здесь к пределу сначала при в -«+оо, затем при $,.
-«оо,*имеем Цш х(т) = о,. тогда !!ш /(х(т))=/(о,)=/„, 1пп /'(х(т)) =/'(о«). наконец, иэ (11) при х„= ж, с уче- «О О том (12), (14) получим: х[х(т)]э ( ЦС(х(т))Ц[х(т)Цж(Э) — ж,[+ а(т)]/'(х(т)) — /'(ХО)йх(т)] или х]й(т)[( цс(х(э))]цж(т)-о,]+о(т)]/(х(т))-у (х )[ чэ >О.
Отсюда при т -«со следует, что !нп й(Э) = О. Теорема 2 доказана. П «О В заключение заметим, что метод (6), основанный нэ изменяющейся вдоль траектории х(в) С-метрике, можно рассматривать кэк непрерыэный аналог большой группы итерационных методов, которые з лнтерэтуре принято называть метадэми Ос растяжением прострэнстнэ« или методэми с переменной метрикой [76; 273; 586; 738; 769]. й 22.
Метод покоордннатного спуска В предыдущих параграфах мы рассмотрели методы, которые для своеи реализации требуют вычисления первых или вторых производных минимизируемой функции. Однако в практических задачах нередко встречаются случаи, когда минимизируемая функция либо не обладает нужной гладкостью, либо является гладкой, но вычисление ее производных с нужной точностью требует слишком большого обьема работ, много машинного времени. В таких случаях желательно иметь методы минимизации, которые требуют лишь вычисления значения функции.
Одним из таких методов является метод покоординатного спуска [74; 374; 753]. $. Сначала опишем этот метод для задачи /(х) — «!и[; х Е Х =Я", р„= ев, э„= й — и ~ — ~ + 1, [»1 (2) [ь1 где ~ — ~ означает целую часть числа й/и, Условие (2) обеспечивает циклический перебор координатных векторов е„ е,..., е„ т. е. р =е„..., р„,=е„, р„=е„..., р„,=е„, рэв=е„ Вычислим значение функции /(х) в точке х = х„+ (О»р» и проверим неравенство /(х» + гг,р») < /'(х»).
(3) Если (3) выполняется, то примем х,=х +(в»р», о» « — — ст . (4) В том случае, если (3) не выполняется, вычисляем значение функции /(х) в точке х = х„— сг»р» и проверяем неравенство (5) /(х» сг р„) </(х ) В случае выполнения (5) положим :э„, = *, — о»р»«с~„« = (~». (б) Назовем (й + 1)-ю итерацию удачной, если справедливо хотя бы одно из неравенств (3) или (5).
Если (й + 1)-я итерация неудачная, т. е. не выпол- няются оба неравенства (3) и (5), то полагаем Л с»„, Ст»в «Ож Ст» э =п,х„=х В ~ПИЛИ Х»фХ„ или 0 < й < и — 1; (7) х , = х , здесь А, 0 < Л < 1 — фиксированное число, являющееся параметром метода. Условия (7) означают, что если за один цикл из и итераций при переборе направлений всех координатных осей е„ ..., е„ с шагом о» реализовалась хотя бы одна удачная итерация, то длина шага ст» не дробится и сохраняется на протяжении по крайней меце следующего цикла из п итераций. Если же среди последних и итерации не оказалось ни одной удачной итерации, то шаг сг» дробится. Таким образом, если на итерации с номером й = й,„ произошло дробление сг», то ./(х» + с»» ев)~)7(х» ), /(х, — сг„ев) >/(х„) Обозначим е« = (О,..., О, 1, О,..., О) — единичный координатный вектор, у которого э-я координата равна 1, остальные равны нулю, э = 1,..., п.
Пусть хо — некоторое начальное приближение, а сг — некоторое положительное число, являющееся параметром метода. Допустим, что нам уже известны точка х, Е Е' и число гт» > 0 при каком-либо й > О. Положим: э 12. МЕТОД ПОКООРДИНАТНОГО СПУСКА З1З 312 Гк 5, МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ откуда при всех й = 1,..., и. Метод покоординатного спуска для задачи (1) описан. Справедлива Т е о р е м а 1. Пусть функция 7(х) выпукла на .Е" и принадлежит классу С'(Е"), а начальное приближение х таково, что множество М(т„) = (х Е .Е": 7'(х) < 7(хь)) ограничено. Тогда последовательность (хй), получаемая описанным методом (2) — (7), минимизирует функцию 7(х) на Е" и сходится ко множеству Х..
Доказательство. Согласно теореме 2.1,2 имеем 7; > — оо, Х, фи, Из описания метода (2)-(7) следует, что У(хйй,) < 7(хй), Й =О, 1,..., так что (хй) е М(т ) и существует !!ш 7" (хй) > Г'.. Покажем, что найдется бесконечно много номеров Й„..., Й,„,... итераций, на которых шаг сйй дробится, и поэтому !!ш сйй =О. Допустим противное: пусть процесс дробй ления конечен, т. е. сйй = сй > 0 при всех Й > 1й!. Обозначим М = (и: и = х„+ сйгей Е М(т„), й'= 1,..., п, г = О, х1, х2,,) — сетку (решетку) с шагом сй. Из описания метода покоординатного спуска при сйй = сй, Й > Ас, следует, что начиная с номера Ас все последующие циклы из и итераций будут содержать хотя бы одну удачную итерацию, и на каждой удачнои итерации будет происходить переход от одной точки сетки М. к другой соседней точке этои сетки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
