Ф.П. Васильев - Методы оптимизации (1125241), страница 49
Текст из файла (страница 49)
Тогда множество (12), являющееся пересечением выпуклых множеств: Хы..., Х, М само будет выпуклым. П 8. Рассмотренное в теореме 3 условие оптимальности сформулировано для непрерывнодифференцируемых функций, Однако аналогичное условие можно получить при гораздо меньших ограничениях на функцию, используя лишь существование производных по направлениям. Напоминаем, что лромзвооной функции 7(в) а точке и ло направлению е, ]е]=-1, называется число оз"(и] . 7 м-1-зе — 7 и (13) ге -с'.о Заметим, что для определения производной по направлению в точка о нужно, чтобы и-ь зе принадлежало области определения 7(м) при 0 < з < зо хотя бы при малом то > О.
Оп р еде лен и е 3. Пусть Х вЂ” некоторое множество из Е", пусть и е Х, Направление е МО называется возможным в точке и, если существует число ~ > 0 такое, что и+ За Е Х при всех з, 0 < 1 ( то, Иначе говоря, достаточно малое перемещение из точки и по возможному направлению не выводит за пределы множества Х. Очевидно, если о е 1п1 Х, то любое направление е ~ 0 является возможным в атой точке, В граничных точках множества возможное направление может и не существовать. При мер б.
Пусть Х =(м =(му) е лсзс е> О, аз < р(2вз). Нетрудно видеть, что в граничной точке (О, 0) нет ни одного возможного направления, Для выпуклых множеств Х, содержащих не менее двух точек, приведенная з примере б ситуация невозможна: в любой точке о такого выпуклого мномсества Х имеется хотя бы одно возможное направление, причем направление е мО будет возможным в точке о тогда и только тогда, когда существуют точка ее Х, о ~ о, и число т > 0 такие, что е = т(е — м). Таким образом, если функции 7(в) определена на множестве Х, а направление е, ]е] =1, ЯвлЯетсЯ возможным в точке и е х, то фУнкциЯ Р(1) = 7(о+ те) опРеделена на отРезке [О, то], где зо > О, и с(г"(и)/ое = Р'(+0) — пРаваЯ пРоизводнаа в(1) в точке з = О, 166 Гл.
4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 5 2. ВЫПУКЛЫЕ ФУНКЦИИ 1б7 исключается), пусть функция д(и) выпукла на выпуклом множестве Х с. Е'", причем д(и) е [а, Ь1 при всех и е Х. Тогда функция у(и) = )р(д(и)) выпукла на Х. Д,ок,аз,ат,ел ь ство. Возьмем произвольные и, ие Х и о е'[О, Ц.
Тогда ,7( +(1 — )и) = ч (д( +(1- )и)) < р(од(и)+(1 — )д(д)) < <,о!р(д(и)) + (1 — о))р(д(и)) = о)'(и) + (1 — оаэи), что:и твребовалось. П Иногда удобнее пользоваться другим вариантом этой теоремы: если функция )р(д) выпукла и не возрастает на отрезке [а, Ь], а д(и) вогнута на выпуклом множестве Х с Е", д(и) а [а, б[ при и е Х, то функция 7(и) = уэ(д(и)) выпукла на Х. Следствие 1, Если функция д(и) вьгпукла а неотрицательна на выпуклом гмножеотве Х, то функция 7(и) =(д(и))" выпукла на Х при всех р > 1. Следств)исе '.2, 'Если функция д(и) выпукла на выпуклом множестве Х, то функция д',(и) = (гпах(0; д(и))г = (дт(и))г выпукла на Х при всех р >:1. С л е д с т.в и,е 3, Если функция д(и) выпукла на выпуклом множестве Х, причем д(и) < 0 пра всех и е Х, то функции у(и) = — '1,/д(и), у(и) = шах( — 1п( — д(и)); Оту", Р > 1, выпуклы.на Х Как увидим ниже, функции, указанные в следствиях к теоремам 7, 8, будут использованы при описании различных методов минимизации (нат пример, в методах штрафных и барьерных ! функций и др.).
6 7. Выпуклые функции являются удоб- ным средством для задания выпуклых мноер1 7' жеств. Это связано с тем, что надграфик всякой выпуклой функции является выпуклым множеством. 0 п р е де л е н и е 2. Надграфиком (или эпиграфом) всякой функции У(х), определенной на множестве Х с Е", называется множество (рис. 4.5) Рис. 4,5 )(Надграфик) Ер! У = ((х, .у) Е Е" " '. х Е Х, у > У(х)). Теорема 9. Для того чтобы функция У(х), определенная на выпуклом множестве Х была выпуклой на Х, необходимо а достаточно, чтобы ее надграфак был выпуклым множеством.
Доказательство. Необходимость. Пусть функция 7(х) выпукла на выпуклом множестве Х. Возьмем две произвольные точки к) = (и„.у,), х, = (ит, у,) Е ер1,7 и составим их выпуклую комбинацию л = ог, + (1 — о) хт = (ои, +(1 — о)из, се у, +(1 — о ) уз), 0 < сз < 1.
Из выпуклости Х следует, что и = ои, +(1 — о)и, Е Х. Из выпуклости функции 7'(х), учн- тываЯ) что з„зтЕ еР!,7, имеем 7(и„) < оУ(и )+(1 — о)7(ит) < от +(1 — о) У,. Следовательно, х е ер! 7", при всех о е [О, Ц. Выпуклость, ер!,7 доказана. Достаточность. Пусть ер! 7 — выпуклое множество. Возьмем произвольные иы и, я Х и о е [О, Ц.
Тогда х, = (и„,У(и) )),, хз = (и„, д (ит)) е ер1 Т. В силу выпуклости ер! 7' точка л = ох + (1 — о)к е ер! у. Это значит, что о7(и)) + (1 — о) у(их) < у(ои) + (1 — о)ит). Выпуклость 7(х) доказана. П Теорема 10, Пусть Х вЂ” выпуклое множество;, а функция 7(х) выпукла на Х.
Тогда множество М(с) = (и: и е Х, 7(и) < с) выпукло при любом с. До к аз а тел ь ство. Возьмем произвольные и, ие М(с), о е[0, Ц. Используя выпуклость множества Х и функции 7(х), имеем 7(ои+(1 — о)и) < < оу(и)+(! — о)7(чц) < с, т, е. ои+(1 — о)иеМ(с), что и требовалось. П Заметим, что обратное утверждение здесь неверно: из выпуклости множества М(с) при любом с, вообще говоря, не следует выпуклость функции у(х). Например, множество М(с) =(и: и ~ Е), и' < с) выпукло при любом с, а функция 7(и) = и' невыпукла на Е' (см.
упражнение 33)) Теорема 11. Пусть Х, — выпуклое множество, функции дг(х), з' = 1,..., т, выпуклы на Хо, а д,. (х) = (аг, х) — б„з = то+ 1,..., в, где а,.— заданные векторы аз Е", б, — заданные числа, з' = то+1,..., з, Тогда выпукло множество Хье(и: иЕХо, д,(и)<0, (=1,..., т; д,(и)=0, з=т+1),..., а). (12) Доказательство. В силу теоремы 10 множество Х, =(и: и Е Е Хо, д,(и) < О) выпУкло пРи всех з = 1,..., тп. ВыпУкло также множество М = (и Е Е: (а„и) — б, = О, з = тп+ 1,..., в) — см. пример 1.5. Тогда множество (12), являющееся пересечением выпуклых множеств. Х„..., Хм, М само будет выпуклым.
П 8. Рассмотренное в теореме 3 условие оптимальности сформулировано для непрерывнодифференцируемых функций. Однако аналогичное условие мо)кно получить при гораздо мень. ших ограничениях на функцию, используя лишь существование производных по направлениям. Напоминаем, что производной функции У(в) в точкеи понапразлению е, [в[=1, называется число я)в - )) ли.с — 'у.:гы. ) В) е ),эо Заметим, что для определения производной по направлению в точке и нужно, чтобы и + те принадлежало области определения 7(м) при 0~ (т < Фо хотя бы при малом то > О. О и р е д е л е н и е 3. Пусть Х вЂ” некоторое множество из В", пусть и е Х. Направление е ф 0 называетса возможным в точке и, если сУществУет число то > 0 такое, что и+ Ее Е Х пРи всех т, 0 < т < го.
Иначе говоря, достаточно малое перемещение из точки и по возможному направлению не выводит за пределы мнохгества Х. Очевидно, если и е 1п1 Х, то любое направление е ф 0 является возможным в этой точке. В граничных точках множества возмолгное направление может и не существовать, Пример 6. Пусть Х =(и =(му) ен; х >О, и ~(у < 2х ). Нетрудно видеть, что в граничной точке (О, 0) нет ни одного возможного направления.
Для выпуклых множеств Х, содержащих не менее двух точек, приведенная в примере 6 ситуация невозможна: в любой точке и такого выпуклого мнохгества Х имеется хотя бы одно возможное направление, причем направление е ~0 будет возможным а точке и тогда и только тогда, когда существуют точка и Е Х, и я' и, и число т > 0 такие, что е = т(е — и).
Таким образом, если функции 7(м) определена на множестве Х, а направление е, [е! = 1, Явлаетсв возможным в точке и е х, то фУнкциЯ д(т) = У(и+ те) опРеделена на отРезке [О, то), где то > О, и ву(и)/йе = д)(+0) — правая производная д(1) в точке т =О. [69 Гл. 4. ЭЛЕМЕНТЪ| ВЫПУКЛОГО АНАЛИЗА 5 2. ВЫПУКЛЫЕ ФУНКЦИИ Заметим, что если функция /(х) определена е некоторой г-окрестности точки и и дифференцируема в этой точке, то /(х) имеет производные по всем направлениям, причем — ад[ — ) = (/ (и), е), ]е] =! (14) (ср.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
