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