Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 73
Текст из файла (страница 73)
Описанный выше вариант метода возможных направлений (2) — (4) на практике применяют редко. Дело в том, что когда в решении (е„о„) задачи (2) координата а,< О мала по абсолютной величине, направление е„, теоретически являясь возможным направлением убывания в точке и„, практически может обладать указанными свойствами в весьма слабой форме. Это оз- Ф иачает, что либо сд«(иь), еь)ж оь ж 0 при некотором 1 си 1„и направление е„почти «касается» множества У, не ведет «вглубь» У, а величина р„из (4) может оказаться очень малой, либо <У'(и„), е,> = о, = О, т. е.
вдоль е„функция 1(и) в точке и, убывает слишком медленно. В результате длина шага а» в (3) может получиться очень малой даже вдали от стационарной точки, и сходимость метода может оказаться очень медленной. Чтобы как-то избежать таких неприятных явлений, можно попытаться несколько варьировать множество номеров 1„в (2) и осуществлять спуск из точки и, только в том случае, когда получаемое из (2) направление е„обладает достаточно ярко выраженными свойствами возможного направления убывания.
Опишем один из таких подходов. Пусть и,ш У, з,> 0 — некоторое начальное приближение, Допустим, что )с-е приближение (и„, е,), и„ш У, з, > О, при каком-то й ) 0 уже известно. Определим множество номеров 1,= (1: 1 < 1 < и», — е,< йс(и«) < 0) (13) и решим вспомогательную задачу (2) при таком 1,. Задача (2) по-прежнему будет задачей линейного программирования и будет обладать хотя бы одним решением (ем с,) со«= 1п1п(О.Имен'а ются две возмолсности: 1) с,< — е,. В этом случае считаем, что е, является достаточно хорошим возможным направлением убывания в точке и„, и полагаем и„+,=и„+а,е„, 0<а„<р„, е„+,=е„ (14) где 1)» определяется из (4), а выбор а„может быть осуществлен одним из описанных выше способов.
2) — е„< о„< О. В этом случае считаем, что направление е, не обладает ясно выраженным свойством возможного направления в точке и„полагаем и„+,= и„е»ю е„/2 (15) и снова переходим к рассмотрению задачи (2) с заменой мпоясества 1, на множество 1„.«=(й 1 < 1 < т, — е„+,= — е,!2 < < дс(и„) < 0), надеясь на то, что на более широком множестве (при сужении 1, множество И'„, вообще говоря, расширяется) удастся найти лучшее возможное направление убывания и т. д. 366 ывтоды ыпнизы13лции Функции ьгногпх пвувыкнных (Гл, в Описание одной итерации метода возможных направлений для задачи (1) аакончено.
В методе (2), (13) — (15) имеются параметры ег, е„..., удачным выбором которых, вообще говоря, можно улучшить выбор направлений е, на каждой итерации, ускорить сходимость метода. Кстати, в (15) вместо деления пополам можно щ)инять иной способ дробления е„например, е,+, =0,9еь. 3. Следуя (11], пзучнм сходнмость ыетода (2), (4), (6), (13) — (15). Предварительно докажем несколько лемм.
Лемма 1, Пусть г(и), ус(и) гнС' '(У) (1= 1, ..., гп) и 7 — кскоторог фиксирсгенное л~ножгсгго номеров, ггягыя иг (1, 2...,, пь) (гсгможнссги 1 = И или 1 = (!...., т) нс исключаются). Для каждого и ш У положим а (и) = ш1па, гдг С(и) = ((с, о) = (с', ..., с", о) гнЕк+'. (Т(и), е> < о, С(и) (у((и), г)(о, (гид )с)) < 1, ) = 1, и). Тогда (о(и) — о(о)) <Ь)(п)и — о), и, ош У, (16) гдг 5 — константа Липтина для градиснтог У'(и), у (и) (г = 1, ..., сп). Доказательство. Возьмем прокзвольлые точкп и, сшУ.
Пусть (с, а) гн С(с), т, е. (у~(с),г)~~о, (шр, )г!!<1, 1=1, ..., и. (Х'(с), с) (о, Тогда <П(и), с> = (Т(с), г>+ <я(гь) — Т(с), е> < о+ Цп — о) ) с) < м. о+ Ци — о)))п н, аналогично (у( (и), г) (о+ 5) и — о) )lп, 1ш Т. Это значкт, что прн каясдом (с, о) си 6(с) точка (е, о+ с)п)и — с)) прннадлежит множеству С(и). Тогда а(и) =ш!по~о+А ~'и) и — о) для С(и) любых (с, о) гн С(с). Следовательно, о(и) < о(с) + 5)1п)и — и). Поменяв в эткх рассужденнях точкч и, о ролями, получим о(с) < о(и) + Пуп)и — с(. Из последних двух неравенств следует неравенство (16). Лемма 2. Пусть г" (и), у (и), ..., ую(и) ги Сг'1(У), шах зпр ~ у((и) ~ < со, гя(кю имп а псслсдсгатгльности (иь), (аь), (()ь), (ег), (ог) определены условиями (2), (4), (6), (13) †(15).
Тогда йь ) А~ ш!п(ег, (оь)), )с = О, 1, ..., (17) гдг Аь = ш!п(1/(Аггп); 4)(пй)) ) О, Ь вЂ” консгенга Липисиее для градиснгог П(и), д (и), ..., Ую (и). Доказательство. Если де= со, то неравенство (17) верно. Поэтому пусть ()ь < сю. Из определевкя (4) величины рь н замкнутостн У следует, что из+ Оьсь ш У н уг(иь+ 6ьгь) = О хотя бы для одного номера 1. Зафнкснруем одкп нз таких номеров 1.
Мо)кет оказаться, что уг(иь) < — еь. тогда еь( — у((иь) =у((из+бага) — у((иа) =(у((ие+6()ага), ()ага)~ ~ А ))а(га)(А угп3а, т. е. Оа~)е /(А (/и). МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНПН 307 6 з) т т Если же окааалосьч что — еа < уг(и») <О, то ггн Ха н1у» (иа), е»Х (аа( ~0. Допустим, что оа ( О.
Тогда направление е» является возможным в точке иа и заведомо 3» ) О. По определению ()а имеем уг(иа+ аеа) (0 прн всех а(0 ( а ( 6»]. Кроме того, ут(и»+ (1»еа) 0 по выбору номера 1. Тогда 0)~ у» (из+ аеа) — уг (иа+ 6»е») = (у,. (иа+ 3»еа), е»Х (а — ба)+ -(-о(|а — 6»|) плп (у,. (иа-). ()аеа), в )) о(|и — ()а|)(6» — а)» при всех а (О ( а < 3»). Отсюда прн а-ьỠ— 0 получим (у,. (и + раса), в»Х) О. Тогда |па | = — оа(( — у»(иа), е»Х(туг(и + 6»еа) — у,. (и,), е»Х~ (ьр»|в» | (Ьп()а, т. е. ()а) !о»)/(пй).Если о» = О, то последнее неравенство также остается верным, так как согласно (4) всегда 6» ) О.
Объединяя обе полученные оценки для бы приходим к оценке (17). Лемма 2 доказана, Лемма 3. Пусть Х(и), уг(и) »НС''(У) (1= 1, ..., т), Пусть, кроме того, в процессе (2), (4), (6), (13) — (15) на некоторой й-й итерации окагалось оа ( — еа. Тогда Х(иа) Х(иа+»)) Азш/п (ба|па|' оа| 6» (18) где Аг = шш(1/2; 1/(2пб) ) ) О. Дока а а тельство.
Из неравенства па< — еа и определения еа, оа следует, что (Х'(иа), еа) ( оа < — еа < О. Кроме того, еа является возможным направлением в точке иа и, следовательно, 3» ) О. Из (6) и леммы 2.3А имеем Х(и ) — Х(и + )) Х(иа) — (п( /а (а) — 6») Х(иа) — Х(из+ага) — ба) о колба з — а(Х'(иа), е Х вЂ” ос~С|в,|з/2 — 6 ) — ао„— пспй/2 — 6» (19) при всех а (О < а ( ба).
Положим здесь а = ш(п(3», | о»!/(пЬ) ). Может случиться, что а = ))а < |оа!/(пЬ). Тогда из (19) получаем Х(иа) — Х(и»т~) ) а|па| — а а пб/2 — ба) 3»!о»| — 6»(!щ|/(пб)) (пЬ/2)— — ба Ва(о»|/2 — 6». Если же а = |о»|/(пЦ ( 9», то из (19) следует Х (и„) — Х (иа+ ) ) оаз/'(пЬ) — (паз/(пЬ)з)(пб/2) — 6 = оаз/(2пЦ вЂ” 6». Объединяя оба рассмотренных случая, приходим к оценке (18). Теорема 2.
Пусть у»дикции Х(и), уг(и) (г = 1, ..., т), определены и выпуклы на Е"; множество ХХ ив (1) регулярно; Х(и), уг(и) ш Сг '((Х), Ае = шах акр| у. (и) | < со. Пусть задача (1) имеет решение, т. е. Хг >— акглю и со, Уе Ф 9,и начальная точка иге ХХ токава, что множество Мг(ие) = = (й и гн У, Х(и) ( Х(иг) + 6) ограничено, Тогда при любом выборе ег ) 0 для последовательности (и»), определяемой условиями (2), (4), (6), (13)— (15), справедливы равенства 1(ш Х (и,) = Х, Иш р (и „(/ ) = О. ,20) а аг а оа Доказательство, Сначала установим, что 11ш(Х(и„) — Х(и,+д)) = О, (21) Если оа ( — еа, то из (14), (6) имеем Х(иа+~) = /а(аа) < /а(0)+ ба = Х(иа)+ + ба. Если же — еа < па (О, то из (15) следует Х(и»+ь) = Х(иа) ~ Х(иа)+6».
303 мвгады мг[нимизвции Функций ынОГих переменных [Гл, з Таким образом, 1 [иа) )~ 1» > — со и, кроме того, » 1[из+ )<1(иа)+ба, а=0,1, ...; ~ б =5< . (22) а-з Согласно лемме 2.3.2 тогда существует Вшу(иа)~)1». Отсюда следует а.»» равенство (21). Далее, покажем, что 11ш за — — О. Согласно (14), (15) последовательь» ность (сь) получается дроблением и не возрастает. Допустим, что 1кп е[, ь-»»» в > О, Это влачит, что в процессе построения (иь) было конечное число дроблений и еь= с > 0 при всех й > йе Ив (14) тогда имеем аь ( — ел = — е, т. е. [аз[ > е, й > й». В этом случае согласно леыме 2 ()ь > А,е, й > > йв Поэтому из леммы 3 получим 1(из) — 1(ш»») > А,ппп(А,е'[ е')— — бь (й > зе), что противоречит равенству (21).
Йтак, показано, что 1пп е, О. *-» Пусть [»» ( [», ( ... ( [», <... — номера тех итераций, когда происходит дробление ем Согласно (14), (15) тогда — сь ( аь ~0 (г=1, 2, ...). Следовательно, 1[ша =О. Теы самым установлено, что существует хо"» тя бы одна подпоследоватсльность [аа ), сходящаяся к нулю. Возьмем произвольную подпоследовательпость [аа [-»О.
Покажем, что тогда любая предельная точка соответствующей подпоследовательности [и„[ принадлежит множеству ([». Из (22) следует, что 1(иь+») ( »1 ~1(и») [-6 (я =О. 1, ...), т. е. (иь)»нМ»(и»). По условию множество ЛХ»(и») ограничено. Поэтоъ[у можем считать, что взятая выше подпоследовательность [иа ) сходится к некоторой точке и». Далее, множество номеров 1», определяемое согласно (13), представляет сооой подмножество конечного числа поыеров (1, 2, ..., гп), поэтому число различных множеств 1» »конечно.
Это значит, что среди [1а, г = 1, 2, ...) найдется хотя бы одно Г' множество 1„=1, которое повторяется бесконечно много раз. Выбирая при необходимости подпоследовательности, можем, таяны образом, считать, что [аь ) "».0 [ид )-» и» 1[ =1 г=1 2 Согласно леыые 1 при О(иа 1 = И'ь имеем г) г [аа — а(и») [ [а(иа ) — а(и») [(Ь [»гп[и, — и [-ьО, и.
е. 11ш а1иь ) =1!ш а = 0 = а(и ), где а(и,) = 1п[ а, 6(и») =* а[и») » [(е, а)»ы й"+~: (1' (и ), с) (~ а, ([[е (и ), е) ( а, ! эи 1[ [ е[ [ ( 1, 1 = 1,... ..., п). Рассмотрим задачу (7), соответствующую точке и» =1!ш иь . Покажем, г~ »»»' что И»» ~6(и»]. По определению множеств 1 = 1д = [И 1 ~([я;г, е[, я, 31 (иа ) ~ 0] (г = 1, 2, ...). Отсюда при г-»- о» получим Ю[ (и») = 0 для всех [си[. Это аначит, что 1[:1», т. е, в определении множества И'» число ограничений типа неравенств но меньше, чем число таких ограничений в определении 6(и»).
Тем самым установлено, что И'» Сб (и»). А то. МЕТОД ЛИНЕАРИЗАЦИИ гда, замечая, что одна и та же функция на более широком множестве име- ет меньшую нижнюю грань, получаем о„= !п1 о) 1п1 о=о(ию) =О. и'ю о(ию) С другой стороны, (О, 0)»и И', поэтому и < О. Следовательно, о О.
Поскольку задача (1) по условию выпукла и множество (»' регулярно, то согласно теореме 1 ию»н (Гю. Выше было доказано существование предела 1!ш х (ие). Теперь можем А-» ю сказать, чему равен этот предел: !пп ю (иа) = 1!ш ю' »'иь ) = у (ию) = ую. ( ь,) Таким образом, построенная последовательность (ию) минимизирует функци»о» (и) па множестве !»'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
