Ф.П. Васильев - Методы оптимизации (1125241), страница 50
Текст из файла (страница 50)
с (2.6.!) при ! +0). Однако обратное неверно; из того, что функция в некоторой точке имеет производные по всем направлениям, вообще говоря, не следует ее дифференцируемость в этой точке, и более того, нельзя гарантировать даже ее непрерывность. Пример 7. Пусть /(и) = /(х, у) = хг -1- у~ — — и = (х, у) ф О, О, и = (О, 0) = О. Возьмем произвольное направление е = (сов сг,в|па), Тогда ПО+ 3- »и гз Т ' сзсозза+з1пза Отсюда имеем й 0 [ соз а/3!и а, з1п а т';0 .у =.[ е (О ыпа =0 Однако эта функция разрывна в точке и = О, В самом деле, устремим точку и =(х, у) к нулю по параболе у = хя.
Тогда /(х, хх) ш 1/2»/(0,0) =О, Таким образом, требование существования производных по направлению существенно менее жесткое, чем требование дифференцируемости. В связи с этилг представляет интерес получить условия оптимальности е терминах производных по направлению. Теорем а !2. Пусть Х вЂ” выпуклое мнозкестго, Х, — множество точек минимума функции /(х) на Х, пусть в точке и, й Х„функция /(х) имеет произгодньгг по всем возможным направлениям. Тогда необходимо выполняется условие д/( *) О (15) для всех возможных направлений е, ]е] = 1, е точке ш. Если, кроме того, функция /(х) выпукла на Х, то условие (15) достаточно для того, чтобы и, б Х,.
Доказательство. Необходимость. Пусть и„сХ, и е, [с[=1 — возможное направление в точке и,. Тогда /(и, + 1е) )~ /(и„) или (/(и, + !е) — /(и,))/1 ) 0 при всех достаточно малых 1 > О. Отсюда при г -»+О получим условие (15). Достаточность. Пусть /(х) — выпуклая функция на Х, пусть в некоторой точке и, б х выполняется условие (15). Возьмем любую точку и б Х, и фи„и положим е = (и— — и,)/]и — и,], направление е — возможное з точке 1ц, так как и, -ь ге б х при всех г, 0 < < ! < з = [и — и ], го > О. Из условия (! 5) тогда имеем д (+0) р О, где д(1) = /(и„+ ге). Ниже в теореме 13 будет показано, что д(!) выпукла на [О, Со], Из неравенства (1.8,6) тогда следУет, что д(г) — д(0) > д'(+0)г или д(г) > д(0) пРи всех ! б [О, го].
В частности, пРи 1 = го — — ]и — и,] отсюда имеем /(и) ) /(и,), что и требовалось. О В частности, если в точке и, существует градиент /'(и,), то для е = (и — и„)Ди — и,[, и б Х, и ф и„, согласно формуле (14) имеем д/(и,)/де = (уг(и,), и — и,)/]и — и,], и в этом случае условйе (15) превращается в условие (5). Таким обрезом, теорема 12 является обобщением теоремы 3 на существенно более широкий класс функций, Более того, условие (15) валяется наиболее естественным дпя класса выпуклых функций. Дело в том, что, оказывается, всякая выпуклая функция в любой внутренней точке множества имеет производные по всем направлениям.
Это вытекает из следующих двух теорем. Теорема !3. Пусть Х вЂ” выпуклое множество, функция /(х) определена на Х. Для того чтобы /(х) была выпуклой на Х, необходимо и достаточно, чтобы для любой точки и б Х и любого возможного направления е в точке и функция д(!) = /(и+ ге) одной переменной 1 бегло выпукла на отрезке ]а, Ь], где а= !п((г: и+ ге б Х), Ь = зцр(с: и+ ге 6Х) (ясно, что а<0 <Ь; если и+пей Х или и+Ье фХ, то функцию д(!) не следует рассматривать соответственно при ! = а или г = Ь). Доказательство. Н еобходи мост ь. Пусть /(х) выпукла на Х, Возьмем произвольнуго точку и н Х, квкое-либо возможное направление е в этой точке и составим функцию д(!) = /(и+ се), а < г < Ь.
ПУсть 1|, гз — пРоизаольные точки из ]а, Ь) и а С [О, 1]. Тогда д(аг!+(! — а) СЗ) = /(а(и+ !! е)+ (1 — а)(и+ Сге)) < а/(и+ г! е)+(1 — а)/(и + !Зе) = ад(г!)+ -1-(1 — а)д(!з), что и требовалось. Достаточность. Пусть дея всех обХ и всех возможных направлений е а точке и функция д(1) = /(и+ ге) выпукла нв соответствующем отрезке [а„Ь]. Возьмем любые точки и, и б Х, ифе, положим с= о — и — это возможное направление в точке и, так как и+ г(ив и) б х при 0 < з < 1, из выпуклости д(г) =/(и+ се) получим /(ах+(1 — а)и) = д(а) = = д(а ° 1+(1 — а) 0) < ад(!)+(! — а)д(0) = а/(о)+(1 — а)/(и) при всех а б[0,1], О Теорема !4.
Пуст~ Х вЂ” выпуклое множество, функция /(х) выпукла на Х. Тогда в любой точке и и и' Х функция /(х) имеет производные по всем направлениям е б Ып Х, В частности, если|п1 Х фО, то е точке ибш1 Х существуют произгодньгг функции /(х) по всем направлениям е й Е", ]е] = 1. Доказательство. Зафиксируем какоелибо направление е с ЫпХ, ]в~= 1, и точку и б и Х. Согласно определению 1.10 существует г окрестность 0(и» е) = (о б В ': [е — и] < г) точки и, такая, что пересечение 0(и, е) гт аЕХ целиком принадлежит Х.
Учитывая, что -е также пРинадлежит Ьйп Х, можем сказать, что и+ ге б Х дла всех Ъ ]г] < !о, 0 < !о < е. Это значит, что фУнкциЯ д(!) = /(и+ !е) опРеделена на отРезке [-го, го] и согласно теоРеме 13 она выпукла на этом отрезке. поскольку 1 = 0 — внутренняя точка отрезка [-со, то], то по теореме !.8,2 существует ,»»=ц;. едим= ц;. д — л — из во ! г .о ! де Если и б Х ~! г! Х, то в такой точке у выпуклой функции производные по возможным направлениям могут и нс существовать — об этом свидетельствует пример 1,8.2.
П 9. Приведенный выше пример 7 показывает, что существование производных по всем направлениям не гарантирует непрерывности функции. Но для выпуклых функций такая ситуация, оказывается, невозможна. Теорема !5. Пусгпь множество Х еьгпукло и 1п! Х фЯ. Тогда выпуклая функция /(х) во всех внутренних точках множества Х непрерывна, В частности, функция, выпуклая на всем пространстве В», непрерывна зо всех точках.
До к а ветел ь с тв о. Возьмем произвольные и б|п! Х и г > О. По определению внутренней точки существует число 6 > 0 такое, что и+Л б Х, и+ яд! ег б Х дая всех Ь =(Ь',..., Л"), ]Ь[ < 6/и; здесь е; = (О,..., О, 1, О,..., 0), Ь = 1,..., и — базис в Я". Поскольку по теореме 14 функция /(х) в точке и имеет производные по направлениям ег, то она непрерывна в этой точке по направлениям ез, 6 = 1,..., и. Поэтому можно взять число 6 столь малым, чтобы ]/(и+ од'е) — /(и)] < е при всех Ь, ]Ь[ < 6/п, 1= 1,..., п, Тогда, пользуясь неравенством (2), получаем ! » /(и+ Ь) — /(и) =/(й ~' (и+яд!в!)) — /(и) < —., д (/(и+ пйзе ) — /(и)) < з (16) г=! г=! для всех Л, ]Ь] < 6/и. В частности, дая -Ь, удовлетворяющих неравенству ] — Ь] < 6/и, из (!6) следует /(и-Ь)-/(и) < е.
Но в силу выпуклости /(х) имеем /(и) =/((и+ А)/2+(и- Ь)/2) < < (/(и+ Ь) + /(и — Ь))/2, поэтому /(и) — /(и+ Ь) < /(и — Л) — /(и) < г. Отсюда и из (16) следует ]/(и+ Ь) — /(и)[ < г при всех Ь, ]И] < 6/и. П Заметим, что если 1п! Х = кГ, то, рассматривая лишь точки из айХ, аналогично можно доказать непрерывность выпуклой на Х функции зо всех точках и б и' Х. В качестве базиса (ег], участвующего в доказательстве, в этом случае нужно взять базис надпространства 11п Х. В точках иб Х тг1 Х выпуклая функция может терпеть разрыв — об этом говорит пример 1.8!.
Теорему 15 дополняет доказываемая ниже теорема 6.6. 10. Рассмотрим выпуклые функции на выпуклом множестве Х, принадлежащие классу Сц '(Х) (см. определение 2,6.3), т. е. гладкие выпуклые функции, градиент которых удовлетворяет условию (17) [/(и) — /(е)]~(0]и е] Чи,обХ, Š— сопз1>0.
Для таких функций имеют место неравенства 0<</~(и) — /г(е) и — о><и]и — и[З !/и обХ. (!8) В самом деле, левое неравенство следует из теоремы 4, а правое — из условия (17). Оказывается, при !и! Х ф |Э зти два неравенства можно записать в виде одного равносильного неравенства [24; 234; 525), полностью характеризующего класс выпуклых функций из С!' '(Х) с данной постоянной 5 > О.
$ 2, ВЪ|ПУКЛЫЕ ФУНКЦИИ 17О 171 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Теорема 16. Пусть Х вЂ” гь!луклог многхгстео из Е, !п1 ХАСЭ. Дяя того чтобы функция /(х) из класса Сг (Х) была гьгпуклой и удовлгтгоряло условию (!7) с посто!,! яинои Ь, необходимо и достаточно, чтобы ]/ (и) — / (о)] < Ь (/ (и) — /!(о), и — о) !/и, о й Х. Иг (19) следует нграггнстго ]24] (/(и) — /'(о),о — ю) ( 46]и — ю] !Сц о, ю 6Х (20) Доказательство. Достаточность. Если выполняется неравенство (19), то нз него, во.первых, следует, что (/~(и) — /'(о), и — о) > О, Чзь о й Х, и выпуклость /(х) гаран- тируется теоремой 4, и, во-вторых, применяя к правой части (19) неравенство Коши — Буня- ковского и деля на ]/'(и) — /'(о)], получаем условие (! 7).
Из выпуклости /(х) и условия (17) имеем неравенства (18). Таким образом, из (19) следует (!8). Кроме того, из (19) имеем (/'(и) — /'( ) — ю) = (/'(и) — /'(о), и — ю) — (/'(и) — /'(о) — ) < < (/ (и) — / (о), и — ю) — — ]/ (и) — / (о)] = — ]Ь / (/ (и) — / (о))— — — Ь (и — ю)] + — Ь]и — ю] < -Ь]и — ю] ти, о, ю 6 Х. 1 СЕ з 1 1 я 2 4 4 неравенство (20) установлено.
Заметим, что при доказательстве достаточности условие Сп1 Х ~ Ф Я не использовано, Необходимость. Пусть функция /(х) выпукла и удовлетворяет условию (17). Тогда, ках было показано выше, справедливы неравенства (!8). Остается из (18) получить (19). Сначала рассмотрим случай, когда /(х) 6 С (Х). Тогда (Гй) 0 < (/Я(и)6, 6) < Ь]6]з !Уи й Х (21) при всех 6 с Е . В самом деле, из неравенств (18) с помощью формулы (2,6.4) в случае он!и! Х имеем Ой ((/ (и+ гб) — / (и), гб) = г~(/г(и + уг()6, 6) ( Ь]6]~а~ или 0< (/я(и+баб)6 с) < Ь]6]~, Ой у < 1, для всех г, ]г] < го, го > О. Отсюда при г — ььО получим (21) для точек и 6 Сп!Х.
Если и 6 ГрХ, то оценка (21) доказывается с помощью предельного перехода от внутренних точек так же, как это делалось при доказательстве теоремы 5. Далее, пользуясь формулой (2.6,5), имеем ! /'(и -1- Л) — /'(и) = АЛ, А = ]/" (и 6 СЛ)дг, Л = о — и. (22) о Разумеется, матрица А зависит от и, о, но эту зависимость мы лля краткости не будем явно указывать. Согласно (2!) 0 < (/я(и+ сЛ)6, 6) < Ь]6]~, 0 ( с < 1, откуда, интегрируя по с, получаем О<(А6,6) <5]6]з, 66Е". (23) Таким образом, симметричная матрица А неотрицательно определена. Тогда существует симметричная неотрицательно определенная матрица А С/э такая, что (А П~) = А 1! 92, 353]. Пользуясь оценкой (23) при 6 = А С/э Л, с помощью формул (22) имеем ]/(и) — /(о)]з=(АЛ,АЛ)=(ААПЯЛ АС/гЛ)<Х]АС/ЗЛ]з Х(АЛ, Л)хй(/'( ) — /( ) и — о) Неравенство (19) доказано при дополнительном предположении /(х) 6 Сз(Х), Наметим схему доказательства для случая, когда /(х) 6 С (Х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
