Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 39
Текст из файла (страница 39)
(4) Доказательство. Необходимость. Пусть г(и) выпукла на П. Перепишем неравенство (1) в виде 1(о+а(и — о)) — г(о)<а(!(и) — г(о)], 0<а<1, и, ежа. Применяя к левой части формулу конечных приращений (2.3.2), имеем а<г' (о + Оа(и — о) ), и — о> < а(Х(и) — г (о)), 0 < О < 1.
Деля обе части этого неравенства на а) 0 и устремляя а — +О, с учетом гладкости функции получим требуемое неравенство (4). Достаточность. Пусть для некоторой гладкой функции на выпуклом множестве выполняется неравенство (4) при всех и, о~и <7. Покажем, что тогда г(и) выпукла на П. Возьмем произвольные точки и, о~и П и число а (0< а <1). Положим и„= = аи + (1 — а) о. Из (4) получим Х(и) — г (и„) ~ <г'(и„), и — и„>, Х(о) — г(и„)~ <г'(и„), о — и,>.
Умножим первое из этих неравенств на а, а второе — на 1 — а и сложим. Получим аг(и)+(1 — а)г(о) — г(и„)> <Х (и„), и„>, что равносильно неравенству (1). Неравенство (4) имеет простой геометрический смысл. Как известно 110, 160, 165, 233~, гиперплоскость Г = ((и, т) ~н Е"+'. з 3! ВЫПУКЛЫЕ ФУНКЦ11И 165 и ьн Е", Г = г(о)+ (Х'(о), и — о>) является касательной плоскостью к графику функции Г = 7(и) в точке о.
Поэтому неравенство (4) означает, что график выпуклой функции лежит не ниже касательной плоскости к этому графику в любой точке о ьи С (ср. с теоремой 1.8.4). 4. Следующая теорема, называемая критерием оптимальности для выпуклых функций, дает необходимые и достаточные условия минимума гладких выпуклых функций на выпуклом множестве. Теорема 3. Пусть сь — выпуклое множество, 7(и)ыСь(ьь') и пусть П вЂ” множество точек минимума )(и) на П. Тогда в любой точке ич ен П„ььеобходимо выполняется неравенство (г" (ив), и — иа) Ъ 0 1ь'и ен ГГ, (5) а в случае ив ен шФ Ст неравенство (5) превращается в равенство г"' (и ) = О.
Если, кроме того, 1(и) выпукла на С, то условие (5) является достаточным для того, чтобы ив е= П„. Доказательство. Необходимость. Пусть ивенПч. Тогда при любых ие П и аьи(0, 1] с помощью формулы (2.21), определяющей градиент функции, имеем 0 (~у(ив + а (и — ив))— —.т (ив) = а(Х'(ив), и — и, ) + о(а) или 0((У'(и ), и — и,„) + о(а)Га, 0(а(1. Отсюда прн а — +О получим условие (5). Если ивенш1С, то для любого ее Е" найдется е, >0 такое, что и =и„+сея ГГ при всех е (~е~ < е,). Полагая в (5) и =- ив + ее, получаем е (г ' (ив), е) ~ )0 при всех е ( ~ е | < е,), что возможно только при (л'(ив), е) = О. В силу произвола е отсюда имеем л'(ив) = О.
Заметим, что если ив — граничная точка множества П, то равенство т' (ив) = 0 может выполняться, может и не выполняться. Например, если !(и)=и', П=(иыГ: 1<и< 2), то ив = 1, л" (ив) = 2 и условие (5) в точке ив, конечно, выполняется. Если ту же функцию Х(и) = и' рассматривать на отрезке П = (и ~ Е'. 0< и<2), то ив = — О, г"'(и,„) = О, хотя ич = 0 — граничная точка П. Таким образом, условие (5) является естественным обобщением условия стационарностп (2.2.5) па задачи минимизации гладких функций на выпуклых множествах ПФ Е". Д о с т а т о ч н о с т ь. Пусть функция г (и) ~ С'(П) является выпуклой на П, пусть для некоторой точки иве= П выполнено условие (5).
Тогда пз неравенства (4) при о = и„получим л (и) — Х(и. ))(л" (и ), и — ив) )О илп л (и))у(и,„) прн всех иенП, т. е. и„явь,„. 5. Сформулируем и докажем два критерия выпуклости для гладких функций, Теорема 4. Пусть П вЂ” выпуклое множество, г(и)ьнС'(Гь'). Тогда для вътуклости функции г(и) на П необходимо и доста- ~гл. с 166 элкмкнты выпгклого лнллизл точно, чтобы (Х'(и) — Х'(о), и — о>':вО Чи, ген П.
(6) Доказательство. Необходимость. Пусть 1(и) выпукла на У. Тогда для любых и, о~ У имеет место неравенство (4). Поменяв в (4) переменные и и о ролями, получим 1(о) > 1(и1+ (1'(и), о — и). Сложив это неравенство с (4),придем к условию (6). Достаточность. Пусть для некоторой функции 1(и)~ ~С'(У) выполнено условие (6). Тогда с помощью формулы конечных приращений (2.3.2) для любых и, о м с1 и ая[0, 1) имеем а1(и) + (1 — сс)Х(и) — Х(яи+ (1 — а)о) = = а [Х(и) — Х(аи+ (1 — а) о)) + + (1 — а) [Х(о) — Х(сси+ (1 — а) о)] = = а~ с',Х'(яи+ (1 — а) о+ 1(и — аи — (1 — я) о)), и — яи— о — (1 — а) о) с[1+ (1 — а) ~ (Х' (аи + (1 — а) о + Г (о — аи— в — (1 — а) о)), о — аи — (1 — а) о) сй = 1 = а (1 — а) ) (Х' (аи + (1 — а) о + с (1 — я) (и — о))— о — Х' (сси + (1 — сс) о + 1я (о — и)), и — о) с[1, или аХ (и) + (1 — я) Х (и) — Х (аи + (1 — а) о) = 1 = я(1 — а) ~(Х'(г,) — Х'(г,), г,— г.,'1 — с[1, (7) 1 о где г, = аи+(1 — а) о+ с(1 — а) (и — о), г, = аи+(1 — а) о+ + Га(о — и).
Из условия (6) имеем <1'(г,) — 1'(г-.), г, — г,> >0 при всех г (О < Е ( 1) . Это значит, что правая часть (7) и, следовательно, левая часть (7) неотрицательна прп любом выборе и, о ~ У, сс ~н [О, 1), т. е. 1(и) выпукла на У. Заметим, что для функций одной переменной неравенство (6) равносильно неубыванию производной 1'(и). Это значит, что доказанная теорема 4 является естественным обобщением теоремы 1.8.8 на случай гладких функций многих переменных. ВЫПУКЛЫЕ ФУНКЦ11И 167 Следующий критерий выпуклости обобщает теорему 1.8.9.
Теорема 5. Пусть У вЂ” выпуклое множество из Е", 1(и)ы гнС" (Ьт), Тогда для выпуклости 1(и) на У необходимо и достаточно, чтобы <1" (и)$, $> ~0 (8) при всех и ы У и всех 6 = ($', ..., $"), принадлежащих надпространству Е = Еш 71, параллельному аффинной оболочке лтожества У (в частности, если 1в1 У Ф И, то (8) выполняется при всех $ыЕ"). Доказательство. Необходимость. Пусть 1(и) выпукла на У. Пусть аЛУ=(иыЕ'. Аи=б), где А — некоторая матрица размера тХп, а ЬыЕ" (см. пример 1.4).
Тогда подпространство Е, параллельное аЛ Г, имеет вид Е = Ц~и Е": А$ = = 0). Далее, согласно теореме 1.10 г1 У Ф ю. Возьмем произвольные $ыЕ, иыг1 К Тогда А(и+е$)=Аи+еАс=Аи=Ь, т. е. и+ е$ ы аЛА при всех е. По определению 1.10 относительно внутренней точки множества найдется такое число е, > О, что и+ е$ ы Г прп всех е (!е! < е,). Поскольку для гладкой выпуклой функции справедливо неравенство (6), то из него с учетом формулы (2.3.4) имеем <1'(и+ ез) — 1'(и), 6>е = <1" (и+ Ое$) ь, $>е' > О, 0 < О < 1, яли <1" (и+Ось)6, 6>~0 для всех е (0<!е! <е,).
Отсюда, пользуясь непрерывностью 1" (и), прн е — 0 получим условие (8) для всех иыг1 К Если и~и йг1 У, то, как следует пз теоремы 1АО, существует последовательность (и,) ыг1 У, сходящаяся к и. По доказанному <1" (и,)$, $> ~0 при всех $ ы Е. Отсюда прп й- получим неравенство (8) и для точек иы Г~г1 К Д о с т а т о ч н о с т ь. Пусть 1(и) ы С'(<') и выполнено условие (8). Возьмем произвольные точки и, выП. Тогда 6=и— — о ы Е. Пользуясь формулой (2.3.4) и неравенством (8) при $ = и — о, получим <1'(и) — 1'(о), и — о> = = <1" (о+ 6(и — о))(и — о), и — о>)0 чи, о~ Ьт.
Таким образом, для функции 1(и) выполняется условие (6). Из теоремы 4 следует выпуклость 1(и) на У. Замечание 1. Если 1птУчьо, то Е=Е' и условие (8) должно выполняться прп всех $ ыЕ". Следующий пример показывает, что прп 1пг У= 8 условие (8) может н не выполняться прн каждом 6 ыЕ'.
Пример 1. Пусть 1(и)=х' — у', У=(и=(х, у)ыЕ': у =0). Ясно, что 1(и) выпукла на Г Но условие <1" (и)$, $> = 2(с')'— — 2($')' > 0 не выполняется, например, для $ =(О, 1). Здесь 1п1 Г = И, аЛ П = У = Е. Однако если требовать, чтобы условие (8) выполнялось лишь для тех $, которые принадлежат надпространству, параллельному »гл. » ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА аИ(1 (а не для всех $»ИЕ"), то теорема 5 остается справедливой для любых выпуклых множеств ГЫ8". В этом случае доказательство необходимости проводится по той же схеме, что и выше, нужно лишь сначала рассмотреть точки и»нг»с», а для точек и ш Рг» с» воспользоваться последовательностью (и ) ш шг»'Ь», сходящейся к и.
Доказательство достаточности остается без изменений, так как вектор $ = и — и при любых и, о»н Ьт принадлежит надпространству, параллельному аН с». Замечание 2. Условие (8) представляет собой условие неотрицательности квадратичной формы В»1 (и] (1- (и) $, $) = „'~ ",.
'"' Й' на Е". Имеется следующий простой алгебранческпй критерий неотрицательности квадратичной формы [»05): для того чтобы (А$ $) = ~л~~ а»Д'$')~0 при всех $=Д', ..., $"), необходимо и »д» т достаточно, чтобы все главные миноры матрицы А = [аз! были пеотрицательны. Напоминаем, что главными минерал»и матрицы А [а;,] называются всевозможные определители [-а..... а [ 1,1, " »,»А1 Л»» = Йе»~ 1" А а а »А»! " ' »Д»А где»<»,<»,«...»а~п (Й=1, ..., и). Симметричную матрицу А называют неотри»»отельно определенной, если она является матрицей неотрицательио определенной квадратичной формы, и обозначают А ~ О.
Отметим также, что неотрицательность квадратичной формы <1а (и) $, О> равносильна тому, что собственные числа Л,(и), ..., Л„(и) матрицы 1' (и) (т. е. решения уравнения»)ей !1" ~и) — Л1! =О, 1 — единичная матрица размера н Х и) неотрицательны при всех и»н (1. Учитывая замечание 2, можно сказать, что условие (8) является достаточно удобным средством проверки выпуклости дважды гладких функций небольшого числа переменных.
П р и м е р 2. Определим, при каких а, Ь, с функция 1(и) = х'+ 2аху + Ьу'+ сз' будет выпуклой на Е'. Здесь »2 2а 01 1-(и) =~2а 2Ь О О О 2а Условие неотрицательности всех главных миноров атой матрицы дает искомые условия на а, Ь, с: Ь вЂ” а' > О, с > О. вьшгкльгя Фтнкции 169 Пример 3. Пусть У(и) = — (Аи, и) — (Ь, и), и е= Е", (9) где А — симметричная неотрицательно определенная матрица размера и Хи, ЬшЕ". В частности, если А =21 — единичная матрица, Ь = О, то У(и)= <и, и> =! иР.
Приращение функции (9) нетрудно записать в виде Х(и + й) — Х (и) = (Аи — Ь, й) + — (Ай, Ь) (10) при любых и, Ь~иЕ". Из (10) имеем У'(и) = Аи — Ь, У" (и) = А. По условию А ~ О. Отсюда и из теоремы 5 следует выпуклость У(и) па Е". Согласно теореме 3 для того, чтобы функция (9) достигала своей нижней грани на Е" в точке и, необходимо и достаточно, чтобы из являлась решением линейной алгебраической системы Аи= Ь. Указанная связь между задачей минимизации функции (9) на Е" и системой Аи=Ь с матрицей А~О лежит в основе ряда численных методов линейной алгебры (4, 13, 54). Пример 4. Пусть У( ) ~А (Р ~Еп (11) где А — матрица порядка лтХ п, Ь~н Е".
Покажем, что такая функция выпукла на Е". Для етого вычислим ее производные. Пользуясь следующей просто проверяемой формулой <Ах, у> = <х, А'у>, хшЕ", ушЕ'", где Аг — матрица, полученная трансяонированием матрицы А, нетрудно представить приращение функцпн (11) в виде У(и + Ь) — Х (и) = 2 (А (Аи — Ь), Ь) + — (2А~АЬ, Ь) при всех и, Ь ~я Е". Отсюда имеем У'(и) = 2Аг(Аи — Ь), У" (и) = 2А'А. Но <У" (и)$, 9> = 2<А Ай, 5> = 2<Аз, А$> = 2!А5Р ~ >О при всех $ ~ Е".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
