Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 93
Текст из файла (страница 93)
5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $12 МЕТОД ПОКООРДИНАТНОГО СПУСКА 3П 1. Сначала опишем этот метод для задачи в силу выпуклости /(ж) (теорема 4.2.4). С учетом этих соотношений ив (! 1) имеем (14) (5) Ла„, ай+ !— Ц =гь, х,=хй Ц ф и или х ф хй или 0<й<п — 1; (7) хй -!-! й « (С(ж(т))ж(т), ж(1)) + оГ(«/«(х,) — «р(х(т)) + («р (х(т)) ж(!) ж«)) + (/( ( )) /(ж) (/'( ), (!) —,))<О ут>О, эж,ЕХ,.
И Интегрируя это неравенство на произвольном отрезке (т, !], получим с «=! ](С(х(в))х(э)«х(э))«!э+(«р(х«)-«р(х(в))+(«р'(х(э)),х(з)-х ))~ + «=с +о(т)(/( (з))-/(ж.)-(/'(х.),ж(з)-ж.))~ ! « — ] ж'(з)]/(ж(з))-/(ж,) — (/'(х,),х(э) — х«)]с!э<0 «7! > т > О, «/ж«е Х„. (13) Из выпуклости /(ж) (теорема 4.2.2) и сильной выпуклости «Р (х) (теоремы 4.3.2 и 4.3.4) следует /(х(!)) — /(х«) — (/'(ж,), ж(т) — ж„) )в 0 т! л О, «/«(ж„) — «р(х(т)) + («р (ж(т)), х(т) — ж„) ) х]х(!) — ж„] (С(х(!))х(!), х(!)) ) х!ж(1)]т т! >О. Отсюда и из (13) с учетом о(т) > О, ж'(т) < 0 имеем ] ]х(э)!зь«жх]х(т) х !з < «р(х,)-«р(х(т))+(«р'(х(т))«х(т)-х,)+о(т)/(х(т)) /(х ) (/'(ж ) ж(т.)-х ) ж э(т, ж,) Ч! > т ~ )О, Чх, е Х,.
(15) Это означает, что ]х(!) — ж,]~ < э(0, ж„)/х «/! >0 и ] ]й(!)]зш < э(0, х,)/ж. Поэтому существ вует последовательность (! )-«оо такая, что (ж(т!))- е„, (ж(т!)) — «О. Так как множество Х замкнуто, ж(!)+ х(т) е Х (г! > О, то Ив (ж(!!)+ ж(!!)) = е, е Х.
Положим в (8) ! = тз," при «сс с -«оо с Учетом Ив о(т!) = ж(оо) > оо >О полУчим о(оо)(/ (э,), У-е,) )жО «У ЕХ. Согласно «о« теореме 423 тогда е, е Х,. Из (! 5) при т = !!, ж„= е„следует: ]ж(! )-э,]т < э(1,, е)/х тт > О. Переходя здесь к пределу сначала при ! -«-1-оо, затем при й -« со, имеем Ив ж(!) = е,. Тогда !кп /(х(1)) = /(е,) = /„ Ив /'(ж(!)) = /'(е,), Наконец, из (11) при х„ = е, с уче! со С сэ том (12), (14) получим: х]й(1)]з ( цС(х(!))ц]ж(с)цх(т) — э,]+ ж(т)]/'(ж(т)) — /'(е,)цй(т)] или х]ж(т)]~ (ЦС(х(!))Ц]ж(!)-э ]+о(!)]/(х(т)) — / (э )] 'т! )О.
Отсюда при е-«со следует, что )нп ж(!) = О. Теорема 2 доказана. Г! В заключение заметим, что метод (6), основанный на изменяющейся вдоль траектории х(т) С-метрике, можно рассматривать как непрерывный аналог большой группы итерационных методов, которые в литературе принято называть методами «с растяжением пространства« или методами с переменной метрикой [76; 273; 586; 738; 769]. й 12.
Метод покоордпнатного спуска В предыдущих параграфах мы рассмотрели методы, которые для своеи реализации требуют вычисления первых или вторых производных минимизируемой функции. Однако в практических задачах нередко встречаются случаи, когда минимизируемая функция либо не обладает нужной гладкостью, либо является гладкой, но вычисление ее производных с нужной точностью требует слишком большого объема работ, много машинного времени.
В таких случаях желательно иметь методы минимизации, которые требуют лишь вычисления значения функции. Одним из таких методов является метод покоординатного спуска 174; 374; 7531. " 'г«' *« .! с , !с ! У1-.".' /(х)- !П]; хех=й". (1) Обозначим е! = (О,..., О, 1, О,..., О) — единичный координатный вектор, у которого т'-я координата равна 1, остальные равны нулю, Ц = 1,...
тй. Пусть х — некоторое начальное приближение, а а — некоторое положительное ч сло, являющееся параметром метода. Допустим, что нам уже известны н о точка хй е Е" и число а„> 0 при каком-либо й > О. Положим: рй =ей, ай=й — и!! — !+1, (ь! (2) (ь] где ~ — „! означает целую часть числа й/гт. условие (2) обеспечивает циклический перебор координатных векторов е„ гт,..., е, т.
е. Ро = и! ! Р„, = е„, р„= е!,, р „, = е, р „= е,, Вычислим значение функции /(х) в точке х = х + а„рй и проверим неравенство /(хй+ йрй) </'(хй] (3) Если (3) выполняется, то примем х! + ! = хй + ай Рй (4) В том случае, если (3) не выполняется, вычисляем значение функции /(х) в точке х = х, — айр, и проверяем неравенство /(хй — айрй) < /(хй). В случае выполнения (5) положим х э! = х — айра, ай„, = ай. (б] Назовем (й + 1)-ю итерацию удачной, если справедливо хотя бы одно из неравенств (3) или (5). Если (й + 1)-я итерация неудачная, т. е.
не выполняются оба неравенства (3) и (5), то полагаем здесь Л, 0 < Л < 1 — фиксированное число, являющееся параметром метода, Условия (7) означают, что если за один цикл из п итераций при переборе направлений всех координатных осей е„ ..., е„ с шагом ай реализовалась хотя бы одна удачная итерация, то длина шага ай не дробится и сохраняется на протяжении по крайней меое следующего цикла из п итераций. Если же среди последних и итерации не оказалось ни одной удачной итерации, то шаг а дробится.
Таким образом, если на итерации с номером й = й„ произошло дробление ай то ,/(хй + ай е!) >Пхй ), /(хй — ай е,.) > /(х ) 4 12. МЕТОД ПОКООРДИНАТНОГО СПУСКА 81З 312 Гк 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ откуда при всех Г = 1,..., и. Метод покоординатного спуска для задачи (1) описан. Справедлива Теорема 1. Пусть функция 7"(х) выпукла на Е" и принадлежит классу С'(Е"), а начальное приближение х таково, что множество М(хь) = (х Е Е":,7(х) < 7(хь)) ограничено. Тогда последовательность (х„), получаемая описанн«ям методом (2) — (7), минимизирует функцию Г'(х) на Е" и сходится ко множеству Х..
Д о к а з а т е л ь с т в о. Согласно теореме 2.1.2 имеем 7„> — оо, Х, ф О. Из описания метода (2)-(7) следует, что У(х,~«) < 7(х„), к = О, 1,..., так что (х„) Е М(х ) и сУществУет !пп У(хь) ) Г",. Покажем, что найдетсЯ бесконечно много номеров к„..., й„,... итераций, на которых шаг о„дробится, и поэтому 1пп о, =О. Допустим противное: пусть процесс дробь ю ления конечен, т. е. о, = о > 0 при всех й > 1У. Обозначим М„= (и: и = хв+ сите,.
б М(х,), Г = 1,..., п, т =О, х1, х2,...) — сетку (решетку) с шагом о. Из описания метода покоординатного спуска при о„= о, Ь > 1ч', следует, что начиная с номера )ч' все последующие циклы из и итераций будут содержать хотя бы одну удачную итерацию, и на каждой удачной итерации будет происходить переход от одной точки сетки М, к другой соседней точке этои сетки. По определению удачной итерации йереход от точки к точке сопровождается строгим уменьшением значения функции 7(х), поэтому каждая точка сетки М, будет просматриваться не более одного раза, Но множество М(х ) по условию ограничено, и поэтому сетка М, состоит из конечного числа точек.
Следовательно, процесс перебора точек этой сетки закончится через конечное число итераций определением точки х,, й„ > Ж, для которой выполняются неравенства (8) при всех л = 1,...,п. А тогда вопреки допущению придется дробить число оь = о, Полученное противоречие показывает, что процесс дробления о„бесконечен и !пп о, =О. Пусть й с кг «... Ь„с... — номера тех итераций, на которых длина шага о, дробится и выполйяются неравенства (8). Так как последовательность (х,) принадлежит ограниченному множеству М(х,), то из (х„) можно выбрать сходящуюся подпоследовательность.
Без умаления общности можем считать, что сама последовательность (х. ) сходится к некоторой точке х,. С помощью формулы конечных приращейий из (8) имеем (7'(х„+ д,„о е,.), е«)о > О, (7'(х„— д о„е«), е,)( — о, ) ) О, 1,,(х„+ 0 о„е,) >О, 7',«(хь — д оь е;) <О, 0< д, 0,„<1 при всех 4 =1,..., п и та =1, 2, '. Пользуясь тем, что 7(х) е Е С'(Е )™и 1пп о = О, отсюда получим 7",, (х„) =О, 1=1,..., и, т. е.
7'(х„) = = О. В силу выпуклости 7(х) тогда х, е Х,. Следовательно, 1пп 7(х,) = = !ип 7"(х, )=Г'(х,)=7,. Таким образом, последовательность (х )является минимизирующей. Отсюда и из теоремы 2.1.2 следует, что р(хю Х,) — 0 при й — оо. Теорема доказана. П Заметим, что хотя метод (2)-(7) для своей реализации не требует знания градиента минимизируемой функции, однако в условии теоремы 1 содержится требование гладкости этан функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
