Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 69
Текст из файла (страница 69)
й=з 2. Описанный выше ъсетод проекции субградиента после некоторой модификация можно использовать для решения следующей задачи 233 мктоды минимизации егункции многих лкукмкнных 1гл. ь выпуклого программирования: 1(и)-~-1п(; ишУ=(ишЕ": ишУ„У,(и) <О, с= 1,, ю), (10) Заметим, что система неравенств ХВ(и) <0 (1= 1, ..., и) равносплька одному неравенству у(и) <О, где у(и) = шах уг(и) (иш У). Кроьге тотлглтл го, из выпуклости функций йч(и) (1= 1, ..., т) на Ус следует выпуклость у(и) на У, (см. теорему 4.2.7). Поэтому задачу (10) можно переформулировать в виде эквивалентной задачи Х(и) - ш(; и ш У = (и тн Ус, у(и) < 0), (11) также являющейся задачей выпуклого программирования. Предположим, что субдифференциалы д1(и), ду(и) непусты при всех и ш У,.
Следуя (334), рассмотрим метод иа+т=УП (иа каса) 5=0 1' '" иоан Уо (12) где (аь) выбирается из условий аа)0, /с=О, 1, ..., ч', аат+т= ос, ~' иве<со, 0<7<1, (13) а=о а=о а субградиенты (са) таковы, что сати дХ(иа) пРи У(иа) < иа ти са ш дд(иа) пРи У(иа) ) ига. (14) Таким образом, метод (12) — (14) работает так: если ограничение у(и) <0 при и = иь не нарушено или нарушено немного, то ьшнпмизируем функ- цию 1(и), а если нарушение этого ограничения велико, то минимизируем функцию у(и). Если функции Х(и), у(и) дифференцируемы на У„то в (12), (14) вместо сь нужно брать соответствующие градиенты 1'(иь) или у'(иа).
В качестве последовательности (аь), удовлетворяющей условиям (13), мо;кно взять, например, па = С(а+ 1) '*, где С = сопят) О, а чис- ло и таково, что 1/2 < и < (1+ 7) '. В частности, при а = 3/5, 7 = 1/2, С = 1 получим аь = (а + 1) г'г (а = О, 1, ...). Т е о р е м а 2. Пусть Ус — выпуклое вамкнутое миоасество ив Е", 1дункиии 1(и), у(и) определены и выпуклы на некотором открытом выпук- лом многкестве И', содерэкаи1ем Ус (напрпмер, И' = Е"). Пусть Хе = ш11(и)) — со, мноксеспгво Уе точек минимума задачи (И) непусто, и ограничено и, краме того, епр зпр (с(=А<ос.
«ып сыо11йгс1ду/йг Тогда д.гя последовательности (иа), опредсллемой условилми (12) — (14), справедливы равенства (5). Д о к а з а т е л ь с т в о. При выполнении условий теоремы функции 1(и), у(и) непрерывны на Ус, субдифференциалы дХ(и), ду(и) непусты, выпуклы, замкнуты и огранлчены при всех и тн Уо (см. теоремы 4.2Л5, 4.6Л, 4.6.2), а множество У„выпукло и замкнуто (см. теорему 4.2Л и лемму 2.1.1).
Покажем, что множество М(Сь Сг) = (и тн Уо. 1(и) < Сь д(и) < Сг) ограничено при всех С ) 1п( 1 (и), С )!п( у (и). В самом деле, /тХ(Хв, 0)= по пв Уь ограничено по условию. Тогда по теореме 4.2Л7 множество М(Сг 0] = (и: иш Уо, у(и) <О, 1(и) <СД ограничено при всех С > (п(1(и). 1 е метод пРОекции суБГРАдиеитА 6 3) Теперь, фиксируя любое Сь по той же теореме 4.2Л7 получаем ограниченность М(Сь С,) при каждом С ) 1п1 л(и). г ие Нетрудно видеть, что неравенства (6), (7) сохраняют силу и для метода (12) — (14).
Из (7) имеем ~~ ив+тазу(с,, иг — у, (ид)) <В«оо, с=1, 2... ° (15) А=Е Отсюда следует существование номеров 1и < Аг «... А < ... таких, что (с,, и, — Ус (и ))(ауь, ив=1,2, (16) В самом деле, допустим, что (16) не имеет всеста. Тогда (с,, и — У, (и,)) > сот при всех А = О, 1, ... Отсюда и из (15) имеем ~ сов+ты ~~ аа (сг, иа — Уп (иь)) ~ В < оо, г = 1, 2, ...
А-О А=О что противоречит расходимости ряда ~э о +". в+т А О Тем самым показано существование подпоследовательиости удовлетворяющей условию (16). Докажем, что 11ш У (и, ) = с „11ш р (ии, (Го) = О. ° о со о1 ов оо (17) Сначала убедимся в том, что са Шдс (иа ), св=в1, 2..., (18) Для этого достаточно показать, чтод(иь ) < аа (ов = 1, 2, ...), и ваном.
т нить условия (14). Допустим, чтод(ив ) > ат при некотором ш > 1. учитывая, что тогда са си ддуиа ) И, крОмЕ ТОГО, Уп гиа )си С с П, т.е. т ( ов) о', во) л(У (и„)) <О, из (16) имеем сот «с(и )<г(иа ) — г(УО '(и ))< «(с, и, — Уп (иа ))(даат Получили противоречивое неравенство. Включения (18) доказаны, и попутно установлено, что д (иа ) « а~ ~, св = 1, 2, ... (19) Множества номеров (А ), удовлетворяющих условиям (16), представим в виде объединения непересекающихся множеств 1 = (А,„: У(иа ) й >~ со) и 7 (Аю: э (иа ) с со).
290 метОды минимизАции Функции мнОГ11х нереыенных (гл. э Сначала рассмотрим случай, когда множество П бесконечно. Из (16), (18) имеем 0 < у [иь ) — У» = у [за ) — у (5»и» [ва )) < < (са , и„ вЂ” У [иа )) < аа , й »и 7 . Отсюда следует, что У (иь ) -» У» при зг-» оо, у ш 11.
Тогда з (иь ) < ~С < с», и, кроме того, согласно (13), (19) д(иь '1(се~~ <зпра„" ь>о = С < со, т. е. [и„[ ш М(С, С ) (й ш У ). Так как М(С, С ) ограничено, то [и„, у„,зм 7 ] имеет хотя бы одну предельную точку. Не умаляя общности, можем считать, что [иа [-» л» (» зи Х ). Из замкнутости 0», неравенства (19) и непрерывности у(и) следует, что и» ен У. Но»(иа 1-»» (и») = х» при л~-~соз~ ш П, так что и» ш У».
Отсюда п "т. из непрерывности р (и, У») имеем р (иа, С ) -» р (и», У») = 0 при 7с + со л»ъ ш 11. Теперь рассмотрим случай, когда множество 7» бесконечно. Если з ш »и Гь то» (иа ) < У», а у(иа ) < азу < зпрсгьт = С в силу (19). Это 7й ь>з значит, что(иа ) шМ(У», С ) (»,вшу). Поскольку множество М(У», С ) огРаничено, то [иа, Е зм 7 ) нмеет пРеДельнУ1о точкУ. Не Умалал обшности, тюжем считать, что [иь \- л», й„,<а1.
Пз (19) и замкнутости У» ь»о следует, что и ш У. Поэтому У(и )>У». О другой стороны, У(иа 1<У» »~т (й ш 1 ), так что Пш У 7иь ) = У (и») < у». Следовательно, Ь Ыг,а»» з' л (и») =У», т. е. и зн (1 . Отсюда и мз непрерывности р(и, У ) получаем р(иь У»)-~.р(и», У») =0 при уж-~-о», у,„ш 7 . Объединяя оба рассмотренных случая, закл1очаек, что для подпоследовательности [иа Н удовлетворяющей условию (16), справедливы равенн[' ства (17). Отсюда, повторив заключительные рассуждения из доказательства теоремы 1, убеждаемся в справедливости равенств (5) и для метода (12) — (14).
Замечание 1 сохраняет силу и здесь. На этом закончим рассмотреяпе методов мннимлзаппи негладких выпуклых функций. Отметим, что негладкие задачи в последние годы интенсивно исследуются, продол1кается вазраоотка различных методов нх решения (27, ПЗ, 123, 127, 132, 133, 148, 156, 158, 214, 219, 235, 306, 334, 336, 339). У п р а ж н е и и я. 1. Рассмотреть возможность применения метода проекции субградиента к задачам из упражнений 4.6.1 и 4.6.3. 2. Описать метод (12) — (14) применительно к задаче 7(и) = [х + у[ + [х — у[ -» ш1, и ш (Г = (и = (х, у) ш ЕН и ш У», 8(и) из — 1 < О), У» = (и = (х.
у): х ) О, у ) О). 3. Проверить условия теоремы 2 для задачи 7(и) = [(с, и)[ -» 1п(; и а У = (и а Е ; и ) О, д(о) = [(а, и>( — 1 < О), где а, сш е», Описать метод (12) †(14) прэмел1ыельно к атой задаче. 4, Пользуясь ф1ормулой (4.6Л2), модифицировать метод (12) †(14) так, чтобь1 его можно было применять к задаче (10) непосредственно, пе сводя ее к задаче (11). 291 МЕТОД УСЛОВНОГО ГРАДИЕНТА 5. Пусть Яс — открытое выпуклое множество, Х(и] — выпуклая функция на Б'. Показать, что вентор се, удовлетворяющнй условиям (с (= (и( (с()0, с «иду(и), сиа.цш является направлением убывания функции Х(и) в точке и. 9 4. Метод условного градиента 1.
Этот метод приспособлен для решения задачи 1(и)- ш1; иж 11, где «1 — выпуклое замкнутое ограниченное множество иа Е", функция 1(и)«иС'(<1). Опишем его. Пусть и,«и<1 — некоторое начальное приближение. Если известно й-е приближение иьш 1«' (й>0), то приращение функции 1(и) в точке и, можем пред- ставить в виде 1(и) — 1(и,) = <1'(и„), и — иь>+ о((и — иь) ). Возьмем главную линейную часть этого приращения 1„(и)= <1 (и„), и — иь>, и определим вспомогательное приближение й, из условий ил«1, «п11а(и) =1а(иа) =(1'(иа), иа — иа). (3) и Так как множество «1 замкнуто и ограничено, а линейная функция 1,(и) непрерывна, то точка й, из (3) всегда существует.
Если функция 1,(и) достигает своей нижней грани на «1 более чем в одной точке, то в качестве точки й, возьмем любую из них. Заметим, что если <1=(и«нЕ": и>0, <аь и) <(««, 1= 1, ..., т; <аь и) = Ь«, « = т+ 1, ..., а), то задача (3) превратится в задачу линейного программирования, которая ыожет быть решена известными методами (например, описанным в гл. 3 симплекс-методом). Укажем случаи, когда решение задачи (3) выписывается в явном виде. Если (1=(и=(и', ..., и"): и«<и«~р«, 1=1, ...,и) — п-мерный параллелепипед, то функция 1а(и) = ~'~ 1 «(иа) (и— «1 ъ« — иа) или ~, 1„«(и„) и', очевидно, достигает своей нижней 292 методы минимизАции ФункциЙ мнОГих пегеменных»Гл, ь l 1 а1 грани на»»' в точке ид = (ид, ..., ид), где а », .»„»(ид)) О, !)»,,» „» (ид) < 0; в случае У„»(ид) = 0 здесь возникает неопределенность и в качестна ид можно взять любое число из отрезка (аь (1;] (обычно берут из= а», илп ид = (3ь пли и'„=(а»+ »3»)»2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
