Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 83
Текст из файла (страница 83)
Пусть функции /(х), д (х), с = 1,..., т апредглень» и выпуклы на » Жо, выполнено условие Слейтера (4 9!5); /(х), д (х) еС~ '(Х), Ао — — тах зар(дй (х)(< ((с< х < оо. Пусть задача (1) имеет решение, т. е. /, > -са, Х, ф»2(, и начальная точка хо Е Х такова, что мноэегстзо Мг(хо) =(х: х ЕХ /(х)(/(то)+6) ограничена.
Тогда при любом выборе го > О для последазатзльнасти (хй), определяемой условиями (2), (3), (6), (13)-(15), справедливы равенства 1»в /(хй) =/„, Игп д(хй, Х,) =О. (20) й со й о Доказательство, Сначала установим, что Если а < — з„, то иэ (14), (6) имеем /(хй») = да(ий) < дй(0)+ бй — — /(хй)+ бй. Если же -з < сг. < О, то из (15) следует /(хй „() = /(хй) < /(хй) + бй. Таким образом, /(х„,)</( й) ьбй у=о,(,.,ц Т.
ба=6<. й=о и, кроме того, /(хй) л /, > -са, й = 0,1,... Согласно лемме 2.6.2 тогда существует !пп /(хй) > /ы Отсюда следует равенство (2!) » ' ф(<" Далее, покажем, что Ив эй — -О. Согласно (14), (!5) последовательность (г,) получается й й дроблением и не возрастает. Допустим, что !пп гй — — а > О. Это значит, что в процессе по. й со строения (хй) было конечное число дроблений и гй — — г > 0 при всех й > йо. Из (14) тогда имеем ий < — гй = -г, т. е. (ай! > г, й > йа. В этом случае согласно лемме 2 ймеем /Уй > А» г, й > йа. Поэтому из леммы 3 получим /(хй) — /(хй () > Аэ в(п(А»зэ; зэ) — бй, й > й„, что противоречит равенству (21). Итак, показано, что И й г. = О. й со й— Пусть й( < йэ «...
й, <... — номера тех итераций, когда происходит дробление эй. Со. гласно (14), (!Ь) тогда -зй < ай (О, г =1,2,... Следовательно, Ив и. =О. Тем самым й, установлено, что существует хотя бы одна подпоследовательность (ссй ), сходящаяся к нулю. Возьмем произвольную подпоследовательность (ай ) — ° О. Покажем, что тогда любая пре. дельная точка соответствующей подпоследавательности (хй ) принадлежит множеству Х„. Из (22) следУет, что /(ха+ () < (/(хо)+ б, й =О, 1, .. о т. е, (хй) Е Мг(ха). По Условию мно- жество Мг(то) ограничено.
1!оэтому можем считать, что взятая выше подпоследовательность (хй ) сходится к некоторой точке х,. Далее, множество номеров 1й, определяемое соглас- но (13), представляет собой подмножество конечнога числа номеров (1, 2,..от), поэтому число различных множеств 1й конечна. Это значит, что среди (1й, г = 1, 2,...) найдется хотя бы одно множество 1д — — 1, которое повторяется бесконечно много раз.
Выбирая при необхо. димости подпоследовательности, можем, таким образом, считать, что (»тй ) -» О, (хй ) †» х„ 1й = 1, г = 1, 2, (а~ — а(х„) ( = (а (хй ) — и (х„) ( ( Ь ч(п(хй — х„! -о О, т.е. Ив а(хй )со 1цп ай — — О=а(х ), где а(х,)= (п( и, С(х )=((е, сг)ЕЖ~~'(/(х,) е)( со «» а( ) (сс, (ду (х),е)<а, »Е(; (еу((1, 3=!,...,а), Рассмотрим задачу (7), соответствующую точке и, = (пп хй . Покажем, что И", С С(х ). По о *— определению мно»кеств 1=1й — — (И ! <с <г, -эй <д (хй ) <0), г= 1,2,... Отсюда при г-»аа получим дэ(х„) = 0 для всех с Е 1, Это значит, что 1 Е /„, т.
е. в определении множества И'„ число ограничений типа неравенств не меньше, чем число таких ограничений в определений С(з,). Тем самым установлено, что Иг, Е С(х„), А тогда, замечая, что одна и тз же функция на более широком множестве имеет меньшую нижнгою грань, получаем и, = (п( и > !и! и = н; а(х,) = а(х„) = О. С другой стороны, (О, 0) Е Иы поэтому а, < О. Следовательно, и, = 0 и согласно теореме 1 имеем х„Е Х,.
Выше было доказано существование предела Игп /(хй ). Теперь можем сказать, чему равен й со этот предел: !пп /(хй) = !пп /(хй ) =/(х„) =/». Таким образом, построенная последовательность (хй) минимизирует функцию /(х) на мно- жестве Х. Поскольку (хй) Е Мг(хо) — ограниченное множество, то из теоремы 2.1.2 следует, что Ив р(хй, Х,) = О. Равенства (20) и, тем самым, теорема 2 докаваны. (3 й оо 4. Для задачи ,/(х)-»!и!( хЕХ=(хЕЕ; д;(х)(0, (=1,,т ду(х)=(»»у,х) — 6»=0 содержащеи линеиные ограничения типа равенств, метод возможных направлений описывается так же, как выше, лишь в задаче (2) ну»кно добавить еще ограничения (ау, е) =О, » =и»+1,...,г. Можно заметить, что описанный в гл.
3 симплекс-метод для решения канонической задачи линейного прогрвммирования по существу является вариантом метода возможных направлений, Более того, опираясь на идеи метода возможных направлений, можно получить симплекс- метод непосредственно для основной задачи линейного программирования (без ее сведения к канонической задаче). Выше во вспомогательной задаче (2) было принято условие нормировки (еу! (1, У = 1,..., и.
Возможны и другие условия нормировки, например, (е)~ < 1 или (йй а! < 1, где Вй — специаль. но выбираемая матрица. Заметим, что при такой нормировке задача (2) уже не будет задачей 279 $ б. ПРОКСИМАЛЬНЫЙ МЕТОД 278 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Упражнении 9 6. Проксимальный метод (7) (8) (2) 1о(' ' ) 2~ (3) линейного программирования. Тем не менее удачный выбор Вь может облегчить выбор зоз- можного направления убывания, ускорить сходимость метода. О других способах нормировки, о сходимости различных вариантов метода возможных направлений и других аспектах етого метода см„ например, 1319; 326; 374; 7741.
1. Сделать несколько итераций метода возможных напразлений для задачи минимизации 7(м) =з-ьу на мнохсьстзе х =(м=(и, у): уг(м) =аз — у~(0, дз(о)= у — 1 <0) прн различном выборе начальной точки оо. 2. Вычислить несколько приближений по методу зозможных направлений для задачи из примера 1 при различном начальном приближении оо. 1. Этот метод используется для решения выпуклых задач минимизации 7(х) ь !п1, х Е Х, (1) когда Х вЂ” выпуклое замкнутое множество из Е, функция 7(х) выпукла на Х. В его основе лежит понятие проксимального оператора, который определяется следующим образом. Фиксируются точка х Е Е" и число а > > О, определяется функция переменной г е Х, и рассматривается задача минимизации (о(я, х, и) — ~ !п1, я Е Х.
Так как функция чт(я, х, и) сильно выпукла на Х с постоянной сильной выпуклости х = 1, то согласно теореме 4.3.1 задача (3) имеет, притом единственное решение л„= г„(х, а). Тем самым определен оператор, который каждой точке х Е Е" и числу а > О ставит в соответствие решение г„задачи (3). Этот оператор называется проксимальным, его обозначают символом рг. Таким образом, рг (х, а) = г, е Х вЂ” решение задачи (3). Изучим некоторые свойства проксимального оператора. Из (3) и неравенства (4.3.3) следует, что -~г — рг(х, п)1з < чз(л, х, а) — ~р(рг(х, а), х, п) Чз Е Х, х Е Е") сх > О. Если функция 7(х) дифференцируема на Х, то чт„(з, х, а) = г — х+ п7"'(г) и для решения рг (х, а) задачи (3) по теореме 4.2.3 имеем (рг (х, а) — х+ а)т(рг(х, а)), г — рг (х, п)) ) О Чз е Х Отсюда, вспоминая характеристическое свойство проекции точки на мне жество (неравенство (4.4.1)), обнаруживаем следугощую связь между прок симальным оператором и оператором проектирования: рг(х, а) =Рх(х — а1'(рг(х, а))) Чх Е Е", а >О.
(5) (Лзгй ;,т" г 1' ог г Если функция 7"(х) не является дифференцируемой, то эту связь можно выразить с помощью субградиентов. Всюду ниже в этом параграфе мы будем предполагать, что функция 7(х) определена и выпукла на открытом выпуклом множестве Иг, содержащем множество Х. Тогда при каждом г е Х субдифференциал ду"(з) является непустым выпуклым замкнутым ограниченным множеством (теорема 4.6.2).
По правилу 7 субдифференцирования из у 4.6 для функции (2) имеем др(г, х, а) = з — х+ аду(г) Чг Е Х (6) Согласно теореме 4.6.4 для решения рг(х, а) задачи (3) найдется субградиент с,(рг(х, а)) Е ду(рг(х, а), х, и), такой, что (с (рг(х, а)),г — рг(х, ст)) ) О 1уг Е Х. Из формулы (6) следует существование с(рг (х, а)) Е ду(рг (х, и)), для кото- рого с,(рг(х, а)) = рг(х, а) — х+ ас(рг (х, а)), и поэтому предыдущее нера- венство можно записать в виде (рг(х, а) — х+ ас(рг(х, а)), л — рг(х, а)) > О Уг Е Х; Отсюда вместо формулы (5) получим рг(х, а) = Рх(х — ас(рг(х, а)) 1гх е Е, а > О, для некоторого субградиента с(рг (х, а)) е ду'(рг(х, а)). С помощью установленной связи (8) между проксимальным оператором и оператором проектировании нетрудно доказать следующий критерий оптимальности для задачи (1).
Теорема 1. Для того, чтобы х„еХ., необходимо и достаточно, чтобзм х =рг(х а) чп >О Доказательство. Необходимость. Пусть х„еХ,. По теореме 4.6.4 найдется субградиент с(х,) Е д7(х„) такой, что (с(х„), г — х,) > О Чг Е Х. Тогда, как следует из формулы (6) с (х ) = х„— х + ас(х ) = ас(х ) Е Е доз(х„, х„, а). Умножая на а > О предыдущее варйационное неравенство, получаем: (с,(х„), г — х.) > О Чг Е Х. Согласно теореме 4.6.4 это означает, что х, — решение задачи (3) при х = х„т. е.
х, = рг(х„а). Достаточность. Пусть х, =рг(х„, а). Согласйо формуле (8) найдется с(рг (х, а)) = с(х ) е ду(рг (х„а)) = ду(х), что х, = Рх(х, — ас(х )). Отсюда и из замечания 1 к теореме 4.6.4 имеем: х, е Х.. Теорема 1 доказана. П Т е о р е м а 2. 77роксимальный оператор рг (х, п) непрерывен по переменной х равномерно относительно а > О и, более того, !рг(х, а) — рг (у, а)~ < !х — у! Чх, у Е Е, сз ) О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
