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