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