Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 72
Текст из файла (страница 72)
я~(ид)< О, то в силу непрерывности функции я<(и) неравенство я,(ид+аед)<0 сохранится при всех а (0< <а<а,), где а,) 0 — достаточно малое число. Положим а, шш (а„..., а ) ~ О. Тогда я;(ид+аед)<0, 1=1, ..., и; 0<а<а„ т. е. е,— возможное направление множества 1/ в точке и,. Далее, взяв при необходимости число а,) 0 еще меньшим, можно добиться выполнения неравенства 1(и„+аз„) — 1(ид)= <1'(и,), е„>а+ о(а) < <а[ад+о(а)/а) <О при всех а, О< а<а,. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ Тем самым показано, что если (е„с„) — решение вадачи (2), причем с„< О, то е,— возможное направление убывания функции у(и) в точке и, на множестве у. Используя найденное таким образом направление е„следующее (й+ 1)-е приближение определим так: и,+, — — и, + а„е„, 0 < ао < рм (3) (4) где г/ апр(а: и„+8е,~и У, 0<ай<а) )О.
Выбирая а„в (3) различными способами, будем получать различные варианты метода возможных направлений. Перечислим некоторые способы выбора ао. 1) Величина а, может выбираться из условий 0(ао(~ы ~о(аь) = ш1 ~о(а) = ~о ', о<аась ~А (а) = У (иь + ае„). (5) Х(ид + аоеь) ( (1 — Ль) Х (ид) + Лф„, О ( Л ( Ло ( 1. 2) Если функция У(и)шС''(У) и константа Липшица 5 для градиента 1'(и) известна, то в (3) в качестве а„можно принять а, =ш(п(р„; !о„!Ь-').
3) Возможен выбор а, из условий Х(и„) — У(и„+ а,ео) > ссссо!, 0 < а, < 5м 0 < е < 1/2. Для определения такого а„сначала можно положить а,= ро, а затем при необходимости дробить эту величину. 4) В тех случаях, когда трудно оценить величину б„из (4), приходится довольствоваться нахождением какого-либо а„) О, обеспечивающего включение и,+ а,е„он У и условие монотонностп У(и„+а,е,)<1(и,). Для этого обычно выбирают какую-либо постоянную а) О, полагают а„=а и проверяют условие монотонности и принадлежность точки и„+, множеству У; при необ« ходимости дробят величину ах=а, добиваясь выполнения упо мянутых условий.
Для минимизации функции ~о(а) могут быть использованы известные методы (см., например, гл. 1). Точное решение задачи (5) удается найти лишь в редких случаях; возможно также, что на некоторых направлениях е„величина р,= и нижняя грань функции Яа) при а) 0 не достигается. Поэтому вместо (5) на практике целесообразно употреблять такой способ выбора а,: 0(аь(~)м ~о(ао)(~о+ бм бь)0, ~ ба = 5(0 (6) ь=о 303 мктоды минимизации Фънкцин многих пвгкь»киных»гл. з Один шаг метода возможных направлений для задачи (1) в случае о„(0 описан. Попутно выяснен смысл вспомогательной задачи (2): минимизируя о, мы добиваемся того, чтобы направление е„было как можно ближе к направлению антиградиента (это обеспечивается условием <У'(и»), е„> (о) и в то же время оставалось возможным направлением для множества П в точке и„(это обеспечивается условиями»,д»(и»), е») <о, »»вТ„), причем чем меньше о, тем ярче выражены указанные свойства направления е„.
Кстати, если Т» = Ы, т. е. и„»и»п1 У, то е„= = — с»У'(и,), а = ( шах ~Х„; (иь) !) — ')Π— направление антигради- ~»с»ча ента. Теперь рассмотрим случай, когда в решении (е„, о,) задачи (2) координата о„=О. Как видно из (2), это может случиться, Р например, при У'(и,)=0 или д»(ид) = 0 для некоторого номера » ш 1ь При о„= 0 уже нельзя гарантировать, что е„будет возможным направлением убывания.
В этом случае итерационный процесс (2) — (4) прекращается. Оказывается, при о,=О точка иь является стационарной точкой задачи (1), нли иначе говоря, в точке и, выполняются необходимые условия минимума, выраженные в теореме 4.81. Для выпуклой регулярной задачи (1) условие о,= 0 гарантирует, что из ~ У„. Покажем это. Теорема 1. Пусть Яункции У(и), у»(и) (1 1, ..., и) определены на Е", г'(и), д»(и)»иС'(У), где множество У задано услоеиял»и (1), и пусть задача (1) имеет решение, т. е. Хв) > — ь~, П„чь 8. Тогда для любой точки иь ~ Пе задача о-»- 1п1; г = (е, о) ен И' = ((е, о): (Г (и.
), е) < о, (у»(и ), е) <о, »я 1в, )е»((1, 1=1, ..., и), (У) где » =(»: 1<»<т у»(и,„) = 0), необходимо имеет решение (е, о ) с о„= ш1по = О. Если, кро- И'е ме того, г'(и), у»(и) выпуклы на Е", а множество У регулярно (см. определение 4.9.2), то всякая точка ие ~ У, для которой задача (7) определяет величину о„= 1п1 о = О, является решением Я'э задачи (1). Доказательство.
Необходимость. Пусть и„енУь. По теореме 4.8.1 тогда существуют множители Лагранжа Л,» ... ° °, Л, неотрицательные и не все равные нулю, такие, что Лзу'(ие) + лч Л;У,(и„) = О, Л У»(иь) = О, 1= 1, °, °, »пе (8) »=1 Если» ф Тю то из второго равенства (8) следует Л» = О, поэтому МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕННН первое равенство (8) можно переписать в виде Л, Х' (и») + ~~в Л*;б1 (и ) = О. 1М1» (9) Возьмем любуго точку (е, о) я 11' .
Тогда (Х'(и»), е) ~ (а, (б (и»), е)~(о (1ен1„). Умножим первое из этих неравенств на Л,)0, остальные — на соответствующие Л1 ~)0 и сложим. С учетом равенства (9) получим ' Л» Х' (и„) + ~ Л,'д1' (и»), е ' = 0 ~ о ('о + Л1 + ° ° ° + Л~). 1Е1» Г Д о с т а т о ч н о с т ь. Пусть теперь Х (и), я1 (и) выпуклы на У, а множество 11 регулярно, пусть для некоторой точки и ~У задача (7) определяет величину о„=!Н(О=О. Покажем, что и» тогда и» сна». С этой целью введем конус К = (г = (е, о) ен Е"+'. (Х' (и»), е) + ( — 1) о < О, (д; (и»), е) + ( — 1) о з-.
О, 1 ен 1» ), образующими которого являются векторы с =(Х'(и»), — 1), с;= = (б1(и»), — 1) (1 а= 1»). Покажем, что вектор 11 = (О, 1) 1и К* двойственный к К конус. Из (7) с учетом 1п1а= о = 0 имеем тг* (а,г)=(О,е)+1 а=о)~а»=0 (10) для всех г = (е, а) жК, для которых !е'! < 1 (1= 1, ..., и). Однако условие !е'! (1 (1=1, ..., и) здесь можно отбросить, и неравенство (10) на самом деле верно для всех гж К.
В самом деле, пусть г =(е, а)ю К и )е1! ) 1 для некоторого номера у (1(У ~ и). Тогда )!е(! = шах ! е1 !)1. Положим 1Е>зэ г = (е, а), е = е1!!е!!, а а1)!е)!. Ясно, что з ен И'». Следовательно, <И, г> = <д, з>/)!е!! = а = о/!!е!! > О, так что <й, г> = о ~ О. Тем самым показано, что неравенство (10) верно для всех г 1н К, т. е. д 1в К». По теореме 4.9.3 тогда существуют неотрицательные числа Л», ..., Л,*, такие, что 1! (О 1) Лого Х Л~е1 ив 1» Вспоминая определения векторов с,,с, (11н1„), отсюда имеем 0 = — Ло Х' (и,) — ~ Л1 д1 (и») = О, 1 = Л» + Х Л1 ° (11) 1Н1» 1е1» Вроме того, из определения множества 1„следует, что я1 (и») = = О, поэтому Л;д1(и ) = 0 (1~ 1»).
Доопределим Л1 = Опри всех 304 методы минимизАции Ф1'нкции мнОГих пеРеменных 1гл, з 1ф1 . В реаультате с учетом первого равенства (11) получим Лээ" (и ) + ~1 Л1д1 (из) = О, Л;41 (из) = О, 1 = 1, ..., т, (12) 1-1 ч а а из второго равенства (11) следует, что не все числа Лз1 Л1 (1е= ~ 1 ), равны нулю. Покажем, что Л,)0. Если 1„= 8, то из (11) сразу имеем Л,' = 1. Допустим, чтоХэФ 8, но тем не менее Л, = О. Тогда среди В неотрицательных чисел Л, (1 ее 1з) найдется хотя бы одно положительное число.
Пусть ЛР)0, р~1„,. По условию мноя1ество У регулярно, поэтому существует точка й ~ У такая, что «,(й)< 0 для всех 1= 1, ..., т. Поскольку 1,„~ 8, то и ~из. В силу выпуклости множества У тогда аи +(1 — а) иэ=ив + а(иа — иэ) ~ У при всех а (О < к < 1). Это значит, что направление с= и — и чь чьО является возможным для множества У в точке иэ. Из выпуклости функций д1(и) для всех 1ее 1э имеем 0) «1(и)= = Е1(п) — бз(и„))(41(иэ), и — и„) = (д (иа), е). Поэтому ~ Л, (б;(и„,), е) <Лр(др(иэ), е) <О. Но с другой стороны, из пер- 1-1 вого равенства (12) при Лэ — — 0 получим ~ Л1 (Е1(иэ), е) = О.
1=.1 ч Полученное противоречие показывает, что Л, ) О. Разделив первое равенство (12) на Л,') 0 и сделав очевидные переобознат чениа, ИРиДем к РавенствУ У'(иа) + ~ Л1д1(иэ) = О. ФУнкдпн 1=1 Лагранжа Ь (и, Л*) = Х (и) + ~ Л1*41(и) выпукла по и 1н Е" иа-за 1=1 выпуклости Х(и), Е1(и) и неотрицательности Л1 (1 = 1, ..., и). Поэтому предыдущее равенство в силу теоремы 4.2.3 равносильно условию Ь(иэ, Лз))Ь(и, Л") при всех и ~ Е". Отсюда и из второго равенства (12) с помощью леммы 4.9.1 и теоремы 4.9.1 получим, что иэ ее У .
Теорема 1 доказана. В невыпуклых задачах условие о„ = 0 не является достаточным для оптимальности точки и~. Это показывает следующий Пример 1. Пусть У(и) =х+созу, и1н У=(и=(х, у) 1я 1ИЕ'1 д(и) = — х(0) (ср. с примером 4.8.1). Воаьмем точку и,„= (О, 0). Тогда 1'(в )= (1, 0), л'(и ) = ( — 1, 0), И' = ((е, а) = =(е1, ез, О): е1<о, — е1<о, (е1(<1, !ез(<1).
Отсюда !е1!<О при всех (е, О) ее ИГ . Это значит, что 1п1о = а = О, причем ннж1те няя грань достигается при е = (О, 1) илн за = (О, — 1), О =О. Но адесь и = (О, 0) не является точкой минимума У(и) на У. Любо- $»1 ьтетод воэмоясных ньпглвленсий зоб пытно заметить, что векторы е„ = (0,1) или (О, — 1) в данном случае являются возможными направлениями убывания. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
