Ф.П. Васильев - Методы оптимизации (1125241), страница 78
Текст из файла (страница 78)
2 виям леммы 2,6.2, из ноторой следует существование предела 1!гп р (хь, Х,), Так как под- 2 Ь 0 последовательность (р~(хь, Х,)) сходится к нулю, то этот предел может равняться лишь нулю. Следовательно, 1пп д(хь, Х,) = О. Покажем, что тогда 1]гп 7(хь) = 7,. По условию Ь ОО Ь ОО множество х, ограничено. тогда последовательность (ха), сходящаяся к х„, также ограничена.
Возьмем любую предельную точку х„этой последовательности. Пусть (хь ) -Р х„. Так как Х вЂ” замкнутое множество и йп р(хь РХ„) = д(х„Х,) =О, то х, с Х,. А тогда ОО Вш 7(хь ) = 7(х,) = 7,. Это означает, что числовая последовательность (7(хь)) имеет един- Р 0 ственную предельную точку, равную у„т. е. (пп 7(хь) = Д. Теорема 1 доказана. П Ь 00 Замечание 1, Б условии теоремы 1 предполагается выполнение условия (4). В том случае, когда Х ограничена, то, как следует из теоремы 4.6.5, условие (4) всегда выполняется.
Заметим также, что в теореме ! вместо (4) можно потребовать скодимость ряда Я оь!сь( . 2 2 Ь=О 3 а м е ч а н и е 2. Описанный выше метод проекции субградиента после некоторой м фикации мал!но использовать для решения следующей задачи выпуклого программирован 7(х)Р(п1; хЕХ=(хЕЛ":хЕХо,д(х)<О,РРО1, Опт).
Заметим, что система неравенств д((х) ( О, ! = 1,.. 0 тп, равносильна одному неравенству д(х)(чо, где д(х)= шак дз(х), х 6Х. КРоме того, из выпУклости фУнкций д,.(х), ! =1,... ! ( ' ( ОР .. О т, на хо следует выпуклость д(х) на хо (см. теорему 4.2.7). поэтому задачу (10) можно переформулйровать в виде эквивалентной задачи (11) также являющейся задачей выпуклого программирования. Предположим, что субдифференциалы д7(х), дд(х) непусты при всех х е Х,, Следуя 17661, рассмотрим метод х,„! — — Р] (х,— оьсь)Р Й=0,1,..» хоехо, (12) где (оя) выбирается из условий о >О, й=о 1,, Я оь]+о=со, л тОтьз(со, 0< г<1, (13) Ь О Ь=О а субградиенты (сь) таковы, что с е д)(хь) при д(хь) Е оТ ти с! е дд(хь) при д(х!) > оь7. (14) ]ЕР Таким образом, метод (12)-(14) работает так; если ограничение д(х) < 0 при х = х! не нарушена или нарушено немного, то минимизируем функцию 7(х), а если нарушение этого ограничения велико, то минимизируем функцию д(х).
Если функции г(х), д(х) дифференцируемы на Хо, то в (12), (!4) вместо сь нужно брать соответствующие градиенты 7'(хь) или д'(хз), В качестве последовательности (оа), удовлетворяющей условиям (13), можно взять, например, оь — — С(й+ 1) о, где С = сола! > О, а число а таково, что 1/2 < о <(1+ 7) '. В частности, при о = 3/5, у = 1(Р2, С = 1 получим о = (й 41) ~Р~, й = О, 1,...
Тес р ем а 2. Пусть Хо — выпуклое замкнутое множастао из В", функции 7(х), д(х) определены и выпуклы на некоторол открытом аьтуклол множестве Ь(г, содержащем Хо (налример, И" = Е" ). Пусть Д = !и! 7(х) > — оо, нножестао Х„точек минимума задача (11) х непусто, озраничено и, кроле тоео, Тоеда для лоследоаательностн (хь), определяемой условиями (!2)-(14), справедливы ра- аенстаа (5), До к аз а тел ьс т во, При выполнении условий теоремы функции 7(х), д(х) непрерывны на Хо, субдифференциалы ду(х), дд(х) непусты, выпуклы, замкнуты и ограничены при всех х Е Л,] (см. теоремы 4.2.15, 4.6.1, 4.6.2), а мноясество Х, выпукло и замкнуто (см, теорему 4.2.1 и лемму 2.1.1).
Покажем, что мноРкество М(СР, Сз) = (х С Х] У(х) Е СР, д(х) Е Сз) ограничено при всех С! > 'ш17(х), Сз > !п(д(х), В самом деле, М(7, 0) = Х ограничено по »О «а условию. Тогда по теореме 4.2.17 множество М(С(, О) = (х: х е Хо, д(х) < О, 7" (х) < С, ) огра. ничено при всех С! >!п(7(х), Теперь, фиксируя лРобое С(, по той же теореме 4.2.17'получаем х, ограниченность м(с„сз) при каждом сз > гп1д(х). Х Нетрудно видеть, что неравенства (6), (7) созранюот силу и для метода (12)-(14), Из (7) имеем Р оь! ч ' оь т(сь, хз — Р» (хь)) < В < со, а = 1, 2, (!5) ь=о Отсюда следует существование номеров Й! ( Йз «...
й <... таких, что г (сь, хь — Р» (хь )) < оьт, Р= 1,2,... (16) В самом деле, допустим, что (!6) не имеет места. Тогда (сь, хь — Рх (х )) > аьт при всех й = О, 1,... Отсюда и из (15) имеем оььт< ~ аь(сь,хз — Рх(ха))(В<со, з=1,2,..0 а=О а=О что пРотивоРечит Раскодимости 2 оз т т. !+ Р а=О Тем самым показано существование подпоследовательности (хь ), удовлетворяющей уело вию (16). Докажем, что 1!ш 7(хь ) = 7„, !!ш р(х(,, Х„) = О.
(17) Сначала убедимся в том, что сь сду(хь ), р=1,2, (!8) Дла этого достаточно показать, что д(хь ) < аьт, Р = 1, 2, .. О и вспомнить УсловиЯ (14). Дот Р пустим, что д(хь ) > оь при некотором р > 1. Учитывая, что тогда сь Еду(хь ) и, кроме того, Рх (ха ) е х„с РГ, т. е. д(Р» (хь )) < О, из (16) имеем аь < д(хь ) Е <д(хь ) д(Р» (хь )) < (с],, хь — Р» (хь )) < аьт . Получили противоречивое неравенство. Включения (18) доказаны, и попутно установлено, что д(хь ) < «ьт, р = 1 2 " (19) 263 262 Гл. 5. МЕТОДЪ| МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 4 4, МЕТОД УСЛОВНОГО ГРАДИЕНТА й 4.
Метод условного градиента с Упражнения Множество номеров (йр), удовлетворяющих условиям (16), представимо в виде объединения непересекающихся множеств Е! = (й„' 7(ха ) > 1,) и Ез = (йр. '7(ха ) < 7,). Сначала рассмотрим случаи, когда множество Х! бесконечно. Йз (16), (18) имеем 0(7(ха,) рр = 1'(ха„)- т"(тол,(ха )) < (са„ха, 7'х.(ха )) < аат й 6 Гт Отсюда следУет, что 7(ха ) т 7"„пРи Р т со, йр е 7!. Тогда Г(ха ) < С! < оо, и, кРоме того, согласно (13), (19) имеем д(ха ) <хат < зцр хат =Сз <со, т.
е. (ха )еМ(С|, Сз), й бум Так а>о как М(Сп Сз) ограничено, то (ха, й е 71) имеет котя бы одну предельную точку. Не умаляя а ' р общности, макаем считать, что (ха ) -т х„йр е Гн Из замкнутости Хо, неравенства (!9) и непрерывности д(х) следует, что х, е х. но 7(ха ) ч г(х„) = у„при й ч со, йр е |п так что х, е Х,. Отсюда и из непрерывности р(х, Х„) имеем р(ха, Х„) т р(х„Х,) = 0 при й т со, йр Е Еп Теперь рассмотрим случай, когда множество Гз бесконечно. Если й е Гз, то Г(ха ) < Д, а д(х ) < аат < зцр ат = Сз в силу (19), Это значит, что (ха ) е М(Г„Сз), й е Гз, Поскольку а>о множество М(Д, Сз) ограничено, то (ха, йр е Гз) имеет предельную точку. Не умаляя общнасти, можем считать, что (ха ) х„, йр е Гз.
Из (19) и замкнутости Хо следует, что х„с Х. ПозтомУ Г(х )>Д. СдРУгойстоРоны,г(ха )<уы й Г Гз, так что !!ш Г(ха )=7(х,) <У. р а агхр ю Следовательно, 7(х„) = уы т. е. х, е Х„. Отсюда и из непрерывности р(х, Х,) получаем р(ха, Х„) р р(х„, Х,) = 0 при йр т со, йр е Гз. Обьединяя оба рассмотренных случая, заключаем, что для подпоследовательности (ха ), Р удовлетворяющей условию (16), справедливы равенства (17). Отсюда, повторив заключительные рассуждения из доказательства теоремы 1, убеждаемся в справедливости равенств (5) и для метода (12)-(14). Замечание 1 сохраняет силу и здесь. На атом закончим рассмотрение методов минимизации негладких выпукльж функций.
От. метим, что негладкие задачи в последние годы интенсивно исследуются, продолжается разработка различных методов их оешения 173; 226; 251; 256; 263-266; 302; 3!4; 318; 361; 386; 396; 426; 434; 495; 502; 542; 572; 586; 613; 718; 720; 769; 777; 7951. 1. Рассмотреть возможность применения метода проекции субградиента к задачам из упраж пений 4.6.1 и 4.6.3. 2. Описать метод (!2)-(14) применительно к задаче р(и) = !х+ у|+ |х — у! — а |и|, и е Х = (и = (х, у) е Е: и е Хо, д(и) = и — 1 (О]-, Хо — — (и= (х, у): х >О, у (О). 3.
Проверить условия теоремы 2 для задачи 7(и) = /(с, и)! -т 1п|; иеХ=(иеЕ"; и>0, д(и)=!(а,и)! — 1<0), где а, с е Е", Описать метод (12) — (14) применительно к этой задаче. 4. Пользуясь формулой (4,6,10), модифицировать метод (12)-(14) так, чтобы его можно было применять к задаче (1О) непосредственно, не сводя ее к задаче (1! ). 5. Пусть И' — открытое выпуклое множество, 7(х) — выпуклая функция на Иг. Показать, что вектор с„удовлетворяющий условиям |о,! = !и! !с! > О, с„ц ВУ(х), р а ддр| является направлением убывания функции 7(х) в точке х. 1. Этот метод приспособлен для решения задачи 7"(х) - |п1; х Е Х, (1) где Х вЂ” выпуклое замкнутое ограниченное множество из Е", функция 7(х) Е С|(Х).
Опишем его. Пусть х Е Х вЂ” некоторое начальное приближение. Если известно й-е приближение ха е Х, й > О, то приращение функции 7'(х) в точке х„можем представить в виде 7 (х) — )'(ха) = (У'(ха), х — х,) + о(!х — ха!). Возьмем главную линейную часть этого приращения 7 (х) = (7'(ха), х — х„), (2) и определим вспомогательное приближение х„из условий Ха б Х, !П17а(Х) = уа(Ха) = (1'(Ха), Ха — Х„). (3) Так как множество Х замкнуто и ограничено, а линейная функция )а(х) непрерывна, то точка ха из (3) всегда существует. Если функция 7",,(х) достигает своей нижней грани на Х более чем в одной точке, то в,качестве точки х, возьмем любую из них. Заметим, что если Х=(хеЕ": х>0, (а,,х)<Ь', з=1,...,рп; (а,,х)=Ь', з'=тп+1,,зГ, то задача (3) превратится в задачу линейного программирования, которая может быть решена известными методами (например, описанным в гл. 3 симплекс-методом), Укажем случаи, когда решение задачи (3) будет выписываться в явном виде.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
